【正文】 ∝∝∝∝∝∝∝∝∝習 題 八 查 找 單項選擇題1. 順序查找法適合于存儲結構為_B___的線性表。V1v2v3v4 ^v5v6 ^V2V5V4 ^v3V5 ^V4V6V3 ^V6 ^ 圖G的鄰接表5. 已知一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是____。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2⑵ 根據有向圖的寬度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是__B__。A. n B. n(n1) C. n(n1)/2 D. 2n4. 具有4個頂點的無向完全圖有__A__條邊。使用07的二進制表示形式是另一種編碼方案。11. ，回答以下問題：⑴ 其中序遍歷序列為_dgbaechif__；⑵ 其前序遍歷序列為___ abdgcefhi_；⑶ 其后序遍歷序列為_gdbeihfca___；⑷ 該二叉樹的中序線索二叉樹為___ _；⑸ 該二叉樹的后序線索二叉樹為____；⑹ 該二叉樹對應的森林是____。4. 一棵二叉樹的結點數據采用順序存儲結構，存儲于數組t中，則該二叉樹的鏈接表示形式為____。A. 有序數據元素 B. 無序數據元素 C. 元素之間具有分支層次關系的數據 D. 元素之間無聯(lián)系的數據20. 任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序_A___。A. 正確 B. 錯誤14. 按照二叉樹的定義，具有3個結點的二叉樹有__C__種。A. 正確 B. 錯誤7. 設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為__B__。2. ，__B_是平衡二叉樹。A. acbed B. decab C. deabc D. cedba10．設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前的條件是 B 。這里，我們把由樹轉化得到的二叉樹叫做這棵數對應的二叉樹。A. n=h+m B. h+m=2n C. m=h1 D. n=2 h123. 如果某二叉樹的前序為stuwv，中序為uwtvs，那么該二叉樹的后序為_C___。6. 在一棵二叉樹中，度為零的結點的個數為n 0，度為2的結點的個數為 n 2，則有n0=_n2+1___。 算法設計題:1．試編寫算法，對一棵以孩子兄弟鏈表表示的樹統(tǒng)計葉子的個數。請畫出該樹。A. n B. n+1 C. n1 D. n/27. 對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是__D__。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13. 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用___D_。2．請用克魯斯卡爾普里姆兩種算法分別構造最小生成樹： badcef（1） 16 11 15 15 15 13 16 14 12 21（2）12637546121321249520151610 3. 試列出下圖中全部的拓撲排序序列。A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)5. 有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值82為的結點時，___C_次比較后查找成功。2. 二分查找的存儲結構僅限于__順序存儲__，且是___有序的_。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4. 一組記錄的關鍵字為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12. 快速排序方法在_C___情況下最不利于發(fā)揮其長處。(2)(12,70,33,65,24,56,48,92,86,33)(3)(103,97,56,38,66,23,42,12,30,52,06,20)(4)(05,56,20,23,40,38,29,61,35,76,28,100).17