数据结构试卷及参考答案_101
需积分: 0 111 浏览量
2022-08-08
21:13:37
上传
评论
收藏 26KB DOCX 举报
数据结构试卷（十）
一、选择题(24 分)
1．下列程序段的时间复杂度为（ ）。
i=0，s=0； while (s<n) {s=s+i；i++；}
(A) O(n
1/2
) (B) O(n
1/3
) (C) O(n) (D) O(n
2
)
2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式
最节省运算时间。
(A) 单向链表 (B) 单向循环链表
(C) 双向链表 (D) 双向循环链表
3．设指针 q 指向单链表中结点 A，指针 p 指向单链表中结点 A 的后继结点 B，指针 s 指向被
插入的结点 X，则在结点 A 和结点 B 插入结点 X 的操作序列为（ ）。
(A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p；
(C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q；
4．设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。
(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1
(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3
5．设有一个 10 阶的下三角矩阵 A（包括对角线），按照从上到下、从左到右的顺序存储到
连续的 55 个存储单元中，每个数组元素占 1 个字节的存储空间，则 A[5][4]地址与
A[0][0]的地址之差为（ ）。
(A) 10 (B) 19 (C) 28 (D) 55
6．设一棵 m 叉树中有 N
1
个度数为 1 的结点，N
2
个度数为 2 的结点，……，Nm 个度数为 m 的
结点，则该树中共有（ ）个叶子结点。
(A)
�
�
�
m
i
i
Ni
1
)1(
(B)
�
�
m
i
i
N
1
(C)
�
�
m
i
i
N
2
(D)
�
�
��
m
i
i
Ni
2
)1(1
7. 二叉排序树中左子树上所有结点的值均（ ）根结点的值。
(A) < (B) > (C) = (D) !=
8. 设一组权值集合 W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈
夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。
(A) 129 (B) 219 (C) 189 (D) 229
9. 设有 n 个关键字具有相同的 Hash 函数值，则用线性探测法把这 n 个关键字映射到 HASH
表中需要做（ ）次线性探测。
(A) n
2
(B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2
10.设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为 n，则这棵二叉
中共有（ ）个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l
11.设一组初始记录关键字的长度为 8，则最多经过（ ）趟插入排序可以得到有序序列。
(A) 6 (B) 7 (C) 8 (D) 9
12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母
升序的第一趟冒泡排序结束后的结果是（ ）。
(A) F，H，C，D，P，A，M，Q，R，S，Y，X
(B) P，A，C，S，Q，D，F，X，R，H，M，Y
评论0
最新资源