【正文】 子結(jié)點(diǎn)的指針數(shù)組。一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目，稱為結(jié)點(diǎn)的度。由于它呈現(xiàn)出與自然 界的樹(shù)類似的結(jié)構(gòu) 形式，所以 稱它為樹(shù)。字符串所 包含的有效字符數(shù)稱為字符 串 樹(shù)和二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，用它們能很好地描述有分支和層次特性的數(shù)據(jù)集合。多維數(shù)組的所有元素并未排 在一 個(gè)線性序列里，要順序存儲(chǔ)多維數(shù)組就需要按一定次序把所有的數(shù)組元素排在一個(gè)線性 序列里，常用的排列次序有行優(yōu)先 順序和列優(yōu)先順序兩種。數(shù)組由固定個(gè)數(shù)的元素組成，全部元素的類型相同，元素依次順序存儲(chǔ)。習(xí)慣稱插入隊(duì)列結(jié)點(diǎn)為進(jìn)隊(duì)，刪除隊(duì)列結(jié)點(diǎn)為出隊(duì)。習(xí)慣稱插入棧的結(jié)點(diǎn)為進(jìn)棧，刪除棧的結(jié)點(diǎn)為出棧。從鏈表的第一個(gè)表元開(kāi)始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在鏈表的各表元中。如查找運(yùn)算就有兩種，一種是查找線性表中某個(gè)結(jié)點(diǎn)的值， 有多種存 儲(chǔ)方式能將線性表存儲(chǔ)在計(jì)算機(jī)內(nèi)，其中最常用的是順序存儲(chǔ)和鏈接存 (1) 線性表的順序存儲(chǔ)是最簡(jiǎn)單的存儲(chǔ)方式。線性表的結(jié)點(diǎn)可由若干個(gè)成分組成，其中能唯一標(biāo)識(shí)表元的成分稱為了，簡(jiǎn)稱鍵。 線性表的結(jié)點(diǎn)個(gè)數(shù)稱為線性表的長(zhǎng)度，長(zhǎng)度為 0 的 線性表稱為空的線性表，簡(jiǎn)稱空表。其中， A 是 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù) (稱為結(jié)點(diǎn) )的非空有限集合， R 是定 義在 A 上的 關(guān)系的非空有限集合。 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 1 頁(yè) 共 34 頁(yè) 第二章 高 級(jí)程序員級(jí)軟件基礎(chǔ)知識(shí)試題覆蓋面寬，有一定的理論深度，需要考生全面系統(tǒng)地掌握大 綱所規(guī)定的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯關(guān)系的不同分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大為，共中非線性結(jié)構(gòu)又可分為樹(shù)形結(jié)構(gòu)和圖結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)又可分為樹(shù)結(jié)構(gòu)和二叉樹(shù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，線性結(jié)構(gòu)習(xí)慣稱為線性表。對(duì)于非空線性表， e0是 線性表的第一個(gè)結(jié)點(diǎn)， en1是 線性表的最后一個(gè)結(jié)點(diǎn)。 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 2 頁(yè) 共 34 頁(yè) 線性表包含的表元個(gè)數(shù)可以動(dòng)態(tài)增加或減少，可以在任何位置插入或刪除表元。程序通常使用一個(gè)足夠在的數(shù)組，從數(shù)組的第一個(gè)元素開(kāi)始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在數(shù)組中。鏈表的每個(gè)表元除了要存儲(chǔ)線性表結(jié) 棧是只允許在同一 端進(jìn)行插入和刪除運(yùn)算的線性表。因?yàn)樽詈筮M(jìn)棧的結(jié)點(diǎn)必定最先出棧，所以棧具有后進(jìn)先出的的特性。若有隊(duì)列 Q=(q0， q1， … ， qn1)q0 為隊(duì)首結(jié)點(diǎn)， qn1為隊(duì)尾結(jié)點(diǎn)。每個(gè)元素對(duì)應(yīng)一個(gè)下標(biāo)，數(shù)組元素按數(shù)組名和元素的下標(biāo)引用，數(shù)組元素的下標(biāo)個(gè)數(shù)稱為數(shù)組的維數(shù)。對(duì)于多維數(shù)組， C語(yǔ)言按行優(yōu)先 字符串是非 數(shù)值處理應(yīng)用中重要的處理對(duì)象。習(xí)慣稱 樹(shù)和二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)為樹(shù)形結(jié)構(gòu)。樹(shù)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集 T，它 滿足以下兩個(gè) ②其余的結(jié)點(diǎn)分成 (m＞ m=0)個(gè)互不相交的有限集 T0， T1， … ， Tm1。樹(shù)中各結(jié)點(diǎn)的度的最大值稱為樹(shù)的度。當(dāng)程序需從結(jié)點(diǎn)返回到其父結(jié)點(diǎn)時(shí)，需要在樹(shù)的結(jié) (3) 在 應(yīng)用樹(shù)結(jié)構(gòu)時(shí)，常要求按某種次序獲得樹(shù)中全部結(jié)點(diǎn)的信息，這可通過(guò)樹(shù)的遍歷操作來(lái)實(shí) 樹(shù)的后序遍歷。首先訪問(wèn)處于 0層上的根結(jié)點(diǎn)，然后從左到有依次訪問(wèn)處于 1層、 2 層上的 另外，在二叉樹(shù)中，結(jié)點(diǎn)的 子 樹(shù)是有序的，分左、右兩棵子二叉樹(shù)。 中序遍 歷。作為一種特殊的二叉樹(shù)，它或者為空，或者滿足 下列 在線性結(jié)構(gòu)中，除首結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，末結(jié)點(diǎn) 沒(méi)有后繼結(jié)點(diǎn)之外，一個(gè)結(jié)點(diǎn)只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 6 頁(yè) 共 34 頁(yè) 圖分有向圖和無(wú)向圖。圖中代表一條邊的結(jié)點(diǎn)的偶對(duì)如果是無(wú)序的，則稱此圖為無(wú)向圖。由 鄰接矩陣的定義可知，無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣不定的對(duì)稱。 在無(wú)向圖的鄰接表中，對(duì)應(yīng)某結(jié)點(diǎn)的鏈表的結(jié)點(diǎn)個(gè)數(shù)就是該頂點(diǎn)的度 。從某個(gè)結(jié)點(diǎn)出發(fā)，訪問(wèn)此結(jié)點(diǎn)，然后依次訪問(wèn)與此結(jié)點(diǎn) 鄰接的、未被訪問(wèn)過(guò)的結(jié)點(diǎn)，然后再分別從這些為出發(fā)進(jìn)行廣度優(yōu)先周游，直至圖中所有被 訪問(wèn)過(guò)的結(jié)點(diǎn)的相鄰結(jié)點(diǎn)都被訪問(wèn)到。一個(gè)圖可以有許 (5)求最短路 求最短路 徑就是從圖中某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。在排序過(guò)程中，線性表的全部結(jié)點(diǎn)都在內(nèi)存、并在內(nèi)存中調(diào)整它們?cè)? 線性表中的存儲(chǔ)順序，稱為內(nèi)排序。按查找數(shù)據(jù)在內(nèi)存還是在外存分為內(nèi)存查找和外存查找。對(duì)于通過(guò)比 較來(lái)縮小查找范圍來(lái)說(shuō)，唯一能提高查找效率的辦法是通過(guò)一次比較能大幅減小查找范圍。 在 關(guān)于樹(shù)的幾個(gè)敘述中，只有 { E }是正確的。 查找 樹(shù)中，由根結(jié)點(diǎn)到所有其他結(jié)點(diǎn)的路徑長(zhǎng)度總和稱為內(nèi)部路徑長(zhǎng)度。由豐滿樹(shù)同平衡樹(shù)定義可知，豐滿樹(shù)一 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 10 頁(yè) 共 34 頁(yè) 定是平穩(wěn)樹(shù) ，但是平衡 m階 B樹(shù)是一種平衡的 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)所有 葉結(jié)點(diǎn)在 【答案】： A： ① B： ② C： ③ D： ② E： 試題 2(1999 年 試題 從供選擇的答案中，選出應(yīng)填入下面敘述中 { }內(nèi)的最確切的解答，把相應(yīng)編號(hào) 結(jié)定結(jié)點(diǎn)的關(guān)鍵字序列 (F， B， J， G， E， A， I， D， C， H)。 二路 歸并排序的第一趟結(jié)局是 { D }。插入排序、 選擇排序、交換排序、基數(shù)排序和歸并排序是幾種常用的排序方法，每種方法 中 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 12 頁(yè) 共 34 頁(yè) 插入排序的基本思想是：每一步 將一個(gè)待排序 的記錄按其關(guān)鍵碼值的大小插入到前面已排序 的文件中的適 當(dāng)位置上，直到全部插完為止。冒泡排序和快速排序又是交換排序的兩種具體方法。問(wèn)題 B 比 較簡(jiǎn)單，順次將關(guān)鍵字 序列 兩兩比較，第 1趟 快速排序是 對(duì)冒泡排序的一種改進(jìn)，方法是：在待排序序列中確定一個(gè)記錄，以它為基準(zhǔn)， 用交 換的方法將所有的記錄分成兩部分，即關(guān)鍵碼值比它小的一部分和比它大的一部分。一般采用 從兩端往中間加入的移動(dòng)方式， 第 1 趟排序的 F， B， J， G， E， A， I， D， C， C， B， J， G， E， A， I， D， F， C， B， F， G， E， A， I， D， J， C， B， D， G， E， A， I， F， J， C， B， D， F， E， A， I， G， J， C， B， D， A， E， F， I， G， J， H第一趟 歸并排序要求待排序列已經(jīng)部分排序，形成了若干子序列。具體的方式分為二路歸并和多路歸并。理解 了 這個(gè)過(guò)程，則問(wèn)題 D 的解答就 會(huì)非常簡(jiǎn)單。在建堆的過(guò)程中，要記 住堆的特征，作 為堆的二叉樹(shù)具有這樣的特征：樹(shù)根的關(guān)鍵碼值小于樹(shù)葉的關(guān)鍵碼值；堆的 調(diào)整過(guò)程是從最下層開(kāi)始的，先將二叉樹(shù)的樹(shù)根與左子樹(shù)進(jìn)行比較，如果樹(shù)葉小于樹(shù)根，則 交 換；然后比較樹(shù)根與右子，若樹(shù)葉小 于樹(shù)根，則交換。在 調(diào)整完最下層的子樹(shù)后，整個(gè)子樹(shù)的結(jié)構(gòu)如圖 中國(guó) 最龐大的下資料庫(kù) (整理 . 版權(quán)歸原作者所有 ) 第 14 頁(yè) 共 34 頁(yè) 21(b)所示。 供 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＞， 這樣很快就答案案③和④排除了， 然后再看答案 ①②。結(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)的邊表的指針。各種排序方法有其不同的排序?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 }。上 述 過(guò)程稱為一趟冒泡排序，結(jié)果是最大的數(shù)被稱鮐了最后。在排序過(guò)程中只進(jìn)行 n1次 比 較，不交換數(shù)據(jù)?？焖倥判虻膹?fù)雜是 O(nlog2n)。然而，無(wú)論數(shù) 據(jù)的初始次序如何，它所需 進(jìn)行的關(guān)鍵字的比較次數(shù)相同，均為 n(n1)/2，因此，直接 選擇 排序的復(fù) 雜性是 O(n2)。 中國(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。 中國(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)寫在答卷的 一棵二叉排序 樹(shù)可順序存放在一組物理上相鄰的存儲(chǔ)區(qū)中，每個(gè)結(jié)點(diǎn)及左、右針依次分別放 在 該存儲(chǔ)區(qū)的 3 個(gè)連續(xù)單元中。 供 中國(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。 【答案】 A： ⑨ B： ⑦ C： ⑤ D： ② E： 試題 7 (1996 年 試題 從供選擇的答案中，選出應(yīng)填入下面敘述中 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的 下列 圖中， A 是非 簡(jiǎn)單圖， B 是完全 圖， C 和 D 都是哈密 爾頓圖，其中 C 又是歐拉圖， E 是 樹(shù)。圖的連通性和圖中不存在度數(shù)為 1的 頂點(diǎn)都是哈密爾頓圖的必要 條件。無(wú)向圖 G， 當(dāng)且僅當(dāng) G 是 連通的，所有結(jié)點(diǎn)度數(shù)全為偶數(shù)，且有歐拉回路，該無(wú) 向 圖稱為無(wú)向歐拉圖。 ②在哈夫曼樹(shù)中，外部結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)部結(jié)點(diǎn)個(gè)數(shù)多 1； ④在二叉樹(shù)的前序序列中，若結(jié)點(diǎn) u在 結(jié)點(diǎn)