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

【數(shù)據(jù)結(jié)構(gòu)試題】java數(shù)據(jù)結(jié)構(gòu)面試題一、選擇題(30分)以下程序段的時(shí)間復(fù)雜度為( )。(A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t)(D)O(m*t+n)設(shè)次序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要挪動(dòng)( )個(gè)元素。(A)n-i(B)n+l-i(C)n-1-i(D)i3.設(shè)F是由T1、T2和T3三棵樹(shù)構(gòu)成的叢林，與F對(duì)應(yīng)的二叉樹(shù)為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為( )。(A)N1-1(B)N2-1(C)N2+N3(D)N1+N3利用直接插入排序法的思想成立一個(gè)有序線性表的時(shí)間復(fù)雜度為( )。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后邊插入結(jié)點(diǎn)X的操作序列為( )。p->right=s;s->left=p;p->right->left=s;s->right=p->right;s->left=p;s->right=p->right;p->right=s;p->right->left=s;p->right=s;p->right->left=s;s->left=p;s->right=p->right;s->left=p;s->right=p->right;p->right->left=s;p->right=s;以下各樣排序算法中均勻時(shí)間復(fù)雜度為O(n2)是( )。迅速排序(B)堆排序(C)合并排序(D)冒泡排序設(shè)輸入序列1、2、3、、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(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最好選擇( )。小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)9.設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)1有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有( )個(gè)。4(B)5(C)6(D)7設(shè)完整無(wú)向圖中有n個(gè)極點(diǎn)，則該完整無(wú)向圖中有( )條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2設(shè)次序表的長(zhǎng)度為n，則次序查找的均勻比較次數(shù)為( )。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在此中利用二分法查找值為24的元素需要經(jīng)過(guò)( )次比較。(A)1(B)2(C)3(D)4設(shè)次序線性表的長(zhǎng)度為30，分紅5塊，每塊6個(gè)元素，假如采納分塊查找，則其均勻查找長(zhǎng)度為( )。(A)6(B)11(C)5(D)6.5設(shè)有向無(wú)環(huán)圖G中的有向邊會(huì)合E={，，，}，則以下屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖? )。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3設(shè)有一組初始記錄重點(diǎn)字序列為(34，76，45，18，26，54，92)，則由這組記錄重點(diǎn)字生成的二叉排序樹(shù)的深度為( )。(A)4(B)5(C)6(D)7二、填空題(30分)設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：s->next=___________;2)p->next=s;3)t=p->data;p->data=___________;5)s->data=t;設(shè)某棵完整二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結(jié)點(diǎn)。設(shè)某次序循環(huán)行列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)地點(diǎn)，隊(duì)尾指針R指向隊(duì)尾元素的目前地點(diǎn)，則該循環(huán)行列中最多儲(chǔ)存_______行列元素。對(duì)一組初始重點(diǎn)字序列(40，50，95，20，15，70，60，45，10)進(jìn)行冒泡2排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_(kāi)_________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才能夠達(dá)成。在堆排序和迅速排序中，假如從均勻狀況下排序的速度最快的角度來(lái)考慮應(yīng)最好選擇_________排序，假如從節(jié)儉儲(chǔ)存空間的角度來(lái)考慮則最好選擇________排序。設(shè)一組初始記錄重點(diǎn)字序列為(20，12，42，31，18，14，28)，則依據(jù)這些記錄重點(diǎn)字結(jié)構(gòu)的二叉排序樹(shù)的均勻查找長(zhǎng)度是。設(shè)一棵二叉樹(shù)的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹(shù)的前序序列為_(kāi)___________________。設(shè)用于通訊的電文僅由8個(gè)字母構(gòu)成，字母在電文中出現(xiàn)的頻次分別為7、19、2、6、32、3、21、10，依據(jù)這些頻次作為權(quán)值結(jié)構(gòu)哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為_(kāi)_______________。設(shè)一組記錄重點(diǎn)字序列為(80，70，33，65，24，56，48)，則用挑選法建成的初始堆為_(kāi)______________________。10.設(shè)無(wú)向圖G(如右圖所示)，則其最小生成樹(shù)上全部邊的權(quán)值之和為_(kāi)________________。三、判斷題(20分)有向圖的毗鄰表和逆毗鄰表中表結(jié)點(diǎn)的個(gè)數(shù)不必定相等。( )對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不用挪動(dòng)鏈表中結(jié)點(diǎn)。( )子串“ABC”在主串“AABCABCD”中的地點(diǎn)為2。( )若一個(gè)葉子結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( )希爾排序算法的時(shí)間復(fù)雜度為O(n2)。( )用毗鄰矩陣作為圖的儲(chǔ)存結(jié)構(gòu)時(shí)，則其所占用的儲(chǔ)存空間與圖中極點(diǎn)數(shù)沒(méi)關(guān)而與圖中邊數(shù)相關(guān)。( )中序遍歷一棵二叉排序樹(shù)能夠獲得一個(gè)有序的序列。( )入棧操作和入行列操作在鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧