【正文】 度為 。(Ａ) 233。log2(n)249。 (Ｂ) 235。 log2(n) (Ｃ) 235。 log2(n) +1 (Ｄ) 233。log2(n)+1249。注1：233。x 249。表示不小于x的最小整數(shù)；235。 x表示不大于x的最大整數(shù)，它們與[ ]含義不同！注2：選（A）是錯誤的。例如當(dāng)n為2的整數(shù)冪時就會少算一層。似乎235。 log2(n) +1是對的？（ A ）4．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。（Ａ）唯一的 （Ｂ）有多種（Ｃ）有多種，但根結(jié)點(diǎn)都沒有左孩子 （Ｄ）有多種，但根結(jié)點(diǎn)都沒有右孩子5. 【94程P11】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。樹是結(jié)點(diǎn)的有限集合，它A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m≥0）個 B 的集合T1，T2，…，Tm，每個集合又都是樹，此時結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。一個結(jié)點(diǎn)的子結(jié)點(diǎn)個數(shù)為該結(jié)點(diǎn)的 C 。供選擇的答案A： ①有0個或1個 ②有0個或多個 ③有且只有1個 ④有1個或1個以上 B: ①互不相交 ② 允許相交 ③ 允許葉結(jié)點(diǎn)相交 ④ 允許樹枝結(jié)點(diǎn)相交C： ①權(quán) ② 維數(shù) ③ 次數(shù)（或度） ④ 序答案：ABC＝1，1，36. 【95程P13】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。二叉樹 A 。在完全的二叉樹中，若一個結(jié)點(diǎn)沒有 B ，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點(diǎn)N的左子女是N在原樹里對應(yīng)結(jié)點(diǎn)的 C ，而N的右子女是它在原樹里對應(yīng)結(jié)點(diǎn)的 D 。供選擇的答案A： ①是特殊的樹 ②不是樹的特殊形式 ③是兩棵樹的總稱 ④有是只有二個根結(jié)點(diǎn)的樹形結(jié)構(gòu) B: ①左子結(jié)點(diǎn) ② 右子結(jié)點(diǎn) ③ 左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn) ④ 兄弟C～D： ①最左子結(jié)點(diǎn) ② 最右子結(jié)點(diǎn) ③ 最鄰近的右兄弟 ④ 最鄰近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟答案：A= B= C= D＝ 答案：ABCDE＝2，1，1，3四、簡答題（每小題4分，共20分）1. 【①】一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結(jié)點(diǎn)只有一個孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。第7章 圖一、單選題（每題1分，共16分） 前兩大題全部來自于全國自考參考書?。? C ）1. 在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8個結(jié)點(diǎn)的無向圖最多有 條邊。 A．14 B. 28 C. 56 D. 112 （ C ）4. 有8個結(jié)點(diǎn)的無向連通圖最少有 條邊。 A．5 B. 6 C. 7 D. 8 （ C ）5. 有8個結(jié)點(diǎn)的有向完全圖有 條邊。 A．14 B. 28 C. 56 D. 112 （ B ）6. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用 來實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹 D. 圖 （ A ）7. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時，通常是采用 來實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹 D. 圖 二、填空題（每空1分，共20分）1. 圖有 鄰接矩陣 、 鄰接表 等存儲結(jié)構(gòu)，遍歷圖有 深度優(yōu)先遍歷 、 廣度優(yōu)先遍歷 等方法。2. 有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。3. 如果n個頂點(diǎn)的圖是一個環(huán)，則它有 n 棵生成樹。 （以任意一頂點(diǎn)為起點(diǎn)，得到n1條邊）4. n個頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲，則空間復(fù)雜度為 O(n2) 。5. n個頂點(diǎn)e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為 O(n+e) 。6. 設(shè)有一稀疏圖G，則G采用 鄰接表 存儲較省空間。7. 設(shè)有一稠密圖G，則G采用 鄰接矩陣 存儲較省空間。8. 圖的逆鄰接表存儲結(jié)構(gòu)只適用于 有向 圖。9. 已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點(diǎn)出發(fā)的方法是 將鄰接矩陣的第i行全部置0 。10. 圖的深度優(yōu)先遍歷序列 不是 惟一的。11. n個頂點(diǎn)e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復(fù)雜度為 O(n2) ；若采用鄰接表存儲時，該算法的時間復(fù)雜度為 O(n+e) 。12. n個頂點(diǎn)e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復(fù)雜度為 O(n2) ；若采用鄰接表存儲，該算法的時間復(fù)雜度為 O(n+e) 。13. 圖的BFS生成樹的樹高比DFS生成樹的樹高 小或相等 。14. 用普里姆(Prim)算法求具有n個頂點(diǎn)e條邊的圖的最小生成樹的時間復(fù)雜度為 O(n2) ；用克魯斯卡爾(Kruskal)算法的時間復(fù)雜度是 O(elog2e) 。15. 若要求一個稀疏圖G的最小生成樹，最好用 克魯斯卡爾(Kruskal) 算法來求解。16. 若要求一個稠密圖G的最小生成樹，最好用 普里姆(Prim) 算法來求解。17. 用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度 遞增 的次序來得到最短路徑的。18. 拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有 0 個前驅(qū)頂點(diǎn)的過程來完成的。第8章 查找 一、填空題（每空1分，共10分）1. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 順序查找（線性查找） 。2. 線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個結(jié)點(diǎn)，用二分法查找時，最大比較次數(shù)是 7 。3. 假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8 ；平均查找長度為 。解：顯然，平均查找長度＝O（log2n）5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式來計(jì)算（即（21log221）/20＝?。?。因?yàn)檫@是在假設(shè)n＝2m1的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為＝（1＋22＋43＋84＋55）＝74； ASL＝74/20= ！??！4．【計(jì)研題2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。5. 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的查找方法是 散列查找 。6. 散列法存儲的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲地址。7. 有一個表長為m的散列表，初始狀態(tài)為空，現(xiàn)將n（nm）個不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測法。如果這n個關(guān)鍵碼的散列地址都相同，則探測的總次數(shù)是 n(n1)/2=（ 1＋2＋…＋n1） 。(而任一元素查找次數(shù) ≤n1)二、單項(xiàng)選擇題（每小題1分，共27分）（ B ）1．在表長為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長度為Ａ. ＡＳＬ＝ｎ。 Ｂ. ＡＳＬ＝（ｎ＋１）／２。 Ｃ. ＡＳＬ＝＋１。 Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2．【計(jì)研題2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50（ C ）3．【計(jì)研題2001】對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較 次關(guān)鍵字。A．3 B．4 C．5 D． 6（ A ）4. 鏈表適用于 查找A．順序 B．二分法 C．順序，也能二分法 D．隨機(jī)（ C ）5. 折半搜索與二叉搜索樹的時間性能 A. 相同 B. 完全不同 C. 有時不相同 D. 數(shù)量級都是O（log2n）11