2025年大学大三（计算机科学与技术）数据结构阶段测试试题及答案.doc

2025年大学大三（计算机科学与技术）数据结构阶段测试试题及答案

（考试时间：90分钟 满分100分）
班级______ 姓名______

第I卷（选择题 共40分）
答题要求：本大题共20小题，每小题2分，共40分。在每小题给出的四个选项中，只有一项是符合题目要求的。

1. 以下关于数据结构的说法，正确的是（ ）
A. 数据结构只研究数据的逻辑结构
B. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
C. 数据的存储结构不会影响算法的效率
D. 数据结构中数据元素之间不存在任何关系

2. 线性表的顺序存储结构中，元素的存储地址（ ）
A. 与元素值有关
B. 连续
C. 部分连续，部分不连续
D. 无规律

3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 循环链表

4. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。
A. n - i
B. n - i + 1
C. i
D. i - 1

5. 单链表中，增加一个头结点的目的是（ ）
A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储

6. 带头结点的单链表head为空的判定条件是（ ）
A. head == NULL
B. head->next == NULL
C. head->next == head
D. head != NULL

7. 循环链表的主要优点是（ ）
A. 不再需要头指针了
B. 从表中任一结点出发都能访问到整个链表
C. 在进行插入、删除运算时，能更好地保证链表不断开
D. 已知某个结点的位置后，能够容易地找到它的直接前驱

8. 栈和队列的共同特点是（ ）
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点

9. 若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）
A. 1，4，3，2
B. 2，3，4，1
C. 3，1，4，2
D. 3，4，2，1

10. 一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）
A. edcba
B. decba
C. dceab
D. abcde

11. 队列的操作原则是（ ）
A. 先进先出
B. 先进后出
C. 只能进行插入
D. 只能进行删除

12. 设循环队列中数组的下标范围是0..n - 1，其头指针front指向队首元素的前一个位置，尾指针rear指向队尾元素，则队列的长度为（ ）
A. rear - front
B. rear - front + 1
C. (rear - front + n) % n
D. (rear - front + 1) % n

13. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（ ）
A. 99
B. 100
C. 101
D. 102

14. 二叉树第i（i≥1）层上至多有（ ）个结点。
A. 2^i
B. 2^(i - 1)
C. 2^i - 1
D. 2^(i + 1)

15. 深度为k的完全二叉树至少有（ ）个结点。
A. 2^k - 1
B. 2^(k - 1)
C. 2^k
D. 2^(k + 1)

16. 对一棵二叉排序树进行（ ）遍历，可以得到该二叉排序树所有结点构成的有序序列。
A. 前序
B. 中序
C. 后序
D. 层次

17. 哈希表的平均查找长度与（ ）有关。
A. 哈希函数
B. 哈希表的大小
C. 装填因子
D. 以上都是

18. 下列排序方法中，平均时间复杂度最低的是（ ）
A. 冒泡排序
B. 选择排序
C. 插入排序
D. 快速排序

19. 下列排序算法中，（ ）是稳定的排序算法。
A. 快速排序
B. 堆排序
C. 归并排序
D. 希尔排序

20. 对n个记录的文件进行快速排序，所需要的辅助存储空间为（ ）
A. O(log2n)
B. O(n)
C. O(1)
D. O(n^2)

第II卷（非选择题 共60分）
答题要求：本大题共5小题，共60分。请根据题目要求，在相应位置作答。

21. （12分）简述顺序表和单链表的优缺点。

22. （1）（8分）已知栈S初始为空，元素a，b，c，d，e依次进栈，出栈序列为b，d，c，e，a，请画出栈的变化过程。

23. （1）（12分）请画出一棵深度为4的满二叉树，并计算其叶子结点数和总结点数。

24. （14分）给定一组关键字(46, 25, 78, 62, 12, 37, 95, 53)，请写出对其进行快速排序的每一趟排序结果。

25. （14分）设有一组关键字(26, 36, 41, 38, 44, 15, 68, 12)，请构造一棵二叉排序树，并画出该二叉排序树。

答案：1. B 2. B 3. A 4. A 5. C 6. B 7. B 8. C 9. C 10. C 11. A 12. C 13. A 14. B 15. A 16. B 17. D 18. D 19. C 20. A
21. 顺序表优点：随机访问效率高，可通过下标直接访问元素；存储密度高。缺点：插入和删除操作效率低，需要移动大量元素；空间分配不灵活。单链表优点：插入和删除操作效率高，无需移动元素；空间分配灵活。缺点：随机访问效率低，需要从头遍历；额外的指针空间开销。
22. 进栈：a进栈，b进栈，b出栈，c进栈，d进栈，d出栈，c出栈，e进栈，e出栈，a出栈。
23. 深度为4的满二叉树：
o
/ \
o o
/ \ / \
o o o o
叶子结点数：8，总结点数：15
24. 初始序列：(46, 25, 78, 62 12, 37, 95, 53)
第一趟：(37, 25, 12), 46, (53, 62, 95, 78)
第二趟：(12, 25), 37, 46, (53, 62), 95, (78)
第三趟：12, 25, 37, 46, 53, (62), (78, 95)
第四趟：12, 25, 37, 46, 53, 62, (78, 95)
第五趟：12, 25, 37, 46, 53, 62, 78, 95
25. 二叉排序树：
26
/ \
15 36
/ \
38 41
/ \
12 44
/
68