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