數據結構附錄習題及B卷答案答案

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數據結構附錄習題及B卷答案答案數據結構附錄A樣卷一

一、推斷題：（10分）

正確在括號內打√，錯誤打×

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

（）2．假如一個二叉樹中沒有度為1的結點，則必為滿二叉樹。

()3.循環(huán)鏈表的結點結構與單鏈表的結點結構徹低相同，只是結點間的銜接方式不同。()4.挨次存儲結構只能用來存放線性結構；鏈式存儲結構只能用來存放非線性結構。()5.在一個大根堆中，最小元素不一定在最后。

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

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

（）8.內部排序是指排序過程在內存中舉行的排序。

（）9.拓撲排序是指結點的值是有序羅列。

()10.AOE網所表示的工程至少所需的時光等于從源點到匯點的最長路徑的長度。

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

1．有一個含頭結點的單鏈表，頭指針為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．鏈表不具有的特點是。

A、可隨機拜訪任一個元素

B、插入刪除不需要移動元素

C、不必事先估量存儲空間

D、所需空間與線性表的長度成正比

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

A、單鏈表

B、雙鏈表

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

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

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

A、單鏈表

B、雙鏈表

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

D、挨次表

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

A、A，B，C，D

B、D，C，B，A

C、A，C，D，B

D、D，A，B，C

7．一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是。

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，18．設循環(huán)隊列中數組的下標范圍是1~n，其頭尾指針分離為f，r，若隊列中元素個數

為。

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

9．串是。

A、不少于一個字母的序列

B、隨意個字母的序列

C、不少于一個字符的序列

D、有限個字符的序列

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

A、1140

B、1145

C、1120

D、1125

11．將一棵有100個結點的徹低二叉樹從根這一層開頭，每一層從左到右依次對結點舉行編號，根結點編號為1，則編號為49的結點的左孩子的編號為。

A、98

B、99

C、50

D、48

12．對二叉樹從1開頭編號，要求每個結點的編號大于其左右孩子的編號，同一個結點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采納實現編號。

A、先序遍歷

B、中序遍歷

C、后序遍歷

D、從根開頭舉行層次遍歷

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

A、空或惟獨一個結點

B、高度等于其結點數

C、任一結點無左孩子

D、任一結點無右孩子

14．在有n個葉子結點的哈夫曼樹中，其結點總數為。

A、不確定

B、2n

C、2n+1

D、2n-1

15．一個有n個頂點的無向圖最多有條邊。

A、n

B、n（n-1）

C、n（n-1）/2

D、2n

16．任何一個無向連通圖的最小生成樹。

A、惟獨一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

17．一組記錄的關鍵字為（46，79，56，38，40，84），利用迅速排序的辦法，以第一個記錄為基準得到的一次劃分結果為。

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．已知數據表A中每個元素距其終于位置不遠，則采納排序算法最節(jié)約時光。

A、堆排序

B、插入排序

C、迅速排序

D、直接挑選排序

19．下列排序算法中，算法可能會浮現下面狀況：初始數據有序時，花費時光反而最多。

A、堆排序

B、冒泡排序

C、迅速排序

D、SHELL排序20．對于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必需從鍵值為的結點開頭。

A、100

B、60

C、12

D、15

三、填空題（40分）

1在挨次表（即挨次存儲結構的線性表）中插入一個元素，需要平均動個元素.

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

3.為防止在圖中走回，應設立.

4.一個棧的輸入序列為123，寫出不行能是棧的輸出序列。

5.N個結點的二叉樹,采納二叉鏈表存放,空鏈域的個數為.

6.要在一個單鏈表中p所指結點之后插入s所指結點時,

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

7.Dijkstra算法是按的次序產生一點到其余各頂點最短路徑的算法.

8.在N個結點徹低二叉樹中，其深度是.

9.對二叉排序樹舉行遍歷,可得到結點的有序羅列.

10．設一哈希表表長M為100，用除留余數法構造哈希函數，即H（K）=KMODP（P〈=M〉,為使函數具有較好性能，P應選

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

12．深度為6（根層次為1）的二叉樹至多有個結點。

13．已知二維數組A[0..20][0..10]采納行序為主方式存儲，每個元素占4個存儲單元,并且A[0][0]的存儲地址是1016,則A[10][5]的存儲地址是

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

15．在查找辦法中，平均查找長度與結點個數無關的查找辦法是。

16．隊列的特性是

17．具有3個結點的二叉樹有種

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

19．已知一個圖的鄰接矩陣表示，要刪除全部從第i個結點動身的邊，在鄰接矩陣運算是

四、構造題：（30分）

1．已知關鍵字序列為：（75,33,52,41,12,88,66,27）哈希表長為10，哈希函數為：

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

查找長度。

2．已知無向圖如圖1所示，

（1）給出圖的鄰接表。

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

3．給定葉結點權值：（1，3，5，6，7，8），構造哈夫曼樹，并計算其帶權路徑長度。

4．從空樹開頭，逐個讀入并插入下列關鍵字，構造一棵二叉排序樹：

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

5．對長度為8的有序表，給出折半查找的判定樹，給出等概率狀況下的平均查找長度。

6．已知一棵樹如圖2所示，要求將該樹轉化為二叉樹。

五、算法設計題(40分)

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

1．已知一棵二叉樹采納二叉鏈表存放，寫一算法，要求統計出二叉樹中葉子結點個數并輸出二叉樹中非終端結點（輸出無挨次要求）。

2．編寫算法，推斷帶頭結點的雙循環(huán)鏈表L是否對稱。

對稱是指：設各元素值a1,a2,...,an,則有ai=an-i+1

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

結點結構為

數據結構附錄B樣卷二

一、簡答題（15分，每小題3分）

1.簡要說明算法與程序的區(qū)分。

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

3.說明在圖的遍歷中，設置拜訪標志數組的作用。

4.說明以下三個概念的關系：頭指針，頭結點，首元素結點。

5.在普通的挨次隊列中，什么是假溢出？怎樣解決假溢出問題？

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

正確在括號內打√，錯誤打×

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

()（2）在哈夫曼樹中，權值最小的結點離根結點最近。

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

()（4）在平衡二叉樹中，隨意結點左右子樹的高度差（肯定值）不超過1。

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

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

()（7）數組元素的下標值越大，存取時光越長。

()（8）用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的狀況下，所占用的存儲空間大小只與圖中結點個數有關，而與圖的邊數無關。

()（9）拓撲排序是按AOE網中每個結點大事的最早發(fā)生時光對結點舉行排序。

()（10）長度為1的串等價于一個字符型常量。

三、單項挑選題（10分,每小題1分）

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

A、堆排序

B、直接插入排序

C、迅速排序

D、冒泡排序

2．已知一個有向圖的鄰接矩陣表示，要刪除全部從第i個結點發(fā)出的邊，應當：

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

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

3．有一個含頭結點的雙向循環(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)中，用折半法查找關鍵碼值11，所需的關鍵碼比較次數為：

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

5.以下哪一個不是隊列的基本運算？

A）從隊尾插入一個新元素B）從隊列中刪除第i個元素

C）推斷一個隊列是否為空D）讀取隊頭元素的值

6.在長度為n的挨次表的第i個位置上插入一個元素（1≤i≤n+1），元素的移動次數為：

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

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

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

8．對包含n個元素的哈希表舉行查找，平均查找長度為：

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

9．將一棵有100個結點的徹低二叉樹從根這一層開頭，每一層從左到右依次對結點舉行編號，根結點編號為1，則編號最大的非葉結點的編號為：

A、48

B、49

C、50

D、51

10．某二叉樹結點的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹中結點數目為：

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

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

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

intQKPass(RecordTyper[],intlow，inthigh)

{x=r[low]；

while(low,,,,

,,,,,}

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

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

4．（4分）已知權值集合為：{5，7，2，3，6，9}，要求給出哈夫曼樹，并計算其帶權路徑長度WPL。

六、算法分析題（10分）

閱讀下面程序，并回答有關問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。（1）簡要說明程序功能。（5分）

（2）n個結點的滿二叉樹的深度h是多少？（3分）

（3）假設二叉排序樹*bst是有n個結點的滿二叉樹,給出算法的時光復雜度。（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;

}

七、算法設計題（25分）

1．已知一個帶頭結點的整數單鏈表L，要求將其拆分為一個正整數單鏈表L1和一個負整數單鏈表L2。（9分）

2．無向圖采納鄰接表存儲結構，編寫算法輸出圖中各連通重量的結點序列。（8分）3．編寫一個建立二叉樹的算法，要求采納二叉鏈表存儲結構。（8分）

《數據結構》附錄B樣卷二參考答案

一、簡答題（15分，每小題3分）

6.算法是解決特定問題的操作序列，可以用多種方式描述。程序是算法在計算機中的實現，與詳細的計算機語言有關。

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

8.圖中結點可能有多個前驅，設置拜訪標志數組主要是為了避開重復拜訪同一個結點。

9.頭指針指向頭結點，頭結點的后繼域指向首元素結點。

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