《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案

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