《數(shù)據(jù)結(jié)構(gòu)與算法》試卷與答案1

廣州大學(xué)學(xué)年第學(xué)期考試卷課程數(shù)據(jù)結(jié)構(gòu)與算法考試形式（閉卷，考試）信息學(xué)院系專業(yè)級(jí)班學(xué)號(hào)：姓名：題次一二三四五六總分評(píng)卷人分?jǐn)?shù)201010302010100評(píng)分一、填空題：（每格2分，共20分）對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0..m-1]，隊(duì)頭、隊(duì)尾指針分別是f，r，其判空的條件是，判滿的條件是。前序序列和中序序列相同的二叉樹為。.設(shè)根結(jié)點(diǎn)處在第一層，那么具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其高度為?？焖倥判蚍椒ǖ淖顗臅r(shí)間復(fù)雜度為;平均時(shí)間復(fù)雜度為。給定表（55，63，44，38，75，80，31，56），用篩選法建立初始堆，則初始堆表為。已知二叉樹中葉子數(shù)為50，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為已知8個(gè)數(shù)據(jù)元素由（35,75,40，15,20，55,95,65）按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為假設(shè)有n個(gè)關(guān)鍵字，它們具有相同的Hash函數(shù)值，用線性探測方法解決沖突，把這n個(gè)關(guān)鍵字散列到大小為n的地址空間中，共計(jì)需要做次插入和探測操作。設(shè)圖G有n個(gè)頂點(diǎn)e條邊，采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為 。

10.已知有序表為(12,18,24,35,47,50,62,83,90,115,134),當(dāng)用二分法查找100時(shí)，需進(jìn)行次查找時(shí)才能確定不成功。。二、單項(xiàng)選擇題(每題1分，共10分)1.( )組成數(shù)據(jù)的基本單位是A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量2.( )串的邏輯結(jié)構(gòu)與()的邏輯結(jié)構(gòu)不同A.線性表B.棧C.隊(duì)列D.樹3.( )設(shè)一數(shù)列的順序?yàn)?,2,3,4,5,6，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為A.3,2,5,6,4,1B.1,5,4,6,2,3C.2,4,3,5,1,6D.4,5,3,6,2,14.( )設(shè)有一個(gè)10階的對(duì)稱矩陣A,米用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1,每元素占一個(gè)存儲(chǔ)空間，則a85的地址為13TOC\o"1-5"\h\z331840( )二叉樹在線索化后，仍不能有效求解的問題是前(先)序線索二叉樹中求前(先)序后繼；中序線索二叉樹中求中序后繼；中序線索二叉樹中求中序前趨；后序線索二叉樹中求后序后繼。( )如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B的度為TOC\o"1-5"\h\z3451( )設(shè)有100個(gè)元素，用二分法查找時(shí)，最大比較次數(shù)是TOC\o"1-5"\h\z257101( )快速排序在( )情況下最不利于發(fā)揮其長處被排序的數(shù)據(jù)量太大被排序的數(shù)據(jù)中含有多個(gè)相同的關(guān)鍵字被排序的數(shù)據(jù)完全無序被排序的數(shù)據(jù)已基本有序( )判定一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蛲?，還可以利用求關(guān)鍵路徑的方法求最短路徑的Dijkstra方法深度優(yōu)先遍歷算法寬度優(yōu)先遍歷算法( )對(duì)于含有個(gè)n頂點(diǎn)e條邊的無向連通圖，利用Prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為( )，利用Kruskal時(shí)間復(fù)雜度為( )O(log2n)O(n2)O(ne)o(elog2e)三、判斷題(在括號(hào)內(nèi)填上""”或“X”，每題1分，共10分，做錯(cuò)不倒扣)()具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)原子，則必定有a<b的關(guān)系。()對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個(gè)頂點(diǎn)。()一個(gè)滿二叉樹同時(shí)又是一棵平衡樹。()任一AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點(diǎn)到匯點(diǎn)的路徑中最長的一條。()快速排序是排序算法中最快的一種。()刪除二叉排序樹中一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。()對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。()在索引順序表查找方法中，對(duì)索引順序表可以使用順序表查找方法，也可以使用二分查找方法。()雙循環(huán)鏈表中，任一結(jié)點(diǎn)的前驅(qū)指針均為不空。()哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。

四、 （1） （6分）給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu).33（2）解答下面的問題（6分）（（2）解答下面的問題（6分）（1） 求網(wǎng)的最小生成樹有哪些算法？各適用何種情況？為什么？（2） 由以下的網(wǎng)絡(luò)鄰接矩陣，畫出一棵最小生成樹17202217812118111920191534221215111920191534221215348（3）已知一棵非空二叉樹，其按中根和后根遍歷的結(jié)果分別為：中根：CGBAHEDJFI后根：GBCHEJIFDA試將這樣的二叉樹構(gòu)造出來。若已知先根和后根的遍歷結(jié)果，能否構(gòu)造出這棵二叉樹，為什么？5分（4）一項(xiàng)工程由P1、P2、.......P6六項(xiàng)子工程組成，這些工程之間有下列關(guān)系:P1<P2，P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符號(hào)“<”表示“先于”關(guān)系，例如P2<P6表示P2完成后P6才能開始。請(qǐng)給出工程P的三種可能的施工順序。（6分）（5）假定用于通信的電文由8個(gè)字母A，B，C，D，E，F(xiàn)，G，H組成，各字母在電文中出現(xiàn)的概率為5%,25%,4%,7%,9%,12%,30%,8%，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。（7分）五、 (1)讀程序，分析其時(shí)間復(fù)雜度：4分m=91;n=100;while(n>0)if(m>0){m=m-10;n=n-1;}elsem=m+1;此程序的時(shí)間復(fù)雜度是。(2)以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請(qǐng)?zhí)羁胀晟浦?6分typedefstructnode{chardata;structnodelchild,rchild;}*bitree;intdepth(bitreebt)/*bt為根結(jié)點(diǎn)的指針*/{inthl,hr;if(br==NULL)return();hl=depth(bt->lchild);hr=depth(bt->rchild);if() return(hr+1);已知N元整型數(shù)組a存放N個(gè)學(xué)生的成績，已按由大到小排序，以下算法是用折半查找方法統(tǒng)計(jì)成績大于或等于x分的學(xué)生人數(shù)，請(qǐng)?zhí)羁胀晟浦?分#defineN /*學(xué)生人數(shù)*/intuprx(inta[N],intx) /*函數(shù)返回大于或等于x分的學(xué)生人數(shù)*/{inthead,mid,rear;do{mid=(head+rear)/2;if(x<=a[mid])else;}while();if(a[head]<x)returnhead-1;returnhead;}簡述以下算法的功能：4分voidBB(LNode*s,LNode*q){P=s;while(p->next!=q)p=p->next;p->next=s;}voidAA(LNode*pa,LNode*pb){ //pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn)BB(pa,pb);BB(pb,pa);}六、給定有m個(gè)整數(shù)的遞增有序數(shù)組a[1..m]和有n個(gè)整數(shù)的遞減有序數(shù)組b[1..n]。試寫出算法：將數(shù)組a和b歸并為遞增有序數(shù)組c[1..m+n]。(要求：算法的時(shí)間復(fù)雜度為O(m+n)。)(10分)試卷答案一、 填空題：(每格2分，共20分)r=f，(r+1)%m=f。單右枝二叉樹或孤立結(jié)點(diǎn)。卜0&2。」+1。O(n2)； O(nlog2n)。(31,38,44,56,75,80,55,63)或(80,75,55,56,63,44,31,38)。129。2 n(n+1)/2 O(n+e)。10*.已知有序表為(12,18,24,35,47,50,62,83,90,115,134),當(dāng)用二分法查找100時(shí)，需進(jìn)行3 次查找時(shí)才能確定不成功。。二、單項(xiàng)選擇題(每題1分，共10分)TOC\o"1-5"\h\z( C )(D)( B )( B )( D )( D )( B )( D )( C )*10.(BD)對(duì)于含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為( )，利用Kruskal時(shí)間復(fù)雜度為( )O(log2n)\o"CurrentDocument"O(n2)O(ne)

H.O(elog2e)二 、判斷題11(F)12(F)13(F)14(T)15(F)16(F)17(T)18(T)19(T)20(T)四、(1)（6分）解:鄰接矩陣為

(2)解答下面的問題(6分)解(1)：求網(wǎng)的最小生成樹時(shí)可使用Prim算法，此算法適用于邊較多的稠密圖;也可使用Kruskual算法，此算法適用于邊較少的稀疏圖。(2)：一棵最小生成樹如圖所示：(3)解：由中根和后根所確定的二叉樹如圖所示前根序列和后根序列不能唯一確定一棵二叉樹。因?yàn)楦鶕?jù)中根序列，結(jié)合前根或后根序列可以把二叉樹區(qū)分出左右子樹來。而前根序列和后根序列訪問左右子樹是順序連在一起的，故無法區(qū)分出左右子樹來，那么也就無法確定一棵二叉樹了。(4)解：可給出有向圖表示各子工程間的關(guān)系如下圖:找出3個(gè)可能的施工順序如下：P1,P2,P3,P4,P5,P6P1,P4,P2,P3,P5,P6P4,P5,P1,P2,P3,P6(5)解：A:1001 B:11C:1000 D:0000E:101 F:001G:01 H:0001五、(1)O(n)(2)typedefstructnode{chardata;structnodelchild,rchild;}*bitree;intdepth(bitreebt) /*bt為根結(jié)點(diǎn)的指針*/{inthl,hr;if(br==NULL)return(0);hl=depth(bt->lchild);hr=depth(bt->rchild);if(hl>hr)return(hl+1)return(hr+1);}(3)#defineN /*學(xué)生人數(shù)*/intuprx(inta[N],intx) /*函數(shù)返回大于或等于x分的學(xué)生人數(shù)*/{inthead,mid,rear;do{mid=(head+rear)/2;if(x<=a[mid])head=mid+1elserear=mid-1;}while(head>rear);if(a[head]<x)re