《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案_第1頁
《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案_第2頁
《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案_第3頁
《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案_第4頁
《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案_第5頁
已閱讀5頁,還剩7頁未讀 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案(2003-2004學(xué)年第2學(xué)期)單項選擇題 1、C 2 D 3、A 4、D 5、C 6 D 7、A 8、B 9、C 10、C1.對于一個算法,當輸入非法數(shù)據(jù)時,也要能作出相應(yīng)的處理,這種要求稱為(c)。(A)、正確性 (B).可行性 (C).健壯性(D).輸入性2 .設(shè)S為C語言的語句,計算機執(zhí)行下面算法時,算法的時間復(fù)雜度為(dfor(i=n-1 ; i>=0; i-)for(j=0 ; j<i; j+)S;(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3 .折半查找法適用于( a )。(A)、有序順序表(B)、有序單鏈

2、表(C)、有序順序表和有序單鏈表都可以(D)、無限制4 .順序存儲結(jié)構(gòu)的優(yōu)勢是(d )。(A)、利于插入操作(B)、利于刪除操作(C)、利于順序訪問 (D)、利于隨機訪問5 .深度為k的完全二叉樹,其葉子結(jié)點必在第( c )層上。(A)、k-1(B)、k (0、k-1 和 k(D)、1 至 k6 .具有60個結(jié)點的二叉樹,其葉子結(jié)點有12個,則度過1的結(jié)點數(shù)為()(A)、11(B)、13(C)、48(D)、377 .圖的Depth-First Search(DFS)遍歷思想實際上是二叉樹( a )遍歷方法的 推廣。(A)、先序 (B)、中序(C)、后序(D)、層序8 .在下列鏈隊列 Q中,元素

3、a出隊的操作序列為( a b )(A)、p=>next; p->next= >next;(B)、p=>next; >next=p->next;C C)、p=>next; p->next= >next;D D)、 p=Q->next; Q->next=p->next;9 . Huffman樹的帶權(quán)路徑長度 WPL等于( c )(A)、除根結(jié)點之外的所有結(jié)點權(quán)值之和(B)、所有結(jié)點權(quán)值之和(C)、各葉子結(jié)點的帶權(quán)路徑長度之和(D)、根結(jié)點的值10 .線索二叉鏈表是利用( c )域存儲后繼結(jié)點的地址。(A)、Ichild (B)

4、、data (C)、rchild (D)、root二、填空題1 .邏輯結(jié)構(gòu)決定了算法的設(shè)計,而存儲結(jié)構(gòu)決定了算法的實現(xiàn)。2 .棧和隊列都是一種特殊的線性表.棧的插入和刪除只能在棧頂進行。L,元素 ai3 .線性表(a1,a2,制的順序存儲結(jié)構(gòu)中,設(shè)每個單元的長度為的存儲地址LOC(a)為已知一雙向鏈表如下(指針域名為next和prior):p4 .現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間,其操作步驟5 . n個結(jié)點無向完全圖的的邊數(shù)為 ,n個結(jié)點的生成樹的邊數(shù)為 。6.已知一有向無環(huán)圖如下:任意寫出二種拓撲排序序列: 、。7.已知二叉樹的中序遍歷序列為BCA,后序遍歷序列為 CBA,則該二叉樹的先

5、序遍歷序列為 ,層序遍歷序列為 。三、應(yīng)用題1 .設(shè)散列函數(shù) H(k尸k % 13,設(shè)關(guān)鍵字系列為22,12,24,6,45,7,8,13,21,要求用線性探測法處理沖突。(6分)(1)構(gòu)造HASH表。(2)分別求查找成功和不成功時的平均查找長度。2 . 給定表(19,14,22,15,20,21,56,10 ) . (8 分)(1) 按元素在表中的次序,建立一棵二叉排序樹(2)(1)中所建立的二叉排序樹進行中序遍歷,寫出遍歷序列。(3)畫出對(2)中的遍歷序列進行折半查找過程的判定樹。3 .已知二個稀疏矩陣 A和B的壓縮存儲三元組表如下:ABijV13-524625242-1529ijV25

6、233741352-9558寫出A-B壓縮存儲的三元組表。(5分)4 .已知一維數(shù)組中的數(shù)據(jù)為(18,12,25,53,18),試寫出插入排序(升序)過程。并指出具有n個元素的插入排序的時間復(fù)雜度是多少(5分)5.已知一網(wǎng)絡(luò)的鄰接矩陣如下,求從頂點A開始的最小生成樹。(8分,要有過程)A B C D E FA6 5 1B 65 3C 572D 15 76 4E366F2 4 6(1)求從頂點A開始的最小生成樹。(2)分別畫出以 A為起點的DFS生成機口 BFS生成樹。6.已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:ABCDEF(7分,要有過程)。把這些字母和頻率作為葉子結(jié)點及權(quán)值,完成如下工作(

7、1) 畫出對應(yīng)的Huffman樹。(2) 計算帶權(quán)路徑長度 WPL。(3) 求 A、B、C、D、E、F 的 Huffman 編碼。7.已知有如下的有向網(wǎng):求頂點A到其它各頂點的最短路徑(采用 Dijkstra算法,要有過程)。(6分)三、 設(shè)計題(30分,每題10分,用C語言寫出算法,做在答題紙上) 1.已知線性表(ai,a2,制以順序存儲結(jié)構(gòu)為存儲結(jié)構(gòu),其類型定義如下:#define LIST_INIT_SIZE 100/順序表初始分配容量typedef struct Elemtype *elem;/順序存儲空間基址int length;/當前長度(存儲元素個數(shù))SqList;設(shè)計一個算法,

8、刪除其元素值為 x的結(jié)點(假若x是唯一的)。并求出其算法的 平均時間復(fù)雜度。其算法函數(shù)頭部如下:Status ListDelete(Sqlist &L,Elemtype x)abase2 .設(shè)順序棧如左圖所示。其中結(jié)點定義如下:typedef struct Elemtype*base;/ 棧底指針Elemtype*top;/ 棧頂指針Stack;設(shè)計算法,將棧頂元素出棧并存入e中.3 .設(shè)二叉鏈樹的類型定義如下:typedef int Elemtype;typedef struct nodeElemtype data;struct node *lchild, *rchild;BinNo

9、de, *BinTree;試寫出求該二叉樹葉子結(jié)點數(shù)的算法Status CountLeaves(BinTree &root,int &n)/n is the number of leaves 答案:選擇題(每題1分)1、C 2、D 3、A 4、D 5、C & D 7、A 8、B 9、C 10、C一、填空題1. 設(shè)計、實現(xiàn)2. 特殊、棧頂3. LOC (a1) +(i-1)*L4. p->next=q->next;q->next->prior=p; q->next=p;p->prior=q;5. n(n-1)/2、n-16. ADCBF

10、EG ABCDEFFG7. ABC ABC二、應(yīng)用題1 (1) Hash 表(4 分)地址0123456789101112關(guān)鍵安132164572282412探測次數(shù)171231311(2)查找成功的平均查找長度:(1分)(5*1+1*2+2*3+1*7 ) /9=20/9查找不成功的平均查找長度:(1分)(2+1+9+8+7+6+5+4+3+2+1) /13=第趟:1218 25 53 182 (1)、構(gòu)造(3分)151056(2)、10 14 15 19 20 21 22 56 (2 分)(3)、(3 分)3、(5分,每行ijv13-524633741342-1521855853 1853

11、 184、 初始關(guān)鍵字:1812 25第一趟:1218 25趟:1218 25 53 18第四趟:121818 2553(4分)2、(10 分)O (n2) (1 分)。5、7分(1) 4 分6、(1) 3 分AEF(2) 4 分ABCD WPL=*3+*3+*2+*3+*3+03*21 =(1分)(3) A: 010 B: 011 C: 110D:111E: 00 F; 10(3分)A-C: (A、D、C) 2 分A-D: (A、D)1 分A-E: (A、D> E)2 分三,設(shè)計題(20分)1、(10 分)Status ListDelete(Sqlist &L,ElemType x)int i,j;for(i=0;i<L->length;i+)if(L->elemi=x) break;if(i=L->length) return ERROR;for(j=i;j<L->lengthi-1;j+)L->elemj=L->elemj+1;L->length-;(8 分)平均時間復(fù)雜度:(2分)設(shè)元素個數(shù)記為n,則平均時間復(fù)雜度為:1 n (n i)n i 12 (10 分)void pop(Stack &S,E

溫馨提示

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

最新文檔

評論

0/150

提交評論