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

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

（考试时间：90分钟满分100分）班级______姓名______第I卷（选择题，共40分）每题给出的四个选项中，只有一项是符合题目要求的。(总共8题，每题5分，每题只有一个正确答案，请将正确答案填写在括号内)1.以下哪种算法设计策略常用于解决动态规划问题？（）A.分治法B.贪心算法C.回溯法D.最优子结构2.对于一个具有n个顶点的无向连通图，其最小生成树的边数为（）A.nB.n-1C.n+1D.2n3.下列关于数据结构的说法，正确的是（）A.栈是一种先进先出的数据结构B.队列是一种后进先出的数据结构C.线性表只能采用顺序存储结构D.树是一种非线性数据结构4.已知一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）A.257B.258C.384D.3855.以下排序算法中，平均时间复杂度为O(nlogn)的是（）A.冒泡排序B.选择排序C.快速排序D.插入排序6.若有一个递归算法如下：```intf(intn){if(n==0)return1;elsereturnnf(n-1);}```则计算f(5)时，函数调用的次数为（）A.5B.6C.7D.8w7.对于一个有向图，其拓扑排序的结果（）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>voidmerge(intarr[],intleft,intmid,intright){intn1=mid-left+1;intn2=right-mid;intL[n1],R[n2];for(inti=0;i<n1;i++)L[i]=arr[left+i];for(intj=0;j<n2;j++)R[j]=arr[mid+1+j];inti=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++;}}voidmergeSort(intarr[],intleft,intright){if(left<right){intmid=left+(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid+1,right);merge(arr,left,mid,right);}}```w13.（15分）这段代码实现的是什么排序算法？请简述该算法的基本思想，并分析其时间复杂度。答案：1.D2.B3.D4.D5.C6.B7.B8.D9.深度优先搜索（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.