數(shù)據(jù)結(jié)構(gòu)作業(yè)題及參考答案

1、頁眉內(nèi)容東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題(一)、選擇題(每題2分，共20分)1 .在一個(gè)長度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為()。2AQn)B、O(n/2)C、OQO(n)2 .帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是()。A、first=NULL;B、first->link=NULL;C、first->link=first;D、first!=NULL;3 .在一棵樹中，()沒有前驅(qū)結(jié)點(diǎn)。A、分支結(jié)點(diǎn)B、葉結(jié)點(diǎn)C、樹根結(jié)點(diǎn)D、空結(jié)點(diǎn)4 .在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的()。A、入度B、出度C、入度與出度之和D、入度與出度之差5 .對于長度為9的有序

2、順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為()的值除以9。A、20B、18C、25D、226 .下列程序段的時(shí)間復(fù)雜度為()。s=0;for(i=1;i<n;i+)for(j=1；j<n；j+)s+=i*j;A、O(1)B、O(n)C、O(2n)D、O(n2)7 .棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是()。A、先進(jìn)先出B、后進(jìn)先出C、進(jìn)優(yōu)于出D、出優(yōu)于進(jìn)8 .假設(shè)以數(shù)組An存放循環(huán)隊(duì)列的元素，其頭、尾指針分別為front和rear。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為()。A、(rear-

3、front-1)%nB、(rear-front)%nC、(front-rear+1)%nD、(rear-front+n)%n9 .高度為5的完全二叉樹中含有的結(jié)點(diǎn)數(shù)至少為(A、16B、17C、31D、3210 .如圖所示有向圖的一個(gè)拓?fù)湫蛄惺?)A、 ABCDEFB、 FCBEADC、 FEDCBAD、 DAEBCF二、填空題(每空1分，共20分)1 .n(n>0)個(gè)頂點(diǎn)的無向圖最多有條邊，最少有條邊。2 .在一棵AVL樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對值不超過。3 .已知8個(gè)數(shù)據(jù)元素為(34,76,45,18,26,54,92,65),按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排

4、序樹，則該樹的深度為。4 .在二叉樹的第i層上至多有結(jié)點(diǎn)。5 .對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號為i(1<i<n),則它的左孩子結(jié)點(diǎn)的編號為，右孩1子結(jié)點(diǎn)的編號為，雙親結(jié)點(diǎn)的編號為。6 .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。7 .假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J),則樹中所含的結(jié)點(diǎn)數(shù)為個(gè)，樹的深度為，樹的度為。8 .在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要條邊。9 .在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著、和的聯(lián)系。10 .一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。三、運(yùn)算題(每題5分，共10分)1.設(shè)有一

5、個(gè)1010的對稱矩陣A,將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A00存放于B0中,那么A85存放于B中什么位置。2.已知一個(gè)有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲(chǔ)于一維數(shù)組a12中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94時(shí)的比較次數(shù)。兀素值3456586394比較次數(shù)頁眉內(nèi)容四、應(yīng)用題（每題10分，共50分）1設(shè)待排序的記錄共7個(gè)，排序碼分別為8，3，2，5，9，1，6。（1）用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程（動(dòng)態(tài)過程）要求按遞減順序排序。（2）用直接選擇排序。試以排序碼序列的變化描

6、述形式說明排序全過程（動(dòng)態(tài)過程）要求按遞減順序排序。2判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）1）100，85，98，77，80，60，82，40，20，10，662）100，98，85，82，80，77，66，60，40，20，103）100，85，40，77，80，60，66，98，82，10，204）10，20，40，60，66，77，80，82，85，98，1003試找出分別滿足下列條件的所有二叉樹。1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列與層次遍歷序列相同114設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)

7、點(diǎn)的度數(shù)皆為2，若T中有6個(gè)葉結(jié)點(diǎn)，試問：(1) T樹的最大深度Kmax=?最小可能深度Kmin=?(2) 2)T樹中共有多少非葉結(jié)點(diǎn)？(3) 若葉結(jié)點(diǎn)的權(quán)值分別為1,2,3,4,5,6。請構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長度wpl。5.一棵有n(n>0)個(gè)結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹的多重鏈表中有多少個(gè)空鏈域?為什么?儲(chǔ)，則A7,1和A2,4的第一個(gè)字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題(二)2分，共20分)1 在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行()。A、HL=p;p->next=HL;B、p->

8、next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;2由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A、24B、48C、72D、533 .一個(gè)數(shù)組元素ai與()的表示等價(jià)。A、*(a+i)B、a+iC、*a+iD、&a+i4 下面程序段的時(shí)間復(fù)雜度為()。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A、O(m 分，共 40 分)1 含n 個(gè)頂點(diǎn)的無向連通圖中至少含有條邊。2若對關(guān)鍵字序列(43， 02，

9、 80， 48， 26， 57， 15， 73， 21 ， 24， 66)進(jìn)行一趟增量為 3 的希爾排序，則得到的結(jié)果為。 一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n) ，其數(shù)量級表示為。 在以HL 為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為和。5快速排序在平均情況下的時(shí)間復(fù)雜度為，在最壞情況下的時(shí)間復(fù)雜度為。 假定對長度n=50 的有序表進(jìn)行二分查找，則對應(yīng)的判定樹高度為 ，判定樹中前5 層的結(jié)點(diǎn)數(shù)為 ，最后一層的結(jié)點(diǎn)數(shù)為 。7假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J) ，則度為 3、 2、 1、 0 的結(jié)點(diǎn)數(shù)分別為

10、、 、和個(gè)。 在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5 個(gè)，單分支結(jié)點(diǎn)數(shù)為 6 個(gè)，則葉子結(jié)點(diǎn)數(shù)為個(gè)。)B、O(n2)C、O(m*n)D、O(m+n)5 數(shù)據(jù)結(jié)構(gòu)是()。A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、一組性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合6 在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是()。A、插入B、刪除C、排序D、定位7 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為()。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，18在任意一棵二叉樹的前

11、序序列和后序序列中，各葉子之間的相對次序關(guān)系()。A、不一定相同B、都相同9圖的鄰接矩陣表示法適用于表示(A、無向圖 B、有向圖C 、都不相同 D 、互為逆序)。C、稠密圖 D、稀疏圖10若有序表的關(guān)鍵字序列為(b,c,d,e,f,g,q,r,s,t)，則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為()。A、f,c,bB、f,d,bC、g,c,bD、g,d,b9 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、和四種。10 .在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素（iwiwn+i）之前插入一個(gè)新元素時(shí)，需要從后向前依次后移個(gè)元素。三、應(yīng)用題（每題10分，共60分）1.設(shè)有5個(gè)互不相同的元素a、b、c、

12、d、e,能否通過7次比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。2有一隨機(jī)數(shù)組(25,84,21,46,13,27,68,35,20),則該排序方法是什么?初始:25,84,21,46,13,27,68,35,20第二趟:13,20,21,25,35,27,46,68,84現(xiàn)采用某種方法對它們進(jìn)行排序,其每趟排序結(jié)果如下,第一趟:20,13,21,25,46,27,68,35,84第三趟:13,20,21,25,27,35,46,68,843請?jiān)冢ǎ﹥?nèi)填入正確的排序方法。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組由不同排序方法進(jìn)行一遍排序后的結(jié)

13、果。（）排序的結(jié)果為：（）排序的結(jié)果為：（）排序的結(jié)果為：12，13，15，18，20，6013，15，18，12，20，6013，15，20，18，12，604設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度數(shù)皆為2，若T中有6個(gè)葉結(jié)點(diǎn)，試問：(1) T樹的最大深度Kmax=?最小可能深度Kmin=?(2) 2)T樹中共有多少非葉結(jié)點(diǎn)？(3) 若葉結(jié)點(diǎn)的權(quán)值分別為1,2,3,4,5,6。請構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長度wpl。5.一棵有n(n>0)個(gè)結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹的多重鏈表中有多少個(gè)空鏈域?為什么?6有一個(gè)二維數(shù)組A

14、0:8,1:5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ),存儲(chǔ)器按字節(jié)編址，假設(shè)存儲(chǔ)數(shù)組元素A0,1的第一個(gè)字節(jié)的地址是0，那么存儲(chǔ)數(shù)組的最后一個(gè)元素的第一個(gè)字節(jié)的地址是多少？若按行存儲(chǔ),則A3,5和A5,3的第一個(gè)字節(jié)的地址是多少？若按列存儲(chǔ)，則A7,1和A2,4的第一個(gè)字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（三）一、單選題（每題2分，共10分）1、在長度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（iwi買的，需要從前向后依次前移個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i2、設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n,則求廣義表深度算法的時(shí)間復(fù)雜度為。A、O（1）B、O（n）C、O（n2）D、O（log2n）3

15、、假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r,則判斷隊(duì)空的條件為。A、f+1=rB、r+1=fC、f=0D、f=r4、由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹。A、2B、3C、4D、55、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為。A、鏈接方式存儲(chǔ)，元素?zé)o序B.鏈接方式存儲(chǔ)，元素有序C、順序方式存儲(chǔ)，元素?zé)o序D.順序方式存儲(chǔ)，元素有序二、填空題（每空1分，共25分）1 、在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著、和的聯(lián)系。2 、在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為，若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為。3、在初始化一個(gè)稀疏

16、矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為參數(shù)。4、棧又稱為表，隊(duì)列又稱為表。5、后綴表達(dá)式“45+3*24+*的值為?！? 、一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為個(gè)，一棵深度為3的滿四叉樹中的結(jié)點(diǎn)數(shù)為個(gè)。7 、對于一棵含有40個(gè)結(jié)點(diǎn)的理想平衡樹，它的高度為。8、從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向查找。9、對于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為。10、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中頂點(diǎn)數(shù)和邊數(shù)分別為和。11、二分查找過程所對應(yīng)的判定樹既是一棵，又是一棵。12、

17、在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為，整個(gè)排序過程的時(shí)間復(fù)雜度為，空間復(fù)雜度為。13、給定一組數(shù)據(jù)6，2，7，10，3，12以它構(gòu)造一棵哈夫曼樹，則樹高為，帶權(quán)路徑長度WPLI勺值為。三、運(yùn)算題（每題6分，共24分）1 、假定一棵普通樹的廣義表表示為a（b（e）,c（f（h,i,j）,g）,d），分別寫出先根、后根、按層遍歷的結(jié)果。先根：。后根：。按層：。2 、已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：V=0，1，2，3，4，5，6，7；E=（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20；則求

18、出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)：。3、對于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為0的元素有個(gè)，散列地址為3的元素有個(gè)，散列地址為5的元素有個(gè)。4、假定一組記錄的排序碼為(46，79，56，38，40，80，25，34)，在對其進(jìn)行快速排序的過程中，對應(yīng)二叉搜索樹的深度為，分支結(jié)點(diǎn)數(shù)為。四、閱讀算法(第一題7分，第二題8分)1 、voidAA(LNode*&HL)InitList(HL);InsertRear(HL,30);InsertRear(HL,50);inta5=15,8,9,26,12;f

19、or(inti=0;i<5;i+)InsertFront(HL,ai);該算法被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素依次為：。2 、voidAH(Heap&HBT,constElemTypeitem)/HBT為一個(gè)小根堆HBT.heapHBT.size=item;HBT.size+;ElemTypex=iteminti=HBT.size-1;while(i!=0)intj=(i-1)/2;if(x>=HBT.heapj)break;HBT.heapi=HBT.heapj;i=j;HBT.heapi=x;該算法的功能為：。五、算法填空，在畫有橫線的地方填寫合

20、適的內(nèi)容。(12分)從一維數(shù)組An中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應(yīng)元素的下標(biāo)，否則返回-1。intBinsch(ElemTypeA,intlow,inthigh,KeyTypeK)if(low<=high)intmid=(low+high)/2;if(K=Amid.key);elseif(K<Amid.key);else;elsereturn-1;六、編寫算法(14分)item 的結(jié)點(diǎn)的非遞歸算法，若查找成功則由編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item帶回整個(gè)結(jié)點(diǎn)的值并返回true,否則返回false。bool Find( BTreeNo

21、deBST , ElemType & item )數(shù)據(jù)結(jié)構(gòu)作業(yè)題（四）一、選擇題（每題2分，共20分）1 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D,初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）？A.廣義表B.二叉樹C.稀疏矩陣D.串3 連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（）。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)4 若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）。A.O（0）B.O（1）C.O（n）D.O（n2）5 在雙向鏈表指針p的結(jié)點(diǎn)前

22、插入一個(gè)指針q的結(jié)點(diǎn)操作是（）。A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p-

23、>Llink=q;6 .若一個(gè)棧的輸入序列為1,2,3,n,輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的7 有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？（）A.543612B.453126C.346521D.2341568用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改9 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除頁眉內(nèi)容一個(gè)元素，再加入兩個(gè)元素后，rear和front的值

24、分別為多少？（）A.1和5B.2和4C.4和2D.5和110 .棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)二、填空題（每空2分，共30分）1 .數(shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個(gè)重要指標(biāo)是和。2 .一個(gè)算法具有5個(gè)特性：、，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。3 .在一個(gè)長度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。4 .對于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共個(gè)，單鏈表為個(gè)。5 .設(shè)數(shù)組a1.50,1.80的基地址為2000,每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元

25、素a45,68的存儲(chǔ)地址為;若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a45,68的存儲(chǔ)地址為。6 .所謂稀疏矩陣指的是。7 .廣義表的定義為廣義表中括弧的重?cái)?shù)。8 .具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。9 .已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有個(gè)葉子結(jié)點(diǎn)。10 .高度為8的完全二叉樹至少有個(gè)葉子結(jié)點(diǎn)。三、計(jì)算題（每題6分，共30分）1 .如果輸入序列為123456,試問能否通過棧結(jié)構(gòu)彳#到以下兩個(gè)序列:435612和135426;請說明為什么不能或如何才能得到。2 .假定一棵二叉樹廣義表表示為a（b（c）,d（e,f）,分別寫出對它進(jìn)行先序、中序、后序、按

26、層遍歷的結(jié)果。先序：中序：后序：按層：13頁眉內(nèi)容3已知一個(gè)圖的頂點(diǎn)集V和邊集G分別為：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20,(6,7)30;按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。4.已知一個(gè)圖的頂點(diǎn)集V和邊集G分別為：V=0,1,2,3,4,5,6,7,8;E=<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6

27、>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，則按主教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄?提示：先畫出對應(yīng)的圖形，然后再運(yùn)算)拓?fù)湫蛄校?假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進(jìn)行快速排序的第一次劃分后的結(jié)果為四、算法填空(10分)1向以BST為樹根指針的二又攫索樹上插入值為item的結(jié)點(diǎn)的廛歸曾法TQidInser-t(ETreetJodeBSTj

28、czonstEleinTypeitem)if(BST-NULL)3ST=n噂wBTreeNcdSjEl5THt或itain,elseif(itejn<fiST->datQ).eIse'五、編程(10分)1.設(shè)計(jì)算法以求解從集合1.n中選取k(k<=n)個(gè)元素的所有組合。例如，從集合1.4中選取2個(gè)元素的所有組合的輸出結(jié)果為：12,13,14,23,24,34。數(shù)據(jù)結(jié)構(gòu)作業(yè)題(五)一、選擇題（每題2分，共20分）1 若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為（）參數(shù)。A指針B引用C值）。2 在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)

29、，則執(zhí)行（Aq>next=p>next；p>next=q；Bp>next=q>next；q=p；C9>next=p>next；p>next=q；Dp>next=q>next；q一>next=p；3 在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（）位置。A前一個(gè)B后一個(gè)C當(dāng)前4向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。AO（1）BO（1og2n）CO（n）DO（nlog2n）5 假設(shè)有兩個(gè)串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（）。A.連接B.模式匹配C.求子串D.求串長6 我們對記錄進(jìn)行排序的目的是（）。A.

30、分類B.合并C.存儲(chǔ)D.查找7 在最壞的情況下，冒泡排序法的時(shí)間復(fù)雜度為（）。A.O（lgn）B.O（nlgn）C.O（n2）D.O（n）8廣義表（A,B,E,F,G）的表尾是（）。A.（B,E,F,G）B.（）C.（A，B，E，F(xiàn)，G）D.（G）9 線性表如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，要求內(nèi)存中的存儲(chǔ)單元的地址（）。A. 必須是連續(xù)的B. 部分要求是連續(xù)的C. 一定不是連續(xù)的D. 可以是連續(xù)的，也可以是不連續(xù)的10在數(shù)據(jù)結(jié)構(gòu)中，從邏輯結(jié)構(gòu)上，我們可以把數(shù)據(jù)結(jié)構(gòu)分為（）。A. 線性結(jié)構(gòu)和非線性結(jié)構(gòu)B. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)C. 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)二、填空題（每空1分，共25分）1

31、 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、和四種。2 對于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。3在一個(gè)稀疏矩陣中，每個(gè)非零元素所對應(yīng)的三元組包括該元素的、和三項(xiàng)。4在廣義表的存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)均包含有個(gè)域。5 當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t表示棧滿的條件為。6 假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為，最大深度為。7 在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為。8在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的。9 在一個(gè)具有n個(gè)頂點(diǎn)的無向圄中，要連通所有頂點(diǎn)則至少需要條邊。10

32、假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，貝采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為、和。11以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是存儲(chǔ)的表。12在索引表中，若一個(gè)索引項(xiàng)對應(yīng)主表中的一條記錄，則稱此索引為表。13快速排序在平均情況下的空間復(fù)雜度為，在最壞情況下的空間復(fù)雜度為。三、運(yùn)算題（每題5分，共20分）1 假定一個(gè)大堆為（56，38，42，30，25，40，35，20），則依次從中刪除兩個(gè)元素后得到的堆為。2 已知一個(gè)圖的頂點(diǎn)集V和邊集6分別為：V=0，1，2，3，4，5，6，7；E=（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，

33、（3，5）9，（3，6）10，（4，6）4，（5，7）20；按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。，。3 假定一組數(shù)據(jù)的初始堆為（84，79，56，42，40，46，50，38），請寫出在堆排序階段進(jìn)行前三次對換和篩運(yùn)算后數(shù)據(jù)的排列情況。數(shù)據(jù)排列情況：。4 假定一組記錄的徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對其進(jìn)行歸并排序的過程中，第三趟歸并后的結(jié)果為：。四、閱讀算法，回答問題（每題5分，共10分）1 voidAA（ListL）InitList（L）；InsertRear（L，30）；InsertFront（L，

34、50）；inta4=5，8，12，15for（inti=0;1v4;i+=InsertRear（L,ai）;該算法被調(diào)用執(zhí)行后，得到的線性表L為：。2 voidAF（QueueQ）InitQueue（Q）：inta4=5，8，12，15for（inti-0;iv4;i斗十=Qlnsert（Q,遷6）;QInsert（Q，QDelete（Q）；QInsert（Q，30）；QInsert（Q，QDelete（Q）10）；while（!QueueEmpty（Q）coutvvQDeleie（Q）vv”;該算法被調(diào)用后得到的輸出結(jié)果為：。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）從一維數(shù)組A

35、n上進(jìn)行快速排序的遞歸算法。voidQuickSort（ElemTypeA，ints，intt）inti=sj=t十1；ElemTypex=As；d0doi+；while；填寫一個(gè)循環(huán)條件doj-;while(Aj.stn>x.stn);if(I<j)ElemTypetemp=Ai;Ai=Aj;Aj=temp;while(ivj);As=Aj；Aj=x；if(svi-1);if(j十1<t);六、編寫算法(15分)BT 為樹根指針的二叉樹中的葉子結(jié)點(diǎn)的個(gè)數(shù)。編寫一個(gè)遞歸算法，統(tǒng)計(jì)并返回以intCount(BTreeNode*BT)東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題參考答案

36、習(xí)題一參考答案、選擇題(每題2分，共20分)12345678910ABCCCDBBAB、填空題(每題1分，共20分)1. n(n-1)/2;02. 13. _54. 215. 2i;2i+1;i/26. 順序；鏈接；索引；散列7. 10;4;38. n-19. 一對一：一對多：多對多10. _J0三、運(yùn)算題(每題5分，共10分)1.根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I>W,任意元素AIJ在一維數(shù)組B中的存放位置為I*(I+1)/2+J,因此，A85在數(shù)組B中位置為8*(8+1)/2+5=41。2.判斷結(jié)果兀素值3456586394比較次數(shù)21344四、應(yīng)用題(每題10分，共50分)1

37、 .答：(1)直接插入排序第一趟(3)8,3,2,5,9,1,6第二趟(2)8,3,2,5,9,1,6第三趟(5)8,5,3,2,9,1,6第四趟(9)9,8,5,3,2,1,6第五趟(1)9,8,5,3,2,1,6第六趟(6)9,8,6,5,3,2,1(2)直接選擇排序(第六趟后僅剩一個(gè)元素，是最小的，直接選擇排序結(jié)束)第一趟(9)9,3,2,5,8,1,6第二趟(8)9,8,2,5,3,1,6第三趟(6)9,8,6,5,3,1,2第四趟(5)9,8,6,5,3,1,2第五趟(3)9,8,6,5,3,1,2第六趟(2)9,8,6,5,3,2,12 .(1)是大堆；(2)是大堆；(4)是小堆；

38、(3)不是堆，調(diào)成大堆100,98,66,85,80,60,40,77,82,10,203 .答：先序遍歷二叉樹的順序是根一左子樹一右子樹”，中序遍歷左子樹一根一右子樹”，后序遍歷順序是:左子樹一右子樹一根"，根據(jù)以上原則，本題解答如下：(1)若先序序列與后序序列相同，則或?yàn)榭諛洌驗(yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(2)若中序序列與后序序列相同，則或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹.(3)若先序序列與中序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹.(4)若中序序列與層次遍歷序列相同，則或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹19頁眉內(nèi)容4.答：（1）T樹的最大深度Km

39、ax=6（除根外，每層均是兩個(gè)結(jié)點(diǎn)）T樹的最小深度Kmin=4（具有6個(gè)葉子的完全二叉樹是其中的一種形態(tài)）（2）非葉子結(jié)點(diǎn)數(shù)是5。（n2=n0-1）（3）哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51Wpl=4*3+3*3+2*（4+5+6）=5110. n-i+15.答：n (n>0)個(gè)結(jié)點(diǎn)的域有 nd-(n-1)=n(d-1)+1d度樹共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該樹的空鏈個(gè)。習(xí)題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA、填空題（每空2分，共40分）1. n-12. (15,02,21：24：26：57：43,66：

40、81：48,73)3. O(n)4. HL->next=NULLHL->next=HL5. O(nlog2n)；O(n2)6. 6;31;197. 2;1;1;68. _69. 集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹型結(jié)構(gòu)；圖形結(jié)構(gòu)頁眉內(nèi)容三、應(yīng)用題(每題10分，共60分)1 .答：可以做到。取a與b進(jìn)行比較，c與d進(jìn)行比較。設(shè)a>b,c>d(a<b和c<d情況類似)，此時(shí)需2次比較,取b和d比較，若b>d,則有序a>b>d;若b<d時(shí)則有序c>d>b,此時(shí)已進(jìn)行了3次比較。再把另外兩個(gè)元素按折半插入排序方法，插入到上述某個(gè)序列中共需4次

41、比較，從而共需7次比較。2 .該排序方法為快速排序。3 .快速排序冒泡排序直接插入排序4 .答：(1)T樹的最大深度Kmax=6(除根外，每層均是兩個(gè)結(jié)點(diǎn))T樹的最小深度Kmin=4(具有6個(gè)葉子的完全二叉樹是其中的一種形態(tài))(2)非葉子結(jié)點(diǎn)數(shù)是5。(n2=n0-1)(3)哈夫曼樹見下圖，其帶權(quán)路徑長度Wpl=4*3+3*3+2*(4+5+6)=515 .答：n(n>0)個(gè)結(jié)點(diǎn)的d度樹共啟域后nd-(n-1)=n(d-1)+1個(gè)。6 .答：7 1)176(2)76和108(3)習(xí)題三參考答案一、單選題(每題2分，共10分)1、A2、B3、D二、填空題(每空1分，共25分)1、1:11:N

42、M:N2、p->nextap.next3、引用4、后進(jìn)先出先進(jìn)先出5、1626、31217、6wpl=51_A6：4：1：53nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該樹的空?8和116。4、D5、D(或者1對11對NM對N)8、查找成功左子樹右子樹259、n210、nn-111、二叉搜索樹理想平衡樹(次序無先后)12、O(n)O(nlog2n)O(n)13、596三、運(yùn)算題(每題6分，共24分)1、先根:a,b,e,c,f,h,i,j,g,d;(2分)后根：e,b,h,i,j,f,g,c,d,a;(2分)按層：a,b,c,d,e,f,g,h,i,j;(2分)2、最小生成樹

43、的權(quán)：553、 3124、 56四、閱讀算法，回答問題(第一題7分，第二題8分)1、(12,26,9,8,15,30,50)2、向HBT堆中插入一個(gè)值為item的元素，使得插入后仍是一個(gè)堆。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(12分)returnmidreturnBinsch(A,low,mid-1,K)returnBinsch(A,mid+1,high,K)六、編寫算法(14分)評分標(biāo)準(zhǔn)：請根據(jù)編程情況酌情給分。boolFind(BTreeNode*BST,ElemType&item)while(BST!=NULL)if(item=BT->data)item=BST->data;returntrue;elseif(item<BST->data)BST=BST->le化elseBST=BST->right;returnfalse;習(xí)題四參考答案一、選擇題(每題2分，共20分)12345678910CDACCDCDBC1算法的時(shí)間復(fù)雜度