數(shù)據(jù)結(jié)構(gòu)（Java語言版）模擬試卷1（含參考答案）

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

(2)將鏈表的最后一個(gè)節(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)計(jì)出單鏈表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使用java改寫：publicintis_