全國計(jì)算機(jī)等級考試解析例題精解與應(yīng)試模擬三級數(shù)據(jù)

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

※本章大綱要求：

(1)基本概念

(2)線性表

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

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

(5)查找

(6)排序

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

根據(jù)對歷年真題的分析可知，本章考核內(nèi)容約占15%,主要包括以下幾個方面：

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

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

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

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

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

(6)二叉樹的定義、存儲與表示、線索二叉樹

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

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

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

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

2.1基本概念

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

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

數(shù)據(jù)就是采用計(jì)算機(jī)能夠識別、存儲和處理的方式，對現(xiàn)實(shí)世界的事物進(jìn)行的描述，簡而言之,

數(shù)據(jù)就是計(jì)算機(jī)化的信息。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是有獨(dú)立含義

的數(shù)據(jù)最小單位。

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

數(shù)據(jù)結(jié)構(gòu)一般包括3個方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲方式以及在

這些數(shù)據(jù)上定義的運(yùn)算的集合。

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

在計(jì)算機(jī)中的存儲方式。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

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

c.數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，而實(shí)現(xiàn)是在存儲結(jié)構(gòu)上。主要的運(yùn)算包括插入、刪

除、排序、查找等。

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

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

儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Ψ绞健?/p>

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

順序存儲結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，結(jié)點(diǎn)之間的關(guān)系由

存儲單元的鄰接關(guān)系來體現(xiàn)，其主要特點(diǎn)是：

a.結(jié)構(gòu)中只有自身信息域，沒有鏈接信息域，因此，存儲密度大，存儲空間利用率高；

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

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

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

鏈?zhǔn)酱鎯Y(jié)構(gòu)是在每個結(jié)點(diǎn)中至少包括一個指針域，用指針來體現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)

系。其主要特點(diǎn)是：

a.存儲密度小，存儲空間利用率低；

b.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表示；

c.插入、刪除操作靈活方便，不必移動結(jié)點(diǎn)。

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

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

算法分析主要是分析算法所要占用的計(jì)算機(jī)資源，即時間代價和空間代價兩個方面。

a.時間代價是當(dāng)問題的規(guī)模以某種單位由1增至n時解決該問題的算法運(yùn)行時所耗費(fèi)的時間，

也以某種單位由f(l)增至f(n),則稱該算法的時間代價為f(n)

b.空間代價是當(dāng)問題的規(guī)模由1增至n時，解決該問題的算法實(shí)現(xiàn)時所占用的空間也以某種

單位由g(l)增至g(n),則稱該算法的空間代價為g(n)o

2.2線性表

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

線性表的邏輯結(jié)構(gòu)是〃個數(shù)據(jù)元素的有限序列(切,〃2”..,東)。按存儲方式不同線性表可以分為:

順序存儲的順序表、鏈?zhǔn)酱鎯Φ逆湵?、散列存儲的散列?/p>

順序表是用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性表，其邏輯相鄰的數(shù)據(jù)元素具有

相鄰的物理(存儲)位置。對數(shù)據(jù)元素進(jìn)行插入、刪除操作時需要移動數(shù)據(jù)元素，存儲空間被分配

后難以再被擴(kuò)充。

各種高級語言中的一維數(shù)組就是用順序方式存儲的線性表，因此也常用一維數(shù)組來稱呼順序

表。

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

鏈表的特點(diǎn)是可以用一組任意的存儲單元來存儲線性表的各個數(shù)據(jù)元素，不要求邏輯上相鄰的

元素物理上也相鄰。鏈表的優(yōu)點(diǎn)是插入、刪除等操作不需要移動元素，只需要修改指針，比較靈活,

缺點(diǎn)是不能隨機(jī)存取。

鏈表可以分為線性鏈表和雙向鏈表兩種，前者也稱為單鏈表，每個結(jié)點(diǎn)中只有一個指向后一個

結(jié)點(diǎn)的指針；后者每個結(jié)點(diǎn)有兩個指針，一個指向直接前驅(qū)結(jié)點(diǎn)，一個指向直接后繼結(jié)點(diǎn)。

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

棧與隊(duì)列都是對操作位置加以限制的線性表?？梢允褂庙樞虼鎯σ部梢圆捎面?zhǔn)酱鎯Α?/p>

棧的插入和刪除只能發(fā)生在線性表的一端，允許插入、刪除的這一端稱為棧頂，另一個固定端

稱為棧底。當(dāng)表中沒有元素時稱為空棧。棧是按“后進(jìn)先出”的規(guī)則進(jìn)行操作的。棧的常用運(yùn)算主

要包括入棧(push)、出棧(pop)和取棧頂元素(top)。

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

隊(duì)列的插入只能在線性表的一端進(jìn)行，而刪除在線性表的另一端進(jìn)行，允許插入的一端叫隊(duì)尾

(rear),允許刪除的一端叫隊(duì)頭(front)。隊(duì)列是按“先進(jìn)先出”的規(guī)則進(jìn)行操作的。隊(duì)列常用的

運(yùn)算有入隊(duì)(enq)、出隊(duì)(deq)和取隊(duì)首元素(front),

隊(duì)列在計(jì)算機(jī)中應(yīng)用也十分廣泛，硬件設(shè)備中的各種排隊(duì)器、緩沖區(qū)的循環(huán)使用技術(shù)、操作系

統(tǒng)中的作業(yè)隊(duì)列等都是隊(duì)列應(yīng)用的例子。

考點(diǎn)7：串

串(或字符串)是由零個或多個字符組成的有限序列，零個字符的串是空串。串的存儲方式有:

順序存儲和鏈?zhǔn)酱鎯Αｍ樞虼鎯r可以采用非緊縮方式，也可以采用緊縮方式。

串的基本運(yùn)算有連接、賺值、求長度、全等比較、求子串、求子串位置以及替換等。其中找子

串位置(也稱模式匹配)是非常重要的一種運(yùn)算。

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

考點(diǎn)8：多維數(shù)組的線性存儲*

多維數(shù)組是一維數(shù)組的推廣，其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于

同一數(shù)據(jù)類型。多維數(shù)組中最常用的是二維數(shù)組。

多維數(shù)組的存儲方式一般是多維數(shù)組中的元素放在一個線性序列中，排列方式可以是行優(yōu)先順

序或列優(yōu)先順序。二維數(shù)組第i行、第j列元素a”存儲地址的計(jì)算公式為：

行優(yōu)先順序：LOC(aij)=L0C(an)+((i-1)*n+(j-1))

列優(yōu)先順序：LOC(au)=L0C(aH)+((j-1)*m+(i-D)*九

式中m和n分別為數(shù)組中每列和每行的元素個數(shù)，入為每個數(shù)組元素占用的存儲單元個數(shù)。

考點(diǎn)9：稀疏矩陣的存儲

具有大量0元素的矩陣稱為稀疏矩陣。對稀疏矩陣進(jìn)行壓縮存儲，即只存儲非0元素。

對非0元素的分布有規(guī)律的矩陣，如下三角矩陣，按行優(yōu)先順序存儲，非零元素的存儲地址用

下式計(jì)算：

LOC(a“)=L0C(an)+(i*(i-1)/2+(j-1))

對一般的稀疏矩陣，可以采用三元組方法或十字鏈表方法存儲。前者是按行優(yōu)先順序存儲非零

元素所在的行、列以及它的值構(gòu)成的三元組，后者則采用十字鏈表。

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

廣義表是線性表的推廣，也稱為列表，是由零個或多個單元素或子表所組成的有限序列。廣義

表與線性表的區(qū)別在于：線性表的成分都是結(jié)構(gòu)上不可分的單元素，而廣義表的成分既可以是單元

素，又可以是有結(jié)構(gòu)的表。

廣義表的特征：

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

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

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

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

考點(diǎn)11：樹及二叉樹的定義及表示*

樹是一個或多個結(jié)點(diǎn)組成的有限集合T,有一個特定的結(jié)點(diǎn)稱為根，其余結(jié)點(diǎn)分為m(m2O)

個不相交的集合Tl，T2,…，Tm。每個集合又是一棵樹，被稱為這個根的子樹。這是樹的遞歸定義。

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

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

(2)度為k的樹中第i層上至多有k-個結(jié)點(diǎn)(泛1)。

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

(4)具有n個結(jié)點(diǎn)的k叉樹的最小深度為「logk(n(k-l)+l)l

二叉樹是樹形結(jié)構(gòu)的一個重要類型。二叉樹是結(jié)點(diǎn)的有限集合，這個有限集合或者為空集，或

者由一個根結(jié)點(diǎn)及兩棵不相交的分別稱做這個根的左子樹和右子樹的二叉樹組成。

二叉樹不是樹的特殊情況，樹與二叉樹之間最主要的區(qū)別是：二叉樹的子樹有左右之分，其次

序不能顛倒，即使是在只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。

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

在最左邊的位置上，這樣的一棵二叉樹稱為完全二叉樹。

樹與二叉樹可以互相轉(zhuǎn)化，樹(樹林)轉(zhuǎn)換為二叉樹的算法：在一棵樹中，凡是兄弟結(jié)點(diǎn)就用

線連起來，然后去掉父結(jié)點(diǎn)到子結(jié)點(diǎn)的連線，只保留父結(jié)點(diǎn)到第一個子結(jié)點(diǎn)的連線。如果把森林中

第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則同樣可以導(dǎo)出森林與二叉樹的對應(yīng)關(guān)

系。

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

子……，都與該結(jié)點(diǎn)雙親用線連起來，最后去掉所有的雙親到右孩子的連線。

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

遍歷一個樹形結(jié)構(gòu)就是按一定的次序系統(tǒng)地訪問樹上的所有結(jié)點(diǎn)，使每個結(jié)點(diǎn)恰好被訪問一

次。

由二叉樹的定義可知，一棵二叉樹由3部分組成：根、左子樹和右子樹。因此對二叉樹的遍歷

也可相應(yīng)地分為3類先序(根)遍歷、中序(對稱序)遍歷、后序(根)遍歷。

先序遍歷：訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。

中序(對稱序)遍歷：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。

后序遍歷：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。

由于樹也是一種層次結(jié)構(gòu)，所以對樹有時也進(jìn)行按層遍歷，所謂按層遍歷，就是從樹根結(jié)點(diǎn)開

始，依次訪問每一層，對同一層結(jié)點(diǎn)，由左至右進(jìn)行訪問。

樹和森林的遍歷也主要有三種：先根次序、后根次序和層次次序。其中，前兩種是按深度優(yōu)先

方式進(jìn)行的，后一種是按廣度優(yōu)先方式進(jìn)行的。

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

按后序遍歷樹正好等同于按對稱序法遍歷對應(yīng)的二叉樹。

考點(diǎn)13：二叉樹的存儲與線索二叉樹

(1)二叉樹的Llink-rlink法存儲

二叉樹通常的存儲方式是鏈?zhǔn)酱鎯?，每個鏈結(jié)點(diǎn)除了數(shù)據(jù)域外，還可以增加兩個指針域llink

和rlink,分別指向左右兩個子結(jié)點(diǎn)。當(dāng)某個結(jié)點(diǎn)的子結(jié)點(diǎn)不存在時，相應(yīng)的指針值為空(nil)。

(2)線索二叉樹

一個具有n個結(jié)點(diǎn)的二叉樹若采用二叉鏈表存儲結(jié)構(gòu)，在2n個指針域中只有n-1個指針域是

用來存儲結(jié)點(diǎn)孩子的地址的，而另外n+1個指針域存放的都是nil。為了保留結(jié)點(diǎn)在某種遍歷序列中

直接前驅(qū)和直接后繼的位置信息，可以利用二叉樹的二叉鏈表存儲結(jié)構(gòu)中的這n+1個空指針域來記

錄這些信息。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索(thread),加了線索的

二叉樹稱為線索二叉樹。

(3)完全二叉樹的順序存儲

二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)

從上至下、從左到右的順序存儲。完全二叉樹或者滿二叉樹比較適合于順序存儲。

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

霍夫曼(Huffman)樹，也稱為最優(yōu)二叉樹，是指對于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具

有最小帶權(quán)路徑長度的二叉樹。

設(shè)二叉樹具有n個帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個葉結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值

的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為：

WPL=^WkLk

k=l

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

最優(yōu)二義樹算法為：對于n個權(quán)為w2,w3,w”的結(jié)點(diǎn)，首選找出兩個最小的叱值，

不妨設(shè)為W］和W2,然后對m-1個權(quán)W1+W2，W3,來解這個問題，并且將解中的代替，

如此進(jìn)行下去，直到所有的W構(gòu)成一棵二叉樹。

給定一組權(quán)值，構(gòu)造出來的霍夫曼樹不是唯一的。在霍夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。另

外，在霍夫曼樹中，沒有度為1的結(jié)點(diǎn)。

2.5查找

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

查找是確定一個元素在表或樹中的位置，衡量一個查找算法的標(biāo)準(zhǔn)是對關(guān)鍵碼平均比較的次

數(shù)，或稱為平均檢索長度ASL。對于線性表的查找主耍分下面幾種：

(1)順序查找

順序查找是線性表的最簡單的查找方法，其具體步驟是：用待查關(guān)鍵碼從頭開始逐個與表中元

素比較，直到找出相等的元素，則查找成功；或者找遍所有元素，則查找失敗。

順序查找的優(yōu)點(diǎn)：對線性表的結(jié)點(diǎn)的邏輯次序無要求，對線性表的存儲結(jié)構(gòu)無要求。

順序查找的缺點(diǎn)：平均檢索長度長，與表中結(jié)點(diǎn)個數(shù)n成正比，若檢索關(guān)鍵碼的概率相等，則

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

(2)二分查找

二分查找法是一種效率較高的線性表查找方法，要求線性表結(jié)點(diǎn)必須是按關(guān)鍵碼值排好序的，

且線性表以順序方式存儲。其具體步驟是：首選用要查找的關(guān)鍵碼值與線性表中間位置結(jié)點(diǎn)的關(guān)鍵

碼值相比較，這個中間結(jié)點(diǎn)把線性表分成兩個子表，比較相等則查找完成，不等則根據(jù)比較結(jié)果確

定下一步的查找應(yīng)該在哪一個子表中進(jìn)行，如此進(jìn)行下去，直到找到滿足要求的點(diǎn)。

二分查找的優(yōu)點(diǎn)：平均查找長度小，為［log?!!」

二分查找的缺點(diǎn)：線性表排序需要花費(fèi)時間，順序方式存儲的插入、刪除不便。

(3)分塊查找

分塊查找要求把線性表分成若干塊，每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須有序，還要

求將各塊中的最大關(guān)鍵碼值組成一個有序的索引表。其具體步驟是：首選在索引表中用順序查找或

二分查找法確定所求記錄所在的塊，然后再從該塊中用順序查找方法找出所求的記錄。

(4)散列表查找

散列法的基本思想是：由結(jié)點(diǎn)的關(guān)鍵碼決定結(jié)點(diǎn)的存儲地址，即以關(guān)鍵碼k為自變量，通過散

列函數(shù)計(jì)算出對應(yīng)的函數(shù)值h(k),將這個值解釋為結(jié)點(diǎn)的存儲地址。檢索時再根據(jù)要檢索的關(guān)鍵碼

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

散列法需要解決以下兩個問題：

a.構(gòu)造好的散列函數(shù)，能夠?qū)⒁唤M關(guān)鍵碼值盡可能均勻地安排在事先確定的范圍里，并且使

得發(fā)生碰撞的可能性最小?常見的散列函數(shù)有直接定址法除余法、數(shù)字分析法、折疊法、平方取中

法等。

b.制定解決碰撞的方案。處理碰撞的方法主要有拉鏈法和開放定址法。

影響產(chǎn)生沖突多少有以下三個因素：哈希函數(shù)是否均勻；處理沖突的方法；哈希表的負(fù)載因子。

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

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

CC------------------------------------------------------

基本區(qū)域能容納的結(jié)讖

負(fù)載因子的大小體現(xiàn)散列表的裝滿程度，e越大，則散列表裝得越滿，發(fā)生碰撞的機(jī)會越大，

一般取a<1o

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

(1)二叉排序樹

二叉排序樹是一類特殊的二叉樹，其特點(diǎn)是：若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于

根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；所有的子樹也遵守相同

的規(guī)則。

對二叉排序樹中序遍歷(周游)可以得到關(guān)鍵字從小到大的有序序列。對無序序列可以通過構(gòu)

造一棵二叉排序樹而變成一個有序序列，構(gòu)造二叉排序樹的過程就是對無序序列進(jìn)行排序的過程。

對二叉排序樹的操作主要的插入和刪除操作。

平衡二叉樹是對二叉排序樹的一種“平衡化”處理。結(jié)點(diǎn)的平衡因子定義為其右子樹高度減去

左子樹高度。若任一結(jié)點(diǎn)的平衡因子均取一1,0或+1,則此二叉排序樹為平衡的二叉排序樹(AVL

樹)。平衡二叉排序樹的查找方法與一般的二叉排序樹完全一樣，優(yōu)點(diǎn)是總能保持檢索長度為

OQogzn)量級。

往平衡二叉樹插入新結(jié)點(diǎn)時，需要對樹的結(jié)構(gòu)進(jìn)行必要調(diào)整，以動態(tài)地保持平衡二叉樹的特點(diǎn)。

（2）B樹和B+樹

B樹和B+樹是一種平衡的多路查找樹形結(jié)構(gòu)，用于組織外存儲器中文件的動態(tài)索引結(jié)構(gòu)。這樣

可以使得每個結(jié)點(diǎn)包含多個關(guān)鍵碼值，有多個孩子，使得樹的層次降低，查找時訪問外存的次數(shù)減

少。

由B樹定義可以知：

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

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

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

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

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

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

b.在B樹中，每個非葉結(jié)點(diǎn)的關(guān)鍵碼個數(shù)都在］「m/21T,m-1］之間。

c.B樹中關(guān)鍵碼的插入不是在葉結(jié)點(diǎn)上進(jìn)行的，而是在最底層的某個非終端結(jié)點(diǎn)中添加一個關(guān)

鍵碼。若插入結(jié)點(diǎn)上關(guān)鍵碼個數(shù)不超過mT個，則可直接插入到該結(jié)點(diǎn)上；否則，要進(jìn)行調(diào)整，即

結(jié)點(diǎn)的“分裂”。

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

a.有n棵子樹的結(jié)點(diǎn)中含有n個關(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.對B+樹進(jìn)行兩種查找運(yùn)算：一種是從最小關(guān)鍵碼起順序查找，另一種是從根結(jié)點(diǎn)開始，進(jìn)

行隨機(jī)查找。

2.6排序

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

插入排序的基本思想是每次將一個待排序記錄按其關(guān)鍵碼值大小插入到前面已排序的文件中

的合適位置上，直到記錄插入完為止。

a.直接插入排序：在已排好序的序列中查找插入位置時用順序法查找，找到插入位置后將該

位置原來的記錄及其后面所有的記錄順序后移一個位置，空出該位置來插入記錄。

b.二分法插入排序：在已排好的序列中找插入的位置時，用二分法查找，找到插入位置后和

直接插入排序法同樣處理。

c.shell排序：又稱縮小增量法，是按增量將文件分組。首先取增量di<n,把全部記錄分成出

個組，所有距離為出倍數(shù)的記錄放在一組中，各組內(nèi)用插入法排序，然后取d2<di，重復(fù)上述分組

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

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

選擇排序的基本思想是每次從待排序的記錄中選出關(guān)鍵碼值最?。ɑ蜃畲螅┑挠涗?，順序放在

已排記錄序列的最后，直到全部排完，這里主要講堆排序

堆排序是對一組待排序的關(guān)鍵碼，首先把它們按堆的定義排成一個序列（稱為建堆），這就找

到了最小的關(guān)鍵碼，然后將最小的關(guān)鍵碼取出，用剩下的關(guān)鍵碼再建堆，便得到次最小的關(guān)鍵碼，

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

堆排序的兩個主要問題：

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

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

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

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

a.起泡排序是將排序的記錄順次兩兩比較，若為逆序則進(jìn)行交換，將序列照此方法從頭到尾

處理一遍稱做一趟起泡。第二趟起泡再將次最大關(guān)鍵碼交換到倒數(shù)第二個位置，即它的最終位置，

如此進(jìn)行下去，若某一趟起泡過程中沒有發(fā)生任何交換，或排序已經(jīng)進(jìn)行了n-1趟，則排序過程結(jié)

束。

b.快速排序是在待排序序列中任取一個記錄，以它為基準(zhǔn)用交換的方法將所有的記錄分成兩

部分，關(guān)鍵碼值比它小的一個部分，關(guān)鍵碼值比它大的在另一部分，再分別對兩個部分實(shí)施上述過

程，一直重復(fù)到排序完成。

考點(diǎn)20：歸并排序

歸并排序的基本思想是對兩個或兩個以上的表組合成一個新的有序表。排序方法為先將原始序

列中的每個關(guān)鍵字都看作一個序列，兩兩有序歸并，逐步擴(kuò)大于序列尺寸，直到全部排序完成。

2.7經(jīng)典題解

一、選擇題

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

A）棧B）隊(duì)列

C）鏈表D）線性表

解析：數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器里的實(shí)現(xiàn)，如鏈表。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，

它只抽象地反映數(shù)據(jù)元素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的存儲方式。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)（如線性表、棧、

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

答案：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ī)中的存儲方式

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

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

解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)元素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的

存儲方式，在計(jì)算機(jī)中的存儲是由存儲結(jié)構(gòu)決定的。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)（如線性表、棧、隊(duì)列）和非線性結(jié)構(gòu)

（如樹）。

答案：B

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

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

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)是在存儲結(jié)構(gòu)上。主要的運(yùn)算包括插入、刪除、排序、查

找等。

答案：B

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

A）表達(dá)式求值

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

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

D）二叉樹對稱序周游算法的實(shí)現(xiàn)

解析：樹的層次次序周游算法需要先存儲每一層的結(jié)點(diǎn)，然后按照先進(jìn)后出的順序依次訪問結(jié)點(diǎn)信息，需要用

先進(jìn)先出的隊(duì)列來實(shí)現(xiàn)，而不是用先進(jìn)后出的棧來實(shí)現(xiàn)；表達(dá)式求值，需要設(shè)置操作數(shù)和操作符兩個棧；快速排序

需要用棧實(shí)現(xiàn)遞歸；二叉樹對稱序周游算法即中序周游算法，也需要用棧結(jié)構(gòu)實(shí)現(xiàn)。

答案：C

5.雙鏈表的每個結(jié)點(diǎn)包括兩個指針域。其中rlink指向結(jié)點(diǎn)的后繼，llink指向結(jié)點(diǎn)的前驅(qū)。如果要在p所指結(jié)

點(diǎn)后插入q所指的新結(jié)點(diǎn)，下列哪一個操作序列是正確的。（2007.09）

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

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

C）qf.llink:=p;qf.rlink:=pt.rlink;pf.rlinkt.llink:=q;pt.rlink:=q;

D）qf.rlinkt:=p:qt.llink:=pt.llink;pt.llinkf.rlink:=q;pt.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.

pqnewnode

LlinkRlinkLlinkRlinkLlinkRlink

答案：C

6.在包含1000個元素的線性表中實(shí)現(xiàn)如下運(yùn)算，哪一個所需執(zhí)行時間最長.（2007.09）

A）線性表按順序方式存儲，在線性表的第100個結(jié)點(diǎn)后面插入一個新結(jié)點(diǎn)

B）線性表按鏈接方式存儲、在線性表的第100個結(jié)點(diǎn)后面插入一個新結(jié)點(diǎn)

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

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

解析：線性表按順序方式存儲，執(zhí)行插入操作時要將插入點(diǎn)后的所有元素平移一個單位，在1000個元素的線

性表的第100個結(jié)點(diǎn)后插入新結(jié)點(diǎn)需要移動900個元素。鏈接方式存儲插入新結(jié)點(diǎn)需要查找100次找到結(jié)點(diǎn)再插入。

線性表按順序方式存儲，刪除第900個元素要將第900-1000個元素向前移動一個單位。按鏈接方式存儲，刪除指針

P指向結(jié)點(diǎn)，其平均查找長度為500.5。查找開銷比移動開銷要小。

答案：B

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

0123456789101112131415161718

1907519476855958208

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

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

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

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

基本區(qū)域能容納的結(jié)，敏

由題可知負(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ān)鍵碼值A(chǔ)在序列中的序號是<,(2007.09)

A)1B)4

C)8D)12

解析：堆排序是將待排序的關(guān)鍵碼先按堆的定義排成一個序列(稱為建堆)，找到最小的關(guān)鍵碼，然后將最小的

關(guān)鍵碼取出，用剩下的關(guān)犍碼再建堆，便得到次最小的關(guān)鍵碼，如此反復(fù)進(jìn)行，直至將全部關(guān)鍵碼排好序?yàn)橹?。?/p>

以初始建堆關(guān)鍵碼A即為堆頂，序號為1?

答案：A

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

A)0(1)B)O(log2n)

2

C)O(n)D)0(n)

解析：起泡排序僅需一個輔助存儲空間作為記錄在交換位置時的緩存空間。

答案:A

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

A)數(shù)據(jù)是采用計(jì)算機(jī)能夠識別、存儲和處理的方式，對現(xiàn)實(shí)世界的事物進(jìn)行的描述

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

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

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

解析：一個數(shù)據(jù)元素可由一個或若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是有獨(dú)立含義的不可分割的數(shù)據(jù)的最小單位。數(shù)據(jù)

是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識別、存儲和處理的符號的總稱。

答案：C

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

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

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

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

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

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

A)I、II和IIB)I、ILIII和IV

C)ILIV和VD)I、IH和V

解析：鏈?zhǔn)酱鎯Y(jié)構(gòu)中除了包含保存數(shù)據(jù)元素自身信息的信息域外，還有表示數(shù)據(jù)元素之間的鏈接信息的指針

域，因此比順序存儲結(jié)構(gòu)的存儲密度低；鏈?zhǔn)酱鎯Y(jié)構(gòu)中邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰；不是所有節(jié)

點(diǎn)都包含指針域，如單向鏈表中坡后一個節(jié)點(diǎn)的指針為空。

答案：D

12和13基于以下描述：有一個初始為空的棧和輸入序列A、B、C、E、F、G：現(xiàn)發(fā)過如下操作：

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

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

A)BEB)BD

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刪除。由此可見刪除的序列為BEDC。

答案：C

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

A)AB)BD

C)ABCED)ABCDE

解析：通過上題的分析可知，在操作過程中進(jìn)棧的有ABCDE,刪除的有BEDC,因此最后棧中的元素只有A。

答案：A

14-15基于如下所示的二叉樹。

4

BC

DE

FG

14.該二叉樹對應(yīng)的樹林包括幾棵樹.(2007.04)

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

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

叉樹的右子樹對應(yīng)于樹林中其余的樹；二叉樹右子樹的根節(jié)點(diǎn)作為余下樹中第一棵樹的根節(jié)點(diǎn)，其余以此類推。本

題中的二叉樹應(yīng)該包含2棵樹。

答案：B

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

A)DBAFEGCB)ABCDEFG

C)DBFGECAD)ACBEGDF

解析?：后序遍歷二叉樹的次序是：后序遍歷左子樹I后序遍歷右子樹，訪問根節(jié)點(diǎn)。因此后序遍歷此二叉樹對

應(yīng)的樹林所得的節(jié)點(diǎn)序列為選項(xiàng)C.

答案：C

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

A)DBAFEGCB)ABCDEFG

C)DBFGECAD)ACBEGDF

解析：按層次次序遍歷二義樹的次序是：從樹的根節(jié)點(diǎn)開始，依次訪問每一層，對同一層節(jié)點(diǎn)，由左到右進(jìn)行

訪問。因此按層次次序遍歷此二叉樹對應(yīng)的樹林所得的節(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)行排序，

采取以第一個關(guān)鍵碼為分界元素的快速排序法，第一趟排序完成后關(guān)鍵碼95被放到第幾個位置。(2007.04)

A)7B)8

C)9D)10

解析：快速排序法第一趟排序后，關(guān)鍵碼序列為(12,18,9,25,67,82,53,95,33,70),因此關(guān)鍵碼95

處在第8個位置。

答案：B

18.設(shè)散列表的地址空間為0到16,散列函數(shù)為h(k)=kmodl7,用線性探查法解決碰撞。現(xiàn)從空的散列表開始，

依次插入關(guān)鍵碼值190,89,217,208,75,177,則最后■?個關(guān)鍵碼177的地址為。(2007.04)

A)6B)7

C)8D)9

解析：本題采用除留余數(shù)法構(gòu)造散列函數(shù)，將關(guān)鍵碼值190,89,217,208,75,177分別帶入h(k)=kmodl7,

得到散列地址分別為3,4,13,4,7,7,在存儲關(guān)鍵碼208時，由于其散列地址4與前面的一個關(guān)鍵碼發(fā)生沖突，

因此其存儲地址向后移1位到5。而存儲關(guān)鍵碼177時，由于其散列地址7與前面的一個關(guān)鍵碼發(fā)生沖突，因此其

存儲地址再向后移1位至IJ8.

答案：C

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

I.數(shù)據(jù)的采集II.數(shù)據(jù)的邏輯組織

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

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

A)II和IVB)I、IIIII

C)II、IIIfnVD)1、III和V

解析?：數(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ù)的存儲無關(guān)。數(shù)據(jù)的存儲器內(nèi)表示，它是指用計(jì)算機(jī)語言實(shí)現(xiàn)的邏輯結(jié)構(gòu)，它

依賴于計(jì)算機(jī)語言。數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。

答案：c

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

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

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

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

D)數(shù)據(jù)元素乂稱作記錄

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

以由若干個數(shù)據(jù)項(xiàng)組成，有時也稱作結(jié)點(diǎn)、記錄、表目等。

答案：B

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

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

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

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

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

解析：數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的表示，又稱數(shù)據(jù)的物理結(jié)構(gòu)。分為順序存儲結(jié)

構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。數(shù)據(jù)采用不同的存儲結(jié)構(gòu)，將對數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)有著巨大的影響.

答案：B

22.棧S最多能容納4個元素?，F(xiàn)有6個元素按A、B、C、D、E、F的順序進(jìn)棧，下列哪一個序列是可能的

出棧序列o(2006.09)

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

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

解析：對于選項(xiàng)A,因?yàn)樵摋Ｗ疃嘀荒苋菁{4個元素，而E是第五個元素，在前4個元素還沒出棧的情況下是

不可能進(jìn)棧再出棧的。對于選項(xiàng)B,A元素不可能在D元素還沒出棧的情況下先出棧；對于選項(xiàng)C,其出棧序列為：

C、B、E、D、A、F：對于選項(xiàng)D,B元素不可能在C元素還沒出棧情況下出棧，出棧序列為選項(xiàng)C。

答案：C

23.從單鏈表中刪除指針s所指結(jié)點(diǎn)的下一個結(jié)點(diǎn)t,其關(guān)鍵運(yùn)算步驟為。(2006.09)

A)sf.link:=tB)tT』ink:=s

C)tf.link:=sf.linkD)sf.link:=tT』ink

解析：要從單鏈表中刪除指針s所指節(jié)點(diǎn)的下一個節(jié)點(diǎn)l,則原節(jié)點(diǎn)t指的后繼節(jié)點(diǎn)成為s所指的后繼節(jié)點(diǎn)，因

此關(guān)鍵運(yùn)算步驟為：sT，link:=tj.linko

答案：D

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

aH0...0

a2[a22???0

Ann=

????????????

LanlIann92...annnn

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

A)IJ3C(aij)=LOC(a11)+ix(i+l)/2+j

B)UDC(aij)=IJDC(a11)4-ix(i+l)/24-(j-l)

C)LOC(ajj)=LOC(a||)+ix(i-l)/2+j

D)LOC(aij)=LOC(all)+ix(i-l)/2+(j-l)

解析：非零元素a”在矩陣中處在第i行第j列，在按行優(yōu)先順序存儲時，應(yīng)先存儲前i-1行的非零元素和同一

行的前jT個元素。如果a”的存儲地址為LOC(au),則a,的存儲地址為D。

答案：D

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

A)若一個結(jié)點(diǎn)是某二叉樹對稱序的最后一個結(jié)點(diǎn)，則它必是該二叉樹前序的最后一個結(jié)點(diǎn)

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

C)若一個樹葉是某二叉樹對稱序的最后一個結(jié)點(diǎn)，則它必是該二叉樹前序的最后一個結(jié)點(diǎn)

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

解析?：若一個樹葉是某二又樹對稱序的最后一個節(jié)點(diǎn)，則它必是該二叉樹最右邊的樹葉，即前序的最后一個節(jié)

點(diǎn)。而若將“樹葉”改為“結(jié)點(diǎn)”則不正確，因?yàn)橛锌赡艹霈F(xiàn)二叉樹最右結(jié)點(diǎn)無右孩子的情況。

答案：C

26.如下所示是一棵5階B樹，該B樹現(xiàn)在的層數(shù)為2。從該B樹中刪除關(guān)鍵碼38后，該B樹的第2層的結(jié)

點(diǎn)數(shù)為。(2006.09)

A)6B)7

C)8D)9

解析：刪除38后該節(jié)點(diǎn)剩下的關(guān)鍵碼的個數(shù)為1,小于「5/21-1=2,所以刪除后要將該結(jié)點(diǎn)剩余的41與雙親

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

答案：A

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

A）直接插入排序B）直接選擇排序

C）快速排序D）歸并排序

解析：直接插入排序，若文件基本有序，則比較次數(shù)最小為nT次，移動次數(shù)為0：直接選擇排序，無論待排

序文件是否基本有序，其比較次數(shù)均為n（nT）/2,若文件基本有序，則移動次數(shù)減少，最小為0；快速排序在文件基

本有序時蛻化為起泡排序，時間復(fù)雜度為n（n-l）/2；對于歸并排序，無論待排序文件是否基本有序，其比較次數(shù)均

為|■log,n，若文件基本有序，則移動次數(shù)減少，最小為0，可見直接插入排序效率最高。

答案：A

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

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

B）數(shù)據(jù)的存儲結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(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)可以劃分為集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀

結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。數(shù)據(jù)的存儲結(jié)構(gòu)指的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像），它包括順序存儲和鏈?zhǔn)酱鎯煞N結(jié)

構(gòu)。節(jié)點(diǎn)是由若干位組合起來形成的位串，數(shù)據(jù)的最小單位是節(jié)點(diǎn)中的?個二進(jìn)制數(shù)位（bit）。

答案：C

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

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

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

C）串只能順序存儲

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

解析：串是由零個或多個字符組成的有限序列：如果串中沒有任何字符，則稱為空串。由一個或多個空格組成

的串稱為空格串，空格串不是空串，因?yàn)榭崭翊杏凶址?；串既可以順序存儲也可以鏈表存?：串的基本操作一般

是以“串的整體”作為操作對象，“推入”不是串的基本運(yùn)算。

答案：A

30.雙鏈表的每個結(jié)點(diǎn)包括兩個指針域。其中rlink指向結(jié)點(diǎn)的后繼，llink指向結(jié)點(diǎn)的前驅(qū)。如果要在p所指

結(jié)點(diǎn)前面插入q所指的新結(jié)點(diǎn)，下列哪一個操作序列是正確的。（2006.04）

A）p|.rlinkf.llink:=q：pf.rlink:=q；q1.llink:=p；q1.rlink:=pf.rlink；

B）p1'.llinkf.rlink:=q；pf.llink:=q；qT.Hink:=p；qf.llink:=pT.llink；

C）q|.llink:=p；q1.rlink:=pf.rlink；p|.rlinkf.llink:=q：pf.rlink:=q；

D）q|.rlink:=p；qT，llink:=pf.llink；p|.llinkf.rlink:=q；pf.llink:=q；

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

即qT，rlink:=p；qf.llink:=pf.llink；pf.llink）.rlink:=q；pT.Hink:=q。

答案：D

31.下列咖一個不是隊(duì)列的基本運(yùn)算。（2006.04）

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

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

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

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

解析?：隊(duì)列的基本操作有：構(gòu)造一個空隊(duì)列；將隊(duì)列清為空隊(duì)列；判斷隊(duì)列是否為空隊(duì)列；計(jì)算隊(duì)列的長度；

讀取隊(duì)列的隊(duì)頭元素；向隊(duì)列插入一個元素為該隊(duì)列的隊(duì)尾元素；刪除隊(duì)列隊(duì)頭元素。隊(duì)列只允許在隊(duì)尾插入元素，

而在隊(duì)頭刪除元素。

答案：B

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

A)表達(dá)式求值

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

C)二叉樹對稱序周游算法的實(shí)現(xiàn)

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

解析：見第4題。

答案：B

33.按層次次序?qū)⒁豢糜衝個結(jié)點(diǎn)的完全二叉樹的所有結(jié)點(diǎn)從1到n編號，當(dāng)i<n/2時，編號為i的結(jié)點(diǎn)的左

孩子的編號是?(2006.04)

A)2i-lB)2i

C)2i+lD)不確定

解析：若對有n個節(jié)點(diǎn)的完全二叉樹按層次從上到下，每個層次從左至右的規(guī)則為節(jié)點(diǎn)編號，若i4n/2,則編

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

答案：B

34.對于給出的一組權(quán)w={10,12,16,21,30),通過霍夫曼算法求出的擴(kuò)充二叉樹的帶權(quán)外部路徑長度

為。(2006.04)

A)89B)189

C)200D)300

解析：霍夫曼算法建立的擴(kuò)充二又樹如下圖所示。所以帶權(quán)外部路徑長度為(21+16)X2+30X2+(12+10)X3=200

211630

1210

答案：C

35.設(shè)散列表的地址空間為。到10,散列函數(shù)為h(k戶kmodll,用線性探查法解決碰撞?，F(xiàn)從空的散列表開始,

依次插入關(guān)鍵碼值95,14,27,68,82,則最后一個關(guān)鍵碼82的地址為.(2006.04)

A)4B)5

C)6D)7

解析：本題采用除留余數(shù)法構(gòu)造散列函數(shù)，將關(guān)鍵碼值95,14,27,68,82分別帶入h(k)=kmodll,得到

散列地址分別為7,3,5,2,5,當(dāng)存儲關(guān)鍵碼82時，由于其散列地址與前面的一個關(guān)鍵碼發(fā)生沖突，因此其存儲

地址向后移I位到6。

答案：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）是下列哪一個排序算法一趟掃描的結(jié)果。（2006.04）

A）起泡排序

B）初始步長為4的希爾（shell）排序

C）二路歸并排序

D）以第一個元素為分界元素的快速排序

解析：若進(jìn)行升序起泡排序，則因?yàn)镼大于H,因此Q和H要交換，新序列第一個字符應(yīng)該為H；若進(jìn)行降

序起泡排序，Q和H位置不變；若進(jìn)行希爾排序，始步長為4,則Q應(yīng)該與P分為一組，新序列的第一個字符應(yīng)該

為P（升序）或Q（降序）。若進(jìn)行二路歸并排序，則Q和H歸并，排序后的結(jié)果應(yīng)該為H,Q（升序）或者Q,H

（降序）。快速排序以第一個元素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ī)中的存儲方式

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

D）樹形結(jié)構(gòu)是典型的非線性結(jié)構(gòu)

解析：如第2題。

答案：B

38.在包含1000個元素的線性表中實(shí)現(xiàn)如下各運(yùn)算，哪?個所需的執(zhí)行時間最短?（2005.09）

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

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

C）線性表按順序方式存儲，查找線性表中第900個結(jié)點(diǎn)

D）線性表按鏈接方式存儲，查找線性表中第900個結(jié)點(diǎn)

解析：線性表順序方式存儲，可直接計(jì)算確定第i個節(jié)點(diǎn)的存儲地址，其執(zhí)行時間與i的值沒有關(guān)系。查找鏈

接存儲方式的線性表中的第i個