2025年數(shù)據(jù)結構(c語言版)試題及答案一、單項選擇題（每小題2分，共20分）1.已知某算法的時間復雜度遞推式為T(n)=2T(n/2)+n2，T(1)=1，則該算法的時間復雜度為（）。A.O(n)B.O(nlogn)C.O(n2)D.O(n3)2.若一個長度為n的順序表中，在第i個位置（1≤i≤n+1）插入元素的時間復雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n2)3.設棧S的初始狀態(tài)為空，元素a、b、c、d、e依次入棧，然后依次出棧三次，此時棧頂元素是（）。A.aB.bC.cD.d4.循環(huán)隊列的隊空條件為（）（maxsize為隊列的最大容量，front為隊頭指針，rear為隊尾指針）。A.(rear+1)%maxsize==frontB.rear==frontC.(rear-1)%maxsize==frontD.rear==(front+1)%maxsize5.已知一棵完全二叉樹有768個節(jié)點，則該樹的葉子節(jié)點數(shù)為（）。A.383B.384C.385D.3866.對圖G進行深度優(yōu)先搜索（DFS）時，訪問順序的特性是（）。A.先訪問距離起始點近的節(jié)點B.先訪問距離起始點遠的節(jié)點C.盡可能深地訪問節(jié)點D.按節(jié)點編號順序訪問7.若哈希表的裝填因子α=0.8，表長m=100，則沖突處理前的平均查找長度主要取決于（）。A.哈希函數(shù)B.裝填因子C.處理沖突的方法D.表長8.對序列{55,34,87,21,9,63,42}進行直接插入排序，第三趟排序后的序列是（）。A.{9,21,34,55,87,63,42}B.{21,34,55,87,9,63,42}C.{34,55,87,21,9,63,42}D.{9,21,55,34,87,63,42}9.下列排序算法中，空間復雜度為O(1)的是（）。A.歸并排序B.快速排序C.堆排序D.基數(shù)排序10.若有向圖的鄰接矩陣中主對角線元素均為0，其余元素為1，則該圖一定是（）。A.強連通圖B.完全圖C.有環(huán)圖D.無環(huán)圖二、填空題（每空2分，共20分）1.數(shù)據(jù)的邏輯結構分為集合、線性結構、樹形結構和__________四類。2.雙向鏈表中每個節(jié)點包含兩個指針域，分別指向其前驅(qū)節(jié)點和__________。3.一個棧的輸入序列為1,2,3,4,5，則不可能的輸出序列是__________（任寫一個）。4.若某二叉樹的前序遍歷序列為ABDECFG，中序遍歷序列為DBEAFGC，則后序遍歷序列為__________。5.對于n個節(jié)點的無向連通圖，其提供樹至少包含__________條邊。6.二分查找要求查找表的存儲結構為__________，且元素按關鍵字有序排列。7.在平衡二叉樹（AVL樹）中，每個節(jié)點的左子樹和右子樹的高度差的絕對值不超過__________。8.快速排序的平均時間復雜度為__________。9.若采用鏈地址法處理哈希沖突，則哈希表的每個槽位存儲的是一個__________。10.拓撲排序適用于__________圖（填“有向無環(huán)”或“無向連通”）。三、判斷題（每小題1分，共10分。正確填“√”，錯誤填“×”）1.順序存儲結構的存儲空間可以是連續(xù)的，也可以是不連續(xù)的。（）2.隊列的“假溢出”是指隊列已滿但仍有元素要入隊的情況。（）3.二叉樹的度可以大于2。（）4.無向圖的鄰接矩陣一定是對稱矩陣。（）5.哈希表的查找效率主要取決于哈希函數(shù)的設計，與處理沖突的方法無關。（）6.直接選擇排序是穩(wěn)定的排序算法。（）7.完全二叉樹的葉子節(jié)點只能在最后兩層出現(xiàn)。（）8.廣度優(yōu)先搜索（BFS）遍歷圖時使用的輔助數(shù)據(jù)結構是棧。（）9.對于n個節(jié)點的二叉樹，其高度至少為?log?(n+1)?。（）10.堆排序中，初始堆的構建過程需要從最后一個非葉子節(jié)點開始向前調(diào)整。（）四、應用題（共40分）1.（8分）已知一個帶頭節(jié)點的單鏈表L，其節(jié)點結構為（data,next），存儲的元素為整數(shù)。請畫出以下操作后的鏈表狀態(tài)：（1）刪除L中所有值為偶數(shù)的節(jié)點；（2）將剩余節(jié)點按值從小到大重新排列（要求用直接插入排序思想）。（假設原鏈表為：L→3→6→2→9→4→1→5）2.（8分）設字符集{a,b,c,d,e}的頻度分別為2,5,9,12,16。（1）構造對應的哈夫曼樹（要求左子樹權值≤右子樹權值）；（2）計算該哈夫曼樹的帶權路徑長度（WPL）。3.（8分）對圖G（頂點集V={A,B,C,D,E}，邊集E={(A,B,2),(A,C,5),(B,C,1),(B,D,4),(C,D,3),(D,E,6)}，括號內(nèi)為邊權），使用Dijkstra算法求從A到E的最短路徑，并寫出每一步的距離數(shù)組（初始距離數(shù)組為[A:0,B:∞,C:∞,D:∞,E:∞]）。4.（8分）已知序列{45,38,66,90,88,10,25,45}，要求：（1）以第一個元素45為樞軸，寫出快速排序第一趟劃分后的序列；（2）判斷該序列是否為堆（小根堆或大根堆），若不是則調(diào)整為大根堆。5.（8分）設哈希表表長m=11，哈希函數(shù)H(key)=key%11，采用線性探測法處理沖突。將關鍵字序列{25,37,18,42,6,33,50}依次插入哈希表，畫出最終的哈希表狀態(tài)，并計算查找成功時的平均查找長度（ASL）。五、算法設計題（共30分）1.（10分）設計一個C語言函數(shù)，實現(xiàn)雙向鏈表的逆置操作。雙向鏈表節(jié)點定義如下：typedefstructDNode{intdata;structDNodeprior,next;}DNode,DLinkList;2.（10分）設計一個非遞歸算法，計算二叉樹中所有葉子節(jié)點的個數(shù)。二叉樹節(jié)點定義如下：typedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;3.（10分）已知兩個遞增有序的數(shù)組A和B，長度分別為m和n。設計一個C語言函數(shù)，將它們合并為一個遞增有序的數(shù)組C，要求空間復雜度為O(1)（提示：利用數(shù)組A的剩余空間）。答案一、單項選擇題1.C2.B3.B4.B5.B6.C7.A8.A9.C10.C二、填空題1.圖狀結構（或網(wǎng)狀結構）2.后繼節(jié)點3.5,3,4,2,1（或其他不可能序列）4.DEBFGCA5.n-16.順序存儲7.18.O(nlogn)9.鏈表（或鏈）10.有向無環(huán)三、判斷題1.×2.×3.×4.√5.×6.×7.√8.×9.√10.√四、應用題1.（1）刪除偶數(shù)節(jié)點后鏈表：L→3→9→1→5；（2）直接插入排序后鏈表：L→1→3→5→9。2.（1）哈夫曼樹構造過程：-合并2和5→7（左2，右5）；-合并7和9→16（左7，右9）；-合并12和16（原頻度16）→28（左12，右16）；-合并16（合并后的7+9）和28→44（左16，右28）；最終樹結構：根44，左16（左7，右9；7左2，右5），右28（左12，右16）。（2）WPL=2×3+5×3+9×2+12×2+16×2=6+15+18+24+32=95。3.Dijkstra算法步驟：-初始：距離數(shù)組[A:0,B:2,C:5,D:∞,E:∞]，選中A；-第一步：更新B（2）、C（5），選中B（最小2），更新D=2+4=6；-第二步：距離數(shù)組[A:0,B:2,C:min(5,2+1=3),D:6,E:∞]，選中C（3），更新D=min(6,3+3=6)，E=∞；-第三步：選中D（6），更新E=6+6=12；-最終最短路徑：A→B→C→D→E，總權值12。4.（1）第一趟劃分后序列：{25,38,10,45,88,90,66,45}（樞軸45的位置為第4位）；（2）原序列不是堆。調(diào)整為大根堆：{90,88,66,45,45,10,25,38}（調(diào)整過程：從最后一個非葉子節(jié)點（索引3，值90）開始，無需調(diào)整；索引2（66）與子節(jié)點90、88比較，無需調(diào)整；索引1（38）與子節(jié)點88、10比較，交換38和88，得到{45,88,66,90,45,10,25,38}；索引0（45）與子節(jié)點88、66比較，交換45和88，得到{88,45,66,90,45,10,25,38}；繼續(xù)比較88的子節(jié)點90，交換88和90，最終大根堆為{90,88,66,45,45,10,25,38}）。5.哈希表插入過程：-25%11=3→位置3；-37%11=4→位置4；-18%11=7→位置7；-42%11=9→位置9；-6%11=6→位置6；-33%11=0→位置0；-50%11=6（沖突），探測位置7（沖突），位置8→位置8；最終哈希表：索引0:33，1:空，2:空，3:25，4:37，5:空，6:6，7:18，8:50，9:42，10:空；ASL=(1+1+1+1+1+1+3)/7=8/7≈1.14。五、算法設計題1.雙向鏈表逆置函數(shù)：```cvoidReverseDLinkList(DLinkListL){DNodep=(L)->next;DNodetemp;(L)->next=NULL;//頭節(jié)點暫時斷開while(p!=NULL){temp=p->next;//保存下一個節(jié)點p->next=(L)->next;//新節(jié)點插入到頭節(jié)點之后if((L)->next!=NULL){(L)->next->prior=p;//原頭節(jié)點后繼的前驅(qū)指向當前節(jié)點}p->prior=L;//當前節(jié)點的前驅(qū)指向頭節(jié)點(L)->next=p;//頭節(jié)點的后繼更新為當前節(jié)點p=temp;//處理下一個節(jié)點}}```2.非遞歸計算葉子節(jié)點數(shù)的算法（使用棧）：```cintCountLeaves(BiTreeT){if(T==NULL)return0;intcount=0;BiTreestack[100];//假設樹高不超過100inttop=-1;stack[++top]=T;while(top!=-1){BiTreep=stack[top--];if(p->lchild==NULL&&p->rchild==NULL){count++;}if(p->rchild!=NULL)stack[++top]=p->rchild;//先壓右子樹，后處理左子樹if(p->lchild!=NULL)stack[++top]=p->lchild;}returncount;}```3.合并兩個遞增數(shù)組的函數(shù)（利用A的剩余空間）：```cvoidMergeArrays(intA[],intm,intB[],intn){