數(shù)據(jù)結(jié)構(gòu)附錄習(xí)題及B卷答案答案

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦數(shù)據(jù)結(jié)構(gòu)附錄習(xí)題及B卷答案答案數(shù)據(jù)結(jié)構(gòu)附錄A樣卷一

一、推斷題：（10分）

正確在括號(hào)內(nèi)打√，錯(cuò)誤打×

()1.在單鏈表中，頭結(jié)點(diǎn)是必不行少的。

（）2．假如一個(gè)二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，則必為滿二叉樹(shù)。

()3.循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)徹低相同，只是結(jié)點(diǎn)間的銜接方式不同。()4.挨次存儲(chǔ)結(jié)構(gòu)只能用來(lái)存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用來(lái)存放非線性結(jié)構(gòu)。()5.在一個(gè)大根堆中，最小元素不一定在最后。

()6.在一個(gè)有向圖中，全部頂點(diǎn)的入度之和等于全部頂點(diǎn)的出度之和。

（）7.在采納線性探測(cè)法處理矛盾的散列表中，全部同義詞在表中相鄰。

（）8.內(nèi)部排序是指排序過(guò)程在內(nèi)存中舉行的排序。

（）9.拓?fù)渑判蚴侵附Y(jié)點(diǎn)的值是有序羅列。

()10.AOE網(wǎng)所表示的工程至少所需的時(shí)光等于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。

二、挑選題(30分,每題1.5分)

1．有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為head,則推斷其是否為空的條件為：

________________

A．head=NILB.head^.next=NILC.head^.next=headD.headNIL或A．head==NULLB.Head->next==NULLC.head->next==headD.Head!=NULL2．非空的循環(huán)單鏈表head的尾指針p滿足______________。

A.p^.next=NIL

B.p=NIL

C.p^.next=head

D.p=head

或A.p->next=NULLB.p==NULLC.P->next==headD.p==head

3．鏈表不具有的特點(diǎn)是。

A、可隨機(jī)拜訪任一個(gè)元素

B、插入刪除不需要移動(dòng)元素

C、不必事先估量存儲(chǔ)空間

D、所需空間與線性表的長(zhǎng)度成正比

4．若某鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采納存儲(chǔ)方式最節(jié)約運(yùn)算時(shí)光。

A、單鏈表

B、雙鏈表

C、單循環(huán)鏈表

D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

5．若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采納存儲(chǔ)方式節(jié)約時(shí)光。

A、單鏈表

B、雙鏈表

C、單循環(huán)鏈表

D、挨次表

6．設(shè)一個(gè)棧的輸入序列為A，B，C，D，則借助一個(gè)棧所得到的輸出序列不行能的是。

A、A，B，C，D

B、D，C，B，A

C、A，C，D，B

D、D，A，B，C

7．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是。

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，18．設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針?lè)蛛x為f，r，若隊(duì)列中元素個(gè)數(shù)

為。

A、r-fB、r-f+1C、（r-f+1）modnD、（r-f+n）modn

9．串是。

A、不少于一個(gè)字母的序列

B、隨意個(gè)字母的序列

C、不少于一個(gè)字符的序列

D、有限個(gè)字符的序列

10．?dāng)?shù)組A[1..5,1..6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的延續(xù)內(nèi)存單元中，則A[5，5]的地址是。

A、1140

B、1145

C、1120

D、1125

11．將一棵有100個(gè)結(jié)點(diǎn)的徹低二叉樹(shù)從根這一層開(kāi)頭，每一層從左到右依次對(duì)結(jié)點(diǎn)舉行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為。

A、98

B、99

C、50

D、48

12．對(duì)二叉樹(shù)從1開(kāi)頭編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采納實(shí)現(xiàn)編號(hào)。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、從根開(kāi)頭舉行層次遍歷

13．某二叉樹(shù)的先序序列和后序序列正巧相反，則該二叉樹(shù)一定是的二叉樹(shù)。

A、空或惟獨(dú)一個(gè)結(jié)點(diǎn)

B、高度等于其結(jié)點(diǎn)數(shù)

C、任一結(jié)點(diǎn)無(wú)左孩子

D、任一結(jié)點(diǎn)無(wú)右孩子

14．在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為。

A、不確定

B、2n

C、2n+1

D、2n-1

15．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。

A、n

B、n（n-1）

C、n（n-1）/2

D、2n

16．任何一個(gè)無(wú)向連通圖的最小生成樹(shù)。

A、惟獨(dú)一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

17．一組記錄的關(guān)鍵字為（46，79，56，38，40，84），利用迅速排序的辦法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為。

A、38，40，46，56，79，84

B、40，38，46，79，56，84

C、40，38，46，56，79，84

D、40，38，46，84，56，79

18．已知數(shù)據(jù)表A中每個(gè)元素距其終于位置不遠(yuǎn)，則采納排序算法最節(jié)約時(shí)光。

A、堆排序

B、插入排序

C、迅速排序

D、直接挑選排序

19．下列排序算法中，算法可能會(huì)浮現(xiàn)下面狀況：初始數(shù)據(jù)有序時(shí)，花費(fèi)時(shí)光反而最多。

A、堆排序

B、冒泡排序

C、迅速排序

D、SHELL排序20．對(duì)于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必需從鍵值為的結(jié)點(diǎn)開(kāi)頭。

A、100

B、60

C、12

D、15

三、填空題（40分）

1在挨次表（即挨次存儲(chǔ)結(jié)構(gòu)的線性表）中插入一個(gè)元素，需要平均動(dòng)個(gè)元素.

2.迅速排序的最壞狀況，其待排序的初始羅列是.

3.為防止在圖中走回，應(yīng)設(shè)立.

4.一個(gè)棧的輸入序列為123，寫(xiě)出不行能是棧的輸出序列。

5.N個(gè)結(jié)點(diǎn)的二叉樹(shù),采納二叉鏈表存放,空鏈域的個(gè)數(shù)為.

6.要在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)時(shí),

應(yīng)執(zhí)行和的操作.

7.Dijkstra算法是按的次序產(chǎn)生一點(diǎn)到其余各頂點(diǎn)最短路徑的算法.

8.在N個(gè)結(jié)點(diǎn)徹低二叉樹(shù)中，其深度是.

9.對(duì)二叉排序樹(shù)舉行遍歷,可得到結(jié)點(diǎn)的有序羅列.

10．設(shè)一哈希表表長(zhǎng)M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=KMODP（P〈=M〉,為使函數(shù)具有較好性能，P應(yīng)選

11．單鏈表與多重鏈表的區(qū)分是

12．深度為6（根層次為1）的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。

13．已知二維數(shù)組A[0..20][0..10]采納行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元,并且A[0][0]的存儲(chǔ)地址是1016,則A[10][5]的存儲(chǔ)地址是

14．循環(huán)單鏈表La中，指針P所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是

15．在查找辦法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找辦法是。

16．隊(duì)列的特性是

17．具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有種

18．已知一棵二叉樹(shù)的前序序列為ABDFCE，中序序列為DFBACE，后序序列為

19．已知一個(gè)圖的鄰接矩陣表示，要?jiǎng)h除全部從第i個(gè)結(jié)點(diǎn)動(dòng)身的邊，在鄰接矩陣運(yùn)算是

四、構(gòu)造題：（30分）

1．已知關(guān)鍵字序列為：（75,33,52,41,12,88,66,27）哈希表長(zhǎng)為10，哈希函數(shù)為：

H(k)=KMOD7,解決矛盾用線性探測(cè)再散列法，構(gòu)造哈希表，求等概率下查找勝利的平均

查找長(zhǎng)度。

2．已知無(wú)向圖如圖1所示，

（1）給出圖的鄰接表。

（2）從A開(kāi)頭，給出一棵廣度優(yōu)先生成樹(shù)。

3．給定葉結(jié)點(diǎn)權(quán)值：（1，3，5，6，7，8），構(gòu)造哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度。

4．從空樹(shù)開(kāi)頭，逐個(gè)讀入并插入下列關(guān)鍵字，構(gòu)造一棵二叉排序樹(shù)：

（24，88，42，97，22，15，7，13）。

5．對(duì)長(zhǎng)度為8的有序表，給出折半查找的判定樹(shù)，給出等概率狀況下的平均查找長(zhǎng)度。

6．已知一棵樹(shù)如圖2所示，要求將該樹(shù)轉(zhuǎn)化為二叉樹(shù)。

五、算法設(shè)計(jì)題(40分)

[算法題可用類PASCAL或類C語(yǔ)言,每題20分]

1．已知一棵二叉樹(shù)采納二叉鏈表存放，寫(xiě)一算法，要求統(tǒng)計(jì)出二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)并輸出二叉樹(shù)中非終端結(jié)點(diǎn)（輸出無(wú)挨次要求）。

2．編寫(xiě)算法，推斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L是否對(duì)稱。

對(duì)稱是指：設(shè)各元素值a1,a2,...,an,則有ai=an-i+1

即指：a1=an，a2=an-1。。。。。。

結(jié)點(diǎn)結(jié)構(gòu)為

數(shù)據(jù)結(jié)構(gòu)附錄B樣卷二

一、簡(jiǎn)答題（15分，每小題3分）

1.簡(jiǎn)要說(shuō)明算法與程序的區(qū)分。

2.在哈希表中，發(fā)生矛盾的可能性與哪些因素有關(guān)？為什么？

3.說(shuō)明在圖的遍歷中，設(shè)置拜訪標(biāo)志數(shù)組的作用。

4.說(shuō)明以下三個(gè)概念的關(guān)系：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。

5.在普通的挨次隊(duì)列中，什么是假溢出？怎樣解決假溢出問(wèn)題？

二、推斷題（10分，每小題1分）

正確在括號(hào)內(nèi)打√，錯(cuò)誤打×

()（1）廣義表(((a),b),c)的表頭是((a),b)，表尾是(c)。

()（2）在哈夫曼樹(shù)中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。

()（3）基數(shù)排序是高位優(yōu)先排序法。

()（4）在平衡二叉樹(shù)中，隨意結(jié)點(diǎn)左右子樹(shù)的高度差（肯定值）不超過(guò)1。

()（5）在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面：p->next=s;s->next=p->next;

()（6）抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是自立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的規(guī)律特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。

()（7）數(shù)組元素的下標(biāo)值越大，存取時(shí)光越長(zhǎng)。

()（8）用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的狀況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。

()（9）拓?fù)渑判蚴前碅OE網(wǎng)中每個(gè)結(jié)點(diǎn)大事的最早發(fā)生時(shí)光對(duì)結(jié)點(diǎn)舉行排序。

()（10）長(zhǎng)度為1的串等價(jià)于一個(gè)字符型常量。

三、單項(xiàng)挑選題（10分,每小題1分）

1．排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排序辦法的基本思想？

A、堆排序

B、直接插入排序

C、迅速排序

D、冒泡排序

2．已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除全部從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)當(dāng)：

A）將鄰接矩陣的第i行刪除B）將鄰接矩陣的第i行元素所有置為0

C）將鄰接矩陣的第i列刪除D）將鄰接矩陣的第i列元素所有置為0

3．有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為head,則其為空的條件是：

A.head->priro==NULL

B.head->next==NULL

C.head->next==head

D.head->next->priro==NULL

4.在挨次表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：

A)2B)3C)4D)5

5.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？

A）從隊(duì)尾插入一個(gè)新元素B）從隊(duì)列中刪除第i個(gè)元素

C）推斷一個(gè)隊(duì)列是否為空D）讀取隊(duì)頭元素的值

6.在長(zhǎng)度為n的挨次表的第i個(gè)位置上插入一個(gè)元素（1≤i≤n+1），元素的移動(dòng)次數(shù)為：

A)n–i+1B)n–iC)iD)i–17．對(duì)于只在表的首、尾兩端舉行插入操作的線性表，宜采納的存儲(chǔ)結(jié)構(gòu)為:

A)挨次表B)用頭指針表示的循環(huán)單鏈表

C)用尾指針表示的循環(huán)單鏈表D)單鏈表

8．對(duì)包含n個(gè)元素的哈希表舉行查找，平均查找長(zhǎng)度為：

A)O(log2n)B)O(n)C)O(nlog2n)D)不直接依靠于n

9．將一棵有100個(gè)結(jié)點(diǎn)的徹低二叉樹(shù)從根這一層開(kāi)頭，每一層從左到右依次對(duì)結(jié)點(diǎn)舉行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：

A、48

B、49

C、50

D、51

10．某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：

A）3B）2C）4D）5

四、填空題（10分，每空1分）

1．填空完成下面一趟迅速排序算法：

intQKPass(RecordTyper[],intlow，inthigh)

{x=r[low]；

while(low,,,,

,,,,,}

2．（6分）對(duì)以下關(guān)鍵字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函數(shù)為H(K)=（K中最后一個(gè)字母在字母表中的序號(hào)）MOD7。用線性探測(cè)法處理矛盾，要求構(gòu)造一個(gè)裝填因子為0.7的哈希表，并計(jì)算出在等概率狀況下查找勝利的平均查找長(zhǎng)度。

3.（6分）將關(guān)鍵字序列（3，26，12，61，38，40，97，75，53，87）調(diào)節(jié)為大根堆。

4．（4分）已知權(quán)值集合為：{5，7，2，3，6，9}，要求給出哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度WPL。

六、算法分析題（10分）

閱讀下面程序，并回答有關(guān)問(wèn)題。其中BSTree為用二叉鏈表表示的二叉排序樹(shù)類型。（1）簡(jiǎn)要說(shuō)明程序功能。（5分）

（2）n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)的深度h是多少？（3分）

（3）假設(shè)二叉排序樹(shù)*bst是有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù),給出算法的時(shí)光復(fù)雜度。（2分）intProc(BSTree*bst,KeyTypeK)

{BSTreef,q,s;

s=(BSTree)malloc(sizeof(BSTNode));

s->key=K;s->lchild=NULL;s->rchild=NULL;

if(*bst==NULL){*bst=s;return1;}

f=NULL;q=*bst;

while(q!=NULL)

{if(Kkey)

{f=q;q=q->lchild;}

else

{f=q;q=q->rchild;}

}

if(Kkey)f->lchild=s;

elsef->rchild=s;

return1;

}

七、算法設(shè)計(jì)題（25分）

1．已知一個(gè)帶頭結(jié)點(diǎn)的整數(shù)單鏈表L，要求將其拆分為一個(gè)正整數(shù)單鏈表L1和一個(gè)負(fù)整數(shù)單鏈表L2。（9分）

2．無(wú)向圖采納鄰接表存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法輸出圖中各連通重量的結(jié)點(diǎn)序列。（8分）3．編寫(xiě)一個(gè)建立二叉樹(shù)的算法，要求采納二叉鏈表存儲(chǔ)結(jié)構(gòu)。（8分）

《數(shù)據(jù)結(jié)構(gòu)》附錄B樣卷二參考答案

一、簡(jiǎn)答題（15分，每小題3分）

6.算法是解決特定問(wèn)題的操作序列，可以用多種方式描述。程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)，與詳細(xì)的計(jì)算機(jī)語(yǔ)言有關(guān)。

7.主要與哈希函數(shù)、裝填因子α有關(guān)。假如用哈希函數(shù)計(jì)算的地址分布勻稱，則矛盾的可能性較小，假如裝填因子α較小，則哈希表較稀疏，發(fā)生矛盾的可能性較小。

8.圖中結(jié)點(diǎn)可能有多個(gè)前驅(qū)，設(shè)置拜訪標(biāo)志數(shù)組主要是為了避開(kāi)重復(fù)拜訪同一個(gè)結(jié)點(diǎn)。

9.頭指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的后繼域指向首元素結(jié)點(diǎn)。

10.當(dāng)隊(duì)尾到達(dá)數(shù)組最后一個(gè)單元時(shí)，就認(rèn)為隊(duì)滿，但此時(shí)數(shù)組前面可能還有空單元，因此叫假溢出。解決的辦法是采納循環(huán)隊(duì)列，即令最后一個(gè)單元的后繼是第一個(gè)單元。