武漢科技大學(xué)2022年《數(shù)據(jù)結(jié)構(gòu)(C語言)》考研真題與答案解析

武漢科技大學(xué)2022年《數(shù)據(jù)結(jié)構(gòu)（C語言）》考研真題與答案解析一、選擇題1.計算算法的時間復(fù)雜度是屬于一種（）的方法。A）事前統(tǒng)計B）事前分析估算C）事后統(tǒng)計D）事后分析估算2.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為（A）靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)）。B）物理結(jié)構(gòu)和存儲結(jié)構(gòu)D）虛擬結(jié)構(gòu)和抽象結(jié)構(gòu)C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)3.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）。A）必須是連續(xù)的B）部分地址必須是連續(xù)的D）連續(xù)不連續(xù)都可以C）一定是不連續(xù)的4.線性表既可以用帶頭結(jié)點的鏈表表示，也可以用不帶頭結(jié)點的鏈表表示，前者最主要好處是（）。A）使空表和非空表的處理統(tǒng)一C）節(jié)省存儲空間B）可以加快對表的遍歷D）可以提高存取表元素的速度5.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）。A）1和5B）2和4C）4和2D）5和16.對二叉樹T中的某個結(jié)點x，它在先根序列、中根序列、后根序列中的序號分別為pre（x），in（x）、post（x），a和b是T中的任意兩個結(jié)點，下列選項一定錯誤的是（）。A）a是b的后代且pre（a）<pre（b）

B）a是b的祖先且post（a）>post（b）C）a是b的后代且in（a）<in（b）D）a在b的左邊且in（a）<in（b）7.若二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（叉樹。）的二A）空或只有一個結(jié)點C）任一結(jié)點無右子樹B）任一結(jié)點無左子樹D）高度等于其結(jié)點數(shù)8.下面幾個符號串編碼集合中，不是前綴編碼的是（）。A）{0,10,110,1111}B）{11,10,001,101,0001}C）{00,010,0110,1000}D）{b,c,aa,ac,aba,abb,abc}9.一個n個頂點的連通無向圖,其邊數(shù)至少為（）。A）n-1B）nC）n+1D）n*logn10.下面（A）深度優(yōu)先遍歷徑）方法可以判斷出一個有向圖中是否有環(huán)（回路）？B）求最短路徑C）拓樸排序D）求關(guān)鍵路11.下列關(guān)于無向連通圖特性的敘述中，正確的是（（1）所有頂點的度數(shù)之和為偶數(shù)。（2）邊數(shù)比頂點個數(shù)減1要大。）。（3）至少有1個頂點的度為1。A）只有（1）B）只有（2）C）（1）和（2）D）（1）和（3）12.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于（）。A）它們的邏輯結(jié)構(gòu)不一樣B）施加在其上的操作不同D）存儲實現(xiàn)不一樣C）包含的數(shù)據(jù)元素的類型不一樣13.設(shè)有100個結(jié)點,用二分法查找時,最大比較次數(shù)是（）。

A）25B）50C）10D）714.對初始數(shù)據(jù)序列｛8，3，9，11，2，1，4，7，5，10，6｝進(jìn)行希爾排序。若第一趟排序結(jié)果為｛1，3，7，5，2，6，4，9，11，10，8｝，第二趟排序結(jié)果為｛1，2，6，4，3，7，5，8，11，10，9｝，則兩趟排序采用的增量分別是（）。A）3，1B）3，2C）5，2D）5，315.下列排序算法中，（費時間反而更多。）算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花A）堆排序B）冒泡排序C）快速排序D）希爾排序二、填空題1.將兩個各有n個元素的有序表歸并成一個有序表，其最少比較次數(shù)是（次。）2.在無表頭結(jié)點的單鏈表L的表頭插入s結(jié)點的語句序列是（3.循環(huán)隊列存儲在數(shù)組A[0..m]中，尾指針為rear，則數(shù)據(jù)元素x入隊時,首先將x放到隊尾所在位置，然后隊尾后移，其中隊尾后移的操作語句為（4.由5個結(jié)點可以構(gòu)造出（5.已知一棵完全二叉樹的第6層(設(shè)根為第1層)有8個葉結(jié)點,則完全二叉樹的）。）。）種不同的樹。結(jié)點個數(shù)最多是（）。6.設(shè)森林F中有3棵樹，三棵樹的結(jié)點個數(shù)依次是n1，n2和n3，則與森林F相對應(yīng)二叉樹的根結(jié)點的右子樹上的結(jié)點個數(shù)是（7.有n個結(jié)點，e條邊的無向圖采取鄰接表存儲，求最小生成樹的Kruskal算法的時間復(fù)雜度是（8.已知一無向圖G=（V，E），其中V={a,b,c,d,e}）個。）。E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是（9.有序表包含16個數(shù)據(jù)，順序組織。若采用二分查找方法，則在等概率情況下，查找成功時的ASL值是（10.一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建）遍歷方法。）。立的初始堆（大頂堆）中第2，3，4個排序碼分別為（）。三、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。2.一般認(rèn)為，隨問題規(guī)模n的增大，算法執(zhí)行時間的增長速度較快的算法最優(yōu)。3.在一個長度為n的線性表的第i個位置（1≤i≤n+1）插入一個元素時，需要向后移動n+1-i個元素。4.用鏈接方式存儲的隊列，在進(jìn)行出隊運算時僅需修改頭指針。5.對于任何一顆二叉，樹如果其葉子結(jié)點數(shù)為n0，則度為2的結(jié)點數(shù)為n0－1。6.如果給定二叉的樹先序遍歷序列和后序遍歷序列，則該二叉是樹唯一的。7.一顆有n個頂點的生成有樹且僅有n－1條邊。8.對AOV網(wǎng)進(jìn)行拓?fù)渑判驎r，結(jié)束后如果還有頂點沒有被輸出，且這些頂點的入度均＞0，則該網(wǎng)必定有環(huán)存在。9.采用線性探測法處理沖突，在查找成功的情況下，可能要探測的這些位置上的關(guān)鍵字一定都是同義詞。10.堆排序不是穩(wěn)定的排序方法。四、綜合應(yīng)用題1.將如下圖所示矩陣的非零元素逐行存放于數(shù)組B中（下標(biāo)從0開始存放，即A存放在B[0]中），使得B[k］=A[i，j］，求：11（1）用i，j表示ｋ的變換公式。（2）用ｋ表示i，j的變換公式。aa0aa1,12,11,22,2aaaa03,33,44,34,4…………aaaa2m-1,2m-12m-1,2m-12m,2m-12m,2m2.已知AOV網(wǎng)的鄰接表如下圖所示，要求：1V12V23V34V45V56V6Λ265Λ545Λ3Λ36Λ6Λ（1）畫出該AOV網(wǎng)。（2）給出基于該AOV網(wǎng)鄰接表的從頂點V1出發(fā)的DFS序列。（3）給出基于該AOV網(wǎng)鄰接表的從頂點V1出發(fā)的BFS序列。（4）寫出對該AOV網(wǎng)按照上述鄰接表進(jìn)行拓?fù)渑判虻玫降耐負(fù)湫蛄小?.根據(jù)下列二叉樹，要求：（1）寫出其先序遍歷序列、中序遍歷序列和后序遍歷序列。（2）順序存儲該二叉樹，畫出其存儲示意圖。4.如果一顆非空k叉樹T（k≥2）中每個非葉子結(jié)點都有k個孩子。請回答下列問題并給出推導(dǎo)過程。（1）若T有m個非葉子結(jié)點，則T的葉子節(jié)點有多少個？（2）若T的高度為h，則T的結(jié)點數(shù)最多是多少個？最少是多少個？5.散列表長度是13，散列函數(shù)H(K)=k%13，解決沖突用線性探測再散列法。給定的關(guān)鍵字序列為{19,14,23,1,68,20,84,27,55,11,10,79}，要求：（1）畫出哈希表。（2）求出等概率下查找成功的平均查找長度。（3）求出等概率下查找失敗的平均查找長度。五、算法設(shè)計題1.用帶頭結(jié)點的雙向循環(huán)鏈表（結(jié)點結(jié)構(gòu)為（Left，Data，Right））表示的線性表為L=（a1,a2,…an）。試設(shè)計如下算法Fun實現(xiàn)將L改造成：L=（a1,a3,…an,…a4,a2）。voidFun(DbLinkList&L);2.若表達(dá)式以字符形式已存入數(shù)組s中，‘#’為表達(dá)式的結(jié)束符，試設(shè)計如下算法Match判斷表達(dá)式中括號（‘([{}])’）是否配對，如果配對，則返回1，否則返回0。intMatch(char*s);3.樹采用孩子兄弟鏈表作為存儲結(jié)構(gòu)（結(jié)點結(jié)構(gòu)CSTree為（firstchild，data，nextsibling）），試設(shè)計如下非遞歸算法Leaf計算樹的葉子節(jié)點數(shù)。intLeaf(CSTree*T);//函數(shù)返回值就是樹的葉子節(jié)點數(shù)4.已知無向圖采用鄰接表存儲方式，試設(shè)計如下算法DeletEdge刪除圖中(i,j)邊。voidDeletEdge(AdjListg,inti,intj);

答案解析一、選擇題01-05：BCDAB06-10：ADBAC11-15：ABDDC二、填空題1.n2.s->next=L;L=s;3.rear=(rear+1)%(m+1)4.95.1116.n2+n37.O(eloge)8.深度優(yōu)先9.54/1610.79，56，38三、判斷題01-05：××√×√06-10：×√√×√四、綜合應(yīng)用題1.（1）k=2(i-1)+(j+1)%2（2）i=k/2+1j=k/2+k%2+1-k/2/22.（1）AOV網(wǎng)

V2V3V1V5V6V4（2）DFS序列：V1，V2，V6，V5，V4，V3（3）BFS序列：V1，V2，V4，V3，V6，V5（4）拓?fù)湫蛄校篤1，V2，V4，V3，V5，V63.（1）先序：ABDGCEHFI中序：GDBAEHCFI后序：GDBHEIFCA（2）順序存儲示意圖123456789101112131415ABCD^EFG^^^^H^I4.（1）m(k-1)+1因為T中只存在度為0和k的結(jié)點。N=n0+nk=B+1=k*nk+1----n0=(k-1)nk+1(nk就是m)（2）最多：(kh-1)/(k-1)除第h層外，第1到h-1層的每個結(jié)點的度都是k，即滿k叉樹。N=k0+k1+k2+…+kh-1=(kh-1)/(k-1)最少：k(h-1)+1除第1層外，每層都有k個結(jié)點，其中1個分支節(jié)點和k-1個葉子即：N=（h-1）k+15.（1）畫出哈希表012345678910111214168275519208479231110121431139113（2）成功時的平均查找長度：（1+2+1+4+3+1+1+3+9+1+1+3）/8=30/12=5/2（3）失敗時的平均查找長度（1+2+3+4+5+6+7+8+9+10+11+12+13）/13=91/13=7五、算法設(shè)計題1.voidFun(DbLinkList&L){Tail=L->Left;p=L->Right;i=1;while(p&&p!=Tail){if(i%2==0){q=p;//刪除結(jié)點pp=p->next;p->Left=q->Left;q->Left->Right=p;q->Right=Tail->Right;//插入到Tail之后q->Left=Tail;Tail->Right->Left=q;T->Right=q;}elsep=p->Right;i++;}}2.intMatch(char*s){chars[maxsize];inttop=0,i=0;while(s[i]!=’#’){switch(s[i]){case‘(‘:case‘[‘:case‘{‘:s[top++]=s[i];i++;break;//入棧case‘)’:if(s[top-1]==’(‘){top--;i++;break;}else{printf(“不匹配”);return0;}case‘]’:if(s[top-1]==’[‘){top--;i++;break;}

else{printf(“不匹配”);return0;}case‘}’:if(s[top-1]==’{‘){top--;i++;break;}else{printf(“不匹配”);return0;}case‘#’:if(top==0){printf(“匹配成功”);return1;}else{printf(“不匹配”);return0;}default:i++;//讀入其它字符，不作處理}}}3.intLeaf(CSTree*T){if(T==NULL)return0;intfront=1,rear=1;//front,rear是隊頭隊尾元素的指針intlast=1;//last指向樹中同層結(jié)點中最后一個結(jié)點inttemp=0;//葉子結(jié)點數(shù)Q[rear]=T;//Q是以樹中結(jié)點為元素的隊列while(front<=last){p=Q[front++];//隊頭出隊列if(p->f