2025年大学（工学）工学专业期末测试题及解析.doc

2025年大学（工学）工学专业期末测试题及解析

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

第 I 卷（选择题，共40分）
每题给出的四个选项中，只有一项是符合题目要求的。(总共8题，每题5分，每题只有一个正确答案，请将正确答案填写在括号内)
1. 以下哪种算法设计策略常用于解决动态规划问题？（ ）
A. 分治法 B. 贪心算法 C. 回溯法 D. 最优子结构
2. 对于一个具有n个顶点的无向连通图，其最小生成树的边数为（ ）
A. n B. n - 1 C. n + 1 D. 2n
3. 下列关于数据结构的说法，正确的是（ ）
A. 栈是一种先进先出的数据结构
B. 队列是一种后进先出的数据结构
C. 线性表只能采用顺序存储结构
D. 树是一种非线性数据结构
4. 已知一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）
A. 257 B. 258 C. 384 D. 385
5. 以下排序算法中，平均时间复杂度为O(nlogn)的是（ ）
A. 冒泡排序 B. 选择排序 C. 快速排序 D. 插入排序
6. 若有一个递归算法如下：
```
int f(int n) {
if (n == 0) return 1;
else return n f(n - 1);
}
```
则计算f(5)时，函数调用的次数为（ ）
A. 5 B. 6 C. 7 D. 8
w7. 对于一个有向图，其拓扑排序的结果（ ）
A. 是唯一的 B. 是不唯一的 C. 一定存在 D. 可能不存在
8. 以下关于哈希表的说法，错误的是（ ）
A. 哈希表通过哈希函数将关键字映射到存储位置
B. 哈希表可能会出现哈希冲突
C. 解决哈希冲突的方法有开放定址法和链地址法等
D. 哈希表的查找效率一定比顺序查找高

第 II 卷（非选择题，共60分）
w9. （10分）简述深度优先搜索（DFS）和广度优先搜索（BFS）的区别，并说明它们各自适用于什么场景。

w10. （10分）已知一个带权有向图G=(V,E)，其中V={v1,v2,v3,v4}，E={<v1,v2,3>,<v1,v3,5>,<v2,v3,2>,<v2,v4,6>,<v3,v4,4>}，请用Dijkstra算法求从v1到其他各顶点的最短路径。

w11. （10分）什么是平衡二叉树？简述平衡二叉树的插入和删除操作的基本思想。

阅读以下材料，回答问题。
材料：有一个工程，包含A、B、C、D、E五个任务，它们之间的先后关系如下：A完成后才能开始B和C；B和C都完成后才能开始D；D完成后才能开始E。每个任务所需时间分别为：A：3天，B：2天，C：4天，D：3天，E：2天。

w12. （15分）请画出该工程的AOE网，并计算完成整个工程所需的最短时间。

阅读以下代码，回答问题。
```
include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];

for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```
w13. （15分）这段代码实现的是什么排序算法？请简述该算法的基本思想，并分析其时间复杂度。

答案：
1. D
2. B
3. D
4. D
5. C
6. B
7. B
8. D
9. 深度优先搜索（DFS）是沿着一条路径尽可能深地探索，直到无法继续或达到目标，然后回溯。广度优先搜索（BFS）是逐层地探索，先访问距离起始点近的节点。DFS适用于求解深度相关问题，如迷宫路径探索。BFS适用于求最短路径等问题，因为它能按层次找到最短距离。
10. 用Dijkstra算法求解：
初始：dist[v]= {inf, 0, inf, inf}，pre[v]= {-1, -1, -1, -1}
第一轮：更新dist[v2]=3，pre[v2]=v1
第二轮更新dist[v3]=5，pre[v3]=v1
第三轮更新dist[v4]=9，pre[v4]=v2
第四轮更新dist[v4]=7，pre[v4]=v3
所以从v1到v2最短路径为v1 - v2，长度为3；到v3最短路径为v1 - v3，长度为5；到v4最短路径为v1 - v2 - v4，长度为7。
11. 平衡二叉树是左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。插入操作：插入新节点后，从插入点到根节点的路径上的节点可能失衡，通过左旋、右旋和左右旋等调整操作使树重新平衡。删除操作：删除节点后，同样从删除点到根节点的路径上的节点可能失衡，进行类似插入操作的调整来恢复平衡。
12. AOE网：
A(3) -> B(2) -> D(3) -> E(2)
-> C(4)
关键路径为A - B - D - E，长度=3 + 2 + 3 + 2 = 10天，所以完成整个工程最短时间是10天。
13. 这段代码实现的是归并排序算法。归并排序的基本思想是将一个数组分成两个子数组，对两个子数组分别进行排序，然后将排序好的子数组合并成一个有序的数组。其时间复杂度为O(nlogn)，因为每次将数组分成两半，共需要logn次，每次合并操作时间复杂度为O(n)，所以总体时间复杂度为O(nlogn)。