數據結構各章自測題及答案-資料下載頁

　　

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