杭州電子科技大學(xué)學(xué)生考試卷（B）卷

考試課程數(shù)據(jù)結(jié)構(gòu)考試日期2018年月日成績

課程號A2701410教師號任課教師姓名

考生姓名學(xué)號（8位）年級專業(yè)

特別提醒：答案一律寫在答題紙上，否則不給分。

一.判斷題（每題2分，共10分）（正確的打“止，錯誤的打“X”。）

1.數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)對象通常是指性質(zhì)相同的數(shù)據(jù)元素的集合。（）

10.廣義表D=（A,B,C）,其中A的長度為0,B的長度為1,C的長度為2,則D的長度為（）,

2.線性表采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址是連續(xù)的。（）

A.2B.3C.4D.無法確定

3.一棵所有結(jié)點的度最大為2的樹是二叉樹。（）

11.采用順序查找法查找長度為n的線性表時，則表中每個元素的平均查找長度為（）<>

4.折半查找（二分查找）要求線性表中的節(jié)點必須按關(guān)鍵字遞增排列。（）

A.nB.n/2C.（n-l）/2D.（n+i）/2

5.一個有n（n>0）個頂點的無向圖最多有n（n-l）條邊。（）

12.如果圖G是一個具有n個頂點和e條邊的無向連通圖，則必滿足（

A.n>eB.n<eC.n=eD.e>n-2

二.單選題（每題2分，共30分）

13.平衡二義樹上所有結(jié)點的平衡因子（BF）均不可能為（）。

1.堆排序的時間復(fù)雜度為（）o

A.-2B.-IC.0D.I

A.O（n2）B.O（n）

14.對線性表進行二分查找時，要求線性表必須（）。

C.O（nhgn）D.O（n3/2）

A.順序方式存儲B.鏈式方式存儲

2.鏈表區(qū)別于線性表的特點是（）?

C.順序方式存儲，且結(jié)點按關(guān)鍵字有序排序D.鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排序

A.可隨機訪問任?元素

15.下列排序方法中，所需輔助存儲空間最少的是（）。

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

A.快速排序B.堆排序C.歸并排序D.基數(shù)排序

C.事先需估計存儲空間

三.填空題（每空2分，共10分）

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

1.表達式a+b*c?（d+e）的前綴表達式為。

3.一個棧的入棧序列為A、B、C、D、E,則出棧時不可能的輸出序列是（）。

2.設(shè)S為?個長度為n（n>3）的字符串，其中的字符各不相同，則長度為2的子串個數(shù)

A.EDCBAB.DECBAC.ABCDED.DECAB

為-

4.判斷一個順序隊列sq（容量為QueueSize）為空隊列的條件是（）?

3.已知某二叉樹的后序遍歷次序為DABEC,中序遍歷次序為DEBAC其前序遍歷次序

A.sq.rear==sq.frontB.sq.reai-=0

為，層次遍歷次序為o

C.sq.front==QueueSizeD.sq.rear==QueueSize+1

4.在各種內(nèi)部查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是_

5.一個循環(huán)隊列一旦定義，其占用空間的大?。?/p>

四.問答題（每題10分，共40分）

A.已固定B.可以改變

1.請使用克魯斯卡爾（Kruskal）算法（5分）和普里姆（Prim）用分）（以。點為起點）求出下圖的最小生

C.不能固定D.動態(tài)變化

成樹,依次寫出每次被選擇的合法的合并代價最小的邊的編號，用一個空格分隔。頂點a到頂點b（a<b）

6.非空順序棧s出棧（pop）時，用e返回其值的語句是（）,,

之間的邊編號為ab,例如圖中權(quán)值為10的邊編號為03。

A.e=-*s.top;B.e=*s.top-;

C.e=*-s.top;D.e=*（s.top-l）;

7.G是一個非連通無向圖，共有32條邊，則該圖至少有（）個頂點。

A.6B.7C.8D.9

8.深度為6的二叉樹，節(jié)點數(shù)最多可達（）個。

A.32B.31C.63D.64

9.某項目的AOE圖如下所示，則該項目完工最少需要（）單位時間。

A.18B.17C.16D.15

圖1

2.一個包含100,000個字符的文件，各字符出現(xiàn)頻率如下表所示。

abcdef

頻率（千次）4513121695

①、構(gòu)造赫夫曼（Huffman）樹。（7分）

②、確定其對應(yīng)的赫夫曼編碼。（3分）

3.設(shè)有一組關(guān)鍵字｛19,01,23,14,55,20,84,27,68,11）,采用哈希函數(shù)為

H（key）=key%13

采用開放地址法的二次探測再散列方法解決沖突，在0'18的散列地址空間：

①、畫出哈希表示意圖：（5分）

②、若查找關(guān)鍵字84,需要依次與哪些關(guān)鍵字比較；（3分）

③、假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。（2分）

4.以關(guān)鍵字序列（500,87,512,61,907,170,888,275,653,466）為例,分別寫出進行以下排列算法

進行升序排列時，關(guān)鍵字序列排序的前兩趟狀態(tài)。

①起泡排序；（2分）

②直接插入排序；（從i=2起作為第?趟排序）（2分）

③簡單選擇排序；（2分）

④快速排序：（2分）

⑤基數(shù)排序。（2分）

五.程序設(shè)計題（10分）。

1.當(dāng)二叉樹采用二叉鏈表存儲結(jié)構(gòu)存儲方式時，寫出二叉樹及其結(jié)點結(jié)構(gòu)的C語言實現(xiàn)代碼。（4分）

2.在1的基礎(chǔ)上，設(shè)計?個計算?顆給定二叉樹的所有節(jié)點總數(shù)的算法。（6分）

杭州電子科技大學(xué)學(xué)生考試卷（B）卷答卷(2)a:0b:101c:100d:111e:1101每個符號0.5分，3分)

3.(1)

考試課程數(shù)據(jù)結(jié)構(gòu)考試日期2018年月日成績

0123467891011151617

課程號A270I410教師號任課教師姓名王小軍、王慧

27011455688419202311

考生姓名學(xué)號（8位）年級專業(yè)

3121131111

(2)關(guān)鍵字：1920

一、判斷題(每題2分，共10分)

(3)平均查找長度：15/10=1.5

|L7|2,X|3.X|4.X[5,X]

二、單選題（每選2分，共30分）4.

（1）起泡排序排序:

LC2.B3.D4.A5.A6.C|7.D|8.C|9,A|10.B

87,500,61,512,170,888,275,653,466,907；

1I.DI2.DI3.AI4.C15.B

87,61,500,170,512,275,653,466,888,907；

(2)直接插入排序：

三、填空題（每空2分，共10分）

87,500,512,61,907,170,888,275,653,466；

1.-+a*bc+de或2.n-13.CEDBA4.CEDBA哈希查找87,500,512,61,907,170,888,275,653,466；

+a-*bc+de(3)簡單選擇排序:

61,500,512,87,907,170,888,275,653,466；

四、問答題（每題10分，共40分）

61,87,512,500,907,170,888,275,653,466：

(4)快速排序：

1.

466,87,275,61,170,500,888,907,653,512；

；

Kruskal算法：4535142502(5分)(1+2+3+4+9=19)170,87,275,61,466,500,888,907,653,512

(5)基數(shù)排序：

Prim算法：0225453514(5分)(9+4+1+2+3=19)500,170,61,512,653,275,466,87,907,888：

500,907,512,653,61,466,170,275,87,888：

2.(1)

五、程序設(shè)計題(10分)。

(1)參考代碼(可以有所不同)

(ypcdcfstructnode*link;