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