【正文】 9. 5；a 樹形5種aaaacccccbbbbbb10. dgbaechif 、abdgcefhi 、gdbeihfca 、 1. 5種, EBEFAECDKGHIJ 樹形5種2. 。A. n B. n(n1) C. n(n1)/2 D. 2n5．具有4個頂點的無向完全圖有____條邊。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2⑵ 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是____。 18． 。v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3 圖G的鄰接表5．已知一個有向圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是____。12．若無向圖G的頂點度數(shù)最小值大于等于 時，G至少有一條回路。(3)求出該AOE網(wǎng)的關(guān)鍵路徑。A. 相同 B. 不相同{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值82為的結(jié)點時，____次比較后查找成功。10．解決散列法中出現(xiàn)的沖突問題常采用的方法是 。4. 假設(shè)在有序線性表A[1..20]上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為____，則比較二次查找成功的結(jié)點數(shù)為____，則比較三次查找成功的結(jié)點數(shù)為____，則比較四次查找成功的結(jié)點數(shù)為____，則比較五次查找成功的結(jié)點數(shù)為____，平均查找長度為____。 綜合練習(xí)題:1. 畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為____。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù) 填空題 （將正確的答案填在相應(yīng)的空中）1. 在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較____。 綜合題1. 以關(guān)鍵碼序列（503,087,512,061,908,170,897,275,653,426），為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時的關(guān)鍵碼狀態(tài)：（1） 直接插入排序；（2） 希爾排序（增量d[1]=5）；（3） 快速排序；（4） 堆排序；（5） 歸并排序；（6） 基數(shù)排序。 （23，38，15） 3. 堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序 4. 希爾排序、選擇排序、快速排序和堆排序 5. 快速排序、基數(shù)排序 6. 堆排序、快速排序 7. 插入排序、選擇排序 8. n1。7. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用____；若初始數(shù)據(jù)基本反序，則選用____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11. 下述幾種排序方法中，要求內(nèi)存量最大的是____。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。11．在散列函數(shù)H(key)=key%p中，p應(yīng)取____。，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是____。A. 8 B. 3 C. 5 D. 9，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為____。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序，每個元素的平均查找長度為____.A. n B. n/2 C. (n+1)/2 D. (n1)/2，每個元素的平均查找長度為____。543223356abdfce5．已知AOE網(wǎng)有9個結(jié)點：V1，V2，V3，V4，V5，V6，V7，V8，V9，其鄰接矩陣如下：(1)請畫出該AOE圖。10．一個圖的 表示法是唯一的，而 表示法是不唯一的。3．在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i ]等于____。 （1）在AOE網(wǎng)中，減小一個關(guān)鍵活動上的權(quán)值后，整個工期也就相應(yīng)減??； （2）AOE網(wǎng)工程工期為關(guān)鍵活動上的權(quán)之和； （3）在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必在關(guān)鍵路徑上。① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,bbaecdf② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 圖 一個無向圖11．。 3．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的____倍。請畫出該樹。2．試編寫算法，對一棵二叉樹,統(tǒng)計葉子的個數(shù)。9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有____種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是____。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù) 填空題（將正確的答案填在相應(yīng)的空中）1. ，回答下面的問題：k1 11kkkkkk21 4356 7⑴ 這棵樹的根結(jié)點是____；⑵ 這棵樹的葉子結(jié)點是____；⑶ 結(jié)點k3的度是____； 一棵樹⑷ 這棵樹的度是____；⑸ 這棵樹的深度是____；⑹ 結(jié)點k3的子女是____；⑺ 結(jié)點k3的父結(jié)點是__ 2. 指出樹和二叉樹的三個主要差別____、____、____。A. t—＞left=NULL B. t—＞ltag=1C. t—＞ltag=1且t—＞left=NULL D. 以上都不對21. 二叉樹按某種順序線索化后，任一結(jié)點均有指向其前驅(qū)和后續(xù)的線索，這種說法____。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca12. 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊____。A. 3 B. 4 C. 5 D. 64. 按照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點的不同的二叉樹有____種。A. (rearfront+m)%m B. rearfront+1 D. rearfront13. 棧和隊列的共同點是____。C. HS= HS—＞next。C. s—＞next= HS。 A. i B. n=i C. ni+1 D. 不確定3. 棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是____。free(r)。 while(q!=L amp。 ij。amp。 6. 對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是__ __；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是__ __。s= new Node。 pnext= pnextnext；C. pnext= pnext。 B. snext=pnext。 snext=p。D. sleft=p。B. pright=s。A. 正確 B. 不正確7. 不帶頭結(jié)點的單鏈表head為空的判定條件是____。 算法設(shè)計題1. 試寫一算法,自大到小依次輸出順序讀入的三個數(shù)X,Y和Z的值.2. 試寫一算法,求出n個數(shù)據(jù)中的最大值。sum=s。s=0。 j++) A[i][j]=0。4. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 。數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題1 緒論 單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中,數(shù)據(jù)元素的① 、數(shù)據(jù)信息在計算機中的② 以及一組相關(guān)的運算等的課程。3. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 結(jié)點，其余每個結(jié)點有且只有 個直接前驅(qū)結(jié)點，葉子結(jié)點沒有 結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可以 。jn。9. 分析下面算法（程序段），給出最大語句頻度 ，該算法的時間復(fù)雜度是__ __。k++) s=s+B[i][j][k]。while (i=n) i=i*2。A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的