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

各章例題Contents第1章例題1第4章例題2第4-1章例題3第4-2章例題4第7章例題6第5章例題5第8章例題7第9章例題8第1章例題選擇題A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu) D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)【答案】C在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：（）判斷題：1、每種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)總是一致的（）2、數(shù)據(jù)元素是數(shù)據(jù)的最小單位（）3、數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位（）4、數(shù)據(jù)結(jié)構(gòu)就是指數(shù)據(jù)在計(jì)算機(jī)中的存儲結(jié)構(gòu)（）【答案】1、錯(cuò)誤

2、錯(cuò)誤

3、正確

4、錯(cuò)誤第1章例題填空題：1、存儲結(jié)構(gòu)的基本類型是 （）。2、在算法正確的前提下，評價(jià)一個(gè)算法的兩個(gè)標(biāo)準(zhǔn)是 （）3、數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容包括的三個(gè)方面是 （)4、若各數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡單的表示出來，則稱之為（），否則稱之為 （）。順序存儲、鏈?zhǔn)酱鎯?、索引存儲、散列存儲時(shí)間復(fù)雜度、空間復(fù)雜度邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法線性結(jié)構(gòu)非線性結(jié)構(gòu)第1章例題分析題：設(shè)n為正整數(shù)，確定下列劃線語句的執(zhí)行頻度。

for(i=0;i<n;i++)for(j=0;j<i;j++)for(k=0;k<j;k++)

x=x+1;【分析】語句的執(zhí)行頻度是該語句重復(fù)執(zhí)行的次數(shù)。計(jì)算循環(huán)語句段中某一語句的執(zhí)行次數(shù)，要得到語句執(zhí)行與循環(huán)變量之間的關(guān)系?！窘獯稹?/p>

這是一個(gè)三層嵌套循環(huán)，最內(nèi)層的循環(huán)次數(shù)由j決定，次內(nèi)層的循環(huán)次數(shù)由i決定，而i從1變化到n。所以劃線語句的執(zhí)行頻度為：第1章例題概念題1、描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。

【解答】

頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)或首元結(jié)點(diǎn)）的指針；在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；首元結(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空，頭指針均不為空，否則表示空表的鏈表的頭指針為空。第4章例題2、簡述線性表的兩種存儲結(jié)構(gòu)的主要優(yōu)缺點(diǎn)及各自適用的場合。【分析】【解答】

順序存儲可以按位置直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作是將引起元素移動，降低了效率；鏈?zhǔn)酱鎯υ卮鎯Σ捎脛討B(tài)分配，利用率高，但需增設(shè)表示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作十分簡單。順序存儲適用于線性表中元素?cái)?shù)量基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素的情況；而鏈?zhǔn)酱鎯m用于頻繁進(jìn)行元素的動態(tài)插入或刪除操作的場合。線性表的兩種主要存儲結(jié)構(gòu)各有其優(yōu)點(diǎn)和缺點(diǎn)，不能簡單地說哪個(gè)好哪個(gè)差，要根據(jù)實(shí)際問題和其適用的場合使用。第4章例題3、下面關(guān)于線性表的敘述中，錯(cuò)誤的是()

A）線性表采用順序存儲，必順占用一片連續(xù)的存儲單元。

B）線性表采用順序存儲，便于進(jìn)行插入和刪除操作。

C）線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

D）線性表采用鏈接存儲，便于插入和刪除操作。4、下面關(guān)于串的敘述中，哪一個(gè)是不正確的?()

A)串是字符的有限序列

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

C)模式匹配是串的一種重要運(yùn)算

D)串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

【答案】3、B4、B第4章例題5、下述哪一條是順序存儲方式的優(yōu)點(diǎn)?()A)存儲密度大

B)插入運(yùn)算方便C)刪除運(yùn)算方便

D)可方便地用于各種邏輯結(jié)構(gòu)的存儲表示【答案】5、A

6、C

第4章例題6、以下關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中哪一條是不正確的?

A)結(jié)點(diǎn)除自身信息外還包括指針域,因此存儲密度小 于順序存儲結(jié)構(gòu)

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

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

D)插入、刪除運(yùn)算操作方便,不必移動結(jié)點(diǎn)

7、單鏈表的每個(gè)結(jié)點(diǎn)中包括一個(gè)指針link，它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)?，F(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的單鏈表結(jié)點(diǎn)之后，下面的操作序列中哪一個(gè)是正確的？()

A）q=p->link;p->link=q->link

B）p->link=q->link;q=P->link

C）q->link=p->link;p->link=q;

D）p->link=q;q->link=p->link

【答案】7、C第4章例題第4-1章例題1、有６個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列:()

A)5,4,3,6,2,1B)4,5,3,1,2,6

C)3,4,6,5,2,1D)2,3,4,1,5,62、以下哪一個(gè)不是棧的基本運(yùn)算?()

A)刪除棧頂元素B)刪除棧底元素

C)判斷棧是否為空D)將棧置為空棧3、以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？()

A）從隊(duì)尾插入一個(gè)新元素B）讀取隊(duì)頭元素的值

C）判斷一個(gè)隊(duì)列是否為空D）從隊(duì)列中刪除第i個(gè)元素【答案】1、C2、B3、D4、設(shè)棧S的初始狀態(tài)為空，隊(duì)列Q的初始狀態(tài)為

________________

a1a2a3a4

________________

↑↑

隊(duì)頭隊(duì)尾

對棧S和隊(duì)列Q進(jìn)行下列兩步操作：

1)、刪除Q中的元素，將刪除的元素插入S，直至Q為空。

2)、依次將S中的元素插入Q,直至S為空。

在上述兩步操作后，隊(duì)列Q的狀態(tài)是________。

第4-1章例題【答案】a4a3a2a15、判斷一個(gè)循環(huán)隊(duì)列Q（元素最多為n）為空的條件是（）

A）Q->rear=Q->front B）Q->rearQ->front C）Q->front==（Q->rear+1）MODn D）Q->front(Q->rear+1）MODn6、判斷一個(gè)循環(huán)隊(duì)列Q（元素最多為n）為滿的條件是（）

A）Q->rear==Q->front B）Q->rearQ->front C）Q->front==（Q->rear+1）MODn D）Q->front

（Q->rear+1）MODn7、設(shè)有一個(gè)單端受限的雙端隊(duì)列Q，元素入隊(duì)序列為：ABCD,

問不可能的輸出序列有哪些？第4-1章例題【答案】5、A7、輸入受限：DBCA6、C輸出受限：DBCA第4-2章例題1、設(shè)有二維數(shù)組A[0..9，0..19]，其每個(gè)元素占2個(gè)字節(jié)，數(shù)組按列優(yōu)先順序存儲，第一個(gè)元素的存儲地址為100,那么元素A[6,6]的存儲地址為______.

2、以下關(guān)于廣義表的敘述中,正確的是

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

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

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

D)廣義表不能為空表

3、廣義表（（a））的表頭是（），表尾是（）

A、aB、（a） C、（） D、（（a））【答案】1、2322、A3、B，C

4、求下列廣義表的操作結(jié)果

Head（((a，b)，(c，d))）

Tail（((a，b)，(c，d))）

Head(Tail(((a，b)，(c，d)))) Tail(Head(((a，b)，(c，d)))) Head(Tail(Head(((a，b)，(c，d)))))【答案】

Head（((a，b)，(c，d))）=(a，b)

Tail（((a，b)，(c，d))）=((c，d))

Head(Tail(((a，b)，(c，d))))=(c，d)

Tail(Head(((a，b)，(c，d))))=(b) Head(Tail(Head(((a，b)，(c，d)))))=b

第4-2章例題1、在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹中，（1）高度最小的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？（2）高度最大的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？【答案】

（1）結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹的高度為2，有2層；它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；（2）高度最大的樹的高度為n，有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。第5章例題2、試分別找出滿足以下條件的所有二叉樹：

(1)二叉樹的前序序列與中序序列相同; (2)二叉樹的中序序列與后序序列相同; (3)二叉樹的前序序列與后序序列相同?！窘獯稹?(1)二叉樹的前序序列與中序序列相同： 空樹或缺左子樹的單支樹；

(2)二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；

(3)二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。第5章例題3、深度為k（根的層次為1）的完全二叉樹至少有多少個(gè)結(jié)點(diǎn)？至多有多少個(gè)結(jié)點(diǎn)？k與結(jié)點(diǎn)數(shù)目n之間的關(guān)系是什么？【分析】由完全二叉樹的定義可知，對于k層的完全二叉樹，其上的k-1層是一棵深度為k-1的滿二叉樹。所以對于所有深度為k的完全二叉樹，它們之間的結(jié)點(diǎn)數(shù)目之差等于各樹最后一層的結(jié)點(diǎn)數(shù)目之差?！窘獯稹?/p>

深度為k的完全二叉樹，其最少的結(jié)點(diǎn)數(shù)=深度為k-1的滿二叉樹的結(jié)點(diǎn)數(shù)+1=；其最多的結(jié)點(diǎn)數(shù)=深度為k的滿二叉樹的結(jié)點(diǎn)數(shù)=。

k與結(jié)點(diǎn)數(shù)目n之間的關(guān)系可以根據(jù)二叉樹的性質(zhì)4得出：第5章例題4、對于深度為k，且只有度為0或2的結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)數(shù)至少有多少？至多有多少？(分析)【解答】

結(jié)點(diǎn)數(shù)至多有：2k-1

結(jié)點(diǎn)數(shù)至少有：2k-1【分析】

對于結(jié)點(diǎn)數(shù)至多為多少的問題比較好回答，我們知道滿二叉樹中只有度為0或2的結(jié)點(diǎn)，所以結(jié)點(diǎn)數(shù)至多為同等深度的滿二叉樹的結(jié)點(diǎn)數(shù)。對于結(jié)點(diǎn)數(shù)至少為多少的問題，由于樹中只存在度為0或2的結(jié)點(diǎn)，即對一個(gè)結(jié)點(diǎn)而言，要么它沒有子結(jié)點(diǎn)，要么就有兩個(gè)子結(jié)點(diǎn)，所以在這樣的樹中，除第一層（根所在的層）外，每一層至少有兩個(gè)結(jié)點(diǎn)。第5章例題5、已知一棵二叉樹的中序序列為BDCEAFHG，后序序列為DECBHGFA，求對應(yīng)的二叉樹?！痉治觥扛鶕?jù)各種遍歷方法的定義，可知：二叉樹先序序列=根+左子樹先序序列+右子樹先序序列；二叉樹中序序列=左子樹中序序列+根+右子樹中序序列；二叉樹后序序列=左子樹后序序列+右子樹后序序列+根；從先序和后序序列中可以很容易的知道那一個(gè)結(jié)點(diǎn)是根，而在中序序列中，可以根據(jù)根得到左、右子樹的中序序列，相應(yīng)的也就知道左、右子樹的結(jié)點(diǎn)集合了?？梢愿鶕?jù)集合中的結(jié)點(diǎn)劃分先序或后序序列中除根以外的結(jié)點(diǎn)序列，從而得到左、右子樹的先序或后序序列。依次類推，便可以遞歸得到整棵二叉樹。中序序列左子樹中序序列根右子樹中序序列前序序列根左子樹前序序列右子樹前序序列第5章例題【解答】

構(gòu)造這棵二叉樹的過程如下所示：中序序列：BDCE[A]FHG后序序列：DECBHGF[A]中序：[B]DCE后序：DEC[B]

中序：[F]HG后序：HG[F]中序：D[C]E后序：DE[C]中序：H[G]后序：H[G]中序：[D]后序：[D]中序：[E]后序：[E]中序：[H]后序：[H]AFGHEDCB可以畫出這棵二叉樹為：第5章例題與上題有關(guān)的往屆考題：1、二叉樹的先序遍歷和中序遍歷為：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是（）

A）EB）FC）GD）H2、某二叉樹結(jié)點(diǎn)的對稱序（中序）序列為ABCDEFG，后序序列為BDCAFGE。該二叉樹結(jié)點(diǎn)的前序序列為（）

A）EGFACDBB）EACBDGF

C）EAGCFBDD）EGACDFB3、如果一棵二叉樹結(jié)點(diǎn)的前序序列是ABC，后序序列是CBA，則該二叉樹結(jié)點(diǎn)的對稱序序列

A)必為ABCB)必為ACB

C)必為BCAD)不能確定【答案】1、C2、B3、D第5章例題6、分別畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。并判斷下列論述是否正確，為什么？（1）二叉樹是一種特殊的樹；（2）度為2的樹是一棵二叉樹；（3）度為2的有序樹是一棵二叉樹。

【解答】具有3個(gè)結(jié)點(diǎn)的樹有兩種形態(tài)，如圖1所示；而具有3個(gè)結(jié)點(diǎn)的二叉樹有5種形態(tài)，如圖2所示。

圖1圖2具有3個(gè)結(jié)點(diǎn)的二叉樹的5種形態(tài)（1）錯(cuò)誤（2）錯(cuò)誤（3）錯(cuò)誤第5章例題7、在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序

A）都不相同B）先序和中序相同，而與后序不同

C）完全相同D）中序和后序相同，而與先序不同

8、在完全二叉樹中，若一個(gè)結(jié)點(diǎn)只有一個(gè)葉結(jié)點(diǎn)，則它沒

A）左子結(jié)點(diǎn)B）左子結(jié)點(diǎn)和右子結(jié)點(diǎn)

C）右子結(jié)點(diǎn)D）左子結(jié)點(diǎn)、右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)9、在下列存儲形式中，哪一個(gè)不是樹的存儲形式

A）雙親表示法B）孩子鏈表表示法

B）孩子兄弟示法D）順序存儲表示法【答案】7、C8、C9、D第5章例題填空：10、在樹中，一個(gè)結(jié)點(diǎn)的直接子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的_____。11、如果對于給定的一組權(quán)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為________。12、用數(shù)組A[1..n]順序存儲完全二叉樹的各結(jié)點(diǎn),則當(dāng)i<=(n-1)/2時(shí),結(jié)點(diǎn)A[i]的右孩子是結(jié)點(diǎn)_________。13、完全二叉樹中某結(jié)點(diǎn)無左子樹，則它必是___________。

【答案】10、度11、哈夫曼樹(Huffman)12、A[2i+1]13、葉子第5章例題14、對于如圖所示的森林（1）將其轉(zhuǎn)換為相應(yīng)的二叉樹；（2）寫出該森林的先序遍歷序列和中序遍歷序列?！敬鸢浮緼圖題14BCEFDGHIJKLABCEFDGHIJKL先序序列為：ABDEFCGHIJK中序序列為：DEFBCAHIJGLK

第5章例題15、已知一棵樹的先根遍歷序列為ABCED，后根遍歷序列為BECDA，求對應(yīng)的樹?！痉治觥扛鶕?jù)樹與二叉樹之間的轉(zhuǎn)換關(guān)系，可知：樹的先序序列=對應(yīng)二叉樹先序序列樹的后跟序列=對應(yīng)二叉樹中序序列因此，可以先這兩個(gè)序列構(gòu)造對應(yīng)的二叉樹，再將二叉樹轉(zhuǎn)換為樹?！敬鸢浮緼BCDEABCDE第5章例題16、設(shè)電文中出現(xiàn)的字母為A、B、C、D和E，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別9、27、3、5、和11。按哈夫曼編碼，則C的編碼為:A、10B、110C、1110D、1111【分析】先構(gòu)造哈夫曼樹，再根據(jù)哈夫曼樹進(jìn)行編碼。注意：在構(gòu)造哈夫曼樹時(shí)，應(yīng)注意左右孩子的排列。

ABCDE9273

5118

927118172711

1728

27

2855【答案】C55273511281789第5章例題⒈在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。

A.1/2B.1C.2D.4⒉在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。

A.1/2B.1C.2D.4⒊一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（）條邊。

A.nB.n(n-1)C.n(n-1)/2D.2n⒋具有4個(gè)頂點(diǎn)的有向完全圖有（）條邊。

A.6B.12C.16D.20【答案】1、C2、B3、C4、B第7章例題⒌對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）：

A.nB.(n-1)2C.n-1D.n2⒍已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。

①A.abecdfB.acfebdC.aebcfdD.aedfcb②A.abcedfB.abcefdC.aebcfdD.acfdeb【答案】5、D6、①D②Babcedf第7章例題7、下面關(guān)于圖的存儲的敘述中正確的是

A）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)

B）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)

C）用鄰接表法存儲圖，占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)

D）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)【答案】A第7章例題8、對于下面有向圖（1）可能的拓?fù)湫蛄袨椋ǎ?/p>

A)abcdefB)aebcdfC)abcfedD)abedcf

（2）可以排成多少個(gè)不同的拓?fù)湫蛄校ǎ?/p>

A)2B)3C)4D)5【答案】(1)D(2)B

bacedf第7章例題1、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）

A)插入排序B)選擇排序C)快速排序D)歸并排序2、在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排序次序無關(guān)的是（）

A)起泡排序B)希爾排序C)插入排序D)選擇排序3、排序方法中，從未排序隊(duì)列中依次取出元素與已排序序列（初始時(shí)為第1個(gè)元素）中的元素進(jìn)行比較，然后放入到已排序序列中的正確位置上，這種方法稱為（）

A)起泡排序B)選擇排序C)插入排序D)堆排序4、下列排序方法中，（）是從未排序序列中依次挑選元素，并將其放入已排序序列（初始為空）的末尾。

A)希爾排序B)歸并排序C)選擇排序D)插入排序【答案】1、A2、D3、C4、C第8章例題4、下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法?

A)直接選擇排序B)二分法插入排序

C)希爾排序D)快速排序。5、對n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間為

A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)6、用直接插入排序方法對下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是

A）94、32、40、90、80、46、21、69B）32、40、21、46、69、94、90、80

C）21、32、46、40、80、69、90、94D）90、69、80、46、21、32、94、407、用快速排序法對包含n個(gè)關(guān)鍵字的序列進(jìn)行排序，最環(huán)情況下的執(zhí)行時(shí)間為

A）O(log2n)B）O(n)C）O(nlog2n)D）O(n2)【答案】4、A5、C6、C7、D第8章例題8、下列哪一個(gè)關(guān)鍵碼序列不符合堆的定義？

9、已知一個(gè)序列為{21，39，35，12，17，43}，則利用堆排序的方法建立的初始堆為（）

A）39，21，35，12，17，43B）43，39，35，12，17，21C）43，39，35，21，17，12D）43，35，39，17，21，12

10、一組記錄的關(guān)鍵字為{46，79，50，38，42，80}，利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為

A）38，42，46，50，79，80B）42，38，46，79，50，80C）42，38，46，50，79，80D）42，38，46，80，50，76

【答案】8、C9、B10、C

A)A、C、D、G、H、M、P、Q、R、X

B)A、C、M、D、H、P、X、G、O、R

C)A、D、P、R、C、Q、X、M、H、G

D)A、D、C、M、P、G、H、X、R、Q

第8章例題11、用某種排序方法對線性表（25，84，21，47，15，27， 68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則所采用的排序方法是（）

A）選擇排序B）快速排序C）歸并排序D）希爾排序12、在插入排序、希爾排序、選擇排序、堆排序、快速排序、歸并排序中，排序穩(wěn)定的有————?！敬鸢浮?1、B12、插入排序、歸并排序第8章例題13、已知如下的程序代碼:for(i=1;i<n;i++){

x=A[i];j=i-1;

while(j>=0&&A[j]>x){

A[j+1]=A[j];

j=j-1；

}

A[j+1]=x；

}

1、這段代碼所描述的排序方法是____________。2、這段代碼所描述的排序方法的時(shí)間復(fù)雜度為______。

3、假設(shè)這段代碼開始執(zhí)行時(shí),數(shù)組A中的元素已經(jīng)按值的遞增次序排好了序,則這段代碼的執(zhí)行時(shí)間為____________。【答案】1、插入排序2、O(n2)3、O(n)

第8章例題1、以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)?

A)棧B)散列表C)二叉樹D)雙鏈表2、對包含n個(gè)元素的散列表進(jìn)行檢索，平均檢索長度

A)為O(log2n)B)為O(n)

C)為O(nlog2n)D)不直接依賴于n3、對線性表進(jìn)行二分法查找，其前提條件是

A）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

B）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序

C）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

D）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序【答案】1、A2、D3、B第9章例題4、畫出對長度為10的有序表進(jìn)行折半查找的一棵判定樹，并求其等概率時(shí)查找成功的平均查找長度?！痉治觥俊窘獯稹?/p>

判定樹如圖所示。等概率時(shí)查找成功的平均查找長度

ASLsucc=(1*1+2*2+3*4+4*3)/10=29/10=2.9假設(shè)分別用1至10表示表中的10個(gè)結(jié)點(diǎn)，要畫出對此有序表進(jìn)行折半查找的判定樹，須進(jìn)行折半查找的過程，用第一次得到的mid結(jié)點(diǎn)5作為判定樹的根結(jié)點(diǎn)，用后面得到的兩個(gè)mid結(jié)點(diǎn)2和8為根結(jié)點(diǎn)構(gòu)造根結(jié)點(diǎn)的兩棵子樹，…

根據(jù)判定樹，平均查找長度即為各層的結(jié)點(diǎn)數(shù)和其所在層次數(shù)乘積的累加和。57496318210第9章例題5、在順序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為().

A)2B)3C)4D)56、如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用的方法是()