《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (4)_第1頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (4)_第2頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (4)_第3頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (4)_第4頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (4)_第5頁(yè)
全文預(yù)覽已結(jié)束

付費(fèi)下載

下載本文檔

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

文檔簡(jiǎn)介

1、數(shù)據(jù)結(jié)構(gòu)模擬試題04一、單項(xiàng)選擇題(每題 2 分,共20分)1組成數(shù)據(jù)的基本單位是( )。 (A) 數(shù)據(jù)項(xiàng)(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D=1,2,3,4,R=r,r=<1,2>,<2,3>,<3,4>,<4,1>,則數(shù)據(jù)結(jié)構(gòu)A是( )。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu) (C) 圖型結(jié)構(gòu)(D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列( )的邏輯結(jié)構(gòu)。(A) 線性表(B) 棧 (C) 隊(duì)列(D) 樹4二叉樹中第i(i1)層上的結(jié)點(diǎn)數(shù)最多有( )個(gè)。(A) 2i(B) 2i(C) 2i-1(D) 2i-15設(shè)

2、指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為( )。(A) p->next=p->next->next(B) p=p->next(C) p=p->next->next(D) p->next=p6設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素E1、E2、E3、E4、E5和E6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是( )。(A) 6(B) 4(C) 3(D) 27將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中,則數(shù)組A的長(zhǎng)度最少為( )。(A) 100(B) 40(C) 5

3、5(D) 808設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn),則結(jié)點(diǎn)B的度數(shù)數(shù)為( )。(A) 3(B) 4(C) 5(D) 19根據(jù)二叉樹的定義可知二叉樹共有( )種不同的形態(tài)。(A) 4(B) 5(C) 6(D) 710. 設(shè)有以下四種排序方法,則( )的空間復(fù)雜度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希爾排序二、填空題(每題2分,共20分)1. 設(shè)順序循環(huán)隊(duì)列Q0:m-1的隊(duì)頭指針和隊(duì)尾指針分別為F和R,其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置,隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置,則出隊(duì)列的語(yǔ)句為F =_;。2. 設(shè)線性表中有n個(gè)數(shù)據(jù)元素,則在順序存儲(chǔ)結(jié)構(gòu)上

4、實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_,在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_。3. 設(shè)一棵二叉樹中有n個(gè)結(jié)點(diǎn),則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí),該二叉鏈表中共有_個(gè)指針域,_個(gè)空指針域。4. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)B,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為_。5. 設(shè)無向圖G中有n個(gè)頂點(diǎn)和e條邊,則其對(duì)應(yīng)的鄰接表中有_個(gè)表頭結(jié)點(diǎn)和_個(gè)表結(jié)點(diǎn)。6. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊,所有頂點(diǎn)的度數(shù)之和為m,則e和m有_關(guān)系。7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為_。8. 設(shè)一棵完全二叉樹中有21個(gè)結(jié)點(diǎn),如果按照從上

5、到下、從左到右的順序從1開始順序編號(hào),則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是_,編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是_。9. 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法,要求在下劃線處填上正確語(yǔ)句。int index(char s , char t )i=j=0;while(i<strlen(s) && j<strlen(t) if(si=tj)i=i+l; j=j+l;elsei=_; j=_;if (j=strlen(t)return(i-strlen(t);else return (-1);10. 設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條邊,則其最小生成樹上有_條邊。三、運(yùn)算題(每題

6、 6 分,共30分)1設(shè)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE,要求給出該二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2設(shè)給定一個(gè)權(quán)值集合W=(3,5,7,9,11),要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計(jì)算哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL。3設(shè)一組初始記錄關(guān)鍵字序列為(19,21,16,5,18,23),要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4設(shè)一組初始記錄關(guān)鍵字集合為(25,10,8,27,32,68),散列表的長(zhǎng)度為8,散列函數(shù)H(k)=k mod 7,要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。5設(shè)無向圖G(所下圖所

7、示),要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計(jì)題(每題10分,共30分)1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法。3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。5數(shù)據(jù)結(jié)構(gòu)模擬試題04參考答案一、單項(xiàng)選擇題(每題 2 分,共20分)1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空題(每小題2分,共20分)1.   (F+1) % m2. O(n),O(n)3. 2n,n+14. s->next=p->next; s->next=s5. n, 2e6. m

8、=2e7.   CBA8. 4,169. i-j+1,010. n-1三、算法簡(jiǎn)答題(每題 6分,共30分)1. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略,前序ABDEC,中序DBEAC,后序DEBCA。2. 哈夫曼樹略,WPL=783. (18,5,16,19,21,23),(5,16,21,19,18,23)4. 線性探測(cè):鏈地址法:5. 深度:125364,廣度:123456,最小生成樹T的邊集為E=(1,4),(1,3),(3,5),(5,6),(5,6)四、算法設(shè)計(jì)題(每題10分,共30分)1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。typedef struct int s100; int to

9、p; sqstack;int lklistsymmetry(lklist *head) sqstack stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p->next) stack.top+; stack.sstack.top=p->data; for(p=head;p!=0;p=p->next) if (p->data=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1);2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法。typedef

10、char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt) char ch; scanf("%c",&ch); if(ch='#') bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt->data=ch;createbitree(bt->lchild); createbitree(bt->rchild);3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(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)論