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

數(shù)據(jù)結(jié)構(gòu)試卷（一）選擇題（每題2分，共20分）1.棧和隊列的共同特點是（A）。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點2.用鏈接方式存儲的隊列在進行插入運算時（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)表示用十進制表示。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é)點數(shù)最多為（D）。A.2k-1B.2K+1C.2K-1D.2k-17.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放在A[1]中，現(xiàn)進行二分查找，則查找A[3]的比較序列的下標依次為（C）。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，38.對n個記錄的文件進行快速排序所需要的輔助存儲空間大致為（D）。A.O(1)B.O(n)C.O(1og2n)D.O(n2)9.對線性表(7，34，55，25，64，46，20，10)進行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為1的元素有(C)個。A.1B.2C.3D.410.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（B）條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1分，共26分）1.通常從4個方面評價算法的質(zhì)量，即正確性、易讀性、強壯性和高效性。2.一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示_o（n）_。3.假定一棵樹的廣義表表示為A(C，D(E，F(xiàn)，G)，H(I，J))，則樹中所含的結(jié)點數(shù)為9個，樹的深度為3，樹的度為3。4.后綴算式923+-102/-的值為-1_。中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為34X*+2Y3/*-。5.若用鏈表存儲一棵二叉樹，每個結(jié)點除數(shù)據(jù)域外還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有2n個指針域，其中有n-1指針域存放了地址，有n+1個指針是空指針。6.對于一個有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中所含的邊結(jié)點分別為e個和2e個。7.AOV網(wǎng)是一種沒有回路的圖。8.在一個有n個頂點的無向完全圖中包含有_n(n-1)/2_條邊，在一個有n個頂點的有向完全圖中包含有_n(n-1)_條邊。9.假定一個線性表為(12,23,74,55,63,40)，若按key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的4個子表分別為_{12，40}_、_φ_、{74}_和_{23,55,63}_。10.在向一棵B-樹插入元素的過程中若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度_多1_。11.在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(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.已知一個圖的頂點集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é)點的單鏈表的頭指針

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é)點。

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

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

1

defABC(BT):

2

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

3

ifBTisnotNone:

4

ABC(BT.lchild)

5

ABC(BT.rchild)

6

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

1

defFind(BST,item):

2

#BST是搜索二叉樹的結(jié)點，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é)點的值等于給定值X的結(jié)點數(shù)。定義函數(shù)如下：defis_count(self,X): cur=self.__headcount=0whilecurisnotNone:ifcur.data==X: count+=1cur=cur.nextreturncount使用java改寫：publicintis_