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

2025年大学二年级（计算机科学与技术）数据结构试题及答案

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

第I卷（选择题 共30分）
每题只有一个正确答案，请将答案填在题后的括号内。(总共10题，每题3分，每题给出的四个选项中，只有一项符合题目要求)

1. 以下关于数据结构的叙述中，正确的是（ ）
A. 数据的逻辑结构独立于其存储结构
B. 数据的存储结构独立于其逻辑结构
C. 数据的逻辑结构唯一决定其存储结构
D. 数据结构仅由其逻辑结构和存储结构决定
2. 线性表的顺序存储结构是一种（ ）的存储结构。
A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取
3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
4. 栈和队列的共同特点是（ ）
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
5. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ ）
A. edcba
B. decba
C. dceab
D. abcde
6. 深度为5的完全二叉树的结点数不可能是（ ）
A. 15
B. 16
C. 17
D. 18
7. 若一棵二叉树的前序遍历序列为a,b,c，后序遍历序列为c,b,a，则根结点的孩子结点（ ）
A. 只有左孩子
B. 只有右孩子
C. 有左、右孩子
D. 无法确定
8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ ）
A. O(n)
B. O(1)
C. O(log₂n)
D. O(n²)
9. 下列排序方法中，平均时间复杂度最小的是（ ）
A. 冒泡排序
B. 快速排序
C. 插入排序
D. 选择排序
10. 哈希表的平均查找长度与处理冲突的方法无关。（ 判断对错 ）

第II卷（非选择题 共70分）
11. （8分）简述线性表的两种存储结构及其优缺点。
12. （12分）已知一个栈的入栈序列为1,2,3,4,5，试写出所有可能的出栈序列。
13. （12分）画出一棵具有5个结点的二叉树，使其先序遍历序列为ABDEC，中序遍历序列为DBEAC。
14. （18分）阅读以下材料，回答问题。
材料：有一个无序数组A[10] = {5, 2, 9, 1, 56, 23, 8, 10, 7, 15}，请使用快速排序算法对其进行排序。
（1）简述快速排序的基本思想。
（2）写出一次划分操作后的数组状态。
（3）最终排序后的数组是什么？
15. （20分）阅读以下材料，回答问题。
材料：在一个哈希表中，哈希函数为H(key)=key%13，采用链地址法处理冲突。现有一组关键字序列{23, 45, 16, 37, 28, 56, 49}。
（1）计算每个关键字的哈希地址。
（2）画出哈希表的结构。
（3）若要查找关键字37，简述查找过程。

答案：
1. A
2. A
3. A
4. C
5. C
6. A
7. D
8. C
9. B
10. 错
11. 线性表的顺序存储结构：优点是可以随机存取，存储密度大；缺点是插入和删除操作效率低，可能需要移动大量元素。线性表的链式存储结构：优点插入和删除操作效率高，不需要移动元素；缺点是存储密度小，需要额外的指针空间，且只能顺序存取。
12. 12345，12354，12435，12453，12543，13245，13254，13425，13452，13542，14325，14352，14532，15432，21345，21354，21435，21453，21543，23