【正文】 20. B 21. B 22. B 23. B 24. A 25. C 1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 ⑺ k1 eaEfjcdlghb2. 樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為1(不同教材規(guī)定不同)，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以為0；樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)點(diǎn)的最大度數(shù)為2；樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的結(jié)點(diǎn)有左、右之分；3. 樹(shù)可采用孩子兄弟鏈表（二叉鏈表）做存儲(chǔ)結(jié)構(gòu)，目的并利用二叉樹(shù)的已有算法解決樹(shù)的有關(guān)問(wèn)題。3. （左）所示；（右）所示；。6. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹(shù),可能達(dá)到的最大深度 h=Nk+1 ，最小深度各為: logkN+1。A. 1/2 B. 1 C. 2 D. 4 2．任何一個(gè)無(wú)向連通圖的最小生成樹(shù) 。A. 1/2 B. 1 C. 2 D. 44．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有____條邊。A. 6 B. 12 C. 16 D. 206．具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有____條邊才能確保是一個(gè)連通圖。A. n B. n+1 C. n1 D. n/28．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是____。① A. n B. n+1 C. n1 D. n+e② A. e/2 B. e D. n+e 10．，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)_①__；按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)_②__。12345324524^^^^^ 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)⑴ 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是____。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212．采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的____。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷14．判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用____。 16．下面不正確的說(shuō)法是 。A.（1） B.（2） C.（3） D.（1）、（2）17．用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是 。 19．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)為 。 +k221．對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的入度為k1,、出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為 。2．在無(wú)權(quán)圖G的鄰接矩陣A中，若(vi,vj)或＜vi,vj＞屬于圖G的邊集合，則對(duì)應(yīng)元素A[i][j]等于____，否則等于____。4．，其從頂點(diǎn)v1出發(fā)的深度有限搜索序列為_(kāi)___，其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為_(kāi)___。6．已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是____。8．一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有 個(gè)頂點(diǎn)。BFS遍歷圖的時(shí)間復(fù)雜度為 ，DFS遍歷圖的時(shí)間復(fù)雜度為 ，兩者不同之處在于 ，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是 。11．有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特征是 。13．根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是 的。圖7。1234564．。(2)計(jì)算完成整個(gè)計(jì)劃需要的時(shí)間。∝645∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝習(xí)題答案 1. C 4. C 5. A 6. A 9. AC 11. CB 12. A 13. D 2. 1。10．鄰接矩陣 鄰接表11．一個(gè)結(jié)點(diǎn)可能有若干個(gè)前驅(qū)，也可能有若干個(gè)后繼12．213．唯一156243 1.2.badce1115131412f (1)．612495106154372（2） 3．152364152634156234561234516234512634512364W=3W=7W=9W=6W=543233abdfce4．5．(1)該AOE圖為：(2)完成整個(gè)計(jì)劃需要18天。A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈接存儲(chǔ)C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)，要求線性表必須____。A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)。A. 1 B. 2 C. 4 D. 8=14，哈希函數(shù)H(key)=key%11。 addr (38)=5。 addr (84)=7如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是____。A. 35/12 B. 37/12 C. 39/12 D. 43/129．對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為 。、除余法、平方取中法、除余法、線性探測(cè)法、線性探測(cè)法、多重散列法、多重散列法、鏈地址法11．采用線性探測(cè)法解決沖突問(wèn)題，所產(chǎn)生的一系列后繼散列地址 。這種方式主要適合于 。 填空題（將正確的答案填在相應(yīng)的空中）；折半查找法的平均查找長(zhǎng)度為_(kāi)___；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為_(kāi)___。，且是____。5. 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_(kāi)___；若采用折半法查找，則時(shí)間復(fù)雜度為_(kāi)___；6．已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半查找90時(shí)，需進(jìn)行 次查找可確定成功；查找47時(shí)，需進(jìn)行 次查找成功；查找100時(shí)，需進(jìn)行 次查找才能確定不成功。8．一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵 樹(shù)而變成一個(gè)有序樹(shù)，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。10． 法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。12．在散列存儲(chǔ)中，裝填因子的值越大，則____；的值越小，則____。4. 選取哈稀函數(shù)H（k）=（3k）MOD 11。5. 已知一組關(guān)鍵字{49，38，65，97，76，13，27，44，82，35，50}，畫(huà)出由此生成的二叉排序樹(shù)，注意邊插入邊平衡。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用____排序法。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4. 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為_(kāi)___。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為_(kāi)___。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序8. 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為_(kāi)___。A. 選擇排序 B. 希爾排序 C. 歸并排序 D. 快速排序10. 下述幾種排序方法中，平均查找長(zhǎng)度最小的是____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12. 快速排序方法在____情況下最不利于發(fā)揮其長(zhǎng)處。2. 在利用快速排序方法對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為_(kāi)___，共需遞歸調(diào)用的次數(shù)為_(kāi)___，其中第二次遞歸調(diào)用是對(duì)____一組記錄進(jìn)行快速排序。4. 在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有____。6. 在堆排序和快速排序中，若原始記錄接近正序或反序，則選用____，若原始記錄無(wú)序，則最好選用____。8. 對(duì)n個(gè)元素的序列進(jìn)行起泡排序時(shí)，最少的比較次數(shù)是____。2. 判別以下序列是否為堆（小頂堆或大頂堆）。(1）(100,86,48,73,35,39,42,57,66,21)