南京林業(yè)大學(xué)考研真題-數(shù)據(jù)結(jié)構(gòu)2021

注意事項：

2021年攻讀碩士學(xué)位研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題答案一律寫在答題紙上；答案卷應(yīng)字跡清楚、語義確切；算法應(yīng)對主要數(shù)據(jù)類型、變量給出說明，所寫算法應(yīng)結(jié)構(gòu)清晰、簡明易懂，可加上必要的注釋；算法可用（類C（判斷下列各題是否正確，正確的在括號內(nèi)打“√”，錯的打“×”。每小題220）（）（）（）（）（）（）（）（）（）（）二．單項選擇題（15230。A.規(guī)則 B.集合 C.結(jié)構(gòu) D.運算對于順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的插入一個元素時大約要移動表中的 個元素。A.n/2 B.(n+1)/2 C.(n-1)/2 D.n線性表采用鏈式存儲時，其地址 。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)與否均可以設(shè)有一個空棧，棧頂指針為十六進制，下同，且設(shè)每個入棧元素需要1個單位存儲空間，現(xiàn)有輸入序列為1234，經(jīng)過HHPHP，PUSH，POP，PUSH后，棧頂指針是 。A.1002HB.1003HC.1004HD.1005H將有關(guān)二叉樹的概念推廣到三叉樹則一棵有244個結(jié)點的完全三叉樹的高度Ａ.4 B．5 C．6 D．7A[0..5,0..651000內(nèi)存單元中，則元素A[5,5]的地址是 A．1175 B．1180 C．1205 D．1210設(shè)森林Ｆ對應(yīng)的二叉樹為Ｂ，Ｂ有ｍ個結(jié)點，Ｂ的根為ｐ，ｐ的右子樹結(jié)點個數(shù)為森林Ｆ中第一棵樹的結(jié)點個數(shù)是 。A．m-n B．m-n+1 C．n+1 D．條件不足，無法確定有n個頂點的強連通圖至少條邊A.n+1 B.n C.n-1 D.n(n-1)堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。以下關(guān)鍵字序列 是一個堆A.16，72，31，23，94，53 B.94，23，31，72，16，53C.16，53，23，94，31，72 D.16，23，53，31，94，72關(guān)鍵路徑是AOV網(wǎng)中 。A.從源點到匯點的最短路徑 B.從源點到匯點的最長路C.最長的回路 D.最短的回路折半查找的時間復(fù)雜度。A.O(n2) B.o(n) C.o(nlog2n) D.o(log2n)具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。A.樹結(jié)構(gòu) B.圖結(jié)構(gòu) C.廣義表 D.文件結(jié)構(gòu)設(shè)無向圖G中頂點數(shù)為n,則圖G最多條邊A.n B.n-1 C.n(n-1)/2 D.n(n-1)設(shè)某有向圖中有n個頂點，e條邊，進行拓撲排序時總的時間復(fù)雜度為 。A.o(nlog2e) B.o(e+n) C.o(elog2n) D.o(e*n)不滿足平衡查找樹概念的。A.BST樹 B.AVL樹 C.折半查找判定樹 D.B+樹（本大題共0小題，每小題2分，共0分）分析以下程序段的時間復(fù)雜度(用大“O”記號表示執(zhí)行時間為正整數(shù)的函數(shù))x=n;y=0;While(x>=(y+1)*(y+1)) y++;為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性由兩個棧共享一片連續(xù)的內(nèi)存空時，應(yīng)將兩棧的 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當 時，才產(chǎn)生上溢。一個n*n的對稱矩陣如果以相同的元只存儲一次的原則進行壓縮存儲則其壓縮后的儲容量為 。廣義表（a,(b,c),d,e,((f,g),h)）的長度為 ，深度為 。一棵有n(n>=1)個結(jié)點的d度樹，若用多重鏈表表示，樹中每個結(jié)點都有d個鏈域，則在樹的nd個鏈域中，有 個是空鏈域，只有 個是非空鏈域。若二叉樹有n個結(jié)點當執(zhí)行中序遍歷的遞歸程序時在最壞情況下為處理遞歸調(diào)用所的棧需要 個單元。一棵有n0個葉子結(jié)點的哈夫曼樹上，其結(jié)點總數(shù)為 。對于含有n個頂點e條邊的無向連通圖算法適用于求 網(wǎng)的最小代價生成樹而Kruskal算法適用于求 網(wǎng)的最小代價生成樹。Dijkstra最短路徑算法從源點到其余各頂點的最短路徑長度按 次序產(chǎn)生，設(shè)向圖如下，則當源點取頂點1時，從頂點1到2的最短路徑長度是 。4550 10① ② ⑤20 10 15 302035153153③ ④ ⑥冒泡排序算法不會改變具有相同排序碼的記錄的相對次序，故冒泡排序算法對n個不同的元素進行冒泡排序（從小到大，在最壞情況下比較次數(shù)為 。（本大題共4小題，共0分）nmove2n-1（4）=aaP（6分）mn11n22……，nm個度為m？（4）003B樹，給出5060，B-樹的形態(tài)如何？（6）（本大題共4小題，共0分）一元稀疏多項式以循環(huán)單鏈表按降冪排列，結(jié)點有三個域，系數(shù)域 coef，指數(shù)域和指針域next?，F(xiàn)對鏈表求一階導(dǎo)數(shù)，鏈表的頭指針為ha，頭結(jié)點的exp域為-1。derivative(LinkListha){ q=ha;pa=ha->next;while( (1) {if(pa->exp==0) { (2) ; (3) ;free(pa);pa=q;}else { pa->coef= (4) ;pa->exp=pa->exp-1;q=pa;pa=pa->next;}}}S雙向循環(huán)鏈表的存儲結(jié)構(gòu)為：typedefstructDuLNodeElemType data;structDuLNode *prior;structDuLNode *next;}DuLNode,*DuLinkList;intfunction(DuLinkLists){DuLinkListp,q;intj=1;p=s->next;q=s->prior;while(p!=q&& (5) )if(p->data==q->data){ (6) ; (7) ;}elsej=0;return j;}采用三元組順序存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T整。#defineMAXSIZE100typedefstruct{inti,j; //非零元的行下標和列下標ElemTypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1]; //非零元三元組表，data[0]未用intmu,nu,tu; //矩陣的行數(shù)、列數(shù)、非零元的個數(shù)}TSMatrix;VoidFastTransposeSMartix(TSMatrixM,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;col++) for(t=1;t<=M.tu;t++) ++num[ (8) ];cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]= (9) ;for(p=1;p<=M.tu;p++){col=M.data[p].j; T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e; (10) ;}}}numcpot(11)。thr為：數(shù)據(jù)域data，左、右孩子域lchild，rchild和左、右標志域ltag，rtag，規(guī)定標志域1是線索，0（頭結(jié)點的lchild域指向二叉樹的根結(jié)點，頭結(jié)點的rchildlchildrchild）inorderthread(thr){ p=thr->lchild;while( (12) ){ while( (13) ) p= (14) ;printf(“%d ”,p->d