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

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

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

第I卷（选择题 共40分）
答题要求：本大题共20小题，每小题2分。在每小题给出的四个选项中，只有一项是符合题目要求的，请将正确答案的序号填在括号内。

1. 以下关于数据结构的说法，正确的是（ ）
A. 数据结构只研究数据的逻辑结构
B. 数据结构只研究数据的存储结构
C. 数据结构研究数据的逻辑结构、存储结构及其操作
D. 数据结构与程序设计无关

2. 线性表的顺序存储结构中，元素之间的逻辑关系是通过（ ）表示的。
A. 指针
B. 线性表的存储位置
C. 数组下标
D. 元素的值

3. 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表

4. 一个栈的输入序列为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

5. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）
A. rear=rear+1
B. rear=(rear+1)%(m+1)
C. rear=(rear+1)%m
D. rear=(rear+1)%(m-1)

6. 已知二叉树的前序序列为ABDEGCFH，中序序列为DBGEACHF，则后序序列为（ ）
A. DGEBHFCA
B. ABCDEFGH
C. ABCDEFCGHD
D. DCABHFGE

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

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

9. 下列排序算法中，平均时间复杂度为O(nlogn)且空间复杂度为O(1)的是（ ）
A. 快速排序
B. 归并排序
C. 堆排序
D. 冒泡排序

10. 对一组数据{25, 84, 21, 47, 15, 27, 68, 35, 20}进行排序，当采用快速排序且以第一个元素为基准时，第一趟划分的结果是（ ）
A. 20, 15, 21, 25, 47, 27, 68, 35, 84
B. 15, 20, 21, 25, 35, 27, 47, 68, 84
C. 15, 20, 21, 25, 27, 35, 47, 68, 84
D. 15, 20, 21,
25, 27, 47, 68, 35, 84

11. 若要在一个单链表中删除p所指节点的后继节点，则应执行（ ）
A. p->next = p->next->next;
B. p = p->next; p->next = p->next->next;
C. free(p->next);
D. p->next = p;

12. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个存储单元，则a85的存储地址为（ ）
A. 33
B. 32
C. 34
D. 35

13. 一棵哈夫曼树共有215个节点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A. 107
B. 108
C. 214
D. 215

14. 已知一个有序表为{10, 20, 30, 40, 50, 60, 70}，采用折半查找法查找元素50时，比较次数为（ ）
A. 1
B. 2
C. 3
D. 4

15. 以下关于图的说法，错误的是（ ）
A. 无向图的邻接矩阵一定是对称矩阵
B. 有向图的邻接矩阵不一定是对称矩阵
C. 图的遍历可以采用深度优先搜索和广度优先搜索
D. 图的最小生成树是唯一的

16. 一个有n个顶点的强连通图至少有（ ）条边。
A. n
B. n-1
C. n+1
D. n(n-
1)

17. 对于一个具有n个顶点的有向图，若采用邻接表表示，则顶点i的出度为（ ）
A. 第i个链表的节点数
B. 第i个链表的头节点的度数
C. 第i个链表的尾节点数
D. 邻接表的节点总数

18. 下列数据结构中，属于非线性结构的是（ ）
A. 栈
B. 队列
C. 二叉树
D. 线性表

19. 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）
A. n-i
B. n-i+1
C. i
D. 不确定

20. 已知一棵完全二叉树的第6层（设根为第1层）有8个叶子节点，则该完全二叉树的节点个数最多是（ ）
A. 39
B. 52
C. 111
D. 119

第II卷（非选择题 共60分）
答题要求：请将答案写在答题纸上，写在试卷上无效。

填空题（每题2分，共10分）
1. 数据结构包括数据的逻辑结构、存储结构和____________________。
2. 线性表的链式存储结构中，每个节点包含数据域和____________________。
3. 一个队列的入队序列是1，2，3，4，则队列的输出序列是____________________。
4. 二叉排序树的左子树上所有节点的值都____________________根节点的值。
5. 对于一个具有n个顶点的连通图，其生成树有____________________条边。

简答题（每题各5分，共20分）
1. 简述线性表的顺序存储结构和链式存储结构的优缺点。
2. 简述栈和队列的区别。
3. 简述二叉排序树的定义及特点。
4. 简述图的深度优先搜索和广度优先搜索的基本思想。

算法设计题（每题15分，共30分）
1. 设计一个算法，将一个带头节点的单链表L逆置。
2. 已知一个整数数组A，设计一个算法，找出数组中出现次数最多的元素。

综合应用题（10分）
1. 在一个果园里，小明将水果堆成了如下图所示的形状。最上层有1个水果，第二层有3个水果，第三层有6个水果，第四层有10个水果，……。如果小明堆了n层水果，试用数据结构的知识，设计一个算法来计算水果的总数。

答案
1. C
2. B
3. D
4.B
5.C
6.A
7.A
8.C
9.C
10.B
11.A
12.A
13.B
14.B
15.D
16.A
17.A
18.C
19.B
20.C

填空题答案
1.运算
2.指针域
3.1，2，3，4
4.小于
5.n-
1

简答题答案
1. 顺序存储结构优点：存储密度大，随机访问效率高；缺点：插入和删除操作效率低，可能需要移动大量元素。链式存储结构优点：插入和删除操作效率高，不需要移动元素；缺点：存储密度小，额外的指针空间开销，随机访问效率低。
2. 栈是后进先出，操作在栈顶进行；队列是先进先出，操作在队头和队尾进行。
3. 二叉排序树定义：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值，左右子树也分别为二叉排序树。特点：中序遍历得到的序列是有序的。
4. 深度优先搜索：从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续或达到目标，然后回溯到前一步，继续探索其他路径。广度优先搜索：从起始顶点开始，逐层地访问顶点，先访问距离起始顶点近的顶点。

算法设计题答案
1. 算法思路：遍历单链表，将每个节点的next指针指向前一个节点。具体代码如下：
```c
void ReverseList(LinkList L) {
LinkList p, q;
p = L->next;
L->next = NULL;
while (p!= NULL) {
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
```
2. 算法思路：遍历数组，用一个哈希表记录每个元素出现的次数，最后找出出现次数最多的元素。具体代码如下：
```c
int MostFrequentElement(int A[], int n) {
int maxCount = 0, maxElement = A[0];
unordered_map<int, int> countMap;
for (int i = 0; i < n; i++) {
countMap[A[i]]++;
if (countMap[A[i]] > maxCount) {
maxCount = countMap[A[i]];
maxElement = A[i];
}
}
return maxElement;
}
```

综合应用题答案
设第n层水果数为an，通过观察可得an = an-1 + n，a1 = 1。可以用递归或循环的方式计算水果总数。
递归算法：
```c
int FruitCount(int n) {
if (n == 1) return 1;
return FruitCount(n - 1) + n;
}
```
循环算法：
```c
int FruitCount(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
```
最终水果总数为sum(n(n + 1)/2)，其中n为层数。