數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9

數(shù)據(jù)結(jié)構(gòu)試卷（九）一、選擇題(30分)1．下列程序段的時(shí)間復(fù)雜度為（ ）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j] ；(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)i3．設(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+N34．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（）。(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í)間復(fù)雜度為O(n2)是（）。(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序7．設(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最好選擇（）。(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)710.設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（）條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/211.設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（）。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/212.設(shè)有序表中的元素為 (13，18，24，35，47，50，62)，則在其中利用二分法查找值為 24的元素需要經(jīng)過(guò)（ ）次比較。(A)1(B)2(C)3(D)413.設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（）。(A)6(B)11(C)5(D)6.514.設(shè)有向無(wú)環(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，315.設(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）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為 __________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才可以完成。5．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮應(yīng)最好選擇_________排序，如果從節(jié)省存儲(chǔ)空間的角度來(lái)考慮則最好選擇 ________排序。6．設(shè)一組初始記錄關(guān)鍵字序列為 (20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長(zhǎng)度是 _______________________________。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．設(shè)無(wú)向圖 G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為_________________。三、判斷題(20分)1．有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。 ( )2．對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。 ( )3．子串“ABC”在主串“AABCABCD”中的位置為 2。( )4．若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)， 則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。 ( )5．希爾排序算法的時(shí)間復(fù)雜度為 O(n2)。( )6．用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)， 則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無(wú)關(guān)而與圖中邊數(shù)有關(guān)。( )7．中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。 ( )8．入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。 ( )9．順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。 （ ）10． 堆是完全二叉樹，完全二叉樹不一定是堆。 （ ）五、算法設(shè)計(jì)題 (20分)1．設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。2．設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。3．設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案一、選擇題1．A2．A3．A4．C5．D6．D7．C8．B9．C10．A11．C12．C13．D14．A15．A二、填空題p->next，s->data50m-16，8快速，堆19/7CBDA6(24，65，33，80，70，56，48)8三、判斷題1．錯(cuò) 2．對(duì) 3．對(duì) 4．對(duì) 5．錯(cuò)6．錯(cuò) 7．對(duì) 8．對(duì) 9．錯(cuò) 10．對(duì)四、算法設(shè)計(jì)題1．設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之