【文章內(nèi)容簡介】 ____________________兩種。12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。三、 運算題（每題6分，共24分）1. 已知一個6180。5稀疏矩陣如右所示，試：（1） 寫出它的三元組線性表；（2） 給出三元組線性表的順序存儲表示。2. 設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。3. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(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}。若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。四、 閱讀算法（每題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) 該算法的時間復(fù)雜度是多少？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。 //查找成功，返回元素的下標(biāo) else if (K[mid].key) ______________________________________。 //在左子表上繼續(xù)查找 else __________________________________。 //在右子表上繼續(xù)查找}return 1。 //查找失敗，返回1}六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。ElemType DeleFront(LNode * amp。 HL)模擬試卷三參考答案一、 單選題（每題2分，共20分） 二、 填空題（每空1分，共26分）1. 聯(lián)系 圖（或圖結(jié)構(gòu)）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ù)（或質(zhì)數(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ù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？( ) A. 有向圖 　　 B. 棧 C. 二叉樹 　　 D. B樹2. 若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用( )存儲方式最節(jié)省時間。 3. 以下哪一個不是隊列的基本運算？（ ） A. 在隊列第i個元素之后插入一個元素 B. 從隊頭刪除一個元素 C. 判斷一個隊列是否為空 4. 字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個不同的字符串？ 　　 　　 5. 由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( )。A． 11 C. 19 D. 53以下68題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。6. 則該二叉樹結(jié)點的前序遍歷的序列為( ). 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. 設(shè)有關(guān)鍵碼序列(q，g，m，z，a)，下面哪一個序列是從上述序列出發(fā)建的小根堆的結(jié)果?( ) 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ù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點之間存在1對N（1：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。2. 一個廣義表中的元素分為________元素和________元素兩類。3. 對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為_________，在表尾插入元素的時間復(fù)雜度為____________。4. 向一個由HS指向的鏈棧中插入一個結(jié)點時p時，需要執(zhí)行的操作是_________________。刪除一個結(jié)點時，需要執(zhí)行的操作是___________________________（假設(shè)棧不空而且無需回收被刪除結(jié)點）。5. 棧又稱為_______________表，隊列又稱為___________表。6. 在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按_________為主序、_________為輔序的次序排列。7. 若一棵二叉樹中只有葉子結(jié)點和左、右子樹皆非空的結(jié)點，設(shè)葉結(jié)點的個數(shù)為K，則左、右子樹皆非空的結(jié)點個數(shù)是________。8. 以折半（或二分）查找方法從長度為8的有序表中查找一個元素時，平均查找長度為________。9. 表示圖的三種常用的存儲結(jié)構(gòu)為_____________、____________和_______________。10. 對于線性表（78，4，56，30，65）進行散列存儲時，若選用H（K）=K %5作為散列函數(shù)，則散列地址為0的元素有________個，散列地址為4的有_______個。11. 在歸并排序中，進行每趟歸并的時間復(fù)雜度為______，整個排序過程的時間復(fù)雜度為____________，空間復(fù)雜度為___________。12. 在n個帶權(quán)葉子結(jié)點構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為________。WPL稱為_____________________。13. 在索引表中，若一個索引項對應(yīng)主表的一個記錄，則此索引為__________索引 ，若對應(yīng)主表的若干條記錄，則稱此索引為________索引。三、 運算題（每題 6 分，共24分）1. 寫出下列中綴表達式的后綴形式：（1） 3X/(Y2H)+1（2） 2+X*(Y+3)2. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。 先序： 中序： 后序： 按層：　　 ab cde3. 已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下所示 (1) 畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。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。 }該算法被調(diào)用后得到的輸出結(jié)果為：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