安徽大學(xué)2025年數(shù)據(jù)結(jié)構(gòu)期末考試試卷及答案一、單項(xiàng)選擇題（每小題2分，共20分）1.已知三個算法的時間復(fù)雜度函數(shù)分別為T?(n)=n2+2n+3，T?(n)=3nlog?n+5n，T?(n)=2?+log?n。當(dāng)n足夠大時，三者的時間復(fù)雜度由低到高的順序是（）A.T?<T?<T?B.T?<T?<T?C.T?<T?<T?D.T?<T?<T?2.對于長度為n的順序表，在第i個位置（1≤i≤n+1）插入一個元素的時間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n2)3.若元素入棧順序?yàn)?、2、3、4、5，下列不可能的出棧順序是（）A.5、4、3、2、1B.3、2、5、4、1C.2、3、1、5、4D.4、5、3、2、14.設(shè)循環(huán)隊列的存儲空間為Q[0..m-1]，初始時front=rear=0。經(jīng)過一系列入隊和出隊操作后，front=20，rear=15（m=50），則隊列中元素個數(shù)為（）A.5B.35C.45D.155.一棵完全二叉樹有100個節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)的個數(shù)是（）A.50B.51C.49D.486.對于有n個頂點(diǎn)和e條邊的無向圖，鄰接表的存儲空間復(fù)雜度為（）A.O(n)B.O(e)C.O(n+e)D.O(n×e)7.對長度為15的有序表進(jìn)行二分查找，平均查找長度約為（）（取整）A.3B.4C.5D.68.下列排序算法中，不穩(wěn)定的是（）A.冒泡排序B.歸并排序C.插入排序D.快速排序9.哈希表中解決沖突的方法中，屬于開放定址法的是（）A.鏈地址法B.再哈希法C.公共溢出區(qū)法D.線性探測法10.已知大頂堆的數(shù)組表示為[90,70,80,30,60,50,40]，刪除堆頂元素后，調(diào)整后的堆數(shù)組為（）A.[80,70,50,30,60,40]B.[80,70,60,30,40,50]C.[70,60,80,30,50,40]D.[80,60,70,30,50,40]二、填空題（每空2分，共20分）1.算法T(n)=nlog?n+2?的漸近時間復(fù)雜度為__________。2.雙向鏈表中刪除節(jié)點(diǎn)p（非頭非尾）的操作需修改指針：p->prior->next=__________；p->next->prior=__________。3.表達(dá)式“3+5×(2-4)/6”的后綴表達(dá)式為__________。4.已知二叉樹的后序遍歷序列為D、E、B、F、C、A，中序遍歷序列為D、B、E、A、F、C，則前序遍歷序列為__________。5.一個無向連通圖有8個頂點(diǎn)，其提供樹的邊數(shù)為__________。6.快速排序在最壞情況下的時間復(fù)雜度為__________。7.平衡二叉樹中節(jié)點(diǎn)的平衡因子是該節(jié)點(diǎn)__________的高度差。8.若哈希表長度為11（地址0-10），采用除留余數(shù)法（取p=11），關(guān)鍵字47的哈希地址為__________。9.堆排序中建堆的時間復(fù)雜度為__________。10.線索二叉樹中，節(jié)點(diǎn)的右線索指向其__________。三、判斷題（每小題1分，共10分。正確填“√”，錯誤填“×”）1.順序表的插入操作在表尾的時間復(fù)雜度為O(1)。（）2.隊列是先進(jìn)后出的線性結(jié)構(gòu)。（）3.二叉樹的前序遍歷序列和后序遍歷序列可以唯一確定一棵二叉樹。（）4.鄰接矩陣存儲圖時，空間復(fù)雜度與邊數(shù)無關(guān)。（）5.冒泡排序的時間復(fù)雜度與初始序列的有序性無關(guān)。（）6.二分查找要求查找表必須是順序存儲的有序表。（）7.哈希表的查找效率主要取決于哈希函數(shù)的設(shè)計，與處理沖突的方法無關(guān)。（）8.堆的結(jié)構(gòu)一定是完全二叉樹。（）9.拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖（DAG）。（）10.歸并排序的空間復(fù)雜度為O(n)。（）四、算法設(shè)計題（共30分）1.（10分）用C語言實(shí)現(xiàn)單鏈表的逆置操作。要求：函數(shù)原型為LinkListReverseList(LinkListL)，其中L為帶頭節(jié)點(diǎn)的單鏈表頭指針，返回逆置后的鏈表頭指針。2.（10分）編寫二叉樹中序遍歷的非遞歸算法。要求：函數(shù)原型為voidInOrder(BiTreeT)，其中T為二叉樹根節(jié)點(diǎn)指針，用棧模擬遞歸過程。3.（10分）實(shí)現(xiàn)快速排序的劃分函數(shù)。要求：函數(shù)原型為intPartition(intarr[],intlow,inthigh)，將arr[low..high]劃分為兩部分，返回基準(zhǔn)元素的最終位置。五、綜合應(yīng)用題（共20分）1.（10分）給定括號序列“([)]{}”，用棧判斷該序列是否合法。要求：寫出每一步棧的狀態(tài)（棧底到棧頂）及最終結(jié)論。2.（10分）已知無向圖G的鄰接矩陣如下（頂點(diǎn)編號0-4）：\[\begin{bmatrix}0&1&1&0&0\\1&0&0&1&1\\1&0&0&0&1\\0&1&0&0&0\\0&1&1&0&0\\\end{bmatrix}\]（1）畫出G的鄰接表表示；（2）寫出從頂點(diǎn)0出發(fā)的廣度優(yōu)先搜索（BFS）序列（假設(shè)訪問順序按頂點(diǎn)編號升序）；（3）計算頂點(diǎn)0到頂點(diǎn)3的最短路徑長度（邊數(shù)）。答案一、單項(xiàng)選擇題1.B2.B3.C4.B5.A6.C7.B8.D9.D10.B二、填空題1.O(2?)2.p->next；p->prior3.3524-×6/+4.ABDECF5.76.O(n2)7.左子樹與右子樹8.4（47%11=4）9.O(n)10.后繼節(jié)點(diǎn)三、判斷題1.√2.×3.×4.√5.×6.√7.×8.√9.√10.√四、算法設(shè)計題1.單鏈表逆置```ctypedefstructLNode{intdata;structLNodenext;}LNode,LinkList;LinkListReverseList(LinkListL){LNodepre=NULL,cur=L->next,next;while(cur!=NULL){next=cur->next;//保存下一個節(jié)點(diǎn)cur->next=pre;//反轉(zhuǎn)指針pre=cur;//前驅(qū)后移cur=next;//當(dāng)前節(jié)點(diǎn)后移}L->next=pre;//頭節(jié)點(diǎn)指向原尾節(jié)點(diǎn)（現(xiàn)頭節(jié)點(diǎn)）returnL;}```2.中序遍歷非遞歸算法```ctypedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;voidInOrder(BiTreeT){BiTreep=T;SqStackS;//假設(shè)已定義順序棧InitStack(S);//初始化棧while(p||!StackEmpty(S)){if(p){//向左走到最左Push(S,p);p=p->lchild;}else{//彈出并訪問Pop(S,&p);printf("%d",p->data);//訪問節(jié)點(diǎn)p=p->rchild;//轉(zhuǎn)向右子樹}}}```3.快速排序劃分函數(shù)```cintPartition(intarr[],intlow,inthigh){intpivot=arr[low];//選擇第一個元素為基準(zhǔn)while(low<high){while(low<high&&arr[high]>=pivot)high--;arr[low]=arr[high];//比基準(zhǔn)小的移到左邊while(low<high&&arr[low]<=pivot)low++;arr[high]=arr[low];//比基準(zhǔn)大的移到右邊}arr[low]=pivot;//基準(zhǔn)歸位returnlow;//返回基準(zhǔn)位置}```五、綜合應(yīng)用題1.括號匹配判斷步驟：-初始?？?。-遇到'('，入?！鷹＃?-遇到'['，入?！鷹＃?[-遇到')'，棧頂是'['，不匹配→失??？（實(shí)際應(yīng)為：當(dāng)前字符是')'，需匹配棧頂?shù)?('，但此時棧頂是'['，故不匹配，序列不合法）。最終結(jié)論：序列“([)]{}”不合法