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

武漢科技大學(xué)2022年《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）》考研真題與答案解析一、選擇題1.計(jì)算算法的時(shí)間復(fù)雜度是屬于一種（）的方法。A）事前統(tǒng)計(jì)B）事前分析估算C）事后統(tǒng)計(jì)D）事后分析估算2.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為（A）靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)）。B）物理結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)D）虛擬結(jié)構(gòu)和抽象結(jié)構(gòu)C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)3.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A）必須是連續(xù)的B）部分地址必須是連續(xù)的D）連續(xù)不連續(xù)都可以C）一定是不連續(xù)的4.線性表既可以用帶頭結(jié)點(diǎn)的鏈表表示，也可以用不帶頭結(jié)點(diǎn)的鏈表表示，前者最主要好處是（）。A）使空表和非空表的處理統(tǒng)一C）節(jié)省存儲(chǔ)空間B）可以加快對(duì)表的遍歷D）可以提高存取表元素的速度5.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。A）1和5B）2和4C）4和2D）5和16.對(duì)二叉樹(shù)T中的某個(gè)結(jié)點(diǎn)x，它在先根序列、中根序列、后根序列中的序號(hào)分別為pre（x），in（x）、post（x），a和b是T中的任意兩個(gè)結(jié)點(diǎn)，下列選項(xiàng)一定錯(cuò)誤的是（）。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.若二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是（叉樹(shù)。）的二A）空或只有一個(gè)結(jié)點(diǎn)C）任一結(jié)點(diǎn)無(wú)右子樹(shù)B）任一結(jié)點(diǎn)無(wú)左子樹(shù)D）高度等于其結(jié)點(diǎn)數(shù)8.下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）。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.一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖,其邊數(shù)至少為（）。A）n-1B）nC）n+1D）n*logn10.下面（A）深度優(yōu)先遍歷徑）方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路）？B）求最短路徑C）拓樸排序D）求關(guān)鍵路11.下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（（1）所有頂點(diǎn)的度數(shù)之和為偶數(shù)。（2）邊數(shù)比頂點(diǎn)個(gè)數(shù)減1要大。）。（3）至少有1個(gè)頂點(diǎn)的度為1。A）只有（1）B）只有（2）C）（1）和（2）D）（1）和（3）12.靜態(tài)查找表與動(dòng)態(tài)查找表二者的根本差別在于（）。A）它們的邏輯結(jié)構(gòu)不一樣B）施加在其上的操作不同D）存儲(chǔ)實(shí)現(xiàn)不一樣C）包含的數(shù)據(jù)元素的類型不一樣13.設(shè)有100個(gè)結(jié)點(diǎn),用二分法查找時(shí),最大比較次數(shù)是（）。

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