[北京师范大学]19秋《数据结构》离线作业（答案）

123456aa · 发表于 2020-5-7 12:56:40

在线作业试卷列表
单选
1.顺序存储结构中数据元素之间的逻辑关系是由（）表示的。分值：5
A. 线性结构
B. 非线性结构

C. 存储位置
D. 指针

2.算法指的是（）。分值：5
A. 对特定问题求解步骤的一种描述，是指令的有限序列。
B. 计算机程序

C. 解决问题的计算方法
D. 数据处理

3.散列技术中的冲突指的是（）。分值：5
A. 两个元素具有相同的序号
B. 两个元素的键值不同，而其他属性相同

C. 数据元素过多
D. 不同键值的元素对应于相同的存储地址

4.算法在发生非法操作时可以作出处理的特性称为（）。分值：5
A. 健壮性
B. 确定性

C. 可行性
D. 正确性

5.若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。分值：5
A. 顺序表
B. 单链表

C. 双链表
D. 单循环链表

6.头结点的单链表head为空的判定条件是（）。分值：5
A. head==NULL
B. head->next==NULL

C. head->next==head
D. head!=NULL

7.单循环链表的主要优点是（）。分值：5
A. 不再需要头指针了
B. 从表中任一结点出发都能扫描到整个链表；

C. 已知某个结点的位置后，能够容易找到它的直接前趋；
D. 在进行插入、删除操作时，能更好地保证链表不断开。

8.使用双向链表存储线性表，其优点是可以（）。分值：5
A. 方便双向查找
B. 更方便数据的插入和删除

C. 节约存储空间
D. 很快回收存储空间

9.设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。分值：5
A. S1的栈底位置为0，S2的栈底位置为n-1
B. S1的栈底位置为0，S2的栈底位置为n/2

C. S1的栈底位置为0，S2的栈底位置为n
D. S1的栈底位置为0，S2的栈底位置为1

10.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。分值：5
A. 6
B. 4

C. 3
D. 2

11.表达式a*(b+c)-d的后缀表达式是（）。分值：5
A. abcd*+-
B. abc+*d-

C. abc*+d-
D. -+*abcd

12.深度为k的完全二叉树至少有（）个结点。分值：5
A. 2k-2+1
B. 2k

C. 2的(K-1)次方
D. 2k–1-1

13.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。分值：5
A. n=h+m
B. h+m=2n

C. m=h-1
D. n=2h-1

14.设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，根结点的左子树上有（）个结点。分值：5
A. n1-1
B. n1

C. n1+n2+n3
D. n2+n3+n4

15.有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是（）。分值：5
A. s=b
B. s>b

C. s
D. 不一定

简答
1.带头结点的链表和不带头结点的链表有什么不同？分值：10

论述
1.如果矩阵A中存在这样的一个元素A[j]满足条件：A[j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m×n的矩阵A的所有马鞍点。提示：依题意，先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min中，又在max[j]中，则该元素A[j]便是马鞍点，找出所有这样的元素,即找到了所有马鞍点分值：15