2018年數(shù)據(jù)結(jié)構(gòu)試題

1、20182018年數(shù)據(jù)結(jié)構(gòu)試題數(shù)據(jù)結(jié)構(gòu)試題一、選擇題一、選擇題(30(30分)1.下列程序段的時間復(fù)雜度為()。(A)O(mnt)(B)O(mnt)(C)O(mnt)(D)O(mtn)2.設(shè)順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動()個元素。(A)ni(B)nli(C)n1i(D)i3.設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子

2、樹的結(jié)點數(shù)為()。(A)N11(B)N21(C)N2N3(D)N1N34.利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)5.設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為()。(A)pright=ssleft=pprightleft=ssright=pright(B)sleft=psright

3、=prightpright=sprightleft=s(C)pright=sprightleft=ssleft=psright=pright(D)sleft=psright=prightprightleft=spright=s6.下列各種排序算法中平均時間復(fù)雜度為O(n2)是()。(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序7.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是

4、()。(A)ni(B)n1i(C)nli(D)不能確定8.設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇()。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素數(shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)9.設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有()個。5.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)

5、最好選擇_________排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。6.設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。7.設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。8.設(shè)用于通信的電文僅

6、由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。9.設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。10.10.設(shè)無向圖G(如右圖所示)，則其最小生成樹上所有邊的權(quán)值之和為_________________。三、判斷題三、

7、判斷題(20(20分)1.有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。()2.對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點。()3.子串“ABC”在主串“AABCABCD”中的位置為2。()4.若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。()5.希爾排序算法的時間復(fù)雜度為O(n2)。()6.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。