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

《最新數(shù)據(jù)結(jié)構(gòu)作業(yè)題參考答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、東北農(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．一對(duì)一；一對(duì)多；多對(duì)多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中位置為8*(8+1)/2+5=41。2．判斷結(jié)果元素值3456586394比較次數(shù)21

2、344四、應(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,

3、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．答：先序遍歷二叉樹(shù)的順序是“根—左子樹(shù)—右子樹(shù)”，中序遍歷“左子樹(shù)—根—右子樹(shù)”，后序遍歷順序是：“左子樹(shù)—右子樹(shù)―根＂，根據(jù)以上原則，本題解答如下：（1）若先序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)（2）若中序序列與后序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù)．（3）若先序序列與中序序列相同，則或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)．（4）若中序序列與層次遍歷序列相同，則

4、或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)4．答：（1）T樹(shù)的最大深度Kmax=6（除根外，每層均是兩個(gè)結(jié)點(diǎn)）T樹(shù)的最小深度Kmin=4（具有6個(gè)葉子的完全二叉樹(shù)是其中的一種形態(tài)）（2）非葉子結(jié)點(diǎn)數(shù)是5。（n2=n0-1）（3）哈夫曼樹(shù)見(jiàn)下圖，其帶權(quán)路徑長(zhǎng)度wpl=51Wpl=4*3+3*3+2*(4+5+6)=514561235．答：n（n>0）個(gè)結(jié)點(diǎn)的d度樹(shù)共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該?shù)的空鏈域有nd-(n-1)=n(d-1)+1個(gè)。習(xí)題二答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1．n

5、-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)；樹(shù)型結(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(ad，則有序a>b>d；若bd>b，此時(shí)已進(jìn)行了3次比較。再把另外兩個(gè)元素按折半插入排序方法，插入到上述某個(gè)序列中共需4次比較，從而共需7

6、次比較。2．該排序方法為快速排序。3．①快速排序②冒泡排序③直接插入排序4．答：（1）T樹(shù)的最大深度Kmax=6（除根外，每層均是兩個(gè)結(jié)點(diǎn)）T樹(shù)的最小深度Kmin=4（具有6個(gè)葉子的完全二叉樹(shù)是其中的一種形態(tài)）456123（2）非葉子結(jié)點(diǎn)數(shù)是5。（n2=n0-1）（3）哈夫曼樹(shù)見(jiàn)下圖，其帶權(quán)路徑長(zhǎng)度wpl=51Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n>0）個(gè)結(jié)點(diǎn)的d度樹(shù)共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該?shù)的空鏈域有nd-(n-1)=n(d-1)+1個(gè)。6．答：（1）176（2）76和108（3）28和116。習(xí)題三答案一、單選題（每題2分，共1

7、0分）1、A2、B3、D4、D5、D二、填空題（每空1分，共25分）1、1:11:NM:N（或者1對(duì)11對(duì)NM對(duì)N）2、p->nexta[p].next3、引用4、后進(jìn)先出先進(jìn)先出5、1626、31217、68、查找成功左子樹(shù)右子樹(shù)9、n210、nn-111、二叉搜索樹(shù)理想平衡樹(shù)（次序無(wú)先后）12、O(n)O(nlog2n)O(n)13、596三、運(yùn)算題（每題6分，共24分）1、先根：a,b,e,c,f,h,i,j,g,