本文格式為Word版，下載可任意編輯——中大數(shù)據(jù)結(jié)構(gòu)(C)其次次作業(yè)答案數(shù)據(jù)結(jié)構(gòu)其次次作業(yè)答案

學(xué)號(hào)：姓名：評(píng)分：.一.單項(xiàng)選擇題(20分)

()1.某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)一定是____b____的二叉樹(shù)。

a.空或只有一個(gè)結(jié)點(diǎn)b.高度等于其結(jié)點(diǎn)數(shù)（空樹(shù)高度為0）c.任一結(jié)點(diǎn)無(wú)左孩子d.任一結(jié)點(diǎn)無(wú)右孩子

()2.設(shè)圖的頂點(diǎn)數(shù)=n,邊數(shù)=e，若用鄰接表表示圖，那么求最短路徑的Dijkstra算法的時(shí)間繁雜

度為_(kāi)____b____。

a.O(n*e)b.O(n2)c.O(n+e)d.O(n3)

()3.一棵左右子樹(shù)均不為空的二叉樹(shù)在后序線索化后（不帶頭結(jié)點(diǎn)的線索化），其空指針域數(shù)為

____b_____。

a、0b、1c、2d、不確定()4.下面程序段的時(shí)間繁雜度是____d_____。

i=1;while(i0)個(gè)結(jié)點(diǎn)且為完全二叉樹(shù)的二叉排序樹(shù)中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)

為_(kāi)____b______。

a.O(n)b.O(log2n)c.O(nlog2n)d.O(n2)

()6.采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率一致，假設(shè)采用順序

查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分為_(kāi)___b____個(gè)結(jié)點(diǎn)最正確。a.10b.25c.6d.625

()7.以下排序算法中時(shí)間繁雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是____c______。

a、堆排序b、起泡排序c、直接選擇排序d、快速排序

()8.已知數(shù)據(jù)表中的每個(gè)元素距其最終位置不遠(yuǎn)，則采用____b___排序算法最省時(shí)間。

a.堆排序b.插入排序c.快速排序d.直接選擇排序

()9.假設(shè)圖的頂點(diǎn)數(shù)=n,邊數(shù)=e，那么當(dāng)用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴ǖ臅r(shí)間繁雜度為

____b_____。

a.O(n2)b.O(n+e)c.O(n*e)d.O(n3)

()10.一棵左子樹(shù)為空的二叉樹(shù)在先序線索化后（不帶頭結(jié)點(diǎn)的線索化），其中的空鏈域的個(gè)數(shù)

為_(kāi)___a_____。

a.2b.1c.0d.不確定二.填空作圖簡(jiǎn)答題（共62分）：1.依次插入30，43，21，9，15，51并由空樹(shù)構(gòu)成一棵平衡二叉樹(shù)，畫(huà)出該平衡二叉樹(shù)形成過(guò)程及其中序線索二叉樹(shù)。

3030302143214399219215143154315433030301

2.有一組關(guān)鍵碼序列{40，20，60，15，50，45，95，10，75}，采用Shell排序方法從小到大進(jìn)

行排序，假設(shè)其間隔序列為5，3，1，請(qǐng)寫(xiě)出每趟的結(jié)果。答案：

第1趟：40，20，10，15，50，45，95，60，75第2趟：15，20，10，40，50，45，95，60，75第3趟：10，15，20，40，45，50，60，75，95

3.對(duì)下面的3階B樹(shù)依次插入關(guān)鍵碼60，14，6，畫(huà)出插入三個(gè)關(guān)鍵碼后并刪除關(guān)鍵碼20后的

結(jié)果。20

1040

2812163050

4.用Prim算法求下圖的最小生成樹(shù),若從頂點(diǎn)0出發(fā)，請(qǐng)將算法中的輔助數(shù)組closedge的變化過(guò)

程填入下表。

16053

選出第1條邊3122587

輔助數(shù)組closedge647486557

adjvex

5

6701234所選邊2

lowcostadjvex選出第2條邊lowcostadjvex選出第3條邊lowcostadjvex選出第4條邊lowcostadjvex選出第5條邊lowcostadjvex選出第6條邊lowcostadjvex選出第7條邊lowcost

5.假設(shè)某森林的先根遍歷序列為EBADCFHGIKJ和中根遍歷序列為ABCDEFGHIJK。請(qǐng)畫(huà)出該

森林的帶雙親的孩子鏈表示。

6.已知9個(gè)結(jié)點(diǎn)的值分別為1～9，請(qǐng)將各結(jié)點(diǎn)的值填入下面二叉排序樹(shù)中：

5193647827.用堆排序算法(“最大堆〞排序算法)對(duì)關(guān)鍵字{70，33，79，67，46，24，30，40}進(jìn)行排序，

請(qǐng)先建“最大堆〞，然后輸出一個(gè)堆頂元素,并調(diào)整成堆：初始狀態(tài){40，33，24，67，46，79，30，70}所建大頂堆{79，70，40，67，46，24，30，33}或{79，70，67，46，40，24，30，33}輸出一個(gè)堆頂元素后調(diào)整的結(jié)果{70，67，40，33，46，24，30，79}或{70，46，67，33，40，24，30，79}

3

8.如下圖已知哈希表為空，哈希函數(shù)為H（Key）=KeyMOD11,沖突解決方法分別用線性探測(cè)

再散列和二次探測(cè)再散列。填入在依次插入關(guān)鍵字14，37，25，16之后的狀況，并求等概率狀況下所要求的平均查找長(zhǎng)度。

（1）線性探測(cè)再散列

01234567891014372516（2）二次探測(cè)再散列

01234567891025143716

線性探測(cè)再散列查找不成功時(shí)的平均查找長(zhǎng)度=____21/11_;二次探測(cè)再散列查找成功時(shí)的平均查找長(zhǎng)度=___6/4=3/2=1.5_;

9.用快速排序?qū)σ韵玛P(guān)鍵字進(jìn)行排序（圖示）,基準(zhǔn)元素取第一個(gè)元素。7033796746243040寫(xiě)出兩趟排序的結(jié)果。第一趟排序之后:{40，33，67，46，24，30}70{79}或{40，33，30，67，46，24}70{79};其次趟排序之后:{30，33，24}40{67，46}70，79或{24，33，30}40{46，67}70，79;若基準(zhǔn)元素按“三者取中〞的原則取，則兩趟排序的結(jié)果是：

第一趟排序之后:{40，33，46，24，30}67{79，70}或{33，40，30，24，46}67，{70，79};其次趟排序之后:{30，33，24}40{46}67，70，79或{24，30}33{40，46}67，70，79;

10.已知一字符串bcbdebcecbdcabd，試設(shè)計(jì)其赫夫曼編碼并畫(huà)出相應(yīng)的赫夫曼樹(shù)。a：1；b：5；c：4；d：3；e：2；dbbcdc

aeae

11.求出下圖中頂點(diǎn)A到其余個(gè)頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。

4

27A109E20B37F889C6G13D1HAE=10;AF=17;AB=19;AG=25;AC=26;AD=27;AH=28

三.程序填空(18分)

1.下面是僅給出了部分操作的二叉樹(shù)類(lèi)的定義和實(shí)現(xiàn)。試在程序的每一劃線部分填入一條語(yǔ)

句或表達(dá)式，完成計(jì)算度為1的結(jié)點(diǎn)個(gè)數(shù)的操作countNodes1()。

typedefstructBinNode{intdata;

structBinNode*leftchild,*rightchild;}BinNode,*BinTree;

voidInitBinTree(BinTree}

voidDestroyBinTree(BinTree

DestroyBinTree(root->leftchild);DestroyBinTree(root->rightchild);free(root);}

intcountNodes1(BinTreeelseif(root->leftchild==NULLelseif(root->leftchild!=NULL}

return0;}

5

92.下面是起泡排序算法的實(shí)現(xiàn)。試在程序的每一劃線部分填入一條語(yǔ)句或表達(dá)式，以使該算

法在發(fā)現(xiàn)數(shù)據(jù)有序時(shí)能及時(shí)中止。

voidBubbleSort(intdatalist[],intsize)//要排序的數(shù)據(jù)存放在數(shù)組datalist[]中，元素個(gè)數(shù)=size{

intexchange,i,j,temp;i=1;

exchange=1;

while(i=i;j--)

if(datalist[j-1]>datalist[j])

{

temp=datalist[j-1];datalist[j-1]=datalist[j];datalist[j]=temp;

____⑩___exchange=1_______;}

i++;}}

6

2.下面是起泡排序算法的實(shí)現(xiàn)。試在程序的每一劃線部分填入一條語(yǔ)句或表達(dá)式，以使該算

法在發(fā)現(xiàn)數(shù)據(jù)有序時(shí)能及時(shí)中止。

voidBubbleSort(intdatalist[],intsize)//要排序的數(shù)據(jù)存放在數(shù)組datalist[]中，元素個(gè)數(shù)=size{

intexchange,i,j,temp;i=1;