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

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

四、 （1） （6分）給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu).33（2）解答下面的問題（6分）（（2）解答下面的問題（6分）（1） 求網(wǎng)的最小生成樹有哪些算法？各適用何種情況？為什么？（2） 由以下的網(wǎng)絡鄰接矩陣，畫出一棵最小生成樹17202217812118111920191534221215111920191534221215348（3）已知一棵非空二叉樹，其按中根和后根遍歷的結(jié)果分別為：中根：CGBAHEDJFI后根：GBCHEJIFDA試將這樣的二叉樹構(gòu)造出來。若已知先根和后根的遍歷結(jié)果，能否構(gòu)造出這棵二叉樹，為什么？5分（4）一項工程由P1、P2、.......P6六項子工程組成，這些工程之間有下列關系:P1<P2，P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符號“<”表示“先于”關系，例如P2<P6表示P2完成后P6才能開始。請給出工程P的三種可能的施工順序。（6分）（5）假定用于通信的電文由8個字母A，B，C，D，E，F(xiàn)，G，H組成，各字母在電文中出現(xiàn)的概率為5%,25%,4%,7%,9%,12%,30%,8%，試為這8個字母設計哈夫曼編碼。（7分）五、 (1)讀程序，分析其時間復雜度：4分m=91;n=100;while(n>0)if(m>0){m=m-10;n=n-1;}elsem=m+1;此程序的時間復雜度是。(2)以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?6分typedefstructnode{chardata;structnodelchild,rchild;}*bitree;intdepth(bitreebt)/*bt為根結(jié)點的指針*/{inthl,hr;if(br==NULL)return();hl=depth(bt->lchild);hr=depth(bt->rchild);if() return(hr+1);已知N元整型數(shù)組a存放N個學生的成績，已按由大到小排序，以下算法是用折半查找方法統(tǒng)計成績大于或等于x分的學生人數(shù)，請?zhí)羁胀晟浦?分#defineN /*學生人數(shù)*/intuprx(inta[N],intx) /*函數(shù)返回大于或等于x分的學生人數(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)鏈表中的兩個結(jié)點BB(pa,pb);BB(pb,pa);}六、給定有m個整數(shù)的遞增有序數(shù)組a[1..m]和有n個整數(shù)的遞減有序數(shù)組b[1..n]。試寫出算法：將數(shù)組a和b歸并為遞增有序數(shù)組c[1..m+n]。(要求：算法的時間復雜度為O(m+n)。)(10分)試卷答案一、 填空題：(每格2分，共20分)r=f，(r+1)%m=f。單右枝二叉樹或孤立結(jié)點。卜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),當用二分法查找100時，需進行3 次查找時才能確定不成功。。二、單項選擇題(每題1分，共10分)TOC\o"1-5"\h\z( C )(D)( B )( B )( D )( D )( B )( D )( C )*10.(BD)對于含有n個頂點e條邊的無向連通圖，利用Prim算法生成最小代價生成樹其時間復雜度為( )，利用Kruskal時間復雜度為( )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)的最小生成樹時可使用Prim算法，此算法適用于邊較多的稠密圖;也可使用Kruskual算法，此算法適用于邊較少的稀疏圖。(2)：一棵最小生成樹如圖所示：(3)解：由中根和后根所確定的二叉樹如圖所示前根序列和后根序列不能唯一確定一棵二叉樹。因為根據(jù)中根序列，結(jié)合前根或后根序列可以把二叉樹區(qū)分出左右子樹來。而前根序列和后根序列訪問左右子樹是順序連在一起的，故無法區(qū)分出左右子樹來，那么也就無法確定一棵二叉樹了。(4)解：可給出有向圖表示各子工程間的關系如下圖:找出3個可能的施工順序如下：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é)點的指針*/{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 /*學生人數(shù)*/intuprx(inta[N],intx) /*函數(shù)返回大于或等于x分的學生人數(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