全國(guó)計(jì)算機(jī)等級(jí)考試考點(diǎn)解析、例題精解與應(yīng)試模擬-三級(jí)數(shù)據(jù)庫(kù)

全國(guó)計(jì)算機(jī)等級(jí)考試考點(diǎn)解析、例題精解與應(yīng)試模擬一一三

級(jí)數(shù)據(jù)庫(kù)

第2章數(shù)據(jù)結(jié)構(gòu)與算法

※本章大綱要求：

(1)基本概念

(2)線(xiàn)性表

(3)多維數(shù)組、稀疏矩陣和廣義表

(4)樹(shù)形結(jié)構(gòu)

(5)查找

(6)排序

※重要考點(diǎn)提示：

根據(jù)對(duì)歷年真題的分析可知，本章考核內(nèi)容約占15%,主要包括

以下幾個(gè)方面：

(1)數(shù)據(jù)結(jié)構(gòu)和算法的基本概念

(2)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)

(3)順序表和一維數(shù)組

(4)鏈表、棧、隊(duì)列、串的概念與操作

(5)稀疏矩陣的存儲(chǔ)、廣義表的定義與存儲(chǔ)

(6)二叉樹(shù)的定義、存儲(chǔ)與表示、線(xiàn)索二叉樹(shù)

(7)樹(shù)與二叉樹(shù)的轉(zhuǎn)換、二叉樹(shù)的周游算法

(8)霍夫曼算法及其應(yīng)用

(9)靜態(tài)表、動(dòng)態(tài)表的查找

(10)各種排序算法，插入排序、選擇排序、交換排序、歸并排

序

2.1基本概念

考點(diǎn)1：數(shù)據(jù)結(jié)構(gòu)的基本概念★

(1)數(shù)據(jù)

數(shù)據(jù)就是采用計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的方式，對(duì)現(xiàn)實(shí)世界

的事物進(jìn)行的描述，簡(jiǎn)而言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)

項(xiàng)組成，數(shù)據(jù)項(xiàng)是有獨(dú)立含義的數(shù)據(jù)最小單位。

(2)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)一般包括3個(gè)方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)

在計(jì)算機(jī)中的存儲(chǔ)方式以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。

a.數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)

元素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的存儲(chǔ)方式。數(shù)據(jù)的邏輯結(jié)

構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。

b.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)。

c.數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，而實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)

±0主要的運(yùn)算包括插入、刪

除、排序、查找等。

考點(diǎn)2：主要的數(shù)據(jù)存儲(chǔ)方式★

實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。

最主要的存儲(chǔ)方式有順序存儲(chǔ)儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)方式。

(1)順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的

存儲(chǔ)單元中，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，其主要

特點(diǎn)是：

a.結(jié)構(gòu)中只有自身信息域，沒(méi)有鏈接信息域，因此，存儲(chǔ)密度

大，存儲(chǔ)空間利用率高；

b.可以通過(guò)計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)構(gòu)的存儲(chǔ)地址；

c.插入、刪除運(yùn)算會(huì)引起大量結(jié)構(gòu)的移動(dòng)。

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是在每個(gè)結(jié)點(diǎn)中至少包括一個(gè)指針域，用指針來(lái)體

現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)系。其主要特點(diǎn)是：

a.存儲(chǔ)密度小，存儲(chǔ)空間利用率低；

b.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，可用于線(xiàn)性表、樹(shù)、圖

等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示；c.插入、刪除操作靈活方便，不必移

動(dòng)結(jié)點(diǎn)。

考點(diǎn)3：算法的設(shè)計(jì)與分析

算法的設(shè)計(jì)采用由粗到細(xì)、由抽象到具體的逐步求精的方法。

算法分析主要是分析算法所要占用的計(jì)算機(jī)資源，即時(shí)間代價(jià)和

空間代價(jià)兩個(gè)方面。

a.時(shí)間代價(jià)是當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí)解決該問(wèn)

題的算法運(yùn)行時(shí)所耗費(fèi)的時(shí)間，也以某種單位由f(l)增至f(n),則稱(chēng)

該算法的時(shí)間代價(jià)為f(n)

b.空間代價(jià)是當(dāng)問(wèn)題的規(guī)模由1增至n時(shí)-，解決該問(wèn)題的算法

實(shí)現(xiàn)時(shí)所占用的空間也以某種單位由g(l)增至g(n),則稱(chēng)該算法的空

間代價(jià)為g(n)o

2.2線(xiàn)性表

考點(diǎn)4：順序表和一維數(shù)組

線(xiàn)性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列(al,a2,…,an)。

按存儲(chǔ)方式不同線(xiàn)性表可以分為：順序存儲(chǔ)的順序表、鏈?zhǔn)酱鎯?chǔ)的鏈

表、散列存儲(chǔ)的散列。

順序表是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線(xiàn)性

表，其邏輯相鄰的數(shù)據(jù)元素具有相鄰的物理(存儲(chǔ))位置。對(duì)數(shù)據(jù)元

素進(jìn)行插入、刪除操作時(shí)需要移動(dòng)數(shù)據(jù)元素，存儲(chǔ)空間被分配后難以

再被擴(kuò)充。

各種高級(jí)語(yǔ)言中的一維數(shù)組就是用順序方式存儲(chǔ)的線(xiàn)性表，因此

也常用一維數(shù)組來(lái)稱(chēng)呼順序表。

考點(diǎn)5：鏈表★

鏈表的特點(diǎn)是可以用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表的各個(gè)

數(shù)據(jù)元素，不要求邏輯上相鄰的元素物理上也相鄰。鏈表的優(yōu)點(diǎn)是插

入、刪除等操作不需要移動(dòng)元素，只需要修改指針，比較靈活，缺點(diǎn)

是不能隨機(jī)存取。

鏈表可以分為線(xiàn)性鏈表和雙向鏈表兩種，前者也稱(chēng)為單鏈表，每

個(gè)結(jié)點(diǎn)中只有一個(gè)指向后一個(gè)結(jié)點(diǎn)的指針；后者每個(gè)結(jié)點(diǎn)有兩個(gè)指針,

一個(gè)指向直接前驅(qū)結(jié)點(diǎn)，一個(gè)指向直接后繼結(jié)點(diǎn)。?18?

考點(diǎn)6：棧與隊(duì)列十

棧與隊(duì)列都是對(duì)操作位置加以限制的線(xiàn)性表?？梢允褂庙樞虼鎯?chǔ)

也可以采用鏈?zhǔn)酱鎯?chǔ)。

棧的插入和刪除只能發(fā)生在線(xiàn)性表的一端，允許插入、刪除的這

一端稱(chēng)為棧頂，另一個(gè)固定端稱(chēng)為棧底。當(dāng)表中沒(méi)有元素時(shí)稱(chēng)為空棧。

棧是按“后進(jìn)先出”的規(guī)則進(jìn)行操作的。棧的常用運(yùn)算主要包括入棧

（push）、出棧（pop）和取棧頂元素（top）。

棧是使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)之一，表達(dá)式求值、遞歸過(guò)程實(shí)現(xiàn)

都是棧應(yīng)用的典型例子。隊(duì)列的插入只能在線(xiàn)性表的一端進(jìn)行，而

刪除在線(xiàn)性表的另一端進(jìn)行，允許插入的一端叫隊(duì)尾（rear）,允許刪

除的一端叫隊(duì)頭（）隊(duì)列是按“先進(jìn)先出”的規(guī)則進(jìn)行操作的。

front0

隊(duì)列常用的運(yùn)算有入隊(duì)（）、出隊(duì)（）和取隊(duì)首元素（）

enqdeqfront0

隊(duì)列在計(jì)算機(jī)中應(yīng)用也十分廣泛，硬件設(shè)備中的各種排隊(duì)器、緩

沖區(qū)的循環(huán)使用技術(shù)、操作系統(tǒng)中的作業(yè)隊(duì)列等都是隊(duì)列應(yīng)用的例子。

考點(diǎn)7：串

串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列，零個(gè)字符

的串是空串。串的存儲(chǔ)方式有：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)時(shí)可

以采用非緊縮方式，也可以采用緊縮方式。

串的基本運(yùn)算有連接、賦值、求長(zhǎng)度、全等比較、求子串、求子

串位置以及替換等。其中找子串位置（也稱(chēng)模式匹配）是非常重要的

一種運(yùn)算。

2.3多維數(shù)組、稀疏矩陣和廣義表

考點(diǎn)8：多維數(shù)組的線(xiàn)性存儲(chǔ)★

多維數(shù)組是一維數(shù)組的推廣，其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是

具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類(lèi)型。多維數(shù)組中最常用的是

二維數(shù)組。

多維數(shù)組的存儲(chǔ)方式一般是多維數(shù)組中的元素放在一個(gè)線(xiàn)性序

列中，排列方式可以是行優(yōu)先順序或列優(yōu)先順序。二維數(shù)組第i行、

第j列元素aij存儲(chǔ)地址的計(jì)算公式為：

行優(yōu)先順序:LOC(aij)=LOC(all)+((i?l)*n+(j?D)*?

列優(yōu)先順序:LOC(aij)=LOC(all)+((j?l)*m+(i?l))*?

式中m和n分別為數(shù)組中每列和每行的元素個(gè)數(shù)，？為每個(gè)數(shù)組

元素占用的存儲(chǔ)單元個(gè)數(shù)?？键c(diǎn)9：稀疏矩陣的存儲(chǔ)

具有大量0元素的矩陣稱(chēng)為稀疏矩陣。對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),

即只存儲(chǔ)非0元素。

對(duì)非0元素的分布有規(guī)律的矩陣，如下三角矩陣，按行優(yōu)先順序

存儲(chǔ)，非零元素的存儲(chǔ)地址用下式計(jì)算：

LOC(aij)=LOC(all)+(i*(i?l)/2+(j?l))*?

對(duì)一般的稀疏矩陣，可以采用三元組方法或十字鏈表方法存儲(chǔ)。

前者是按行優(yōu)先順序存儲(chǔ)非零元素所在的行、列以及它的值構(gòu)成的三

元組，后者則采用十字鏈表。

考點(diǎn)10：廣義表的定義和存儲(chǔ)

廣義表是線(xiàn)性表的推廣，也稱(chēng)為列表，是由零個(gè)或多個(gè)單元素或

子表所組成的有限序列。廣義表與線(xiàn)性表的區(qū)別在于：線(xiàn)性表的成分

都是結(jié)構(gòu)上不可分的單元素，而廣義表的成分既可以是單元素，又可

以是有結(jié)構(gòu)的表。

廣義表的特征：

廣義表的元素可以是子表，而子表的元素還可以是子表。

-19-

廣義表可被其他廣義表所共享。

廣義表可以是遞歸的表，即廣義表也可以是本身的一個(gè)子表。

2.4樹(shù)形結(jié)構(gòu)

考點(diǎn)11:樹(shù)及二叉樹(shù)的定義及表示★

樹(shù)是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T,有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為

根，其余結(jié)點(diǎn)分為m(m2。)個(gè)不相交的集合Tl,T2,?,Tm。每

個(gè)集合又是一棵樹(shù)，被稱(chēng)為這個(gè)根的子樹(shù)。這是樹(shù)的遞歸定義。

樹(shù)的性質(zhì)有以下4條：

(1)樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。

(2)度為k的樹(shù)中第i層上至多有ki?l個(gè)結(jié)點(diǎn)021)。

(3)深度為h的k叉樹(shù)至多有(kh?l)/(k?l)個(gè)結(jié)點(diǎn)。

(4)具有n個(gè)結(jié)點(diǎn)的k叉樹(shù)的最小深度為?logk(n(k?l)+l)?

二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。二叉樹(shù)是結(jié)點(diǎn)的有限集合,

這個(gè)有限集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵不相交的分別稱(chēng)

做這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

二叉樹(shù)不是樹(shù)的特殊情況，樹(shù)與二叉樹(shù)之間最主要的區(qū)別是：二

叉樹(shù)的子樹(shù)有左右之分，其次序不能顛倒，即使是在只有一棵子樹(shù)的

情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。

在一棵二叉樹(shù)中，如果最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2,

并且最下面一層結(jié)點(diǎn)都集中在最左邊的位置上，這樣的一棵二叉樹(shù)稱(chēng)

為完全二叉樹(shù)。

樹(shù)與二叉樹(shù)可以互相轉(zhuǎn)化，樹(shù)（樹(shù)林）轉(zhuǎn)換為二叉樹(shù)的算法：在

一棵樹(shù)中，凡是兄弟結(jié)點(diǎn)就用線(xiàn)連起來(lái)，然后去掉父結(jié)點(diǎn)到子結(jié)點(diǎn)的

連線(xiàn)，只保留父結(jié)點(diǎn)到第一個(gè)子結(jié)點(diǎn)的連線(xiàn)。如果把森林中第二棵樹(shù)

的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則同樣可以導(dǎo)出森林

與二叉樹(shù)的對(duì)應(yīng)關(guān)系。

把二叉樹(shù)轉(zhuǎn)換為樹(shù)的算法：若某結(jié)點(diǎn)是其雙親的左孩子，則把該

結(jié)點(diǎn)的右孩子，右孩子的右孩子??，都與該結(jié)點(diǎn)雙親用線(xiàn)連起來(lái)，最

后去掉所有的雙親到右孩子的連線(xiàn)。

考點(diǎn)12：二叉樹(shù)與樹(shù)的周游★

遍歷一個(gè)樹(shù)形結(jié)構(gòu)就是按一定的次序系統(tǒng)地訪(fǎng)問(wèn)樹(shù)上的所有結(jié)

點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪(fǎng)問(wèn)一次。

由二叉樹(shù)的定義可知，一棵二叉樹(shù)由3部分組成：根、左子樹(shù)和

右子樹(shù)。因此對(duì)二叉樹(shù)的遍歷也可相應(yīng)地分為3類(lèi)先序（根）遍歷、

中序（對(duì)稱(chēng)序）遍歷、后序（根）遍歷。

先序遍歷：訪(fǎng)問(wèn)根結(jié)點(diǎn)；先序遍歷左子樹(shù)；先序遍歷右子樹(shù)。

中序（對(duì)稱(chēng)序）遍歷：中序遍歷左子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)；中序遍歷

右子樹(shù)。

后序遍歷：后序遍歷左子樹(shù)；后序遍歷右子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)。

由于樹(shù)也是一種層次結(jié)構(gòu)，所以對(duì)樹(shù)有時(shí)也進(jìn)行按層遍歷，所謂

按層遍歷，就是從樹(shù)根結(jié)點(diǎn)開(kāi)始，依次訪(fǎng)問(wèn)每一層，對(duì)同一層結(jié)點(diǎn),

由左至右進(jìn)行訪(fǎng)問(wèn)。

樹(shù)和森林的遍歷也主要有三種：先根次序、后根次序和層次次序。

其中，前兩種是按深度優(yōu)先方式進(jìn)行的，后一種是按廣度優(yōu)先方式進(jìn)

行的。

根據(jù)樹(shù)和二叉樹(shù)的對(duì)應(yīng)關(guān)系，可以看出，按先序遍歷樹(shù)正好等同

于按先序遍歷對(duì)應(yīng)的二叉樹(shù)；按后序遍歷樹(shù)正好等同于按對(duì)稱(chēng)序法遍

歷對(duì)應(yīng)的二叉樹(shù)。

-20-

考點(diǎn)13：二叉樹(shù)的存儲(chǔ)與線(xiàn)索二叉樹(shù)

(1)二叉樹(shù)的Llink?Hink法存儲(chǔ)

二叉樹(shù)通常的存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)，每個(gè)鏈結(jié)點(diǎn)除了數(shù)據(jù)域外,

還可以增加兩個(gè)指針域llink和rlink,分別指向左右兩個(gè)子結(jié)點(diǎn)。當(dāng)

某個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)不存在時(shí)，相應(yīng)的指針值為空(nil)。

(2)線(xiàn)索二叉樹(shù)

一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，在2n個(gè)

指針域中只有n?l個(gè)指針域是用來(lái)存儲(chǔ)結(jié)點(diǎn)孩子的地址的，而另外

n+1個(gè)指針域存放的都是niL為了保留結(jié)點(diǎn)在某種遍歷序列中直接前

驅(qū)和直接后繼的位置信息、，可以利用二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的

這n+1個(gè)空指針域來(lái)記錄這些信息。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直

接后繼結(jié)點(diǎn)的指針被稱(chēng)為線(xiàn)索（thread）,加了線(xiàn)索的二叉樹(shù)稱(chēng)為線(xiàn)

索二叉樹(shù)。

（3）完全二叉樹(shù)的順序存儲(chǔ)

二叉樹(shù)的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)中的

結(jié)點(diǎn)。一般是按照二叉樹(shù)結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。完全

二叉樹(shù)或者滿(mǎn)二叉樹(shù)比較適合于順序存儲(chǔ)。

考點(diǎn)14：霍夫曼算法及其應(yīng)用★

霍夫曼（Huffman）樹(shù)，也稱(chēng)為最優(yōu)二叉樹(shù)，是指對(duì)于一組帶有

確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。

設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)

的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度,

記為：

WPL??Wk?Lk

k?ln

其中Wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值,Lk為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。

最優(yōu)二叉樹(shù)算法為：對(duì)于n個(gè)權(quán)為wl,w2,w3,…,wn的結(jié)點(diǎn)，

首選找出兩個(gè)最小的wi值，不妨設(shè)為wl和w2,然后對(duì)m?l個(gè)權(quán)

wl+w2,w3,…,,wn來(lái)解這個(gè)問(wèn)題，并且將解中的代替，如此進(jìn)行

下去，直到所有的w構(gòu)成一棵二叉樹(shù)。

給定一組權(quán)值，構(gòu)造出來(lái)的霍夫曼樹(shù)不是唯一的。在霍夫曼樹(shù)中，

權(quán)值大的結(jié)點(diǎn)離根最近。另外，在霍夫曼樹(shù)中，沒(méi)有度為1的結(jié)點(diǎn)。

2.5查找

考點(diǎn)15：線(xiàn)性表的查找

查找是確定一個(gè)元素在表或樹(shù)中的位置，衡量一個(gè)查找算法的標(biāo)

準(zhǔn)是對(duì)關(guān)鍵碼平均比較的次數(shù)，或稱(chēng)為平均檢索長(zhǎng)度ASL。對(duì)于線(xiàn)性

表的查找主要分下面幾種：

(1)順序查找

順序查找是線(xiàn)性表的最簡(jiǎn)單的查找方法，其具體步驟是：用待查

關(guān)鍵碼從頭開(kāi)始逐個(gè)與表中元素比較，直到找出相等的元素，則查找

成功；或者找遍所有元素，則查找失敗。

順序查找的優(yōu)點(diǎn)：對(duì)線(xiàn)性表的結(jié)點(diǎn)的邏輯次序無(wú)要求，對(duì)線(xiàn)性表

的存儲(chǔ)結(jié)構(gòu)無(wú)要求。

順序查找的缺點(diǎn)：平均檢索長(zhǎng)度長(zhǎng)，與表中結(jié)點(diǎn)個(gè)數(shù)n成正比,

若檢索關(guān)鍵碼的概率相等，則

-21-

查找成功時(shí)平均比較次數(shù)為(n+l)/2。查找不成功時(shí)；關(guān)鍵碼的比

較次數(shù)總是n+1次。

(2)二分查找

二分查找法是一種效率較高的線(xiàn)性表查找方法，要求線(xiàn)性表結(jié)點(diǎn)

必須是按關(guān)鍵碼值排好序的，且線(xiàn)性表以順序方式存儲(chǔ)。其具體步驟

是：首選用要查找的關(guān)鍵碼值與線(xiàn)性表中間位置結(jié)點(diǎn)的關(guān)鍵碼值相比

較，這個(gè)中間結(jié)點(diǎn)把線(xiàn)性表分成兩個(gè)子表，比較相等則查找完成，不

等則根據(jù)比較結(jié)果確定下一步的查找應(yīng)該在哪一個(gè)子表中進(jìn)行，如此

進(jìn)行下去，直到找到滿(mǎn)足要求的點(diǎn)。

二分查找的優(yōu)點(diǎn)：平均查找長(zhǎng)度小，為??Iog2n??

二分查找的缺點(diǎn)：線(xiàn)性表排序需要花費(fèi)時(shí)間，順序方式存儲(chǔ)的插

入、刪除不便。

（3）分塊查找

分塊查找要求把線(xiàn)性表分成若干塊，每一塊中的結(jié)點(diǎn)不必有序,

但塊與塊之間必須有序，還要求將各塊中的最大關(guān)鍵碼值組成一個(gè)有

序的索引表。其具體步驟是：首選在索引表中用順序查找或二分查找

法確定所求記錄所在的塊，然后再?gòu)脑搲K中用順序查找方法找出所求

的記錄。

（4）散列表查找

散列法的基本思想是：由結(jié)點(diǎn)的關(guān)鍵碼決定結(jié)點(diǎn)的存儲(chǔ)地址，即

以關(guān)鍵碼k為自變量，通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的函數(shù)值h（k）,將這

個(gè)值解釋為結(jié)點(diǎn)的存儲(chǔ)地址。檢索時(shí)再根據(jù)要檢索的關(guān)鍵碼值用同樣

的方法計(jì)算出結(jié)點(diǎn)位置。

散列法需要解決以下兩個(gè)問(wèn)題：

a.構(gòu)造好的散列函數(shù)，能夠?qū)⒁唤M關(guān)鍵碼值盡可能均勻地安排

在事先確定的范圍里，并且使得發(fā)生碰撞的可能性最小。常見(jiàn)的散列

函數(shù)有直接定址法除余法、數(shù)字分析法、折疊法、平方取中法等。

b.制定解決碰撞的方案。處理碰撞的方法主要有拉鏈法和開(kāi)放

定址法。

影響產(chǎn)生沖突多少有以下三個(gè)因素：哈希函數(shù)是否均勻；處理沖

突的方法；哈希表的負(fù)載因子。散列表的負(fù)載因子公式:

??散列表中結(jié)點(diǎn)的數(shù)目基本區(qū)域能容納的結(jié)點(diǎn)數(shù)

負(fù)載因子的大小體現(xiàn)散列表的裝滿(mǎn)程度，？越大，則散列表裝得

越滿(mǎn)，發(fā)生碰撞的機(jī)會(huì)越大，一般取??1。

考點(diǎn)16：樹(shù)形結(jié)構(gòu)與查找山

（1）二叉排序樹(shù)

二叉排序樹(shù)是一類(lèi)特殊的二叉樹(shù)，其特點(diǎn)是：若左子樹(shù)不空，則

左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹(shù)不空，則右子樹(shù)

上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；所有的子樹(shù)也遵守相同的規(guī)則。

對(duì)二叉排序樹(shù)中序遍歷（周游）可以得到關(guān)鍵字從小到大的有序

序列。對(duì)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列,

構(gòu)造二叉排序樹(shù)的過(guò)程就是對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。

對(duì)二叉排序樹(shù)的操作主要的插入和刪除操作。

平衡二叉樹(shù)是對(duì)二叉排序樹(shù)的一種“平衡化”處理。結(jié)點(diǎn)的平衡

因子定義為其右子樹(shù)高度減去左子樹(shù)高度。若任一結(jié)點(diǎn)的平衡因子均

取一1,0或+1,則此二叉排序樹(shù)為平衡的二叉排序樹(shù)（AVL樹(shù)）。平

衡二叉排序樹(shù)的查找方法與一般的二叉排序樹(shù)完全一樣，優(yōu)點(diǎn)是總能

保持檢索長(zhǎng)度為O（log2n）量級(jí)。

往平衡二叉樹(shù)插入新結(jié)點(diǎn)時(shí)，需要對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行必要調(diào)整，以

動(dòng)態(tài)地保持平衡二叉樹(shù)的特點(diǎn)。?22?

（2）B樹(shù)和B+樹(shù)

B樹(shù)和B+樹(shù)是一種平衡的多路查找樹(shù)形結(jié)構(gòu)，用于組織外存儲(chǔ)器

中文件的動(dòng)態(tài)索引結(jié)構(gòu)。這樣可以使得每個(gè)結(jié)點(diǎn)包含多個(gè)關(guān)鍵碼值，

有多個(gè)孩子，使得樹(shù)的層次降低，查找時(shí)訪(fǎng)問(wèn)外存的次數(shù)減少。

由B樹(shù)定義可以知：

a.m階B樹(shù)每一個(gè)結(jié)點(diǎn)最多有m個(gè)子樹(shù)。

b.m階B樹(shù)根結(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹(shù)；中間結(jié)點(diǎn)

至少有?m/2?棵子樹(shù)。

c.m階B樹(shù)任一結(jié)點(diǎn)的左右子樹(shù)的高度都相等。

B樹(shù)的主要操作是：查找、插入、刪除。

在m階B樹(shù)上插入關(guān)健碼的過(guò)程為：

a.B樹(shù)是從空樹(shù)開(kāi)始，逐個(gè)插入關(guān)鍵碼而生成的。

b.在B樹(shù)中，每個(gè)非葉結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)都在[?m/2??l,m?l]

之間。

c.B樹(shù)中關(guān)鍵碼的插入不是在葉結(jié)點(diǎn)上進(jìn)行的，而是在最底層

的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵碼。若插入結(jié)點(diǎn)上關(guān)鍵碼個(gè)數(shù)不超

過(guò)m?l個(gè)，則可直接插入到該結(jié)點(diǎn)上；否則，要進(jìn)行調(diào)整，即結(jié)點(diǎn)

的“分裂”。

根據(jù)B+樹(shù)的定義可知：

a.有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵碼。

b.所有關(guān)鍵碼均出現(xiàn)在葉結(jié)點(diǎn)中，上層關(guān)鍵碼均是下層相應(yīng)結(jié)

點(diǎn)中最大關(guān)鍵碼的重復(fù)，且葉子結(jié)點(diǎn)所有關(guān)鍵碼是有序的。

c.對(duì)B+樹(shù)進(jìn)行兩種查找運(yùn)算:一種是從最小關(guān)鍵碼起順序查找，

另一種是從根結(jié)點(diǎn)開(kāi)始，進(jìn)行隨機(jī)查找。

2.6排序

考點(diǎn)17：插入排序

插入排序的基本思想是每次將一個(gè)待排序記錄按其關(guān)鍵碼值大

小插入到前面已排序的文件中的合適位置上，直到記錄插入完為止。

a.直接插入排序：在已排好序的序列中查找插入位置時(shí)用順序

法查找，找到插入位置后將該位置原來(lái)的記錄及其后面所有的記錄順

序后移一個(gè)位置，空出該位置來(lái)插入記錄。

b.二分法插入排序：在已排好的序列中找插入的位置時(shí)，用二

分法查找，找到插入位置后和直接插入排序法同樣處理。

c.shell排序：又稱(chēng)縮小增量法，是按增量將文件分組。首先取

增量dl<n,把全部記錄分成dl個(gè)組，所有距離為dl倍數(shù)的記錄

放在一組中，各組內(nèi)用插入法排序，然后取d2<dl,重復(fù)上述分組

和排序工作，直至取d=l,即所有記錄放在一個(gè)組中為止。

考點(diǎn)18：選擇排序支

選擇排序的基本思想是每次從待排序的記錄中選出關(guān)鍵碼值最

?。ɑ蜃畲螅┑挠涗?，順序放在已排記錄序列的最后，直到全部排完，

這里主要講堆排序

堆排序是對(duì)一組待排序的關(guān)鍵碼，首先把它們按堆的定義排成一

個(gè)序列（稱(chēng)為建堆），這就找到了最小的關(guān)鍵碼，然后將最小的關(guān)鍵

碼取出，用剩下的關(guān)鍵碼再建堆，便得到次最小的關(guān)鍵碼，如此反復(fù)

進(jìn)行，直至將全部關(guān)鍵碼排好序?yàn)橹埂?/p>

堆排序的兩個(gè)主要問(wèn)題：

-23-

（1）如何將n個(gè)元素的序列按關(guān)鍵碼建成堆。

（2）輸出堆頂元素后，如何調(diào)整剩余元素使之成為一個(gè)新堆。

考點(diǎn)19：交換排序十

交換排序主要是起泡排序和快速排序。

a.起泡排序是將排序的記錄順次兩兩比較，若為逆序則進(jìn)行交

換，將序列照此方法從頭到尾處理一遍稱(chēng)做一趟起泡。第二趟起泡再

將次最大關(guān)鍵碼交換到倒數(shù)第二個(gè)位置，即它的最終位置，如此進(jìn)行

下去，若某一趟起泡過(guò)程中沒(méi)有發(fā)生任何交換，或排序已經(jīng)進(jìn)行了

n?l趟，則排序過(guò)程結(jié)束。

b.快速排序是在待排序序列中任取一個(gè)記錄，以它為基準(zhǔn)用交

換的方法將所有的記錄分成兩部分，關(guān)鍵碼值比它小的一個(gè)部分，關(guān)

鍵碼值比它大的在另一部分，再分別對(duì)兩個(gè)部分實(shí)施上述過(guò)程，一直

重復(fù)到排序完成。

考點(diǎn)20：歸并排序歸并排序的基本思想是對(duì)兩個(gè)或兩個(gè)以上的

表組合成一個(gè)新的有序表。排序方法為先將原始序列中的每個(gè)關(guān)鍵字

都看作一個(gè)序列，兩兩有序歸并，逐步擴(kuò)大于序列尺寸，直到全部排

序完成。

2.7經(jīng)典題解

一、選擇題

1.下列哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。（2007.09）

A）棧

C）鏈表B）隊(duì)列D）線(xiàn)性表

解析：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)，如

鏈表。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)元

素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的存儲(chǔ)方式。邏輯結(jié)構(gòu)分為線(xiàn)

性結(jié)構(gòu)（如線(xiàn)性表、棧、隊(duì)列）和非線(xiàn)性結(jié)構(gòu)（如樹(shù)）。

答案：c

2.下列關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中，哪一條是不正確的。

（2007.09）

A）數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述

B）數(shù)據(jù)的邏輯結(jié)構(gòu)不僅反映數(shù)據(jù)間的邏輯關(guān)系，而且包括其在

計(jì)算機(jī)中的存儲(chǔ)方式

C）數(shù)據(jù)的邏輯結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)

D）線(xiàn)性表是典型的線(xiàn)性結(jié)構(gòu)

解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)

據(jù)元素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的存儲(chǔ)方式，在計(jì)算機(jī)中

的存儲(chǔ)是由存儲(chǔ)結(jié)構(gòu)決定的。邏輯結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)（如線(xiàn)性表、棧、

隊(duì)列）和非線(xiàn)性結(jié)構(gòu)（如樹(shù)）。

答案：B

3.下列關(guān)于數(shù)據(jù)運(yùn)算的敘述中，哪一條是不正確的o（2007.09）

A）數(shù)據(jù)運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面

B）數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)在數(shù)據(jù)的邏輯結(jié)構(gòu)上進(jìn)行

C）檢索是一種常用的運(yùn)算

D）插入是一種常用的運(yùn)算

解析：數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，而實(shí)現(xiàn)是在存儲(chǔ)結(jié)

構(gòu)上。主要的運(yùn)算包括插入、刪除、排序、查?24?

找等。

答案：B

4.棧結(jié)構(gòu)不適用于下列哪一種運(yùn)用。（2007.09）

A）表達(dá)式求值

B）快速排序算法的實(shí)現(xiàn)

C）樹(shù)的層次次序周游算法的實(shí)現(xiàn)

D）二叉樹(shù)對(duì)稱(chēng)序周游算法的實(shí)現(xiàn)

解析：樹(shù)的層次次序周游算法需要先存儲(chǔ)每一層的結(jié)點(diǎn)，然后按

照先進(jìn)后出的順序依次訪(fǎng)問(wèn)結(jié)點(diǎn)信息、，需要用先進(jìn)先出的隊(duì)列來(lái)實(shí)現(xiàn),

而不是用先進(jìn)后出的棧來(lái)實(shí)現(xiàn)；表達(dá)式求值，需要設(shè)置操作數(shù)和操作

符兩個(gè)棧；快速排序需要用棧實(shí)現(xiàn)遞歸；二叉樹(shù)對(duì)稱(chēng)序周游算法即中

序周游算法，也需要用棧結(jié)構(gòu)實(shí)現(xiàn)。

答案：C

5.雙鏈表的每個(gè)結(jié)點(diǎn)包括兩個(gè)指針域。其中Hink指向結(jié)點(diǎn)的后

繼，llink指向結(jié)點(diǎn)的前驅(qū)。如果要在p所指結(jié)點(diǎn)后插入q所指的新結(jié)

點(diǎn)，下列哪一個(gè)操作序列是正確的。（2007.09）

A）pf.rlinkf.llink:=q;pt.rlink:=q;qt.llink:=p;qf.rlink:=p

t.rlink;

B）pt.llinkf.rlink:=q;pt.llink:=q;qt.rlink:=p;qt.llink:=p

t.llink;

C)qf.llink:=p;qt.rlink:=pt.rlink;pt.rlinkt.llink:=q;p

t.rlink:=q;

D)qf.rlinkf:=p;qt.llink:=pf.llink;pf.llinkf.rlink:=q;p

f.llink:=q;

解析：需要先將待插入結(jié)點(diǎn)q的左指針更新為p，然后將q右指

針的信息更新為p的右指針?biāo)赶蚪Y(jié)點(diǎn)，再將p的右指針?biāo)附Y(jié)點(diǎn)的

左指針信息更新為q，最后將p的右指針信息更新為q。

答案：C

6.在包含1000個(gè)元素的線(xiàn)性表中實(shí)現(xiàn)如下運(yùn)算，哪一個(gè)所需執(zhí)

行時(shí)間最長(zhǎng)。(2007.09)

A)線(xiàn)性表按順序方式存儲(chǔ)，在線(xiàn)性表的第100個(gè)結(jié)點(diǎn)后面插入

一個(gè)新結(jié)點(diǎn)

B)線(xiàn)性表按鏈接方式存儲(chǔ)，在線(xiàn)性表的第100個(gè)結(jié)點(diǎn)后面插入

一個(gè)新結(jié)點(diǎn)

C)線(xiàn)性表按順序方式存儲(chǔ)，刪除線(xiàn)性表的第900個(gè)結(jié)點(diǎn)

D)線(xiàn)性表按鏈接方式存儲(chǔ)，刪除指針P所指向的結(jié)點(diǎn)

解析：線(xiàn)性表按順序方式存儲(chǔ)，執(zhí)行插入操作時(shí)要將插入點(diǎn)后的

所有元素平移一個(gè)單位，在1000個(gè)元素的線(xiàn)性表的第100個(gè)結(jié)點(diǎn)后

插入新結(jié)點(diǎn)需要移動(dòng)900個(gè)元素。鏈接方式存儲(chǔ)插入新結(jié)點(diǎn)需要查找

100次找到結(jié)點(diǎn)再插入。線(xiàn)性表按順序方式存儲(chǔ)，刪除第900個(gè)元素

要將第900?1000個(gè)元素向前移動(dòng)一個(gè)單位。按鏈接方式存儲(chǔ)，刪除

指針P指向結(jié)點(diǎn)，其平均查找長(zhǎng)度為500.5。查找開(kāi)銷(xiāo)比移動(dòng)開(kāi)銷(xiāo)要

答案：B

7.設(shè)某散列表的當(dāng)前狀態(tài)如下：

該散列表的負(fù)載因子約為。(2007.09)

A)0.37B)0.42C)0.58D)0.73

解析：散列表的負(fù)載因子公式：

pqnewnode-25-

??散列表中結(jié)點(diǎn)的數(shù)目

基本區(qū)域能容納的結(jié)點(diǎn)數(shù)

由題可知負(fù)載因子為7/19=0.37

答案：A

8.設(shè)有關(guān)鍵碼序列(Q、G、M、Z、A、N、B、P、X、H、Y、S、

T、L、K、E),采用堆排序法進(jìn)行排序，經(jīng)過(guò)初始建堆后關(guān)鍵碼值A(chǔ)

在序列中的序號(hào)是。(2007.09)

A)1

C)8B)4D)12

解析：堆排序是將待排序的關(guān)鍵碼先按堆的定義排成一個(gè)序列

(稱(chēng)為建堆)，找到最小的關(guān)鍵碼，然后將最小的關(guān)鍵碼取出，用剩

下的關(guān)鍵碼再建堆，便得到次最小的關(guān)鍵碼，如此反復(fù)進(jìn)行，直至將

全部關(guān)鍵碼排好序?yàn)橹?。所以初始建堆關(guān)鍵碼A即為堆頂,序號(hào)為lo

答案：A

9.對(duì)n個(gè)記錄的文件進(jìn)行起泡排序，所需要的輔助存儲(chǔ)空間

為。(2007.09)

A)0(1)

C)O(n).B)O(log2n)D)O(n)2

解析：起泡排序僅需一個(gè)輔助存儲(chǔ)空間作為記錄在交換位置時(shí)的

緩存空間。

答案：A

10.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)基本概念的敘述中，哪一條是不正確的。

(2007.04)

A)數(shù)據(jù)是采用計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的方式，對(duì)現(xiàn)實(shí)世

界的事物進(jìn)行的描述

B)數(shù)據(jù)元素(或稱(chēng)結(jié)點(diǎn)、記錄等)是數(shù)據(jù)的基本單位

C)一個(gè)數(shù)據(jù)元素至少由兩個(gè)數(shù)據(jù)項(xiàng)組成

D)數(shù)據(jù)項(xiàng)是有獨(dú)立含義的數(shù)據(jù)最小單位

解析：一個(gè)數(shù)據(jù)元素可由一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是有

獨(dú)立含義的不可分割的數(shù)據(jù)的最小單位。數(shù)據(jù)是所有能輸入到計(jì)算機(jī)

中并被計(jì)算機(jī)程序識(shí)別、存儲(chǔ)和處理的符號(hào)的總稱(chēng)。

答案：C

11.下列關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，哪些是正確的。

(2007.04)

I.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

II.每個(gè)結(jié)點(diǎn)都包含恰好一個(gè)指針域

III.用指針來(lái)體現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)系

IV.可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

V.存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)

A)I、II和II

B)I、II、III和IVD)I、山和VC)II、IV和V

解析：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中除了包含保存數(shù)據(jù)元素自身信息的信息域

外，還有表示數(shù)據(jù)元素之間的鏈接信息的指針域，因此比順序存儲(chǔ)結(jié)

構(gòu)的存儲(chǔ)密度低；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中邏輯上相鄰的數(shù)據(jù)元素在物理上不

一定相鄰；不是所有節(jié)點(diǎn)都包含指針域，如單向鏈表中最后一個(gè)節(jié)點(diǎn)

的指針為空。

答案：D

12和13基于以下描述：有一個(gè)初始為空的棧和輸入序列A、B、

C、E、F、G：現(xiàn)發(fā)過(guò)如下操作：

push,push,top,pop,push,push,top,push,pop,pop,pop.

12.下列哪一個(gè)是正確的從棧中刪除元素的序列。(2007.04)

A)BEB)BD

-26-

C)BEDCD)BDEC

解析：棧的操作遵循后進(jìn)先出的原則。題中的操作依次為：A進(jìn)

棧、B進(jìn)棧、B讀取、B刪除、C進(jìn)棧、D進(jìn)棧、E進(jìn)棧、E刪除、D

刪除、C刪除。由此可見(jiàn)刪除的序列為BEDC。

答案：C

13.下列哪一個(gè)是上述操作序列完成后棧中的元素列表(從底到

頂)。(2007.04)

A)A

B)BDC)ABCE

答案：A

14—15基于如下所示的二叉樹(shù)。

D)ABCDE解析：通過(guò)上題的分析可知，在操作過(guò)程中進(jìn)棧的有

ABCDE,刪除的有BEDC,因此最后棧中的元素只有A。14.該二叉

樹(shù)對(duì)應(yīng)的樹(shù)林包括幾棵樹(shù)。(2007.04)

A)1B)2C)3D)4

解析：二叉樹(shù)轉(zhuǎn)換為樹(shù)林時(shí)，二叉樹(shù)的根就是樹(shù)林第一棵樹(shù)的根；

二叉樹(shù)的左子樹(shù)轉(zhuǎn)換為樹(shù)林的第一棵樹(shù)，二叉樹(shù)的右子樹(shù)對(duì)應(yīng)于樹(shù)林

中其余的樹(shù)；二叉樹(shù)右子樹(shù)的根節(jié)點(diǎn)作為余下樹(shù)中第一棵樹(shù)的根節(jié)點(diǎn),

其余以此類(lèi)推。本題中的二叉樹(shù)應(yīng)該包含2棵樹(shù)。

答案：B

15.按后根次序周游該二叉樹(shù)對(duì)應(yīng)的樹(shù)林，所得到的結(jié)點(diǎn)序列為

(2007.04)

A)DBAFEGC

C)DBFGECAB)ABCDEFGD)ACBEGDF

解析：后序遍歷二叉樹(shù)的次序是：后序遍歷左子樹(shù)，后序遍歷右

子樹(shù)，訪(fǎng)問(wèn)根節(jié)點(diǎn)。因此后序遍歷此二叉樹(shù)對(duì)應(yīng)的樹(shù)林所得的節(jié)點(diǎn)序

列為選項(xiàng)Co

答案：C

16.按層次次序周游該二叉對(duì)應(yīng)的樹(shù)林，所得到的結(jié)點(diǎn)序列為。

(2007.04)

A)DBAFEGC

C)DBFGECAB)ABCDEFGD)ACBEGDF

解析：按層次次序遍歷二叉樹(shù)的次序是：從樹(shù)的根節(jié)點(diǎn)開(kāi)始，依

次訪(fǎng)問(wèn)每一層，對(duì)同一層節(jié)點(diǎn)，由左到右進(jìn)行訪(fǎng)問(wèn)。因此按層次次序

遍歷此二叉樹(shù)對(duì)應(yīng)的樹(shù)林所得的節(jié)點(diǎn)序列為選項(xiàng)B。

答案：B

17.設(shè)待排序關(guān)鍵碼序列為(25,18,9,33,67,82,53,95,

12,70),要按關(guān)鍵碼值遞增的順序進(jìn)行排序，采取以第一個(gè)關(guān)鍵碼

為分界元素的快速排序法，第一趟排序完成后關(guān)鍵碼95被放到第幾

個(gè)位置。(2007.04)

A)7

C)9

處在第8個(gè)位置。B)8D)10解析：快速排序法

第一趟排序后,關(guān)鍵碼序列為(12,18,9,25,67,82,53,95,33,

70),因此關(guān)鍵碼95

-27-

答案：B

18.設(shè)散列表的地址空間為0到：16,散列函數(shù)為h(k)=kmodl7,

用線(xiàn)性探查法解決碰撞?，F(xiàn)從空的散列表開(kāi)始，依次插入關(guān)鍵碼值

190,89,217,208,75,177,則最后一個(gè)關(guān)鍵碼177的地址為。

(2007.04)

A)6

C)8B)7D)9

解析：本題采用除留余數(shù)法構(gòu)造散列函數(shù)，將關(guān)鍵碼值190,89,

217,208,75,177分別帶入h(k)=kmodl7,得到散列地址分別為3,

4,13,4,7,7,在存儲(chǔ)關(guān)鍵碼208時(shí)，由于其散列地址4與前面的

一個(gè)關(guān)鍵碼發(fā)生沖突，因此其存儲(chǔ)地址向后移1位到5。而存儲(chǔ)關(guān)鍵

碼177時(shí)，由于其散列地址7與前面的一個(gè)關(guān)鍵碼發(fā)生沖突，因此其

存儲(chǔ)地址再向后移1位到8o

答案：C

19.下列哪些是數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。(2006.09)

I.數(shù)據(jù)的采集

V.數(shù)據(jù)的檢索

A)II和IV

B)I、II和IIID)I、III和VC)IK川和VII.數(shù)據(jù)的邏

輯組織IV.數(shù)據(jù)的傳輸III.數(shù)據(jù)的存儲(chǔ)實(shí)現(xiàn)

解析：數(shù)據(jù)的采集和數(shù)據(jù)的檢索不屬于數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。數(shù)

據(jù)結(jié)構(gòu)一般包括三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，它是從邏輯關(guān)系上描

述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。數(shù)據(jù)的存儲(chǔ)器內(nèi)表示，它是指用計(jì)算機(jī)

語(yǔ)言實(shí)現(xiàn)的邏輯結(jié)構(gòu)，它依賴(lài)于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)

施加的操作。

答案：C

20.下列關(guān)于數(shù)據(jù)元素的敘述中，哪一項(xiàng)是不正確的。

（2006.09）

A）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體

B）數(shù)據(jù)元素是有獨(dú)立含義的數(shù)據(jù)最小單位

C）數(shù)據(jù)元素又稱(chēng)作結(jié)點(diǎn)

D）數(shù)據(jù)元素又稱(chēng)作記錄

解析：數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位，而非數(shù)據(jù)元素。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成,

有時(shí)也稱(chēng)作結(jié)點(diǎn)、記錄、表目等。

答案：B

21.下列關(guān)于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的敘述中，哪一項(xiàng)是正確的。

（2006.09）

A）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的抽象描述

B）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)

C）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)

D）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)沒(méi)有影響

解析：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的

表示，又稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)。分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)

據(jù)采用不同的存儲(chǔ)結(jié)構(gòu)，將對(duì)數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)有著巨大的影響。

答案：B

22.棧S最多能容納4個(gè)元素?，F(xiàn)有6個(gè)元素按A、B、C、D、E、

F的順序進(jìn)棧，下列哪一個(gè)序列是可能的出棧序列。（2006.09）

A)E、D、C、B、A、F

C)C、B、E、D、A、FB)B、C、E、F、A、DD)A、D、

F、E、B、C

解析：對(duì)于選項(xiàng)A,因?yàn)樵摋Ｗ疃嘀荒苋菁{4個(gè)元素，而E是第

五個(gè)元素，在前4個(gè)元素還沒(méi)出棧的情況下是不可能進(jìn)棧再出棧的。

對(duì)于選項(xiàng)B,A元素不可能在D元素還沒(méi)出棧的情況下先出棧；對(duì)于

選項(xiàng)C,其出棧序列為：?28?

C、B、E、D、A、F；對(duì)于選項(xiàng)D,B元素不可能在C元素還沒(méi)出

棧情況下出棧，出棧序列為選項(xiàng)C。

答案：C

23.從單鏈表中刪除指針s所指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)3其關(guān)鍵運(yùn)

算步驟為。(2006.09)

A)st.link:=t

B)tf.link:=sD)st.link:=tf.linkC)tt.link:=st.link

解析：要從單鏈表中刪除指針-s所指節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)t,則原

節(jié)點(diǎn)t指的后繼節(jié)點(diǎn)成為s所指的后繼節(jié)點(diǎn)，因此關(guān)鍵運(yùn)算步驟為:

stJink:=tt.linko

答案：D

24.按行優(yōu)先順序存儲(chǔ)下三角矩陣

?allO?aa22Ann??21

?????anlan20??0???????ann??

的非零元素，則計(jì)算非零元素aij(lWiWjWn)的地址公式為

(2006.09)

A)LOC(aij)?LOC(all)?i?(i?l)/2?j

B)LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)

C)LOC(aij)?LOC(all)?i?(i?l)/2?j

D)LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)

解析：非零元素aij在矩陣中處在第i行第j歹U,在按行優(yōu)先順序

存儲(chǔ)時(shí)，應(yīng)先存儲(chǔ)前i?l行的非零元素和同一行的前j?l個(gè)元素。如

果all的存儲(chǔ)地址為L(zhǎng)OC(all),則aij的存儲(chǔ)地址為D。

答案：D

25.下列關(guān)于二叉樹(shù)周游的敘述中，哪一項(xiàng)是正確的。

(2006.09)

A)若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)對(duì)稱(chēng)序的最后一個(gè)結(jié)點(diǎn)，則它必是該

二叉樹(shù)前序的最后一個(gè)結(jié)點(diǎn)

B)若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)前序的最后一個(gè)結(jié)點(diǎn)，則它必是該二

叉樹(shù)對(duì)稱(chēng)序的最后一個(gè)結(jié)點(diǎn)

C)若一個(gè)樹(shù)葉是某二叉樹(shù)對(duì)稱(chēng)序的最后一個(gè)結(jié)點(diǎn)，則它必是該

二叉樹(shù)前序的最后一個(gè)結(jié)點(diǎn)

D)若一個(gè)樹(shù)葉是某二叉樹(shù)前序的最后一個(gè)結(jié)點(diǎn)，則它必是該二

叉樹(shù)對(duì)稱(chēng)序的最后一個(gè)結(jié)點(diǎn)

解析：若一個(gè)樹(shù)葉是某二叉樹(shù)對(duì)稱(chēng)序的最后一個(gè)節(jié)點(diǎn)，則它必是

該二叉樹(shù)最右邊的樹(shù)葉，即前序的最后一個(gè)節(jié)點(diǎn)。而若將“樹(shù)葉”改

為“結(jié)點(diǎn)”則不正確，因?yàn)橛锌赡艹霈F(xiàn)二叉樹(shù)最右結(jié)點(diǎn)無(wú)右孩子的情

況。

答案：c

26.如下所示是一棵5階B樹(shù)，該B樹(shù)現(xiàn)在的層數(shù)為2。從該B

樹(shù)中刪除關(guān)鍵碼38后，該B樹(shù)的第2層的結(jié)點(diǎn)數(shù)為。(2006.09)

A)6B)7

-29-

C)8D)9

解析：刪除38后該節(jié)點(diǎn)剩下的關(guān)鍵碼的個(gè)數(shù)為1,小于「5/2

-I?1=2,所以刪除后要將該結(jié)點(diǎn)剩余的41與雙親結(jié)點(diǎn)中的45一起移

至原結(jié)點(diǎn)的右兄弟節(jié)點(diǎn)，故結(jié)點(diǎn)數(shù)減1,變?yōu)?個(gè)。

答案：A

27.在待排序文件已基本有序的前提下，下列排序方法中效率最

高的是。(2006.09)

A)直接插入排序

C)快速排序B)直接選擇排序D)歸并排序

解析：直接插入排序，若文件基本有序，則比較次數(shù)最小為n?l

次，移動(dòng)次數(shù)為0;直接選擇排序，無(wú)論待排序文件是否基本有序,

其比較次數(shù)均為n(n?l)/2,若文件基本有序，則移動(dòng)次數(shù)減少，最小

為0;快速排序在文件基本有序時(shí)蛻化為起泡排序，時(shí)間復(fù)雜度為

n(n?l)/2；對(duì)于歸并排序，無(wú)論待排序文件是否基本有序，其比較次

數(shù)均為nlog2n,若文件基本有序，則移動(dòng)次數(shù)減少，最小為0,可見(jiàn)

直接插入排序效率最高。2

答案：A

28.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)基本概念的敘述中，哪一條是正確的

（2006.04）

A）數(shù)據(jù)的邏輯結(jié)構(gòu)分為表結(jié)構(gòu)和樹(shù)結(jié)構(gòu)

B）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)

C）數(shù)據(jù)元素是數(shù)據(jù)的基本單位

D）節(jié)點(diǎn)是有獨(dú)立含義的數(shù)據(jù)最小單位

解析：數(shù)據(jù)的基本單位是數(shù)據(jù)元素，故C正確。數(shù)據(jù)的邏輯結(jié)構(gòu)

可以劃分為集合、線(xiàn)性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。數(shù)

據(jù)的存儲(chǔ)結(jié)構(gòu)指的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像），它包括順

序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)。節(jié)點(diǎn)是由若干位組合起來(lái)形成的位串，

數(shù)據(jù)的最小單位是節(jié)點(diǎn)中的一個(gè)二進(jìn)制數(shù)位（bit）。

答案：C

29.下列關(guān)于串的敘述中，哪一條是正確的。（2006.04）

A）串是由零個(gè)或多個(gè)字符組成的有限序列

B）空串是由空格構(gòu)成的串

C）串只能順序存儲(chǔ)

D）“推入”是串的基本運(yùn)算之一

解析：串是由零個(gè)或多個(gè)字符組成的有限序列；如果串中沒(méi)有任

何字符，則稱(chēng)為空串。由一個(gè)或多個(gè)空格組成的串稱(chēng)為空格串，空格

串不是空串，因?yàn)榭崭翊杏凶址?；串既可以順序存?chǔ)也可以鏈表存

儲(chǔ)；串的基本操作一般是以“串的整體”作為操作對(duì)象，“推入”不

是串的基本運(yùn)算。

答案：A30.雙鏈表的每個(gè)結(jié)點(diǎn)包括兩個(gè)指針域。其中rlink指向

結(jié)點(diǎn)的后繼，llink指向結(jié)點(diǎn)的前驅(qū)。如果要在p所指結(jié)點(diǎn)前面插入q

所指的新結(jié)點(diǎn)，下列哪一個(gè)操作序列是正確的。(2006.04)

A)pf.rlinkf.llink:=q；pf.rlink:=q；qf.llink:=p；qt.rlink:=p

t.rlink；

B)p\.llinkt.rlink:=q；pt.llink:=q；qt.rlink:=p；qt.llink:=p\.llink；

C)qt.llink:=p；qt.rlink:=pt.rlink；pt.rlinkf.llink:=q；p

t.rlink:=q；

D)qt.rlink:=p；q\.llink:=pf.llink；pt.llinkt.rlink:=q；p\.llink:=q；

解析：首先要修改p所指節(jié)點(diǎn)的llink字段和原前驅(qū)節(jié)點(diǎn)的rlink

字段，然后置q所指節(jié)點(diǎn)的rlink和llink值，即qt.Hink:=p；qt.llink:=p

；；

t.llinkpt.llinkf.rlink:=qpt.llink:=q0

答案：D

31.下列哪一個(gè)不是隊(duì)列的基本運(yùn)算。(2006.04)

-30-

A)從隊(duì)尾插入一個(gè)新元素

B)從隊(duì)列中刪除第i個(gè)元素

C)判斷一個(gè)隊(duì)列是否為空

D)讀取隊(duì)頭元素的值

解析：隊(duì)列的基本操作有：構(gòu)造一個(gè)空隊(duì)列；將隊(duì)列清為空隊(duì)列；

判斷隊(duì)列是否為空隊(duì)列；計(jì)算隊(duì)列的長(zhǎng)度；讀取隊(duì)列的隊(duì)頭元素；向

隊(duì)列插入一個(gè)元素為該隊(duì)列的隊(duì)尾元素；刪除隊(duì)列隊(duì)頭元素。隊(duì)列只

允許在隊(duì)尾插入元素，而在隊(duì)頭刪除元素。

答案：B

32.棧結(jié)構(gòu)不適用于下列哪一種應(yīng)用。(2006.04)

A)表達(dá)式求值

B)樹(shù)的層次次序周游算法的實(shí)現(xiàn)

C)二叉樹(shù)對(duì)稱(chēng)序周游算法的實(shí)現(xiàn)

D)快速排序算法的實(shí)現(xiàn)

解析：見(jiàn)第4題。

答案：B

33.按層次次序?qū)⒁豢糜衝個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的所有結(jié)點(diǎn)從1

到n編號(hào)，當(dāng)i?n/2時(shí),編號(hào)為i的結(jié)點(diǎn)的左孩子的編號(hào)是。(2006.04)

A)2i?l

C)2i+lB)2iD)不確定

解析：若對(duì)有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)按層次從上到下，每個(gè)層次

從左至右的規(guī)則為節(jié)點(diǎn)編號(hào)，若i?n/2,則編號(hào)為i的節(jié)點(diǎn)的左孩子節(jié)

點(diǎn)的編號(hào)為2i；若i?n/2,則編號(hào)為i的節(jié)點(diǎn)沒(méi)有左孩子節(jié)點(diǎn)。

答案：B

34.對(duì)于給出的一組權(quán)w={10,12,16,21,30},通過(guò)霍夫曼

算法求出的擴(kuò)充二叉樹(shù)的帶權(quán)外部路徑長(zhǎng)度為。(2006.04)

A)89

C)200B)189D)300

解析：霍夫曼算法建立的擴(kuò)充二叉樹(shù)如下圖所示。所以帶權(quán)外部

路徑長(zhǎng)度為(21+16)X2+30X2+(12+10)義3=200

答案：C

35.設(shè)散列表的地址空間為0到10,散列函數(shù)為h(k)=kmodll,

用線(xiàn)性探查法解決碰撞。現(xiàn)從空的散列表開(kāi)始，依次插入關(guān)鍵碼值

95,14,27,68,82,則最后一個(gè)關(guān)鍵碼82的地址為。(2006.04)

A)4

C)6B)5D)7

解析：本題采用除留余數(shù)法構(gòu)造散列函數(shù)，將關(guān)鍵碼值95,14,

27,68,82分別帶入h(k)=kmodll,得到散列地址分別為7,3,5,

2,5,當(dāng)存儲(chǔ)關(guān)鍵碼82時(shí)，由于其散列地址與前面的一個(gè)關(guān)鍵碼發(fā)

生沖突，因此其存儲(chǔ)

-31-

地址向后移1位到6o

答案：C

36.設(shè)有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X),

則新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列哪一個(gè)排

序算法一趟掃描的結(jié)果。(2006.04)

A)起泡排序

B)初始步長(zhǎng)為4的希爾(shell)排序

C)二路歸并排序

D)以第一個(gè)元素為分界元素的快速排序

解析：若進(jìn)行升序起泡排序，則因?yàn)镼大于H,因此Q和H要

交換，新序列第一個(gè)字符應(yīng)該為H；若進(jìn)行降序起泡排序，Q和H位

置不變；若進(jìn)行希爾排序，始步長(zhǎng)為4,則Q應(yīng)該與P分為一組，新

序列的第一個(gè)字符應(yīng)該為P（升序）或Q（降序）。若進(jìn)行二路歸并

排序，則Q和H歸并，排序后的結(jié)果應(yīng)該為H,Q（升序）或者Q,

H（降序）?？焖倥判蛞缘谝粋€(gè)元素Q為分界元素處理原序列可得到

新序列。

答案：D

37.以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中，哪一條是不正確的。

（2005.09）

A）數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述

B）數(shù)據(jù)的邏輯結(jié)構(gòu)不僅反映數(shù)據(jù)間的邏輯關(guān)系，而且反映其在

計(jì)算機(jī)中的存儲(chǔ)方式

C）數(shù)據(jù)的邏輯結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)

D）樹(shù)形結(jié)構(gòu)是典型的非線(xiàn)性結(jié)構(gòu)解析：如第2題。

答案：B

38.在包含1000個(gè)元素的線(xiàn)性表中實(shí)現(xiàn)如下各運(yùn)算，哪一個(gè)所

需的執(zhí)行時(shí)間最短。（2005.09）

A）線(xiàn)性表按順序方式存儲(chǔ),查找關(guān)鍵碼值為666的結(jié)點(diǎn)

B）線(xiàn)性表按鏈接方式存儲(chǔ),查找關(guān)鍵碼值為666的結(jié)點(diǎn)

C）線(xiàn)性表按順序方式存儲(chǔ),查找線(xiàn)性表中第900個(gè)結(jié)點(diǎn)

D）線(xiàn)性表按鏈接方式存儲(chǔ),查找線(xiàn)性表中第900個(gè)結(jié)點(diǎn)

解析：線(xiàn)性表順序方式存儲(chǔ)，可直接計(jì)算確定第i個(gè)節(jié)點(diǎn)的存儲(chǔ)

地址，其執(zhí)行時(shí)間與i的值沒(méi)有關(guān)系。查找鏈接存儲(chǔ)方式的線(xiàn)性表中

的第i個(gè)節(jié)點(diǎn)，依次與前i?l個(gè)節(jié)點(diǎn)進(jìn)行比較，最終確認(rèn)結(jié)點(diǎn)的位置。

答案：c

39.在包含1000個(gè)元素的線(xiàn)性表中實(shí)現(xiàn)如下各運(yùn)算，哪一個(gè)所

需的執(zhí)行時(shí)間最長(zhǎng)。（2005.09）

A）線(xiàn)性表按順序方式存儲(chǔ)，在線(xiàn)性表的第100個(gè)結(jié)點(diǎn)后面插入

一個(gè)新結(jié)點(diǎn)

B）線(xiàn)性表按鏈接方式存儲(chǔ)，在線(xiàn)性表的第100個(gè)結(jié)點(diǎn)后面插入

一個(gè)新結(jié)點(diǎn)

C）線(xiàn)性表按順序方式存儲(chǔ)，刪除線(xiàn)性表的第900個(gè)結(jié)點(diǎn)

D）線(xiàn)性表按鏈接方式存儲(chǔ)，刪除指針P所指向的結(jié)點(diǎn)

解析:A中需要把第1000個(gè)元素到第101個(gè)元素依次后移一位，

共需移動(dòng)900個(gè)元素；B中只需從第一個(gè)節(jié)點(diǎn)開(kāi)始，順序查找到第100

個(gè)節(jié)點(diǎn)，再進(jìn)行兩次交換指針即可；C中在順序表中刪除一個(gè)元素,

需把刪除元素的后面元素前移，共前移100個(gè)元素；D中在鏈接表中

刪除節(jié)點(diǎn)，只需進(jìn)行一次指針的修改即可。

答案：A

40.以下關(guān)于廣義表的敘述中，哪一條是正確的。（2005.09）

A）廣義表是。個(gè)或多個(gè)單元素或子表組成的有限序列

B）廣義表至少有一個(gè)元素是子表

C）廣義表不可以是自身的子表

D)廣義表不能為空表

-32-

解析：廣義表是線(xiàn)性表的擴(kuò)展，它的定義是由n個(gè)數(shù)據(jù)元素組成

的有限序列，其中的數(shù)據(jù)元素既可以是單元素，也可以是子表；廣義

表既可以是自身的子表，也可是空表。

答案：A

41-43題基于下圖所示的二叉樹(shù)：

41.該二叉樹(shù)對(duì)應(yīng)的樹(shù)林包括幾棵樹(shù)。(2005.09)

A)1

C)3B)2D)4

解析：二叉樹(shù)轉(zhuǎn)換為樹(shù)林，二叉樹(shù)的根就是樹(shù)林第一棵樹(shù)的根；

二叉樹(shù)的左子樹(shù)轉(zhuǎn)換為樹(shù)林的第一棵樹(shù)，二叉樹(shù)的右子樹(shù)對(duì)應(yīng)于樹(shù)林

中其余的樹(shù)；二叉樹(shù)右子樹(shù)的根節(jié)點(diǎn)作為余下樹(shù)中第一棵樹(shù)的根節(jié)點(diǎn),

其余以此類(lèi)推。本題中的二叉樹(shù)應(yīng)該包含4棵樹(shù)。

答案：D

42.如果用llink?rlink法存儲(chǔ)該二叉樹(shù)，則各結(jié)點(diǎn)的指針域中共

包含多少個(gè)空指針。(2005.09)

A)6

C)10B)8D)12

解析：二叉樹(shù)采用llink?rlink法存儲(chǔ)時(shí)，其指針域Mink和rlink分

別指向節(jié)點(diǎn)的左孩子和右孩子。題中二叉樹(shù)D、G、H、I四個(gè)節(jié)點(diǎn)的

左右孩子和E節(jié)點(diǎn)的右孩子以及C節(jié)點(diǎn)的左孩子均為空，因此空指針

共有4X2+2X1=10個(gè)。

答案：C

43.如果將該二叉樹(shù)存儲(chǔ)為對(duì)稱(chēng)序線(xiàn)索二叉樹(shù)，則結(jié)點(diǎn)H的左線(xiàn)

索指向哪一個(gè)結(jié)點(diǎn)（2005.09）

A）結(jié)點(diǎn)A

C）結(jié)點(diǎn)EB）結(jié)點(diǎn)CD）結(jié)點(diǎn)G

解析：采用對(duì)稱(chēng)序線(xiàn)索二叉樹(shù)存儲(chǔ)二叉樹(shù)時(shí)，其訪(fǎng)問(wèn)次序是先中

序遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)。題中二叉樹(shù)存儲(chǔ)

為對(duì)稱(chēng)序線(xiàn)索二叉樹(shù)的結(jié)果是：DBGEACHFI,所以節(jié)點(diǎn)H的左線(xiàn)索指

向節(jié)點(diǎn)C。

答案：B

44.以下關(guān)于B樹(shù)運(yùn)算的敘述中，哪一條是正確的o（2005.09）

A）若插入過(guò)程中根結(jié)點(diǎn)發(fā)生分裂，則B樹(shù)的高度加1

B）每當(dāng)進(jìn)行插入運(yùn)算，就在B樹(shù)的最下面一層增加一個(gè)新結(jié)點(diǎn)

C）若要?jiǎng)h除的關(guān)鍵碼出現(xiàn)在根結(jié)點(diǎn)中，則不能真正刪除，只能

做標(biāo)記

D）刪除可能引起B(yǎng)樹(shù)結(jié)點(diǎn)個(gè)數(shù)減少，但不會(huì)造成B樹(shù)高度減小

解析：對(duì)于根節(jié)點(diǎn)，由于沒(méi)有雙親節(jié)點(diǎn)，所以如果根節(jié)點(diǎn)發(fā)生了

分裂，就要建立一個(gè)新的根節(jié)點(diǎn)，則B樹(shù)的高度加1。

答案：A

45.對(duì)n個(gè)記錄的文件進(jìn)行歸并排序，所需要的輔助存儲(chǔ)空間

為。(2005.09)

A)0(1)B)0(n)

-33-

C)O(log2n)

間復(fù)雜度為0(n)。

答案：BD)0(n2)解析：歸并排序需把每次歸并的結(jié)果放

入另一個(gè)空間中，n個(gè)記錄的文件就需再分配n個(gè)大小的空間，所以

空

二、填空題

1.按行優(yōu)先順序存儲(chǔ)下三角矩陣Ann的非零元素，則計(jì)算非零

元素aij(lWjWWn)的地址的公式為L(zhǎng)oc(aij)=,+i*(i?l)/2+(j?l)0

(2007.09)

解析：非零元素aij在矩陣中處在第i行第j歹U，在按行優(yōu)先順序

存儲(chǔ)時(shí)，應(yīng)先存儲(chǔ)前i?l行的非零元素(共iX(i?l)/2個(gè))和同一行的前

j?l個(gè)元素。如果all的存儲(chǔ)地址為L(zhǎng)OC(all),則aij的存儲(chǔ)地址為

LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)o

答案：Loc(all)

2.按對(duì)稱(chēng)序周游二叉樹(shù)等同于按。(2007.09)

解析：按對(duì)稱(chēng)序周游二叉樹(shù)相當(dāng)于中序遍歷二叉樹(shù)。

答案：中序

3.m階B+樹(shù)的根節(jié)點(diǎn)至多有個(gè)孩子。(2007.09)

解析：按照B+樹(shù)的定義，m階B+樹(shù)每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子。

答案：m

4.三元組法和十字鏈表法都可以用于矩陣的存儲(chǔ)表示。

(2007.04)

解析：三元組法和十字鏈表法均用于存儲(chǔ)稀疏矩陣。用三元組存

儲(chǔ)稀疏矩陣僅存儲(chǔ)矩陣中的非零元素，十字鏈表法則為了避免進(jìn)行刪

除和插入操作時(shí)而導(dǎo)致的大量節(jié)點(diǎn)的移動(dòng)。

答案：稀疏

5.有關(guān)鍵碼值為10,20,30的三個(gè)結(jié)點(diǎn)，按所有可能的插入順

序去構(gòu)造二叉排序樹(shù)，能構(gòu)造出棵不同的二叉排序樹(shù)。(2007.04)

解析：二叉排序樹(shù)具有以下性質(zhì)：若其左子樹(shù)非空，則所有左子

樹(shù)上數(shù)據(jù)元素關(guān)鍵字的值均小于根節(jié)點(diǎn)關(guān)鍵字的值；若其右子樹(shù)非空,

則所有右子樹(shù)上數(shù)據(jù)元素關(guān)鍵字的值均大于根節(jié)點(diǎn)關(guān)鍵字的值；其左

子樹(shù)和右子樹(shù)也是二叉排序樹(shù)，因此能夠構(gòu)造出5棵二叉排序樹(shù)。

答案：5

6.散列法存儲(chǔ)的基本思想是：由結(jié)點(diǎn)的決定結(jié)點(diǎn)的存儲(chǔ)地址。

(2006.09)

解析：散列法存儲(chǔ)的基本思想是：由節(jié)點(diǎn)的關(guān)鍵碼值決定節(jié)點(diǎn)的

存儲(chǔ)地址，具體地址由散列函數(shù)決定。答案：關(guān)鍵碼值

7.若一課二叉樹(shù)的度為2的結(jié)點(diǎn)數(shù)為9,則該二叉樹(shù)的葉結(jié)點(diǎn)

數(shù)為。(2006.09)

解析：二叉樹(shù)的葉節(jié)點(diǎn)數(shù)為n0=n2+l,因此葉節(jié)點(diǎn)數(shù)9+1=10。

答案：10

8.在順序表(3,6,8,10,12,15,16,18,21,25,30)中，

用二分法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為o(2006.09)

解析：二分查找法的基本思路是不斷把區(qū)間的中間元素與待查找

的元素比較，根據(jù)比較結(jié)果確定是結(jié)束查找還是在左邊或右邊子表并

按相同的方法繼續(xù)查找。與11比較的關(guān)鍵碼分別為15、8、10、12,

所以比較的次數(shù)為4。

答案：4

-34-

9.廣義表是線(xiàn)性表的推廣，是由零個(gè)或多個(gè)單元素或所組成

的有限序列。(2006.04)

解析：廣義表是線(xiàn)性表的擴(kuò)展，它的定義是由n個(gè)數(shù)據(jù)元素組成

的有限序列，其中的數(shù)據(jù)元素