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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案(2003-2004學(xué)年第2學(xué)期)單項(xiàng)選擇題1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、1對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（ c）。 (A)、正確性 (B). 可行性 (C). 健壯性 (D). 輸入性2設(shè)S為C語(yǔ)言的語(yǔ)句,計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為（ d ）。for(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 ）

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

3、 （D）、層序8在下列鏈隊(duì)列Q中，元素a出隊(duì)的操作序列為（ a b ）b c d afrontrear Q （A）、p=Q.front->next; p->next= Q.front->next; （B）、p=Q.front->next; Q.front->next=p->next; （C）、p=Q.rear->next; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next;9 Huffman樹(shù)的帶權(quán)路徑長(zhǎng)度WPL等于（ c ）（A）、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和

4、（B）、所有結(jié)點(diǎn)權(quán)值之和（C）、各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 （D）、根結(jié)點(diǎn)的值10線索二叉鏈表是利用（ c ）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。 （A）、lchild （B）、data （C）、rchild （D）、root二、填空題1 邏輯結(jié)構(gòu)決定了算法的 設(shè)計(jì) ，而存儲(chǔ)結(jié)構(gòu)決定了算法的 實(shí)現(xiàn) 。2 棧和隊(duì)列都是一種 特殊 的線性表，棧的插入和刪除只能在 棧頂 進(jìn)行。3 線性表（a1,a2,an）的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)單元的長(zhǎng)度為L(zhǎng)，元素ai的存儲(chǔ)地址LOC(ai)為 4 已知一雙向鏈表如下(指針域名為next和prior)： y x e q p現(xiàn)將p所指的結(jié)點(diǎn)插入到x和y結(jié)點(diǎn)之間，其操作步驟為：

5、； ； ； ；5n個(gè)結(jié)點(diǎn)無(wú)向完全圖的的邊數(shù)為 ， n個(gè)結(jié)點(diǎn)的生成樹(shù)的邊數(shù)為 。6已知一有向無(wú)環(huán)圖如下： BACDFEG 任意寫(xiě)出二種拓?fù)渑判蛐蛄校?、 。7已知二叉樹(shù)的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹(shù)的先序遍歷序列為 ，層序遍歷序列為 。三、應(yīng)用題1 設(shè)散列函數(shù)H(k)=k % 13,設(shè)關(guān)鍵字系列為22,12,24,6,45,7,8,13,21,要求用線性探測(cè)法處理沖突。(6分)(1) 構(gòu)造HASH表。(2) 分別求查找成功和不成功時(shí)的平均查找長(zhǎng)度。2 給定表（19,14,22,15,20,21,56,10）.（8分）（1） 按元素在表中的次序，建立一棵二叉排序樹(shù)（2）

6、對(duì)(1)中所建立的二叉排序樹(shù)進(jìn)行中序遍歷，寫(xiě)出遍歷序列。（3） 畫(huà)出對(duì)(2)中的遍歷序列進(jìn)行折半查找過(guò)程的判定樹(shù)。3 已知二個(gè)稀疏矩陣A和B的壓縮存儲(chǔ)三元組表如下： A BijVijV13-525224633725241342-152-9529558寫(xiě)出A-B壓縮存儲(chǔ)的三元組表。（5分）4 已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）, 試寫(xiě)出插入排序（升序）過(guò)程。并指出具有n個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？(5分)5 已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A開(kāi)始的最小生成樹(shù)。(8分，要有過(guò)程) A B C D E F（1）求從頂點(diǎn)A開(kāi)始的最小生成樹(shù)。（2）分別畫(huà)出以A為起點(diǎn)的DFS

7、生成樹(shù)和BFS生成樹(shù)。6已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7分，要有過(guò)程)。（1） 畫(huà)出對(duì)應(yīng)的Huffman樹(shù)。（2） 計(jì)算帶權(quán)路徑長(zhǎng)度WPL。（3） 求A、B、C、D、E、F的Huffman編碼。7 已知有如下的有向網(wǎng)： 2 5 36 4 10 6 1 2 2 AEBDC求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用Dijkstra算法，要有過(guò)程）。（6分）三、 設(shè)計(jì)題（30分，每題10分,用C語(yǔ)言寫(xiě)出算法，做在答題紙上）1 已知線性表（a1,a2,an）以順序存儲(chǔ)結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)，其類型定義如

8、下： #define LIST_INIT_SIZE 100 /順序表初始分配容量 typedef struct Elemtype *elem; /順序存儲(chǔ)空間基址 int length; /當(dāng)前長(zhǎng)度（存儲(chǔ)元素個(gè)數(shù)） SqList;設(shè)計(jì)一個(gè)算法，刪除其元素值為x的結(jié)點(diǎn)（假若x是唯一的）。并求出其算法的平均時(shí)間復(fù)雜度。其算法函數(shù)頭部如下： Status ListDelete(Sqlist &L,Elemtype x) ana2a12設(shè)順序棧如左圖所示。 其中結(jié)點(diǎn)定義如下： top typedef struct Elemtype *base; /棧底指針Elemtype *top; /棧頂指

9、針 Stack;設(shè)計(jì)算法，將棧頂元素出棧并存入e中 base3設(shè)二叉鏈樹(shù)的類型定義如下： typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree;試寫(xiě)出求該二叉樹(shù)葉子結(jié)點(diǎn)數(shù)的算法: Status CountLeaves(BinTree &root,int &n) /n is the number of leaves 答案：選擇題（每題1分）1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、

10、填空題1 設(shè)計(jì)、實(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 ADCBFEG、ABCDEFFG7 ABC、ABC二、 應(yīng)用題1 （1）Hash表（4分）地址0123456789101112關(guān)鍵安132164572282412探測(cè)次數(shù)171231311（2）查找成功的平均查找長(zhǎng)度：（1分） （5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長(zhǎng)度：（1分） （2+1+9+8+7+6+5+4+3+

11、2+1）/13=2（1）、構(gòu)造（3分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-152185584、 初始關(guān)鍵字： 18 12 25 53 18 第 一 趟：12 18 25 53 18第 二 趟：12 18 25 53 18第 三 趟：12 18 25 53 18第 四 趟：12 18 18 25 53 （4分） O（n2）（1分）。5、7分（1）4分A B 1 C 3 2 5 D 4 E F（2）4分6、(1) 3分 E F A B C D （2

12、）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）12、A-B：（A、B） 1分A-C：（A、D、C） 2分A-D：（A、D） 1分 A-E：（A、D、E） 2分 三，設(shè)計(jì)題（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 ERRO

13、R; for(j=i;j<L->lengthi-1;j+) L->elemj=L->elemj+1; L->length-; （8分）平均時(shí)間復(fù)雜度：（2分）設(shè)元素個(gè)數(shù)記為n，則平均時(shí)間復(fù)雜度為：2（10分）void pop(Stack &S,Elemtype &e) if(S.top=S.base) return ERROR; S.top-; e=*s.top;2、（10分）voidCountLeaves(BinTree T,int &n)if(T)if(!(T->lchild)&&!( T->rchild)

14、n+; CountLeaves (T->lchild,n); CountLeaves (T->rchild,n);人生中每一次對(duì)自己心靈的釋惑，都是一種修行，都是一種成長(zhǎng)。相信生命中的每一次磨礪，都會(huì)讓自己的人生折射出異常的光芒，都會(huì)讓自己的身心煥發(fā)出不一樣的香味。我們常常用人生中的一些痛，換得人生的一份成熟與成長(zhǎng)，用一些不可避免的遺憾，換取生命的一份美麗。在大風(fēng)大雨，大風(fēng)大浪，大悲大喜之后，沉淀出一份人生的淡然與淡泊，靜好與安寧，深邃與寬厚，慈悲與欣然生活里的每個(gè)人，都是我們的一面鏡子，你給別人什么，別人就會(huì)回待你什么。當(dāng)你為一件事情不悅的時(shí)候，應(yīng)該想想你給過(guò)人家怎樣負(fù)面的情緒。

15、世界上的幸福，沒(méi)有一處不是來(lái)自用心經(jīng)營(yíng)和珍惜。當(dāng)你一味的去挑剔指責(zé)別人的時(shí)候，有沒(méi)有反思過(guò)自己是否做得盡善盡美呢？假如你的心太過(guò)自我，不懂得經(jīng)營(yíng)和善待，不懂得尊重他人的感受，那么你永遠(yuǎn)也不會(huì)獲得真正的愛(ài)和幸福人生就像一場(chǎng)旅行，我們所行走的每一步都是在豐富生命的意義。我們一邊穿越在陌生的吸引里，一邊咀嚼回味著一抹遠(yuǎn)走光陰的舊味，一切都是不可預(yù)料，一切又似在預(yù)料之中。人生看的多了，走的多了，經(jīng)歷的多了，也就懂得多了。每一份深刻的感悟大多來(lái)自一個(gè)人深刻的經(jīng)歷。人生總有那么一兩件重大的事情讓你成熟和改變。這份錯(cuò)失，會(huì)讓你反思自己，檢討自己，叩問(wèn)自己，也讓你意識(shí)到了自己真正的缺失，這或許就是一份痛苦的領(lǐng)

16、悟吧！人生可以平平淡淡，亦可以異彩紛呈。相信只要自己的德馨足夠善美，上天就會(huì)把最好的一切賜予你。予人快樂(lè)，收獲快樂(lè)；予人幸福，收獲幸福；予人真情，收獲厚意。人生的一切往來(lái)皆有因果，生活只善待有心人假如你有一顆計(jì)較的心，你就會(huì)很難獲得一份幸福。當(dāng)一個(gè)人放下了自己內(nèi)心的那份累心的奢求，你的心空就會(huì)變得更加蔚藍(lán)干凈。寬容，不僅是一種豁達(dá)的態(tài)度，更是一種心靈的品德，是一種處事的修行，寬容別人不是低矮了自己，而是釋放了自己，升華了自己。你把世界寬待在心中，世界也同樣裝飾了你的一份美麗。當(dāng)你簡(jiǎn)約、釋然了自己的時(shí)候，你會(huì)發(fā)現(xiàn)另一份生命中的快樂(lè)。那快樂(lè)是發(fā)自一顆簡(jiǎn)單的心，那快樂(lè)是從心靈的草地里歡快的迸發(fā)出來(lái)，通過(guò)你溫柔的眼眸和開(kāi)心的笑聲來(lái)傳遞。所以，心寬便心悅，你人生的天空是什么顏色，往往取決于你對(duì)人生的態(tài)度和對(duì)于自己情緒的駕馭世界上美好的東西那么多，有緣來(lái)到你的身旁，被你握到掌心的卻又那么少。所以一切在的時(shí)候請(qǐng)學(xué)會(huì)珍惜，因?yàn)榇蠖嗝利惖臇|西只會(huì)為你來(lái)過(guò)一次。你一不小心就會(huì)失落，無(wú)處找尋，增加了你人生的又一次遺憾過(guò)往，終是回不去的曾經(jīng)。人總是在失去的時(shí)候才懂得珍惜，人總是在回味的時(shí)候才知道甜美。往事已矣，該放下的