數(shù)據(jù)結(jié)構(gòu)：Python語言描述期末試卷及答案5套

數(shù)據(jù)結(jié)構(gòu)試卷（一）選擇題（每題2分，共20分）1.棧和隊列的共同特點(diǎn)是（A）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)2.用鏈接方式存儲的隊列在進(jìn)行插入運(yùn)算時（D）。A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3.以下數(shù)據(jù)結(jié)構(gòu)中（D）是非線性結(jié)構(gòu)。A.隊列B.棧C.線性表D.二叉樹4.設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]的存放位置在644(10)，A[2][2]的存放位置在676(10)，每個元素占一個空間，那么A[3][3](10)存放在（C）位置。腳注(10)表示用十進(jìn)制表示。A.688B.678C.692D.6965.樹最適合用來表示（C）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（D）。A.2k-1B.2K+1C.2K-1D.2k-17.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放在A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為（C）。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，38.對n個記錄的文件進(jìn)行快速排序所需要的輔助存儲空間大致為（D）。A.O(1)B.O(n)C.O(1og2n)D.O(n2)9.對線性表(7，34，55，25，64，46，20，10)進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有(C)個。A.1B.2C.3D.410.設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（B）條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1分，共26分）1.通常從4個方面評價算法的質(zhì)量，即正確性、易讀性、強(qiáng)壯性和高效性。2.一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示_o（n）_。3.假定一棵樹的廣義表表示為A(C，D(E，F(xiàn)，G)，H(I，J))，則樹中所含的結(jié)點(diǎn)數(shù)為9個，樹的深度為3，樹的度為3。4.后綴算式923+-102/-的值為-1_。中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為34X*+2Y3/*-。5.若用鏈表存儲一棵二叉樹，每個結(jié)點(diǎn)除數(shù)據(jù)域外還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有2n個指針域，其中有n-1指針域存放了地址，有n+1個指針是空指針。6.對于一個有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中所含的邊結(jié)點(diǎn)分別為e個和2e個。7.AOV網(wǎng)是一種沒有回路的圖。8.在一個有n個頂點(diǎn)的無向完全圖中包含有_n(n-1)/2_條邊，在一個有n個頂點(diǎn)的有向完全圖中包含有_n(n-1)_條邊。9.假定一個線性表為(12,23,74,55,63,40)，若按key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的4個子表分別為_{12，40}_、_φ_、{74}_和_{23,55,63}_。10.在向一棵B-樹插入元素的過程中若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_多1_。11.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_o(log2n)__，整個堆排序過程的時間復(fù)雜度為_o(nlog2n)_。12.在快速排序、堆排序、歸并排序中歸并排序是穩(wěn)定的。三、計算題（每題6分，共24分）1.在如圖A.1所示的數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。圖A.1數(shù)組A線性表為：A[3]->A[2]->A[7]->A[1]->A[5]->A[4]->A[0]->A[3]2.請畫出圖A.2所示的鄰接矩陣和鄰接表。圖A.2無向圖鄰接矩陣：鄰接表：1234213531245413552343.已知一個圖的頂點(diǎn)集V和邊集E如下：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（0,3）2——（4,6）4——（0,2）5——（1,5）6——（0,1）8——（3,6）10——（5,7）20畫出向小根堆中加入數(shù)據(jù)4、2、5、8、3時每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）1.

1

defmynote(L):

2

#L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

3

ifLisnotNoneandL.nextisnotNone:

4

q=L

5

l=L.next

6

p=L

7

whilep.next:

8

p=p.next#S1

9

p.next=q

10

q.next=None

11

returnL請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,…,an),寫出算法執(zhí)行后的返回值所表示的線性表。答：(1)找到鏈表的最后一個節(jié)點(diǎn)。

(2)將鏈表的最后一個節(jié)點(diǎn)指向L，并將L的下一節(jié)點(diǎn)清空。

(3)a2,...,an,a1。2.

1

defABC(BT):

2

#BT是二叉樹的結(jié)點(diǎn)

3

ifBTisnotNone:

4

ABC(BT.lchild)

5

ABC(BT.rchild)

6

print(BT.data,end='')該算法的功能是_打印二叉樹各節(jié)點(diǎn)的值_。五、算法填空（共8分）二叉搜索樹的查找—遞歸算法:

1

defFind(BST,item):

2

#BST是搜索二叉樹的結(jié)點(diǎn)，item是查找的元素

3

ifBSTisNone:

4

returnfalse#查找失敗

5

ifitem==BST.data:

6

item=BST.data#查找成功

7

returntrue

8

elifitem<BST.data:

9

returnFind(BST->left,item)

10

else:

11

returnFind(BST->right,item)六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。定義函數(shù)如下：defis_count(self,X): cur=self.__headcount=0whilecurisnotNone:ifcur.data==X: count+=1cur=cur.nextreturncount數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題（每題3分，共24分）1.下面關(guān)于線性表的敘述錯誤的是（D）。A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C.線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（B）個空指針域。A.2m-1B.2mC.2m+1D.4m3.設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（C）。A.R-FB.F-RC.(R-F+M)％MD.(F-R+M)％M4.設(shè)某棵二叉樹的中序遍歷序列為ABCD、前序遍歷序列為CABD，則后序遍歷該二叉樹得到的序列為（A）。A.BADCB.BCDAC.CDABD.CBDA5.設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有(A)條邊。A.n(n-1)/2B.n(n-1)C.n2D.n2-16.設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為(C)。A.9B.10C.11D.127.設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（B）個表頭結(jié)點(diǎn)。A.n-1B.nC.n+1D.2n-18.設(shè)有一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8二、填空題(每空2分，共24分)1.為了能有效地應(yīng)用Hash查找技術(shù)，必須解決的兩個問題是___如何構(gòu)造哈希函數(shù)和如何解決沖突。2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下畫線處填上正確的語句。

1

classSqStack:

2

def__init__(self):

3

self.data=[None]*100

4

self.top=0

5

#......

6

7

#......

8

9

defpush(self,x):

10

ifself.top==100:

11

raise('overflow')

12

else:

13

__self.data[top]=x____

14

___top=top+1___3.中序遍歷二叉排序樹所得到的序列是____有序____序列(填有序或無序)。4.快速排序的最壞時間復(fù)雜度為___O(n2)_____，平均時間復(fù)雜度為___O(nlogn)_____。5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為____N0-1___；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有____N1+2N0____個空指針域。6.設(shè)某無向圖中的頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=____d/2____。7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為____大根堆：（80，75，55，56，63，44，31，38）小根堆：（31，38，44，56，75，80，55，63）____。8.已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖A.3所示，從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是_____1，3，4，5，2___，BFS遍歷的輸出序列是____1，3，2，4，5____。圖A.3圖的鄰接表存儲結(jié)構(gòu)三、應(yīng)用題(每題6分，共36分)1.設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。答：簡單選擇排序：22，40，45，48，80，78 直接插入排序：40，45，48，80，22，782.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink)。答：q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。答：比較次數(shù)2，平均查找長度25/9圖A.4無向圖G4.設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。答：5.設(shè)有如圖A.4所示的無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。答：{(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。答：構(gòu)造過程如下：插入過程：若二叉排序樹為空，則待插入結(jié)點(diǎn)*S作為根結(jié)點(diǎn)插入到空樹中；當(dāng)非空時，將待插結(jié)點(diǎn)關(guān)鍵字S->key和樹根關(guān)鍵字t->key進(jìn)行比較，若s->key=t->key,則無須插入，若s->key<t->key,則插入到根的左子樹中，若s->key>t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，如此進(jìn)行下去，直到把結(jié)點(diǎn)*s作為一個新的樹葉插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹已有相同關(guān)鍵字的結(jié)點(diǎn)為止。構(gòu)造結(jié)果：四、算法設(shè)計題(每題8分，共16分)1.設(shè)有一組初始記錄關(guān)鍵字序列(K1，K2，…，Kn)，要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。

1

defquicksort(list,i,n):

2

left=i

3

right=n

4

temp=list[i]

5

whileleft<right:

6

whileleft<rightandlist[right]>temp:

7

right=right-1

8

ifleft<right:

9

list[left]=list[right]

10

left=left+1

11

whileleft<rightandlist[left]<temp:

12

left=left+1

13

ifleft<right:

14

list[right]=list[left]

15

right=right-1

16

list[left]=temp2.設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。

1

classNode():

2

i=0

3

def_init_(self,data):

4

self.data=data

5

self.next=None

6

Node.i+=1

7

8

defandOperation(a,b,c):

9

p=a

10

c=None

11

whilep!=None:

12

q=b

13

whileq!=None:

14

ifp.data==q.data:

15

break

16

q=q.next

17

ifq!=None:

18

t=Node(p.data)

19

t.next=c

20

c=t

21

p=p.next數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(每題2分，共20分)1.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是(B)。A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.物理結(jié)構(gòu)D.圖形結(jié)構(gòu)2.下面程序的時間復(fù)雜度為(B)。

1

i=1

2

s=0

3

whilei<=n:

4

i+=1

5

t=1

6

forjinrange(1,i):

7

t=t*j

8

s=s+tA.O(n)B.O(n2)C.O(n3)D.O(n4)3.設(shè)指針變量p指向單鏈表中的結(jié)點(diǎn)A，若刪除單鏈表中的結(jié)點(diǎn)A，則需要修改指針的操作序列為(A)。A.q=p.next；p.data=q.data；p.next=q.next；B.q=p.next；q.data=p.data；p.next=q.next；C.q=p.next；p.next=q.next；D.q=p.next；p.data=q.data；4.設(shè)有n個待排序的記錄關(guān)鍵字，在堆排序中需要(A)個輔助記錄單元。A.1B.nC.nlog2nD.n25.設(shè)一組記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(A)。A.10，15，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，21D.15，10，14，18，20，36，40，216.設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則二叉排序樹的平均查找長度為(B)。A.O(1)B.O(log2n)C.O（n）D.O(n2)7.設(shè)無向圖G中有n個頂點(diǎn)、e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為(D)。A.n、eB.e、nC.2n、eD.n、2e8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有(C)條邊。A.n(n-1)B.n+1C.nD.n(n+1)9.設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列(B)方法可以達(dá)到此目的。A.快速排序B.堆排序C.歸并排序D.插入排序10.下列4種排序中(D)的空間復(fù)雜度最大。A.插入排序B.冒泡排序C.堆排序D.歸并排序二、填空題(每空1分，共20分)1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種情況。2.設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，則該二叉樹的深度為____9_____；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有_____501____個空指針域。3.設(shè)輸入序列為（1，2，3），則經(jīng)過棧的作用后可以得到___5______種不同的輸出序列。4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上的所有元素之和等于頂點(diǎn)i的_____出度____，第i列上的所有元素之和等于頂點(diǎn)i的___入度______。5.設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，則該哈夫曼樹中有____0_____個度數(shù)為1的結(jié)點(diǎn)。6.設(shè)有向圖G中有n個頂點(diǎn)、e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為____e=d_____。7.____中序_____遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8.設(shè)查找表中有100個元素，如果用二分查找方法查找數(shù)據(jù)元素X，則最多需要比較_____7____次就可以斷定數(shù)據(jù)元素X是否在查找表中。9.不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為___O(1)______。10.設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為___i/2(向下取整)______，右孩子結(jié)點(diǎn)的編號為___2*i+1______。11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序的結(jié)果為___5167123729473______。12.設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開__1423______。13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字的功能，請在下畫線處填上正確的語句。

1

classrecord(object):

2

def__init__(self,key,others):

3

self.key=key

4

self.others=others

5

6

defhashSqSearch(hashTable,k):

7

i=j=k%P

8

whilehashTable[j].key!=kandhashTable[j].flag!=0:

9

j=___j+1___%m

10

ifi==j:

11

return-1

12

if_hashtable[j].key==__k___:

13

returnj

14

elsereturn-114.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k的功能，請在下畫線處填上正確的語句。

1

defFind(BST,k):

2

#BST是搜索二叉樹的結(jié)點(diǎn)，k是查找的元素

3

ifBSTisNone:

4

returnfalse#查找失敗

5

ifk==BST.data:

6

k=BST.data#查找成功

7

return_true_____

8

elifitem<BST.data:

9

returnFind(__BST.lchild____,k)

10

else:

11

returnFind(__BST.rchild____,k)三、計算題(每題10分，共30分)1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ、中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2.已知待散列的線性表為(36，15，40，63，22)，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H(K)=Kmod7，若發(fā)生沖突采用線性探查法處理，試計算以下問題：(1)計算出每一個元素的散列地址并在圖A.5中填寫出散列表。圖A.5填寫散列表01234566336152240(2)求出在查找每一個元素概率相等情況下的平均查找長度。(1+2+1+1+3)/5=1.6。3.已知序列(10，18，4，3，6，12，1，9，18，8)，請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。第一趟排序結(jié)果：9436110121818第二趟排序結(jié)果：1436910121818第三趟排序結(jié)果：1436910121818第四趟排序結(jié)果：1346910121818四、算法設(shè)計題(每題15分，共30分)1.設(shè)計在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。class

Node:

def

__init__(self,

data=None,

nxt=None):

self.data

=

data

self.next

=

nxt

def

delete_same_node(node):

p

=

node

if

p

is

None:

return

elif

p.next

is

None:

return

else:

q

=

node.next

while

q!=None:

if

p.data==q.data:

p.next

=

q.next

p

=

q

q

=

q.next

else:

p

=

p.next

q

=

q.next

return

2.設(shè)計一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。class

TreeNode:

def

__init__(self,

data=None,

lchild=None,

rchild=None):

self.data

=

data

self.lchild

=

lchild

self.rchild

=

rchild

def

find_parent(root,

target):

if

root

is

None:

return

None

elif

root.lchild

is

target

or

root.rchild

is

target:

return

root

elif

root.lchild

is

None

and

root.rchild

is

None:

return

None

else:

return

find_parent(root.lchild,

target)

or

find_parent(root.rchild,

target)

數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題（每題2分，共20分）1.設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為(C)。A.O(n)B.O(nlog2n)C.O(1)D.O(n2)2.設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有(D)個結(jié)點(diǎn)。A.2k-1B.2kC.2k-1D.2k-13.設(shè)某無向圖中有n個頂點(diǎn)、e條邊，則該無向圖中所有頂點(diǎn)的入度之和為(D)。A.nB.eC.2nD.2e4.在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為(C)。A.O(1)B.O(n)C.O(log2n)D.O(n2)5.設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有(C)條有向邊。A.nB.n-1C.mD.m-16.設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行(A)趟的分配和回收才能使初始關(guān)鍵字序列變成有序序列。A.3B.4C.5D.87.設(shè)用鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作(B)。A.必須判別棧是否為滿B.必須判別棧是否為空C.判別棧元素的類型D.對棧不做任何判別8.下列4種排序中(D)的空間復(fù)雜度最大。A.快速排序B.冒泡排序C.希爾排序D.堆9.設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是(C)。A.N0=N1+1B.N0=N1+N2C.N0=N2+1D.N0=2N1+110.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(A)。A.log2n+1B.log2n-1C.log2nD.log2(n+1)二、填空題（除第2題2分外每空1分，共20分）1.設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為O(n2)，快速排序的平均時間復(fù)雜度為O(nlog2n)。2.設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為p->llink->rlink=p->rlink;p->rlink->llink=p->llink;(設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink)。3.根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為3。4.深度為k的完全二叉樹中最少有2k-1個結(jié)點(diǎn)。5.設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從[n/2]第個元素開始進(jìn)行篩選。6.設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有50個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有100個空指針域。7.設(shè)一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲M-1個隊列元素；當(dāng)前實(shí)際存儲(R–F+M)%M個隊列元素(設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針R指向當(dāng)前隊尾元素的位置)。8.設(shè)順序線性表中有n個數(shù)據(jù)元素，則在第i個位置上插入一個數(shù)據(jù)元素需要移動表中的n-i+1個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中的n–i個元素。9.設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序的結(jié)果為(18,16,19,20,22,30)。10.設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為(16,18,19,20,30,22)。11.設(shè)某無向圖G中有n個頂點(diǎn)，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是A[i][j]=A[j][i]=1。12.設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i行上非0元素的個數(shù)等于第i列上非0元素的個數(shù)(填等于、大于或小于)。13.設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為BDCA。14.設(shè)散列函數(shù)H(k)=kmodp，解決沖突的方法為鏈地址法。要求在下列算法畫線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。

1

classNode(object):

2

def__init__(self,key=None,next=None):

3

self.key=key

4

self.next=next

5

6

defcreatelkHash(hashTable):

7

foriinrange(m):

8

hashTable[i]=0

9

foriinrange(n):

10

s=Node()

11

s.key=a[i]

12

k=a[i]%P

13

s.next=hashTable[k]

14

hashTable[k]=s三、計算題(每題10分，共30分)1.畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。2.設(shè)有如圖A.6所示的森林：(1)求樹(a)的先根序列和后根序列；ABCDEFBDEFCA(2)求森林的先序序列和中序序列；ABCDEFGHIJKBDEFCAIJKHG(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹。圖A.6森林圖3.設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為H(key)=(key2+2)mod9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計題(每題10分，共30分)1.設(shè)單鏈表中僅有3類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其他字符)，要求利用原單鏈表中的結(jié)點(diǎn)空間設(shè)計出3個單鏈表的算法，使每個單鏈表只包含同類字符。import

random

import

string

class

Node:

def

__init__(self,

data=None,

nxt=None):

self.data

=

data

self.next

=

nxt

def

print_list(head):

list_data

=

[]

while

head

is

not

None:

list_data.append(head.data)

head

=

head.next

print(list_data)

head_all

=

None

tail_all

=

None

for

_

in

range(20):

node

=

Node(random.choice([

random.choice(string.ascii_uppercase),

random.choice(string.digits),

random.choice(list(set(string.printable)

-

set(string.ascii_uppercase)

-

set(string.digits))),

]))

if

tail_all

is

None:

head_all

=

tail_all

=

node

else:

tail_all.next

=

node

tail_all

=

node

print('all:

',

end='')

print_list(head_all)

head_upper

=

None

tail_upper

=

None

head_digit

=

None

tail_digit

=

None

head_other

=

None

tail_other

=

None

while

head_all

is

not

None:

node

=

head_all

head_all

=

node.next

node.next

=

None

if

node.data.isupper():

if

tail_upper

is

None:

head_upper

=

tail_upper

=

node

else:

tail_upper.next

=

node

tail_upper

=

node

elif

node.data.isdigit():

if

tail_digit

is

None:

head_digit

=

tail_digit

=

node

else:

tail_digit.next

=

node

tail_digit

=

node

else:

if

tail_other

is

None:

head_other

=

tail_other

=

node

else:

tail_other.next

=

node

tail_other

=

node

print('upper:

',

end='')

print_list(head_upper)

print('digit:

',

end='')

print_list(head_digit)

print('other:

',

end='')

print_list(head_other)

2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左、右子樹的算法。import

random

class

Node:

id_counter

=

0

def

__init__(self):

self.id

=

Node.id_counter

Node.id_counter

+=

1

self.left

=

self.right

=

None

def

print(self):

print(f'id:

{self.id},

left:

{self.left

and

self.left.id},

right:

{self.right

and

self.right.id}')

if

self.left

is

not

None:

self.left.print()

if

self.right

is

not

None:

self.right.print()

def

swap_children(self):

if

self.left

is

not

None:

self.left.swap_children()

if

self.right

is

not

None:

self.right.swap_children()

self.left,

self.right

=

self.right,

self.left

def

build_random_tree(depth=1):

node

=

Node()

if

depth

<

5:

if

bool(random.getrandbits(1)):

node.left

=

build_random_tree(depth

+

1)

if

bool(random.getrandbits(1)):

node.right

=

build_random_tree(depth

+

1)

return

node

root

=

build_random_tree()

print("original:")

root.print()

root.swap_children()

print("swapped:")

root.print()

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。import

random

class

Node:

def

__init__(self,

key):

self.key

=

key

self.left

=

self.right

=

None

def

to_list(self):

ret

=

[]

if

self.left

is

not

None:

ret.extend(self.left.to_list())

ret.append(self.key)

if

self.right

is

not

None:

ret.extend(self.right.to_list())

return

ret

def

insert(self,

key):

if

key

<

self.key:

if

self.left

is

None:

self.left

=

Node(key)

else:

self.left.insert(key)

else:

if

self.right

is

None:

self.right

=

Node(key)

else:

self.right.insert(key)

data

=

[random.randrange(0,

100)

for

_

in

range(10)]

print(f'orig:

{data}')

root

=

None

for

x

in

data:

if

root

is

None:

root

=

Node(x)

else:

root.insert(x)

print(f'bst:

{root.to_list()}')

數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題（每題2分，共20分）1.數(shù)據(jù)的最小單位是(A)。A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量2.設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為(B)。A.40，50，20，95B.15，40，60，20C.15，20，40，45D.45，40，15，203.設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為(A)。A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，854.函數(shù)substr("DATASTRUCTURE"，5，9)的返回值為(A)。A."STRUCTURE"B."DATA"C."ASTRUCTUR"D."DATASTRUCTURE"5.設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為(D)。A.O(log2n)B.O(1)C.O(n2)D.O(n)6.設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，…，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=(B)。A.N1+N2+…+NmB.1+N2+2N3+3N4+…+(m-1)NmC.N2+2N3+3N4+…+(m-1)NmD.2N1+3N2+…+(m+1)Nm7.設(shè)有序表中有1000個元素，則用二分查找法查找元素X最多需要比較(B)次。A.25B.10C.7D.18.設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為(B)。A.abedfcB.acfebdC.aebdfcD.aedfcb9.設(shè)輸入序列是（1，2，3，…，n），經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中的第i個輸出元素是(C)。A.n-IB.n-1-IC.n+1-ID.不能確定10.設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)得到的一趟快速排序的結(jié)果是(C)。A.40，42，45，55，80，83B.42，40，45，80，85，88C.42，40，45，55，80，85D.42，40，45，85，55，80二、填空題（除第1、2、8題2分外每空1分，共20分）1.設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧頂指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是__top1+1=top2__。2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是_可以隨機(jī)訪問到任一個頂點(diǎn)的簡單鏈表_。3.設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上的元素)存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_i*（i+1)/2+j-1__個數(shù)據(jù)元素。4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為FILO表；隊列的插入和刪除運(yùn)算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為_FIFO表。5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中的存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_ABDECF_、中序遍歷序列為_DBEAFC_、后序遍歷序列為_DEBFCA_。6.設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為_8_，有_64_個葉子結(jié)點(diǎn)。7.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中的所有非零元素個數(shù)之和等于頂點(diǎn)i的_出度_，第i列中的所有非零元素個數(shù)之和等于頂點(diǎn)i的_入度_。8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，…，kn)是堆，則對i=1、2、…、n/2而言滿足的條件為_ki<=k2iandk<=k2i+1_。9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請在下畫線處填上正確的語句。

1

defbubbleSort(sqlist):

2

flag=True

3

i=1

4

whilei<sqlist.lenandflag:

5

flag=False

6

forjinrange(_n-i_):

7

ifsqlist.list[j+1].key<sqlist.list[j].key:

8

p=sqlist.list[j]

9

r[j+1]=r[j]

10

sqlist.list[j+1]=p

11

flag=True

12

i+=110.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請在下畫線處填上正確的語句。

1

classrecord(object):

2

def__init__(self,key=None,other=None):

3

self.key=key

4

self.other=other

5

6

defbisearch(r,k):

7

low=0

8

high=len(r)-1

9

whilelow<=high:

10

_mid=(low+high)/2_

11

ifr[mid].key==k:

12

returnmid+1

13

elifr[mid].key>k:

14

high=mid-1

15

else:

16

low=mid+1

17

return-1三、應(yīng)用題（每題8分，共32分）1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC、前序遍歷序列為ABDEC，要求給出該二叉樹的后序遍歷序列。答：DEBCA2.設(shè)有無向圖G(如圖A.7所示)，給出該圖的最小生成樹上邊的集合，并計算最小生成樹各邊上的權(quán)值之和。圖A.7無向圖G答：E={(1,5),(5,2),(5,3),(3,4)},W=10設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。答：ASL=(1*1+2*2+3*4)/7=17/7;設(shè)散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。答：ASL1=7/6,ASL2=4/3四、算法設(shè)計題（每題14分，共28分）1.設(shè)計判斷兩個二叉樹是否相同的算法。

1

Defjudge(nodenod1,nodenod2):

2

Ifnod1==NULLandnod2==NULL:3returnTrue;

4

Elifnod1==NULLornod2==NULLornod1.data!=nod2.data:5returnFalse;

4

Else:

5

Ifjudge(nod1.lchild,nod2.lchild)andjudge(nod1.rchild,nod2.rchild):

6

ReturnTrue;

7

Else:

8

ReturnFalse2.設(shè)計兩個有序單鏈表的合并排序算法。

1

Defmerge(lklistl1,lklistl2):

2

lklistout=lklist()3While!l1.isempty()and!l2.isempty():

4

Ifl1.front()<l2.front():5out.append(l1.front())

4

l1.pop_front()

5

Else:

6

out.append(l2.front())

7

l2.pop_front()

8

If!l1.isempty():9Foriteminl1:10out.append(item)11

If!l2.isempty():12Foriteminl2:13out.append(item)14Returnout數(shù)據(jù)結(jié)構(gòu)試卷（一）選擇題（每題2分，共20分）1.棧和隊列的共同特點(diǎn)是（A）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)2.用鏈接方式存儲的隊列在進(jìn)行插入運(yùn)算時（D）。A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3.以下數(shù)據(jù)結(jié)構(gòu)中（D）是非線性結(jié)構(gòu)。A.隊列B.棧C.線性表D.二叉樹4.設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]的存放位置在644(10)，A[2][2]的存放位置在676(10)，每個元素占一個空間，那么A[3][3](10)存放在（C）位置。腳注(10)表示用十進(jìn)制表示。A.688B.678C.692D.6965.樹最適合用來表示（C）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（D）。A.2k-1B.2K+1C.2K-1D.2k-17.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放在A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為（C）。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，38.對n個記錄的文件進(jìn)行快速排序所需要的輔助存儲空間大致為（D）。A.O(1)B.O(n)C.O(1og2n)D.O(n2)9.對線性表(7，34，55，25，64，46，20，10)進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有(C)個。A.1B.2C.3D.410.設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（B）條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1分，共26分）1.通常從4個方面評價算法的質(zhì)量，即正確性、易讀性、強(qiáng)壯性和高效性。2.一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示_o（n）_。3.假定一棵樹的廣義表表示為A(C，D(E，F(xiàn)，G)，H(I，J))，則樹中所含的結(jié)點(diǎn)數(shù)為9個，樹的深度為3，樹的度為3。4.后綴算式923+-102/-的值為-1_。中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為34X*+2Y3/*-。5.若用鏈表存儲一棵二叉樹，每個結(jié)點(diǎn)除數(shù)據(jù)域外還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有2n個指針域，其中有n-1指針域存放了地址，有n+1個指針是空指針。6.對于一個有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中所含的邊結(jié)點(diǎn)分別為e個和2e個。7.AOV網(wǎng)是一種沒有回路的圖。8.在一個有n個頂點(diǎn)的無向完全圖中包含有_n(n-1)/2_條邊，在一個有n個頂點(diǎn)的有向完全圖中包含有_n(n-1)_條邊。9.假定一個線性表為(12,23,74,55,63,40)，若按key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的4個子表分別為_{12，40}_、_φ_、{74}_和_{23,55,63}_。10.在向一棵B-樹插入元素的過程中若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_多1_。11.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_o(log2n)__，整個堆排序過程的時間復(fù)雜度為_o(nlog2n)_。12.在快速排序、堆排序、歸并排序中歸并排序是穩(wěn)定的。三、計算題（每題6分，共24分）1.在如圖A.1所示的數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。圖A.1數(shù)組A線性表為：A[3]->A[2]->A[7]->A[1]->A[5]->A[4]->A[0]->A[3]2.請畫出圖A.2所示的鄰接矩陣和鄰接表。圖A.2無向圖鄰接矩陣：鄰接表：1234213531245413552343.已知一個圖的頂點(diǎn)集V和邊集E如下：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（0,3）2——（4,6）4——（0,2）5——（1,5）6——（0,1）8——（3,6）10——（5,7）20畫出向小根堆中加入數(shù)據(jù)4、2、5、8、3時每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）1.

1

defmynote(L):

2

#L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

3

ifLisnotNoneandL.nextisnotNone:

4

q=L

5

l=L.next

6

p=L

7

whilep.next:

8

p=p.next#S1

9

p.next=q

10

q.next=None

11

returnL請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,…,an),寫出算法執(zhí)行后的返回值所表示的線性表。答：(1)找到鏈表的最后一個節(jié)點(diǎn)。

(2)將鏈表的最后一個節(jié)點(diǎn)指向L，并將L的下一節(jié)點(diǎn)清空。

(3)a2,...,an,a1。2.

1

defABC(BT):

2

#BT是二叉樹的結(jié)點(diǎn)

3

ifBTisnotNone:

4

ABC(BT.lchild)

5

ABC(BT.rchild)

6

print(BT.data,end='')該算法的功能是_打印二叉樹各節(jié)點(diǎn)的值_。五、算法填空（共8分）二叉搜索樹的查找—遞歸算法:

1

defFind(BST,item):

2

#BST是搜索二叉樹的結(jié)點(diǎn)，item是查找的元素

3

ifBSTisNone:

4

returnfalse#查找失敗

5

ifitem==BST.data:

6

item=BST.data#查找成功

7

returntrue

8

elifitem<BST.data:

9

returnFind(BST->left,item)

10

else:

11

returnFind(BST->right,item)六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。定義函數(shù)如下：defis_count(self,X): cur=self.__headcount=0whilecurisnotNone:ifcur.data==X: count+=1cur=cur.nextreturncount數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題（每題3分，共24分）1.下面關(guān)于線性表的敘述錯誤的是（D）。A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C.線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（B）個空指針域。A.2m-1B.2mC.2m+1D.4m3.設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（C）。A.R-FB.F-RC.(R-F+M)％MD.(F-R+M)％M4.設(shè)某棵二叉樹的中序遍歷序列為ABCD、前序遍歷序列為CABD，則后序遍歷該二叉樹得到的序列為（A）。A.BADCB.BCDAC.CDABD.CBDA5.設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有(A)條邊。A.n(n-1)/2B.n(n-1)C.n2D.n2-16.設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為(C)。A.9B.10C.11D.127.設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（B）個表頭結(jié)點(diǎn)。A.n-1B.nC.n+1D.2n-18.設(shè)有一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8二、填空題(每空2分，共24分)1.為了能有效地應(yīng)用Hash查找技術(shù)，必須解決的兩個問題是___如何構(gòu)造哈希函數(shù)和如何解決沖突。2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下畫線處填上正確的語句。

1

classSqStack:

2

def__init__(self):

3

self.data=[None]*100

4

self.top=0

5

#......

6

7

#......

8

9

defpush(self,x):

10

ifself.top==100:

11

raise('overflow')

12

else:

13

__self.data[top]=x____

14

___top=top+1___3.中序遍歷二叉排序樹所得到的序列是____有序____序列(填有序或無序)。4.快速排序的最壞時間復(fù)雜度為___O(n2)_____，平均時間復(fù)雜度為___O(nlogn)_____。5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為____N0-1___；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有____N1+2N0____個空指針域。6.設(shè)某無向圖中的頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=____d/2____。7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為____大根堆：（80，75，55，56，63，44，31，38）小根堆：（31，38，44，56，75，80，55，63）____。8.已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖A.3所示，從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是_____1，3，4，5，2___，BFS遍歷的輸出序列是____1，3，2，4，5____。圖A.3圖的鄰接表存儲結(jié)構(gòu)三、應(yīng)用題(每題6分，共36分)1.設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。答：簡單選擇排序：22，40，45，48，80，78 直接插入排序：40，45，48，80，22，782.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink)。答：q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。答：比較次數(shù)2，平均查找長度25/9圖A.4無向圖G4.設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。答：5.設(shè)有如圖A.4所示的無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。答：{(1，3)，(1，2)，(3，5)，(5，6)