數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9_第1頁
數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9_第2頁
數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9_第3頁
數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9_第4頁
數(shù)據(jù)結(jié)構(gòu)試卷與參考答案-9_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

數(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)過棧作用后,輸出序列中的第一個(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è)完全無向圖中有n個(gè)頂點(diǎn),則該完全無向圖中有()條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/211.設(shè)順序表的長度為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)過( )次比較。(A)1(B)2(C)3(D)413.設(shè)順序線性表的長度為30,分成5塊,每塊6個(gè)元素,如果采用分塊查找,則其平均查找長度為()。(A)6(B)11(C)5(D)6.514.設(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,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è)排序過程中最多需要進(jìn)行__________趟排序才可以完成。5.在堆排序和快速排序中,如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序,如果從節(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.設(shè)無向圖 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ù)無關(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)值之

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論