2025年大學(xué)（工學(xué)）工學(xué)專業(yè)期末測(cè)試題及解析

（考試時(shí)間：90分鐘滿分100分）班級(jí)______姓名______第I卷（選擇題，共40分）每題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的。(總共8題，每題5分，每題只有一個(gè)正確答案，請(qǐng)將正確答案填寫在括號(hào)內(nèi))1.以下哪種算法設(shè)計(jì)策略常用于解決動(dòng)態(tài)規(guī)劃問題？（）A.分治法B.貪心算法C.回溯法D.最優(yōu)子結(jié)構(gòu)2.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，其最小生成樹的邊數(shù)為（）A.nB.n-1C.n+1D.2n3.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法，正確的是（）A.棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)B.隊(duì)列是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)C.線性表只能采用順序存儲(chǔ)結(jié)構(gòu)D.樹是一種非線性數(shù)據(jù)結(jié)構(gòu)4.已知一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是（）A.257B.258C.384D.3855.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)的是（）A.冒泡排序B.選擇排序C.快速排序D.插入排序6.若有一個(gè)遞歸算法如下：```intf(intn){if(n==0)return1;elsereturnnf(n-1);}```則計(jì)算f(5)時(shí)，函數(shù)調(diào)用的次數(shù)為（）A.5B.6C.7D.8w7.對(duì)于一個(gè)有向圖，其拓?fù)渑判虻慕Y(jié)果（）A.是唯一的B.是不唯一的C.一定存在D.可能不存在8.以下關(guān)于哈希表的說法，錯(cuò)誤的是（）A.哈希表通過哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置B.哈希表可能會(huì)出現(xiàn)哈希沖突C.解決哈希沖突的方法有開放定址法和鏈地址法等D.哈希表的查找效率一定比順序查找高第II卷（非選擇題，共60分）w9.（10分）簡(jiǎn)述深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的區(qū)別，并說明它們各自適用于什么場(chǎng)景。w10.（10分）已知一個(gè)帶權(quán)有向圖G=(V,E)，其中V={v1,v2,v3,v4}，E={<v1,v2,3>,<v1,v3,5>,<v2,v3,2>,<v2,v4,6>,<v3,v4,4>}，請(qǐng)用Dijkstra算法求從v1到其他各頂點(diǎn)的最短路徑。w11.（10分）什么是平衡二叉樹？簡(jiǎn)述平衡二叉樹的插入和刪除操作的基本思想。閱讀以下材料，回答問題。材料：有一個(gè)工程，包含A、B、C、D、E五個(gè)任務(wù)，它們之間的先后關(guān)系如下：A完成后才能開始B和C；B和C都完成后才能開始D；D完成后才能開始E。每個(gè)任務(wù)所需時(shí)間分別為：A：3天，B：2天，C：4天，D：3天，E：2天。w12.（15分）請(qǐng)畫出該工程的AOE網(wǎng)，并計(jì)算完成整個(gè)工程所需的最短時(shí)間。閱讀以下代碼，回答問題。```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分）這段代碼實(shí)現(xiàn)的是什么排序算法？請(qǐng)簡(jiǎn)述該算法的基本思想，并分析其時(shí)間復(fù)雜度。答案：1.D2.B3.D4.D5.C6.B7.B8.D9.深度優(yōu)先搜索（DFS）是沿著一條路徑盡可能深地探索，直到無法繼續(xù)或達(dá)到目標(biāo)，然后回溯。廣度優(yōu)先搜索（BFS）是逐層地探索，先訪問距離起始點(diǎn)近的節(jié)點(diǎn)。DFS適用于求解深度相關(guān)問題，如迷宮路徑探索。BFS適用于求最短路徑等問題，因?yàn)樗馨磳哟握业阶疃叹嚯x。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，長(zhǎng)度為3；到v3最短路徑為v1-v3，長(zhǎng)度為5；到v4最短路徑為v1-v2-v4，長(zhǎng)度為7。11.平衡二叉樹是左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。插入操作：插入新節(jié)點(diǎn)后，從插入點(diǎn)到根節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)可能失衡，通過左旋、右旋和左右旋等調(diào)整操作使樹重新平衡。刪除操作：刪除節(jié)點(diǎn)后，同樣從刪除點(diǎn)到根節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)可能失衡，進(jìn)行類似插入操作的調(diào)整來恢復(fù)平衡。12.AOE網(wǎng)：A(3)->B(2)->D(3)->E(2)->C(4)關(guān)鍵路徑為A-B-D-E，長(zhǎng)度=3+2+3+2=10天，所以完成整個(gè)工程最短時(shí)間是10天。13.