【導(dǎo)讀】綱所規(guī)定的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、程序語言、軟件工程是考核的重點(diǎn)。為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大為，共中非線性結(jié)構(gòu)又可分為樹形結(jié)構(gòu)和圖結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中，線性結(jié)構(gòu)習(xí)慣稱為線性表。線性表是最簡單也是最常用的一咱數(shù)據(jù)。為0的線性表稱為空的線性表，簡稱空表。兩個(gè)相鄰結(jié)點(diǎn)ei-1和ei，稱前者是后者的前驅(qū)結(jié)點(diǎn)，后者是前者的后繼結(jié)點(diǎn)。線性表的結(jié)點(diǎn)也稱為表元，或稱記錄，要求線性表的結(jié)點(diǎn)是同一類型的任何數(shù)據(jù)。線性表的結(jié)點(diǎn)可由若干個(gè)成分組成，其中能唯一標(biāo)識表元的成分稱為了，簡稱鍵。組的第一個(gè)元素開始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在數(shù)組中。儲(chǔ)來體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。其最大優(yōu)點(diǎn)是能直接訪問線性表中的任。棧是只允許在同一端進(jìn)行插入和刪除運(yùn)算的線性表。習(xí)慣稱插入棧的結(jié)點(diǎn)為進(jìn)棧，刪除棧的結(jié)點(diǎn)為出棧。二叉樹，分別簡稱為左子樹和右子樹。子樹是有序的，分左、右兩棵子二叉樹。一般情況下，二叉樹常采用類似樹的標(biāo)

　　

【正文】 帶權(quán)的總和，而 不是路 徑上邊數(shù)的總和。關(guān)鍵路徑是指兩個(gè)結(jié)點(diǎn)間具有的最大長度的路徑。通過計(jì)算可知， (V1， V2， V5， V7， V8)是最短路 徑， (V1， V6， V5， V3， V8)是 【答案】 A： ⑦ B： ③ C： ② D： ④ E： 試題 11(1992 年 試題 從供選擇的答案中選出應(yīng)填入 { }內(nèi)的正確答案，把編號寫在答卷的對應(yīng)欄內(nèi)。 在 內(nèi)排序的過程中，通常需要對待排序的關(guān)鍵碼集合進(jìn) 行多遍掃描。采用不同排序方法，會(huì) 產(chǎn)生不同的排序中間結(jié)果。設(shè)要將序列＜ Q， H， C， Y， P， A， M， S， R， F， X＞中的 關(guān)鍵碼按字母的升序重新排列，則 A 是冒泡排序一趟 掃描的結(jié)果， B 是初始步 長為 4的希 爾 (Shell)排序一趟 掃描的結(jié)果， C是 兩路歸并 (合并 )排序一趟 掃描的結(jié)果， D 是以第一 個(gè)元素為分界元素的快速排序一趟掃描的結(jié)果， E 是堆排序初始建堆的 供 A～ E： ① F， H， C， D， P， A， M， Q， R， S， Y， ② P， A， C， S， Q， D， F， X， R， H， M， ③ A， D， C， R， F， Q， M， S， Y， P， H， ④ H， C， Q， P， A， M， S， R， D， F， X， ⑤ H， Q， C， Y， A， P， M， S， D， R， F， 【解析】 冒泡排序 將待排序的記錄順次兩兩比較，如為逆序則進(jìn)行交換，將待排序序列依此法從頭至尾處理一遍稱作一趟冒泡，一趟冒泡的效果是將關(guān)鍵碼值最大的元素 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 29 頁 共 34 頁 交換到了最后位置。對于試題給定的序列，經(jīng)一趟冒泡后變成序列＜ H， C， Q， P，A， M， S， R， D， F， X， Y＞。 希 爾排序也是一種插入排序，其特點(diǎn)是把待排序序列每隔某個(gè) 步 長 的元素 組成一個(gè)子序 列，分 別對每個(gè)子序列進(jìn)行直接插入排序， 排序后的結(jié)果稱為一趟掃視。每趟減少相隔步長 ，直至步 長為 1， 對整個(gè)序列作一次掃視。對于試題給定的序列，取初始步為 4，希 爾排序一 趟 掃視后，將序列變成為＜ P， A， C， S， Q， D， F， X， R， H， M， Y＞。 兩路歸并排序是一種最簡單的歸并排序，它將含 n 個(gè)元素的待排序序列看作 n個(gè)已排序的子序 列。首先 將每兩個(gè)子序列歸并，得到 n/2 個(gè)已排序的較大的子序列；再對這些子序列歸并， 如此反復(fù)，直到最后 歸并成一個(gè)序列，排序即告完成。由上述兩路歸并的方法 可知， 對于試 題所給的序列，經(jīng)兩路歸并排序的一趟掃描后，序列變成＜ H， Q， C， Y， A， P，M， S， D， R ， F， X＞。 快速排序的基本思想是通 過一趟掃視將待排序序列分成兩個(gè)子序列，然后分別對這兩個(gè)子序 列 進(jìn)行排序，如此重復(fù)，以達(dá)到最后對整個(gè)序列的排序。具體方法是：任選待排序序列中的 某元素 (通常 選第一個(gè)元素 )，用它的 關(guān)鍵碼同 (子 )序列中所有其余元素的 關(guān)鍵碼相比較，將 所有 關(guān)鍵碼仍比它小的元素移到它之前，所有關(guān)鍵碼較它大的元素都移到它之后。經(jīng)這樣一 趟 掃視后，以該元素為界，將 (子 )序列分成 兩個(gè)子序列。反復(fù)對上述子序列作同樣的操作， 直至每 個(gè)子序列都只有一個(gè)元素為止。對試題給 定的序列，以它的第一個(gè)元素為分界元素作 一次劃分，使序列都只有一 個(gè)元素為止。對試題給定的序列，以它的第一個(gè)元素為分界元素 作一次劃分，使序列 變成＜ F， H， C， D， P， A， M， Q， R， S， Y， X＞。 堆 h1,h2,… ， hn. hi≤h2i ， hi≤h 2i+1， (i=1， 2， … ， ［ n/2］ 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 30 頁 共 34 頁 則稱該序列是一個(gè)堆。即子樹根結(jié)點(diǎn) hi，其 關(guān)鍵碼值比它的左、右子結(jié)點(diǎn)h2i(2i≤n) 和 h2i+1(2i+1≤n) 的 堆排序的基本思想 如下：由于堆的根 結(jié)點(diǎn)的關(guān)鍵碼值是最小的，取走根結(jié)點(diǎn)，讓剩下的其余 結(jié)點(diǎn)重新建成堆，則能從新堆的根結(jié)點(diǎn)取走次最小的。如此反復(fù)，得到一個(gè)遞增的排序序列 。堆排序的基本 問題是如何建堆，建立初始堆的方法是首先將第 1 個(gè)至第 n個(gè)結(jié)點(diǎn)分別看作是 只有一 個(gè)結(jié)點(diǎn)的堆，然后逐步把結(jié)點(diǎn)第［ n1］個(gè)、第［ n/2］ 1個(gè)…第 1個(gè)結(jié)點(diǎn)，分別加到 它 對于試題給定的序列，經(jīng)上述初始建堆步驟后，序列變成＜ A， D， C， R， F， Q，M， S， Y， P ， H， X＞。 【答案】 A： ④ B： ② C： ⑤ D： ① E： 試題 12(1991 年 試題 從下列敘述中選出 5條正確的敘述，把編號依次寫在答卷的 A～ E ① m 階 B樹每一個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)都小于等于 m。 ② m 階 B樹每一個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)都大于等于［ m/2 ③ m 階 B樹具有 k個(gè)后件的非葉子結(jié)點(diǎn)含有 k1 ④ m 階 B ⑥用指針的方式存儲(chǔ)一棵有 n個(gè)結(jié)點(diǎn)的二叉樹，最少要 n+1 ⑦任一查找樹的平均查找時(shí)間都小于用順序查找法查找同樣結(jié) 點(diǎn)的線性表的平均查找時(shí)間。 ⑨已知樹的前序遍歷并不能唯一地確定這棵樹，因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一 【解析】 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 31 頁 共 34 頁 m階 B樹是一種平衡的 m 叉 (1)每 個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)小于等于 m； (2)除了根 結(jié)點(diǎn)和葉結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的后件個(gè)數(shù)大于等于 (m/2)； (3)具有 k 個(gè)后件的非葉結(jié)點(diǎn)含有 k1 (4)所有 m階 B樹是平衡樹，其上任一結(jié)點(diǎn)的所有子樹的高度都是相 具有下列性 質(zhì)的二叉樹稱為查找樹：除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的鍵值大于其左子樹上一切結(jié)點(diǎn) 的 中序遍 歷法訪問二叉樹結(jié)點(diǎn)的過程是：遞歸地訪問左子樹，然后訪問樹根，再訪問右子樹。 因此，用中序遍 歷法遍歷一棵二叉查找樹可以得到按鍵值升序排列的結(jié)點(diǎn)序列。在用鏈接表 表示法存 儲(chǔ) n 個(gè)結(jié)點(diǎn)的二叉樹上，最多有 2n 個(gè)指針，其中 n+1 個(gè)是空指針， n1個(gè)指針用于指 向后件。因此，最少要 n+1 在 給定的查找樹上，由根結(jié)點(diǎn)到所有其他結(jié)點(diǎn)的路徑長度總和稱為內(nèi)部路徑 長度。當(dāng)一棵二 叉 樹退化為線性鏈表時(shí)，它的內(nèi)部路徑長度最大，等于 n(n1)/2，所以退化二叉 樹的查找時(shí) 間 (包括平均查找 時(shí)間 )等于 具有最小 內(nèi)部路徑長度的樹是豐滿樹，對豐滿樹的查找樹進(jìn)行插入或者刪除操作后，會(huì)產(chǎn)生 一棵非豐 滿樹。平衡二叉樹是指其上任一結(jié)點(diǎn)的左右子樹的高度 (或者 結(jié)點(diǎn)個(gè)數(shù) )保持一定比 例的 樹，即平衡樹上任一結(jié)點(diǎn)的左、右子樹仍然保持平衡。平衡樹的查找效率和豐滿樹相近 ，但是在插入或者 刪除結(jié)點(diǎn)時(shí)容易產(chǎn)生仍保持平衡的樹。由豐滿樹同平衡樹定義可知，豐滿 樹一定是 用前序遍 歷法訪問一棵樹的原則是：遞歸地訪問樹根，然后訪問左子樹，再訪問右子樹。因 此，前序遍 歷第一個(gè)被訪問的結(jié)點(diǎn)就是原樹的根結(jié)點(diǎn)， 不知道 樹的根結(jié)點(diǎn) 的 說法是錯(cuò)誤 的。二叉 樹的前序、中序和后序遍歷法都是遞歸的。因此，最適合使用遞歸程序 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 32 頁 共 34 頁 方法實(shí)現(xiàn)這 3種遍 歷算法。當(dāng)然不用遞歸程序方法也能夠?qū)崿F(xiàn)這 3 種遍 歷算法，但是程序比較復(fù)雜，一般 需要用 【答案】 A： ① B： ③ C： ④ D： ⑤ E 試題 13(1990 年 試題 從供選擇的答案中選出應(yīng)填入下列敘 述中的 { }內(nèi)的正確答案，把編號寫在答案 在查找算法，可用平均查找 長度 (記為 ASL)來衡量一個(gè)查找算法的優(yōu)劣，其定義 此 處 Pi 為表中第 i 個(gè)記錄被查找的概率， Ci 為查找第 i 個(gè)記錄時(shí)同關(guān)鍵字比較的次數(shù)， n 為表 中表有 以下 敘述中均假定每一個(gè)記錄被查找的概率相等，即 Pi=1/n(i=1， 2， … ， n)。 當(dāng)表中 的記錄連續(xù)存儲(chǔ)備在一個(gè)一維數(shù)組中時(shí)，可采用順序查找與折半查找方法(折半查找 要求表是按 關(guān)鍵字有序排列的 )。 順序查找時(shí)的 ASL 為 A，折半查找 時(shí)的 ASL 為 B。記錄的關(guān)鍵 字有序 時(shí)，用二叉排序樹查找記錄，在最壞的情況下， ASL 為 C。 當(dāng)二叉排序樹是一棵平衡樹 時(shí)， ASL 為 D。在平衡 樹上刪除一個(gè)結(jié)點(diǎn)后可以通過旋轉(zhuǎn)使其平衡，最壞的情形下需 E 次旋 轉(zhuǎn) 。 供 A～ E： ① O(1) ② O(lon2n) ③ O(lon2n)2 ④ O(nlog2 ⑤ O(n) ⑥ O(n2 【解析】 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 33 頁 共 34 頁 順序查找：比較一次可查到 第 1 個(gè)元素，比較兩次可查到第 2個(gè)元素。一般地，比較 i 次可查 到第 i 順序查找的 ASL 為： ASL=（ 1/n） 折半查找：比 較一次可找到一個(gè)元素；比較兩次可找到兩個(gè)元素；一般地，比較i次可找到 2 i1 個(gè)元素。總共 n 個(gè)元素，最多需比較 log2(n+1)次。 折半查找的 ASL 為： 而 歸納法不難證明： 將此式入上式，折半查找的 ASL 為： ASL=1/n(n+1)(log2(n+1)+1)=1/n(n+1)log2(n+1)1 =O(log2 對于二叉排序樹的查找，最壞情況是二叉樹中沒有結(jié)點(diǎn)，有兩棵子樹。在這種情況下，二叉 排序 樹查找相當(dāng)于順序查找，即最壞情況下， ASLA 為 ASL=O(n)。 對于平衡的二叉排序樹查找，平衡二叉排序樹中的每個(gè)結(jié)點(diǎn)的左右子樹高度差不大于 1， n 個(gè) 結(jié)點(diǎn)的平衡樹的深度和 log2n 是同 數(shù)量級。對二叉排序樹來說，它的查找時(shí)間與樹的深度成 正比。因此，平衡二叉排序 樹的 ASL 為 ASL=O(log2n)。 在平衡 樹上刪除或插入結(jié)點(diǎn)往往會(huì)破壞樹的平衡。通過旋轉(zhuǎn)又可使其重新成為一棵平衡樹。 在最壞情 況下，從葉子開始一直調(diào)整到根為止，需進(jìn)行的旋轉(zhuǎn)次數(shù)與樹的深度一致，等于 O( log2n)次。 【答案】： A： ⑤ B： ② C： ⑤ D： ② E 中國 最龐大的下資料庫 (整理 . 版權(quán)歸原作者所有 ) 第 34 頁 共 34 頁 試題 14 (1990 年 試題 從供選 擇的答案中選出應(yīng)填入下列敘述中的 { }內(nèi)的正確答案，把編號寫在答卷 設(shè) T 是正 則二叉樹，它具有 6 片 樹葉，那么樹 T 的高度最多可以是 A；最小可以是 B； 樹 T 的 內(nèi)結(jié)點(diǎn)數(shù)是 C；如果 T 又是哈夫曼 (Huffman)最優(yōu) 樹，且各片樹葉的權(quán)分別是 6， 則最優(yōu)樹 T的非 樹葉的權(quán)之和是 D； 權(quán)為 1的 樹葉的高度是 E。 (注： 樹的根結(jié)點(diǎn)高度為 供 A、 B、 C、 E： ① 7 ② 5 ③ 6 ④ 4 ⑤ D： ① 27 ② 30 ③ 45 ④ 51 ⑤ 【解析】 這里要注意正則樹的概念，所謂正則二叉 樹，就是每個(gè)非葉結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。根據(jù)這個(gè) 原 則，我們用下面的 26(a)、 26(b)、 26(c) 【答案】： A： ③ B： ④ C： ④ D： ④ E②