【正文】 { Queue Q。 該算法的時間復雜度是多少？2. 2. 指出該算法的功能；(2) (2) } (1) (1) if (ix) return 1。 int x=(int) sqrt(n)。 拓樸排序為： 4 3 6 5 7 2 1 DFS：????… BFS：???…? 4.3. 3. （1） ((1,5,1),(3,2,1),(4,5,2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲表示如圖7示。 運算題（每題6分，共24分）1. 1.若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列.二、 三、 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。3. 3.2. 2. 寫出它的三元組線性表；（2） （2）5稀疏矩陣如下所示， 運算題（每題6分，共24分）1. 1.三、 三、 當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。10. 10.9. 9. 對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個______________。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_____________。7. 7.6. 6.W中第6 行的元素和第4 列的元素共占用＿_______＿個字節(jié)。5. 5.4. 4.3. 3.2. 2. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 快速排序在最壞情況下的時間復雜度為（ D ）。A．行號 B．列號 C．元素值 D．非零元素個數(shù)9. 9. 若需要利用形參直接訪問實參時，應將形參變量說明為（ D ）參數(shù)。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. AOV網(wǎng)是一種（ D ）。 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. 對線性表，在下列哪種情況下應當采用鏈表表示？( B ) 4. 4.3. 3. D. HL=p。 C. pnext=HL。 B. pnext=HL。 A. pnext=HLnext。 對一個算法的評價，不包括如下（B ）方面的內(nèi)容。 單選題（每題 2 分，共20分）1. 1.（一）一、 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度2. 2. 在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行( A )。 HLnext=p。 HL=p。 p=HL。 pnext=HL。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時，其平均查找長度（ S ）。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（ A）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( C )。二、 二、 運算題（每題 6 分，共24分）1. 1.當結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。 隊列的插入操作是在隊列的___尾______進行，刪除操作是在隊列的____首______進行。 當用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。 設W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7 ，列下標j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_____＿個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿________＿。 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。 二叉樹是指度為2的____________________樹。8. 8.對一棵由算術(shù)表達式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達式的__________________。 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。 若對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A[0]中。11. 11.12. 12.一、 填空題（每空1分，共26分）1. 1. 聯(lián)系 圖（或圖結(jié)構(gòu)）2. 2. 尾 首3. 3. top==04. 4. O（1） O（n）5. 5. 128 44 1086. 6. 3 3 7. 7. 655151321452515637 圖7有序 n18. 8. 有序序列 后綴表達式（或逆波蘭式）9. 9. 2n n1 n+110. 10. 2i+1 2i+2 (i1)/211. 11. 開放定址法 鏈接法12. 12. 快速 歸并 已知一個6180。試：（1） （1） 給出三元組線性表的順序存儲表示。 設有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4.E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。2. 2. 圖8如圖8所示。四、 四、 閱讀算法（每題7分，共14分）1. 1. int Prime(int n){ int i=1。 while (++i=x) if (n%i==0) break。 else return 0。 InitQueue(Q)。 39。 QInsert(Q,i)。 edgenode* p=GL[k]。 if(!visited[j]) { coutj39。 visited[j]=true。 } p=pnext。五、 五、 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。int high=n1。 //查找成功，返回元素的下標 else if (K[mid].key) ______________________________________。 //在右子表上繼續(xù)查找}return 1。六、 六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。 HL)參考答案四、五、 編寫算法（8分）ElemType DeleFront(LNode * amp。exit(1)。HL=HLnext。delete p。} 一、 一、 單選題（每題 2 分，共20分）1. 1. 棧和隊列的共同特點是( A )。C A．688 B．678 C．692 D．6965. 5. 樹最適合用來表示( C )。 通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結(jié)點數(shù)為__________個，樹的深度為___________，樹的度為_________。 后綴算式9 2 3 + 10 2 / 的值為__________。5. 5.在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結(jié)點分別有_______個和________個。 AOV網(wǎng)是一種___________________的圖。 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度___________。 在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 增加111. 11. 歸并 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。605078903412. 2.3. 3. E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。4. 4.amp。2. 2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 coutBTdata39。 } } 該算法的功能是： item){ if (BST==NULL) return false。//查找成功 return ___________。 else return Find(_______________,item)。六、 六、 編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 運算題（每題6分，共24分）1. 1. 線性表為：（78，50，40，60，34，90）2. 2. 鄰接矩陣： 鄰接表如圖11所示：