數(shù)據(jù)結(jié)構(gòu)作業(yè)題附參考標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案

數(shù)據(jù)結(jié)構(gòu)作業(yè)題附參考標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案數(shù)據(jù)結(jié)構(gòu)作業(yè)題附參考標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案數(shù)據(jù)結(jié)構(gòu)作業(yè)題附參考標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)作業(yè)題附參考標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題（一）一、選擇題（每題2分，共20分）1．在一個(gè)長度為n地順序表地任一位置插入一個(gè)新元素地漸進(jìn)時(shí)間復(fù)雜度為（）.A、O(n) B、O(n/2) C、O(1) D、O(n2)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地有序順序表，若采用折半搜索，在等概率情況下搜索成功地平均搜索長度為（）地值除以9.A、20 B、18 C、25 D、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ù)組A[n]存放循環(huán)隊(duì)列地元素，其頭、尾指針分別為front和rear.若設(shè)定尾指針指向隊(duì)列中地隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素地前一個(gè)位置，則當(dāng)前存于隊(duì)列中地元素個(gè)數(shù)為（）.p1EanqFDPwA、(rear-front-1)％n B、(rear-front)％nC、(front-rear+1)％n D、(rear-front+n)％n9．高度為5地完全二叉樹中含有地結(jié)點(diǎn)數(shù)至少為（）.A、16B、17C、31 D、3210．如圖所示有向圖地一個(gè)拓?fù)湫蛄惺?)A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空題（每空1分，共20分）1．n(n﹥0)個(gè)頂點(diǎn)地?zé)o向圖最多有條邊，最少有條邊.2．在一棵AVL樹中，每個(gè)結(jié)點(diǎn)地左子樹高度與右子樹高度之差地絕對值不超過.3．已知8個(gè)數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)地方法生成一棵二叉排序樹，則該樹地深度為.DXDiTa9E3d4．在二叉樹地第i層上至多有結(jié)點(diǎn).5．對于一棵具有n個(gè)結(jié)點(diǎn)地二叉樹，若一個(gè)結(jié)點(diǎn)地編號為i(1≤i≤n)，則它地左孩子結(jié)點(diǎn)地編號為，右孩子結(jié)點(diǎn)地編號為，雙親結(jié)點(diǎn)地編號為.RTCrpUDGiT6．?dāng)?shù)據(jù)地存儲結(jié)構(gòu)被分為、、和四種.7．假定一棵樹地廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含地結(jié)點(diǎn)數(shù)為個(gè)，樹地深度為，樹地度為.5PCzVD7HxA8．在一個(gè)具有n個(gè)頂點(diǎn)地?zé)o向圖中，要連通所有頂點(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è)有一個(gè)1010地對稱矩陣A，將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置.jLBHrnAILg2．已知一個(gè)有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數(shù)組a[12]中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94時(shí)地比較次數(shù).xHAQX74J0X元素值3456586394比較次數(shù)四、應(yīng)用題（每題10分，共50分）1．設(shè)待排序地記錄共7個(gè)，排序碼分別為8，3，2，5，9，1，6.（1）用直接插入排序.試以排序碼序列地變化描述形式說明排序全過程（動(dòng)態(tài)過程）要求按遞減順序排序.（2）用直接選擇排序.試以排序碼序列地變化描述形式說明排序全過程（動(dòng)態(tài)過程）要求按遞減順序排序.2．判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）.（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，1003．試找出分別滿足下列條件地所有二叉樹.1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列與層次遍歷序列相同4．設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)地度數(shù)皆為2，若T中有6個(gè)葉結(jié)點(diǎn)，試問：（1）T樹地最大深度Kmax=最小可能深度Kmin=（2）T樹中共有多少非葉結(jié)點(diǎn)(3)若葉結(jié)點(diǎn)地權(quán)值分別為1,2,3,4,5,6.請構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹地帶權(quán)路徑長度5．一棵有n(n>0)個(gè)結(jié)點(diǎn)地d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹地多重鏈表中有多少個(gè)空鏈域?yàn)槭裁碯zz6ZB2Ltk儲，則A[7,1]和A[2,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->next=HL;HL=p;C、p->next=HL;p=HL; D、p->next=HL->next;HL->next=p;dvzfvkwMI12．由權(quán)值分別為3,8,6,2,5地葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它地帶權(quán)路徑長度為（）.A、24 B、48C、72 D、533．一個(gè)數(shù)組元素a[i]與（）地表示等價(jià).A、*(a+i)B、a+iC、*a+i D、&a+i4．下面程序段地時(shí)間復(fù)雜度為（）.for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．?dāng)?shù)據(jù)結(jié)構(gòu)是（）.A、一種數(shù)據(jù)類型B、數(shù)據(jù)地存儲結(jié)構(gòu)C、一組性質(zhì)相同地?cái)?shù)據(jù)元素地集合D、相互之間存在一種或多種特定關(guān)系地?cái)?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)地出棧序列為（）.rqyn14ZNXIA、3，2，6，1，4，5 B、3，4，2，1，6，5C、1，2，5，3，4，6 D、5，6，4，2，3，18．在任意一棵二叉樹地前序序列和后序序列中，各葉子之間地相對次序關(guān)系（）.A、不一定相同 B、都相同 C、都不相同 D、互為逆序9．圖地鄰接矩陣表示法適用于表示（）.A、無向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表地關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b地過程中，先后進(jìn)行比較地關(guān)鍵字依次為（）.EmxvxOtOcoA、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空題（每空2分，共40分）1．含n個(gè)頂點(diǎn)地?zé)o向連通圖中至少含有條邊.2．若對關(guān)鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進(jìn)行一趟增量為3地希爾排序，則得到地結(jié)果為.SixE2yXPq53．一個(gè)算法地時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級表示為.4．在以HL為表頭指針地帶表頭附加結(jié)點(diǎn)地單鏈表和循環(huán)單鏈表中，鏈表為空地條件分別為和.5．快速排序在平均情況下地時(shí)間復(fù)雜度為，在最壞情況下地時(shí)間復(fù)雜度為.6．假定對長度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ù)分別為、、和個(gè).kavU42VRUs8．在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為個(gè).9．?dāng)?shù)據(jù)地邏輯結(jié)構(gòu)被分為、、和四種.10．在一個(gè)長度為n地順序存儲線性表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移個(gè)元素.y6v3ALoS89三、應(yīng)用題（每題10分，共60分）1．設(shè)有5個(gè)互不相同地元素a、b、c、d、e，能否通過7次比較就將其排好序如果能，請列出其比較過程；如果不能，則說明原因.M2ub6vSTnP2．有一隨機(jī)數(shù)組(25,84,21,46,13,27,68,35,20),現(xiàn)采用某種方法對它們進(jìn)行排序,其每趟排序結(jié)果如下,則該排序方法是什么0YujCfmUCw初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84eUts8ZQVRd第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,84sQsAEJkW5T3．請?jiān)冢ǎ﹥?nèi)填入正確地排序方法.設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60.下面是一組由不同排序方法進(jìn)行一遍排序后地結(jié)果.GMsIasNXkA（）排序地結(jié)果為：12，13，15，18，20，60（）排序地結(jié)果為：13，15，18，12，20，60（）排序地結(jié)果為：13，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）T樹中共有多少非葉結(jié)點(diǎn)(3)若葉結(jié)點(diǎn)地權(quán)值分別為1,2,3,4,5,6.請構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹地帶權(quán)路徑長度5．一棵有n(n>0)個(gè)結(jié)點(diǎn)地d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹地多重鏈表中有多少個(gè)空鏈域?yàn)槭裁?EqZcWLZNX6．有一個(gè)二維數(shù)組A[0:8,1:5]，每個(gè)數(shù)組元素用相鄰地4個(gè)字節(jié)存儲,存儲器按字節(jié)編址，假設(shè)存儲數(shù)組元素A[0,1]地第一個(gè)字節(jié)地地址是0，那么存儲數(shù)組地最后一個(gè)元素地第一個(gè)字節(jié)地地址是多少若按行存儲,則A[3,5]和A[5,3]地第一個(gè)字節(jié)地地址是多少若按列存儲，則A[7,1]和A[2,4]地第一個(gè)字節(jié)地地址是多少lzq7IGf02E數(shù)據(jù)結(jié)構(gòu)作業(yè)題（三）一、單選題（每題2分，共10分）1、在長度為n地順序存儲地線性表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要從前向后依次前移個(gè)元素.A、n-iB、n-i+1C、n-i-1D、izvpgeqJ1hk2、設(shè)一個(gè)廣義表中結(jié)點(diǎn)地個(gè)數(shù)為n，則求廣義表深度算法地時(shí)間復(fù)雜度為.A、O(1)B、O(n)C、O(n2)D、O(log2n)NrpoJac3v13、假定一個(gè)順序隊(duì)列地隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空地條件為.A、f+1==rB、r+1==fC、f==0D、f==r1nowfTG4KI4、由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同地二叉樹.A、2B、3C、4D、5 5、適用于折半查找地表地存儲方式及元素排列要求為.A、鏈接方式存儲，元素?zé)o序B．鏈接方式存儲，元素有序C、順序方式存儲，元素?zé)o序D．順序方式存儲，元素有序二、填空題（每空1分，共25分）1、在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著、和地聯(lián)系.2、在線性表地單鏈接存儲中，若一個(gè)元素所在結(jié)點(diǎn)地地址為p，則其后繼結(jié)點(diǎn)地地址為，若假定p為一個(gè)數(shù)組a中地下標(biāo)，則其后繼結(jié)點(diǎn)地下標(biāo)為.fjnFLDa5Zo3、在初始化一個(gè)稀疏矩陣地函數(shù)定義中，矩陣形參應(yīng)說明為參數(shù).4、棧又稱為表，隊(duì)列又稱為表.5、后綴表達(dá)式“45+3*24+*”地值為.6、一棵深度為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ù)向查找.tfnNhnE6e59、對于一個(gè)具有n個(gè)頂點(diǎn)地圖，若采用鄰接矩陣表示，則矩陣大小為.10、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊地連通圖，其生成樹中頂點(diǎn)數(shù)和邊數(shù)分別為和.11、二分查找過程所對應(yīng)地判定樹既是一棵，又是一棵.12、在歸并排序中，進(jìn)行每趟歸并地時(shí)間復(fù)雜度為，整個(gè)排序過程地時(shí)間復(fù)雜度為，空間復(fù)雜度為. 13、給定一組數(shù)據(jù){6，2，7，10，3，12}以它構(gòu)造一棵哈夫曼樹，則樹高為__________，帶權(quán)路徑長度WPL地值為三、運(yùn)算題（每題6分，共24分）1、假定一棵普通樹地廣義表表示為a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷地結(jié)果.V7l4jRB8Hs先根：.后根：.按層：.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}；則求出該圖地最小生成樹地權(quán).最小生成樹地權(quán)：.3、對于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0地元素有個(gè)，散列地址為3地元素有個(gè)，散列地址為5地元素有個(gè).83lcPA59W94、假定一組記錄地排序碼為（46，79，56，38，40，80，25，34），在對其進(jìn)行快速排序地過程中，對應(yīng)二叉搜索樹地深度為，分支結(jié)點(diǎn)數(shù)為.mZkklkzaaP四、閱讀算法（第一題7分，第二題8分）1、voidAA(LNode*&HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);inta[5]={15,8,9,26,12};for(inti=0;i<5;i++)InsertFront(HL,a[i]);AVktR43bpw}該算法被調(diào)用執(zhí)行后，得到地以HL為表頭指針地單鏈表中地?cái)?shù)據(jù)元素依次為：.2、voidAH(Heap&HBT,constElemTypeitem)五、算法填空，在畫有橫線地地方填寫合適地內(nèi)容.（12分）從一維數(shù)組A[n]中二分查找關(guān)鍵字為K地元素地遞歸算法，若查找成功則返回對應(yīng)元素地下標(biāo)，否則返回intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)2MiJTy0dTT{if(low<=high){intmid=(low+high)/2;if(K==A[mid].key);elseif(K<A[mid].key);else;}elsereturn-1;}六、編寫算法（14分）編寫在以BST為樹根指針地二叉搜索樹上進(jìn)行查找值為item地結(jié)點(diǎn)地非遞歸算法，若查找成功則由item帶回整個(gè)結(jié)點(diǎn)地值并返回true，否則返回boolFind(BTreeNode*BST,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ù)存儲設(shè)計(jì)時(shí)，存儲單元地地址（）.A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)4．若長度為n地線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素地算法地時(shí)間復(fù)雜度為（）.uEh0U1YfmhA.O(0)B.O(1)C.O(n)D.O(n2)IAg9qLsgBX5．在雙向鏈表指針p地結(jié)點(diǎn)前插入一個(gè)指針q地結(jié)點(diǎn)操作是（）.A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；WwghWvVhPEB.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;asfpsfpi4kC.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;ooeyYZTjj1D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;BkeGuInkxI6．若一個(gè)棧地輸入序列為1,2,3,…,n，輸出序列地第一個(gè)元素是i，則第j個(gè)輸出元素是（）.PgdO0sRlMoA.i-j-1B.i-jC.j-i+1D.不確定地3cdXwckm157．有六個(gè)元素6，5，4，3，2，1地順序進(jìn)棧，問下列哪一個(gè)不是合法地出棧序列（）A.543612B.453126C.346521D.234156h8c52WOngM8．用鏈接方式存儲地隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）.A.僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改9．若用一個(gè)大小為6地?cái)?shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front地值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front地值分別為多少()v4bdyGiousA.1和5B.2和4C.4和2D.5和1J0bm4qMpJ910．棧和隊(duì)列地共同點(diǎn)是（）.A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)二、填空題（每空2分，共30分）1．?dāng)?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è)元素.XVauA9grYP4．對于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改地指針共______個(gè)，單鏈表為_______個(gè).bR9C6TJscw5．設(shè)數(shù)組a[1..50,1..80]地基地址為2000，每個(gè)元素占2個(gè)存儲單元，若以行序?yàn)橹餍蝽樞虼鎯?，則元素a[45,68]地存儲地址為__;若以列序?yàn)橹餍蝽樞虼鎯Γ瑒t元素a[45,68]地存儲地址為_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).DJ8T7nHuGT10．高度為8地完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn).三、計(jì)算題（每題6分，共30分）1．如果輸入序列為123456,試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列:435612和135426;請說明為什么不能或如何才能得到.QF81D7bvUA2．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進(jìn)行先序、中序、后序、按層遍歷地結(jié)果.4B7a9QFw9h先序：中序：后序：按層：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};ix6iFA8xoX按照普里姆算法從頂點(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>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};Kp5zH46zRk若存儲它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中地邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大地次序鏈接地，則按主教材中介紹地進(jìn)行拓?fù)渑判虻厮惴?，寫出得到地拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?yīng)地圖形，然后再運(yùn)算）.Yl4HdOAA61拓?fù)湫蛄校?．假定一組記錄地排序碼為(46,79,56,38,40,80,25,34)，則對其進(jìn)行快速排序地第一次劃分后地結(jié)果為四、算法填空（10分）1．五、編程（10分）1．設(shè)計(jì)算法以求解從集合{1..n}中選取k（k<=n）個(gè)元素地所有組合.例如，從集合{1..4}中選取2個(gè)元素地所有組合地輸出結(jié)果為：12，13，14，23，24，3數(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)，則執(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.分類 B.合并 C.存儲 D.查找7．在最壞地情況下，冒泡排序法地時(shí)間復(fù)雜度為（）.(lgn)(nlgn)(n2)(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)酱鎯Y(jié)構(gòu)，要求內(nèi)存中地存儲單元地地址（）.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．?dāng)?shù)據(jù)地邏輯結(jié)構(gòu)被分為、、和四種.2．對于一個(gè)長度為n地順序存儲地線性表，在表頭插入元素地時(shí)間復(fù)雜度為，在表尾插入元素地時(shí)間復(fù)雜度為.3．在一個(gè)稀疏矩陣中，每個(gè)非零元素所對應(yīng)地三元組包括該元素地、和三項(xiàng).4．在廣義表地存儲結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)均包含有個(gè)域.5．當(dāng)用長度為N地?cái)?shù)組順序存儲一個(gè)棧時(shí)，假定用top==N表示棧空，則表示棧滿地條件為.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)地?zé)o向圄中，要連通所有頂點(diǎn)則至少需要條邊.10．假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，貝采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí)，其相應(yīng)地空間復(fù)雜度分別為、和.E836L11DO511．以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是存儲地表.12．在索引表中，若一個(gè)索引項(xiàng)對應(yīng)主表中地一條記錄，則稱此索引為表.13．快速排序在平均情況下地空間復(fù)雜度為，在最壞情況下地空間復(fù)雜度為.三、運(yùn)算題（每題5分，共20分）1．假定一個(gè)大堆為（56，38，42，30，25，40，35，20），則依次從中刪除兩個(gè)元素后得到地堆為.S42ehLvE3M2．已知一個(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，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；501nNvZFis按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到地各條邊.，，，，，，.3．假定一組數(shù)據(jù)地初始堆為（84，79，56，42，40，46，50，38），請寫出在堆排序階段進(jìn)行前三次對換和篩運(yùn)算后數(shù)據(jù)地排列情況.jW1viftGw9數(shù)據(jù)排列情況：.4．假定一組記錄地徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對其進(jìn)行歸并排序地過程中，第三趟歸并后地結(jié)果為：.xS0DOYWHLP四、閱讀算法，回答問題（每題5分，共10分）1．voidAA（List＆L）{InitList（L）；InsertRear（L，30）；InsertFront（L，50）；inta[4]={5，8，12，15}for（inti=0；1＜4；i＋＋＝InsertRear（L，a[i]）；}該算法被調(diào)用執(zhí)行后，得到地線性表L為：.2．voidAF（Queue＆Q）{InitQueue（Q）：inta[4]={5，8，12，15}for（inti一0；i＜4；i斗＋＝Qlnsert（Q，遷6）；QInsert（Q，QDelete（Q））；QInsert（Q，30）；QInsert（Q，QDelete（Q）＋10）；whi1e（！QueueEmpty（Q））cout＜＜QDeleie（Q）＜＜”；}該算法被調(diào)用后得到地輸出結(jié)果為：.五、算法填空，在畫有橫線地地方填寫合適地內(nèi)容（10分）從一維數(shù)組A[n]上進(jìn)行快速排序地遞歸算法.voidQuickSort（ElemTypeA[]，ints，intt）{inti=sj=t十1；ElemTypex=A[s]；d0｛doi++；while；／／填寫一個(gè)循環(huán)條件doj--；while（A[j]．stn＞x．stn）；if（I<j）{ElemTypetemp=A［i］；A［i］=A［j］；A［j］＝temp；}}while（i＜j）；A[s]=A[j]；A[j]=x；if（s＜i一1）；if（j十1＜t）；}六、編寫算法（15分）編寫一個(gè)遞歸算法，統(tǒng)計(jì)并返回以BT為樹根指針地二叉樹中地葉子結(jié)點(diǎn)地個(gè)數(shù).intCount（BTreeNode*BT）東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題參考答案習(xí)題一參考答案一、選擇題（每題2分，共20分）12345678910ABCCCDBBAB二、填空題（每題1分，共20分）1．n(n-1)/2；02．13． 54．2i-15．2i；2i+1；i/26．順序；鏈接；索引；散列7．10；4；38．n-19．一對一；一對多；多對多10．10三、運(yùn)算題（每題5分，共10分）1．根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I≥J時(shí)，任意元素A[I][J]在一維數(shù)組B中地存放位置為I*(I+1)/2+J，因此，A[8][5]在數(shù)組B中位置為LOZMkIqI0w8*(8+1)/2+5=41.2．判斷結(jié)果元素值3456586394比較次數(shù)21344四、應(yīng)用題（每題10分，共50分）1．答： (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）是小堆；(3)不是堆，調(diào)成大堆100，98，66，85，80，60，40，77，82，10，203．答：先序遍歷二叉樹地順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則，本題解答如下：ZKZUQsUJed（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)至多只有右子樹地二叉樹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=51 Wpl=4*3+3*3+2*(4+5+6)=5144561235．答：n（n>0）個(gè)結(jié)點(diǎn)地d度樹共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該樹地空鏈域有nd-(n-1)=n(d-1)+1個(gè).dGY2mcoKtT習(xí)題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1．n-12．（15，02，21，24，26，57，43，66，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)10．n-i+1三、應(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次比較，從而共需7次比較.rCYbSWRLIA2．該排序方法為快速排序.3．①快速排序②冒泡排序③直接插入排序4．答：（1）T樹地最大深度Kmax=6（除根外，每層均是兩個(gè)結(jié)點(diǎn)）T樹地最小深度Kmin=4（具有6個(gè)葉子地完全二叉樹是其中地一種形態(tài)）45456123（3）哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n>0）個(gè)結(jié)點(diǎn)地d度樹共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)福试摌涞乜真溣蛴衝d-(n-1)=n(d-1)+1個(gè).FyXjoFlMWh6．答：（1）176（2）76和108（3）28和116.習(xí)題三參考答案一、單選題（每題2分，共10分）1、A2、B3、D 4、D 5、D二、填空題（每空1分，共25分）1、1:11:NM:N（或者1對11對NM對N）TuWrUpPObX2、p->nexta[p].next3、引用4、后進(jìn)先出先進(jìn)先出5、1626、31217、68、查找成功左子樹右子樹9、n210、nn-111、二叉搜索樹理想平衡樹（次序無先后）12、O(n)O(nlog2n)O(n) 13、5 96三、運(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、最小生成樹地權(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->left;elseBST=BST->right;}returnfalse;}習(xí)題四參考答案一、選擇題（每題2分，共20分）12345678910CDACCDCDBC二、填空題（每空2分，共30分）1．算法地時(shí)間復(fù)雜度和空間復(fù)雜度2．有窮性；確定性；可行性.3．n-i+1 4．425．9174 8788 6．非零元很少(t<<m*n)且分布沒有規(guī)律7．深度 8．9 9．12 10．64三、計(jì)算題（每題6分，共30分）1．輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧.7qWAq9jPqE得到135426地過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分