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

6. 设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）
A. p->next = p->next->next
B. p = p->next
C. p->next = p
D. p = p->next->next

7. 栈的特点是（ ）
A. 先进先出
B. 后进先出
C. 进优于出
D. 出优于进

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

9. 一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是（ ）
A. 2，3，4，1，5
B. 5，4，1，3，2
C. 2，3，1，4，5
D. 1，5，4，3，2

10. 队列的特点是（ ）
A. 先进先出
B. 后进先出
C. 进优于出
D. 出优于进

11. 循环队列用数组A[0..m - 1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）
A. (rear - front + m) % m
B. rear - front + 1
C. rear - front - 1
D. rear - front

12. 已知二叉树的前序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ ）
A. DEFBCA
B. DFEBCA
C. DBEFCA
D. ABCDEF

13. 深度为5的满二叉树有（ ）个叶子结点。
A. 16
B. 15
C. 32
D. 31

14. 一棵二叉树中序遍历的结果是ABCDEFG，前序遍历的结果是DBACFEG，则后序遍历的结果是（ ）
A. ACBEGFD
B. CABFEDG
C. CBADEGF
D. EGFACDB

15. 具有n个顶点的有向图最多有（ ）条边。
A. n(n - 1)/2
B. n(n - 1)
C. n(n + 1)/2
D. n + 1

16. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）
A. n
B. (n - 1)×(n - 1)
C. n×n
D. (n + 1)×(n + 1)

17. 以下排序算法中，平均时间复杂度为O(n^2)的是（ ）
A. 快速排序
B. 冒泡排序
C. 归并排序
D. 堆排序

18. 对关键字集合K = {60，40，49，23，25，13，95，196，85}，从空二叉排序树开始逐个插入关键字，建立的二叉排序树的高度为（ ）
A. 4
B. 5
C. 6
D. 7

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

20. 若关键字集合K = {47，7，29，11，16，92，22，8，3}，哈希函数为H(key) = key % 11，则元素92的哈希地址为（ ）
A. 5
B. 6
C. 7
D. 8

第II卷（非选择题 共60分）
答题要求：本大题共5小题，共60分。请根据题目要求，写出详细的解答过程。

21. （10分）简述线性表的顺序存储结构和链式存储结构的优缺点。

22. （12分）已知一个栈的进栈序列为1，2，3，4，5，试写出所有可能的出栈序列。

23. （12分）已知一棵二叉树的前序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，画出该二叉树，并写出其后序遍历序列。

24. （14分）有一个无向图G，其邻接矩阵如下：
0 1 0 1 0