數據結構例題

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

2、錯誤

3、正確

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

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

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

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

【解答】

頭指針是指向鏈表中第一個結點（頭結點或首元結點）的指針；在首元結點之前附設的一個結點稱為頭結點；首元結點是指鏈表中存儲線性表中第一個數據元素結點。若鏈表中附設頭結點，則不管線性表是否為空，頭指針均不為空，否則表示空表的鏈表的頭指針為空。第4章例題2、簡述線性表的兩種存儲結構的主要優(yōu)缺點及各自適用的場合?！痉治觥俊窘獯稹?/p>

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

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

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

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

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

A)串是字符的有限序列

B)空串是由空格構成的串

C)模式匹配是串的一種重要運算

D)串既可以采用順序存儲，也可以采用鏈式存儲

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

B)插入運算方便C)刪除運算方便

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

6、C

第4章例題6、以下關于鏈式存儲結構的敘述中哪一條是不正確的?

A)結點除自身信息外還包括指針域,因此存儲密度小 于順序存儲結構

B)邏輯上相鄰的結點物理上不必鄰接

C)可以通過計算直接確定第i個結點的存儲地址

D)插入、刪除運算操作方便,不必移動結點

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

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、有６個元素6,5,4,3,2,1的順序進棧，問下列哪一個不是合法的出棧序列:()

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、以下哪一個不是棧的基本運算?()

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

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

A）從隊尾插入一個新元素B）讀取隊頭元素的值

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

________________

a1a2a3a4

________________

↑↑

隊頭隊尾

對棧S和隊列Q進行下列兩步操作：

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

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

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

第4-1章例題【答案】a4a3a2a15、判斷一個循環(huán)隊列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、判斷一個循環(huán)隊列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、設有一個單端受限的雙端隊列Q，元素入隊序列為：ABCD,

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

2、以下關于廣義表的敘述中,正確的是

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

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

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

D)廣義表不能為空表

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

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

4、求下列廣義表的操作結果

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、在結點個數為n(n>1)的各棵樹中，（1）高度最小的樹的高度是多少？它有多少個葉結點？多少個分支結點？（2）高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？【答案】

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

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

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

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

深度為k的完全二叉樹，其最少的結點數=深度為k-1的滿二叉樹的結點數+1=；其最多的結點數=深度為k的滿二叉樹的結點數=。

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

結點數至多有：2k-1

結點數至少有：2k-1【分析】

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

構造這棵二叉樹的過程如下所示：中序序列：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章例題與上題有關的往屆考題：1、二叉樹的先序遍歷和中序遍歷為：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是（）

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

A）EGFACDBB）EACBDGF

C）EAGCFBDD）EGACDFB3、如果一棵二叉樹結點的前序序列是ABC，后序序列是CBA，則該二叉樹結點的對稱序序列

A)必為ABCB)必為ACB

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

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

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

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

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

8、在完全二叉樹中，若一個結點只有一個葉結點，則它沒

A）左子結點B）左子結點和右子結點

C）右子結點D）左子結點、右子結點和兄弟結點9、在下列存儲形式中，哪一個不是樹的存儲形式

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

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

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

第5章例題15、已知一棵樹的先根遍歷序列為ABCED，后根遍歷序列為BECDA，求對應的樹。【分析】根據樹與二叉樹之間的轉換關系，可知：樹的先序序列=對應二叉樹先序序列樹的后跟序列=對應二叉樹中序序列因此，可以先這兩個序列構造對應的二叉樹，再將二叉樹轉換為樹。【答案】ABCDEABCDE第5章例題16、設電文中出現的字母為A、B、C、D和E，每個字母在電文中出現的次數分別9、27、3、5、和11。按哈夫曼編碼，則C的編碼為:A、10B、110C、1110D、1111【分析】先構造哈夫曼樹，再根據哈夫曼樹進行編碼。注意：在構造哈夫曼樹時，應注意左右孩子的排列。

ABCDE9273

5118

927118172711

1728

27

2855【答案】C55273511281789第5章例題⒈在一個圖中，所有頂點的度數之和等于所有邊數的（）倍。

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

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

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

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

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

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

A）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結點個數有關，而與邊數無關

B）用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關

C）用鄰接表法存儲圖，占用的存儲空間大小只與圖中結點個數有關，而與邊數無關

D）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關【答案】A第7章例題8、對于下面有向圖（1）可能的拓撲序列為（）

A)abcdefB)aebcdfC)abcfedD)abedcf

（2）可以排成多少個不同的拓撲序列（）

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

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

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

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

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

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

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

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

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

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個關鍵字的序列進行排序，最環(huán)情況下的執(zhí)行時間為

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

9、已知一個序列為{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、一組記錄的關鍵字為{46，79，50，38，42，80}，利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為

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）進行排序時，元素序列的變化情況如下：（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)定的有————。【答案】11、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、這段代碼所描述的排序方法的時間復雜度為______。

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

第8章例題1、以下哪一個術語與數據的存儲結構無關?

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

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

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

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

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

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

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

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

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

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

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