【文章內容簡介】 ____________________兩種。12. 當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。三、 運算題（每題6分，共24分）1. 已知一個6180。5稀疏矩陣如右所示，試：（1） 寫出它的三元組線性表；（2） 給出三元組線性表的順序存儲表示。2. 設有一個輸入數(shù)據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據而生成的二叉搜索樹。3. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。四、 閱讀算法（每題7分，共14分）1. int Prime(int n){ int i=1。 int x=(int) sqrt(n)。 while (++i=x) if (n%i==0) break。 if (ix) return 1。 else return 0。 } (1) 指出該算法的功能；(2) 該算法的時間復雜度是多少？2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 InitQueue(Q)。 couti39。 39。 visited[i]=true。 QInsert(Q,i)。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。 edgenode* p=GL[k]。 while(p!=NULL) { int j=padjvex。 if(!visited[j]) { coutj39。 39。 visited[j]=true。 QInsert(Q,j)。 } p=pnext。 } } }五、 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。int high=n1。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //查找成功，返回元素的下標 else if (K[mid].key) ______________________________________。 //在左子表上繼續(xù)查找 else __________________________________。 //在右子表上繼續(xù)查找}return 1。 //查找失敗，返回1}六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結點的算法。ElemType DeleFront(LNode * amp。 HL)模擬試卷三參考答案一、 單選題（每題2分，共20分） 二、 填空題（每空1分，共26分）1. 聯(lián)系 圖（或圖結構）2. 尾 首3. top==04. O（1） O（n）5. 128 44 1086. 3 3 655151321452515637 圖77. 有序 n18. 有序序列 后綴表達式（或逆波蘭式）9. 2n n1 n+110. 2i+1 2i+2 (i1)/211. 開放定址法 鏈接法12. 快速 歸并三、 運算題（每題6分，共24分）1. （1） ((1,5,1),(3,2,1),(4,5,2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲表示如圖7示。圖82. 如圖8所示。3. DFS：????? BFS：????? 4. 拓樸排序為： 4 3 6 5 7 2 1 四、 閱讀算法（每題7分，共14分）1. (1) 判斷n是否是素數(shù)（或質數(shù)） （2）O（）2. 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。五、 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 編寫算法（8分）ElemType DeleFront(LNode * amp。 HL){if (HL==NULL){ cerr空表endl。exit(1)。}LNode* p=HL。HL=HLnext。ElemType temp=pdata。delete p。return temp。} 模擬試卷四一、 單選題（每題 2 分，共20分）1. 以下數(shù)據結構中哪一個是線性結構？( ) A. 有向圖 　　 B. 棧 C. 二叉樹 　　 D. B樹2. 若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用( )存儲方式最節(jié)省時間。 3. 以下哪一個不是隊列的基本運算？（ ） A. 在隊列第i個元素之后插入一個元素 B. 從隊頭刪除一個元素 C. 判斷一個隊列是否為空 4. 字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個不同的字符串？ 　　 　　 5. 由權值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為( )。A． 11 C. 19 D. 53以下68題基于下面的敘述：若某二叉樹結點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。6. 則該二叉樹結點的前序遍歷的序列為( ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B7. 該二叉樹有（ ）個葉子。 A．3 　　 8. 該二叉樹的按層遍歷的序列為( ) A．E、G、F、A、C、D、B 　　　 B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D 　　　　 D. E、G、A、C、D、F、B9. 下面的二叉樹中，( )不是完全二叉樹。10. 設有關鍵碼序列(q，g，m，z，a)，下面哪一個序列是從上述序列出發(fā)建的小根堆的結果?( ) A. a，g ，m，q， z 　 B. a，g ，m，z,q C. g ，m，q，a，z D. g， m， a，q，z二、 填空題（每空1分，共26分）1. 數(shù)據結構是指數(shù)據及其相互之間的______________。當結點之間存在1對N（1：N）的聯(lián)系時，稱這種結構為_____________________。2. 一個廣義表中的元素分為________元素和________元素兩類。3. 對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。4. 向一個由HS指向的鏈棧中插入一個結點時p時，需要執(zhí)行的操作是_________________。刪除一個結點時，需要執(zhí)行的操作是___________________________（假設棧不空而且無需回收被刪除結點）。5. 棧又稱為_______________表，隊列又稱為___________表。6. 在稀疏矩陣所對應的三元組線性表中，每個三元組元素按_________為主序、_________為輔序的次序排列。7. 若一棵二叉樹中只有葉子結點和左、右子樹皆非空的結點，設葉結點的個數(shù)為K，則左、右子樹皆非空的結點個數(shù)是________。8. 以折半（或二分）查找方法從長度為8的有序表中查找一個元素時，平均查找長度為________。9. 表示圖的三種常用的存儲結構為_____________、____________和_______________。10. 對于線性表（78，4，56，30，65）進行散列存儲時，若選用H（K）=K %5作為散列函數(shù)，則散列地址為0的元素有________個，散列地址為4的有_______個。11. 在歸并排序中，進行每趟歸并的時間復雜度為______，整個排序過程的時間復雜度為____________，空間復雜度為___________。12. 在n個帶權葉子結點構造出的所有二叉樹中，帶權路徑長度最小的二叉樹稱為________。WPL稱為_____________________。13. 在索引表中，若一個索引項對應主表的一個記錄，則此索引為__________索引 ，若對應主表的若干條記錄，則稱此索引為________索引。三、 運算題（每題 6 分，共24分）1. 寫出下列中綴表達式的后綴形式：（1） 3X/(Y2H)+1（2） 2+X*(Y+3)2. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。 先序： 中序： 后序： 按層：　　 ab cde3. 已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下所示 (1) 畫出該圖的圖形； （2）根據鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。4. 已知一個圖的頂點集V和邊集E分別為： V={0,1,2,3,4,5,6,7}。 E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20}。按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。四、 閱讀算法（每題7分，共14分）1. void AE(Stackamp。 S){ InitStack(S)。 Push(S,3)。 Push(S,4)。 int x=Pop(S)+2*Pop(S)。 Push(S,x)。 int i,a[5]={2,5,8,22,15}。 for(i=0。i5。i++) Push(S,a[i])。 while(!StackEmpty(S)) coutPop(S)39。 39。 }該算法被調用后得到的輸出結果為：2. int akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1。 else if ( n == 0 ) return akm ( m1, 1 )。 else return akm ( m1, akm ( m, n1 ) )。 } 該函數(shù)執(zhí)行的功能是什么？五、 算法填空（共8分）二叉搜索樹的查找——非遞歸算法bool Find(BTreeNode* BST,ElemTypeamp。 item){while(BST(!=NULL){ if (item==______________){ item=BSTdat