16春学期奥鹏东大《数据结构Ⅰ》在线作业3标准答案
16春学期《数据结构Ⅰ》在线作业3一、单选题：
1. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 (满分:5)
A. n
B. 2n-1
C. 2n
D. n-1
2. 为便于判别有向图中是否存在回路，可借助于 (满分:5)
A.广度优先搜索算法
B.最小生成树算法
C. 最短路径算法
D. 拓扑排序算法
3. 在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是 (满分:5)
A. LL型
B. LR型
C.RL型
D. RR型
4. 一个有向无环图的拓扑排序序列是 (满分:5)
A. 一定唯一的
B. 一定不唯一的
C. 不一定唯一的
D. 都不对
5. 设给定权值总数有n 个，其哈夫曼树的结点总数为 (满分:5)
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
6. 以下属于逻辑结构的是 (满分:5)
A. 顺序表
B. 哈希表
C. 有序表
D.单链表
7. 执行下列程序段后，串X的值为 S=〞abcdefgh〞; T=〞xyzw〞; substr(X,S,2,strlen(T)); substr(Y,S, stelen(T),2); strcat(X,Y); (满分:5)
A. 〞cdefgh〞
B. 〞cdxyzw〞
C. 〞cdefxy〞
D. 〞cdefef〞
8. 下列数据结构中，属于非线性数据结构的是 (满分:5)
A. 栈
B.队列
C.完全二叉树
D. 堆
9. 若数组s为两个栈s1和s2的共用存储空间，且仅当s全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为 (满分:5)
A.1和n+1
B. 1和n/2
C. －1和n
D. －1和n+1
10. . 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为 (满分:5)
A. 39/15
B. 49/15.
C. 51/15
D. 55/15
11. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 (满分:5)
A. n-1
B. n
C. n+1
D. n+2
12. 以下数据结构中，属于线性结构的是 (满分:5)
A. 广义表
B.二叉树
C.稀疏矩阵
D.串
13. 在一棵高度为k的满二叉树中，结点总数为 (满分:5)
A.2k-1
B. 2k
C. 2k-1
D. log2kû+1
14. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 (满分:5)
A.栈
B. 队列
C.树
D. 图
15. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 (满分:5)
A. 不一定相同
B. 都相同
C. 都不相同
D.互为逆序
16. 倒排文件的主要优点是 (满分:5)
A.便于进行插入和删除运算
B. 便于进行文件的恢复
C.便于进行多关键字查询
D.节省存储空间
17. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 (满分:5)
A. 0
B. 1
C. 48
D. 49
18. 含n个关键字的二叉排序树的平均查找长度主要取决于 (满分:5)
A.关键字的个数
B.树的形态
C.关键字的取值范围
D. 关键字的数据类型
19. 算法的时间复杂度主要取决于 (满分:5)
A. 问题的规模
B. 待处理数据的初态
C. 难度
D. A和B
20. 假设以数组A存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾 元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 (满分:5)
A. (rear-front-1)％n
B. (rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
页:
[1]