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

本文格式為Word版，下載可任意編輯——java數(shù)據(jù)結(jié)構(gòu)面試題數(shù)據(jù)結(jié)構(gòu)試題

一、選擇題(30分)

1.以下程序段的時(shí)間繁雜度為()。

(A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t)(D)O(m*t+n)

2.設(shè)依次線性表中有n個(gè)數(shù)據(jù)元素，那么刪除表中第i個(gè)元素需要移動(dòng)()個(gè)元素。

(A)n-i(B)n+l-i(C)n-1-i(D)i

3.設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，那么二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為()。

(A)N1-1(B)N2-1(C)N2+N3(D)N1+N3

4.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間繁雜度為()。

(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)

5.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向插入的結(jié)點(diǎn)X，那么在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。

(A)p-right=s;s-left=p;p-right-left=s;s-right=p-right;

(B)s-left=p;s-right=p-right;p-right=s;p-right-left=s;

(C)p-right=s;p-right-left=s;s-left=p;s-right=p-right;

(D)s-left=p;s-right=p-right;p-right-left=s;p-right=s;

6.以下各種排序算法中平均時(shí)間繁雜度為O(n2)是()。

(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序

7.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，那么輸出序列中的第i個(gè)輸出元素是()。

(A)n-i(B)n-1-i(C)n+l-i(D)不能確定

8.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，那么p最好選擇()。

(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)

(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)

9.設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有()個(gè)。

(A)4(B)5(C)6(D)7

10.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，那么該完全無向圖中有()條邊。

(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2

11.設(shè)依次表的長度為n，那么依次查找的平均對(duì)比次數(shù)為()。

(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2

12.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，那么在其中利用二分法查找值為24的元素需要經(jīng)過()次對(duì)比。

(A)1(B)2(C)3(D)4

13.設(shè)依次線性表的長度為30，分成5塊，每塊6個(gè)元素，假設(shè)采用分塊查找，那么其平均查找長度為()。

(A)6(B)11(C)5(D)6.5

14.設(shè)有向無環(huán)圖G中的有向邊集合E={1，2，2，3，3，4，1，4}，那么以下屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?)。

(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3

15.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，那么由這組記錄關(guān)鍵字生成的二叉排序樹的深度為()。

(A)4(B)5(C)6(D)7

二、填空題(30分)

1.設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向插入的結(jié)點(diǎn)X，那么在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：

1)s-next=___________;2)p-next=s;3)t=p-data;

4)p-data=___________;5)s-data=t;

2.設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，那么該二叉樹中有______________個(gè)葉子結(jié)點(diǎn)。

3.設(shè)某依次循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，那么該循環(huán)隊(duì)列中最多存儲(chǔ)_______隊(duì)列元素。

4.對(duì)一組初始關(guān)鍵字序列(40，50，95，20，15，70，60，45，10)舉行冒泡排序，那么第一趟需要舉行相鄰記錄的對(duì)比的次數(shù)為__________，在整個(gè)排序過程中最多需要舉行__________趟排序才可以完成。

5.在堆排序和快速排序中，假設(shè)從平均處境下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序，假設(shè)從節(jié)省存儲(chǔ)空間的角度來考慮那么最好選擇________排序。

6.設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，那么根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_______________________________。

7.設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，那么這棵二叉樹的前序序列為____________________。

8.設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中展現(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)值之和為_________________。

三、判斷題(20分)

1.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不確定相等。()

2.對(duì)鏈表舉行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。()

3.子串“ABC”在主串“AABCABCD”中的位置為2。()

4.若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的結(jié)果一個(gè)結(jié)點(diǎn)，那么它必是該二叉樹的先序遍歷序列中的結(jié)果一個(gè)結(jié)點(diǎn)。()

5.希爾排序算法的時(shí)間繁雜度為O(n2)。()

6.用鄰接矩陣作為圖的存儲(chǔ)布局時(shí)，那么其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。()

7.中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。()

8.入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)布局上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的處境。()

9.依次表查