【文章內容簡介】 結果就是題中問題 E 的 答案 【答案】： A： ③ B： ③ C： ② D： ① E： 試題 3(1999 年 試題 從供選擇的答案中，選出應填入下面敘述中 { }內的最確切的解答，把相應編號 給定數(shù)據(jù)結構 (V， E)， V為結點的有限集合， V={V1， V2， V3， V4， V5， V6， V7，V8}， E 是 V 上 E={＜ V1， V2＞，＜ V3， V4＞，＜ V5， V8＞，＜ V6，＜ V1， V3＞， V4＜， V5＞，V6＜，＜ V1 ， V3＞， V4＜， V5＞，＜ V2， V4＞， V4＜， V6＞＝它所 對應的圖表是 { A }， 這就是 { B }。 圖的存儲 結構主要有鄰接表和 { C }，若用 鄰接表來存儲一個圖，則需要保存一個 { D }存 儲的結點表和若干個 { E }存 儲的關系 (又 稱邊表 )。 供 A： B： ①樹 ②無向圖 ③有向圖 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 15 頁 共 34 頁 C： ①轉稱矩陣 ②鄰接矩陣 ③狀態(tài)矩陣 D： ①順序 ②鏈接 ③散列 【解析】 本 題是一道關于圖的試題，應該說是比較簡單的 在 數(shù)據(jù)結構 (V， E)中，有 關系＜ V1， V2＞和＜ V1， V3＞， 這樣很快就答案案③和④排除了， 然后再看答案 ①②。在數(shù)據(jù)結構 (V， E)中， 還有關系＜ V2， V4＞， 這在答案②中沒有反映出 來，所以又排除了答案②。既然確定了答案①就是正確的答案，仔細觀察該圖形，由于關系 ＜ V1， V2＞、＜ V1， V3＞、＜ V2， V4＞，＜ V3， V4＞以及 關系＜ V4， V6＞、＜ V6，V5＞、＜ V4， V5＞的特殊性，我 們排除了該圖是樹、有向圖、無回路圖的可能性，數(shù)據(jù)結構 (V， E)是 圖的存儲結構主要有鄰接表和鄰接矩兩種 。鄰接矩陣是表示結點間的相鄰關系的矩陣，若 G 是一 個具有 n 個結點的圖，則 G 的 臨界陣是如下定義的 nn 矩 A［ ij］ =0，表示 (Vi， Vj)或者 (Vj， Vi)是 G 的 A［ ij］ =1，表示 (Vi， Vj)或者 (Vj， Vi)不是 G 的 用 鄰接表來存儲一個圖，需要保存一個順序存儲的結點表和 n個鏈接存儲的邊表。結點表的 每 個表目對應于圖的一個結點，每個表目包括兩個字段：一個是結點的數(shù)據(jù)或指向結點數(shù)據(jù) 的指 針，另一個是指向此結點的邊表的指針。圖的每一個結點都有一個邊表，一個結點的邊 表的每 個表目對應于與該 結點相關聯(lián)的一條邊。它的每個表目也包括兩個字段：一個是與此 相 邊相關聯(lián)的另一個結點的序號，另一個是指向邊表的下一個表目的指針。對于有向圖來說 ，用 【答案】： A： ① B： ② C： ② D： ① E： 試題 4(1998 年 試題 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 16 頁 共 34 頁 從供選擇的答案中，選出應填入下面敘述中 { }內的最確切的答案，把相應編號 在 內部排序中，通常要對被排序數(shù)據(jù)序列進行多趟掃描。各種排序方法有其不同的排序實施 過程和 (時間 )復 對給定的整數(shù)序列 (541， 132， 984， 746， 518， 181， 946， 314， 205， 827)進行從小到大的 排序 時，采用冒泡排序和直接選擇排序時，若先選出大元素，則第一趟掃描結果分別是 { A }和 { B }；采用快速排序 (以中 間元素 518 為基準 )的第一趟 掃描結果是 { C }。 設被排序數(shù)據(jù)序列有 n 個元素，冒泡排序和直接選擇排序的復雜性是 { D }；快速排序的復 雜性是 { E }。 供 A～ C： ① (181， 132， 314， 205， 541， 518， 946， 827， 746， ② (541， 132， 827， 746， 518， 181， 946， 314， 205， ③ (205， 132， 314， 181， 518， 746， 946， 984， 541， ④ (541， 132， 984， 746， 827， 181， 946， 314， 205， ⑤ (132， 541， 746， 518， 181， 946， 314， 205， 827， ⑥ (132， 541， 746， 984， 181， 518， 314， 946， 205， D、 E： ① O(nlog2n) ② O(n) ③ (nc) ④ O(n2 ⑤ O(log2n)2 ⑥ O(n2log2 【解析】 冒泡排序：冒泡排序的 過程很簡單。首先將第 1 個數(shù)與第 2個數(shù)相比較，若為逆序則交換兩數(shù) ，然后比 較每兩個數(shù)與第 3個數(shù)，依次類推，直到第 n1 個數(shù)與第 n個數(shù)進行過比較為止。上 述 過程稱為一趟冒泡排序，結果是最大的數(shù)被稱鮐了最后。然后進行第 2 趟， 對前面 n1個數(shù) 進行冒泡排序，結果是次大的數(shù)被移到了 n1的位置上。一般 來說，第 i 趟冒泡排序是 從第 1 個數(shù)到第 ni+1 的位置上，整 個排序過程需進行 k(1≤k≤n) 趟。 分析冒泡排序的效率，若初始序列 為正序，則只進行一次排序。在排序過程中只進行 n1次 比 較，不交換數(shù)據(jù)。若為逆序，則需進行 n1 趟排序，需 進行 n(n1)/2 次比 較，交換數(shù)據(jù)的數(shù)量組也相同。因此，冒泡排序的復雜性是 O(n2)。 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 17 頁 共 34 頁 快速排序是 對冒泡排序的一種改進，其基本思想是通過一趟排序將待排序的數(shù)據(jù)分成兩部分 ，其中一部分的 關鍵字均比另一部分的關鍵字小，然后再對這兩部分分別進行快速排序，最 后 達到整個序列有序?？焖倥判虻膹碗s是 O(nlog2n)。 直接 選擇排序，又稱簡單選擇排序，其基本思想是每一趟在 ni+1(i=1， 2， … ，n1)個數(shù)據(jù) 中 選擇最小的數(shù)據(jù)作為有序序列中的第 i 個 數(shù)據(jù)。一趟直接選擇排序的基本操作為通過 ni次 關鍵字的比較，從 ni+1 個數(shù)據(jù)中選出關鍵字最小的數(shù)據(jù)，并和第 i 個數(shù)據(jù)交換。直接選擇排 序 過程中，所需交換數(shù)據(jù)的次數(shù)較少，最小值為 0，最大值 為 3(n1)。然而，無論數(shù) 據(jù)的初始次序如何，它所需 進行的關鍵字的比較次數(shù)相同，均為 n(n1)/2，因此，直接 選擇 排序的復 雜性是 O(n2)。 對于題中給定的整數(shù)序列 (541， 132， 984， 746， 518， 181， 946， 314， 205， 827)進行從小 到大排序，若先 選出較大的元素，則對于冒泡排序，第 1 趟操 作 為 541←→132 ，984←→746 ， 984←→518 ， 984←→181 ， 984←→946 ， 984←→314 ， 984←→205 ， 984←→827 ，其 結果 得到的序列 為 (132， 541， 746， 518， 181， 946， 314， 205， 827， 984)； 對于直接選擇排序 ，第 1 趟操作 為 984←→827 ，其 結果得到的序列為 (541， 132， 827， 746， 518，181， 946， 3 14， 205， 984)。 采用快速排序 (以中 間元素 518 為基準 )的第 1趟 掃描結果是 (205， 132， 314， 181，518， 746 ， 946， 984， 827)。 【答案】： A： ⑤ B： ② C： ③ D： ④ E： 試題 5(1997 年 試題 從供選擇的答案中，選出應填入下面的敘述中 { }內的最確切的解答，把相應編號寫在答卷 的 設數(shù)據(jù)結構 (D， R)由 數(shù)據(jù)結點集合 D={di|1≤i≤7} 及其上的 關系 R R={＜ di1， d|di1， di∈D ， 2≤i≤7} ， 這個數(shù)據(jù)結構對應于 A。 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 18 頁 共 34 頁 R={＜ d4， d2＞， d1＞，＜ d2， d3＞，＜ d4， d6＞，＜ d6， d5＞，＜ d6， d7＞ }， 這個結構的圖形是 B， 用 C 遍 歷法可以得到 A 的 R={＜ d1， d2＞，＜ d1， d3＞，＜ d2， d4＞，＜ d4， d5＞，＜ d4， d5＞，＜d4， d6＞， ＜ d4， d7＞ }， 這個結構的圖形是 D。用 E 遍 歷法可以得到 A 的 供 A、 B、 D： ①二叉樹 ②隊列 ④線性表 ⑤無向圖 C、 E： ①前序 ②中序 ④深度優(yōu)先 【解析】 該題要求考生熟練掌握數(shù)據(jù)結構中常用的線性表、二叉樹、樹、圖的結構及其遍歷方法。數(shù) 據(jù) 結構 (D， R)中， D 由 7個數(shù)據(jù)組成， R決定這 7 (1)R={＜ di1， d|di1， di∈D ， 2≤i≤7 } 其 對應的數(shù)據(jù)結構可以表示為 d1→d2→d3→d4→d5→d6→d7 ，它 對應一個線性表。 (2)R={＜ d4， d2＞，＜ d2， d1＞，＜ d2， d3＞，＜ d4， d6＞，＜ d6， d5＞，＜ d6，d7＞ 其 這棵 二叉樹利用中序遍歷法得到序列為 d1d2d3d4d5d6d7。 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 19 頁 共 34 頁 (3)R={＜ d1， d2＞，＜ d1， d3＞，＜ d2， d4＞，＜ d3， d4＞，＜ d4， d5＞，＜ d4，d6＞，＜ d4， d7＞ }， 對應的數(shù)據(jù)結構為一個有向無回路圖，利用廣度優(yōu)先遍歷法得到的序列為 d1d2d 3d4d5d6d7，正好 對應 (1)中的 【答案】： A④ B① C② D⑥ E 試題 6(1996 年 試題 從供選擇的答案中，選出應填入下面敘述中 { }內的最確切的解答，把相應編號寫在答卷的 一棵二叉排序 樹可順序存放在一組物理上相鄰的存儲區(qū)中，每個結點及左、右針依次分別放 在 該存儲區(qū)的 3 個連續(xù)單元中?，F(xiàn)對一棵結點按字母的字典順序構成的二叉排序樹從根結點 P 開始順序放在一個存儲區(qū)中，結果如圖 22所示。其中 Li 為第 i個結點的左指針， R為第 i 個結點的右指針，則 L2 應為 A， L4 應為 B， R1 應為 C。 該二叉排序樹的前序遍歷序列為 D，后序遍 歷序列為 E。 供 中國 最龐大的下資料庫 (整理 . 版權歸原作者所有 ) 第 20 頁 共 34 頁 A～ C： ① 1003 ② ③ 100A… ④ ⑤ 1006 ⑥ ⑦ 100C ⑧ ⑨ D、 E： ① PBQHCJ ② ③ BCHJPQ ④ CJHBQP ⑤ 【解析】 二叉 樹或者為空，或者由一個根結點加上左子樹和右子樹 (互不相交的 兩棵二叉樹 )構成，因 此，若依次 遍 歷根、左子樹、右子樹，就有 6種遍 歷方法，即 DLR、 DRL、 LDR、RDL、 LRD 和 RL D。限定先左后右的 順序，則有常用的前序遍歷、中序遍歷和后序遍歷 3種情 況。 基于二叉 (1)先序遍 歷 (DLR)算法：若二叉 樹為空，則進行的是空操作，否則訪問根結點： 前序遍 前序遍 (2)中序遍 歷 (LDR)算法：若二叉 樹為空，則進行的是空操作，否則 中序遍