數(shù)據(jù)結構例題

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

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

3、的執(zhí)行頻度。為正整數(shù)，確定下列劃線語句的執(zhí)行頻度。 for( i=0; in; i+) for( j=0; ji; j+) for(k=0; klink; 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章例題章例題第第4-1章例題章例題1 1、有個元素、有個元素6,5,4,3,2,16,5,4,3,2,1的順序進棧，問下列哪一個不是合的順序進棧，問下列哪一個不是合法的出棧序列法的出棧序列:( ) :( ) A)5,4,3,6,

4、2,1 B) 4,5,3,1,2,6 C)3,4,6,5,2,1 D) 2,3,4,1,5,6 2 2、以下哪一個不是棧的基本運算、以下哪一個不是棧的基本運算?( ) ?( ) A) 刪除棧頂元素 B) 刪除棧底元素 C) 判斷棧是否為空 D) 將棧置為空棧 3 3、以下哪一個不是隊列的基本運算？、以下哪一個不是隊列的基本運算？ ( )( ) A）從隊尾插入一個新元素 B）讀取隊頭元素的值 C）判斷一個隊列是否為空 D）從隊列中刪除第i個元素【答案答案】 1、C 2、B 3、D4 4、設棧、設棧S S的初始狀態(tài)為空，隊列的初始狀態(tài)為空，隊列Q Q 的初始狀態(tài)為的初始狀態(tài)為 _ a1 a2 a3

5、 a4 _ 隊頭 隊尾 對棧對棧S S和隊列和隊列Q Q進行下列兩步操作：進行下列兩步操作： 1)、刪除Q中的元素，將刪除的元素插入S，直至Q為空。 2)、依次將S中的元素插入Q,直至S為空。 在上述兩步操作后，隊列Q的狀態(tài)是_。 第第4-1章例題章例題【答案答案】 a4 a3 a2 a15 5、判斷一個循環(huán)隊列、判斷一個循環(huán)隊列Q Q（元素最多為（元素最多為n n）為空的條件是（）為空的條件是（ ） A）Q-rear=Q-frontB）Q-rear Q-frontC）Q-front =（Q-rear+1）MOD nD）Q-front (Q-rear+1）MOD n6 6、判斷一個循環(huán)隊列、判

6、斷一個循環(huán)隊列Q Q（元素最多為（元素最多為n n）為滿的條件是（）為滿的條件是（ ）A）Q-rear = Q-frontB）Q-rear Q-frontC）Q-front =（Q-rear+1）MOD nD）Q-front （Q-rear+1）MOD n7 7、設有一個單端受限的雙端隊列、設有一個單端受限的雙端隊列Q Q，元素入隊序列為：，元素入隊序列為：ABCD,ABCD, 問不可能的輸出序列有哪些？問不可能的輸出序列有哪些？第第4-1章例題章例題【答案答案】 5、A 7、輸入受限：、輸入受限： DBCA 6、C 輸出受限：輸出受限： DBCA第第4-2章例題章例題1、設有二維數(shù)組A0.9

7、，0.19，其每個元素占2個字節(jié)， 數(shù)組按列優(yōu)先順序存儲，第一個元素的存儲地址為100,那么元素A6,6的存儲地址為_. 2、 以下關于廣義表的敘述中,正確的是 A) 廣義表是0個或多個單元素或子表組成的有限序列 B) 廣義表至少有一個元素是子表 C) 廣義表不可以是自身的子表 D) 廣義表不能為空表 3、廣義表（a） 的表頭是（ ），表尾是（ ） A、a B、（a） C、（）D、（a）【答案答案】 1、232 2、A 3、B，C 4、 求下列廣義表的操作結果求下列廣義表的操作結果Head（(a，b)，(c，d)）Tail（(a，b)，(c，d)）Head(Tail( (a，b)，(c，d)

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

9、案答案】 （1）結點個數(shù)為）結點個數(shù)為n時，高度最小的樹的高度為時，高度最小的樹的高度為2，有，有2層；層； 它有它有n-1個葉結點，個葉結點，1個分支結點；個分支結點； （2）高度最大的樹的高度為）高度最大的樹的高度為n，有，有n層；層； 它有它有1個葉結點，個葉結點，n-1個分支結點。個分支結點。第第5章例題章例題2、試分別找出滿足以下條件的所有二叉樹：(1) 二叉樹的前序序列與中序序列相同;(2) 二叉樹的中序序列與后序序列相同;(3) 二叉樹的前序序列與后序序列相同?！窘獯鸾獯稹?1) 二叉樹的前序序列與中序序列相同： 空樹或缺左子樹的單支樹；(2) 二叉樹的中序序列與后序序列相同：

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

11、樹的結點數(shù)+1= ；其最多的結點數(shù)=深度為k的滿二叉樹的結點數(shù)= 。 k與結點數(shù)目n之間的關系可以根據(jù)二叉樹的性質4得出：112112kk12 knk2log1 第第5章例題章例題4 4、對于深度為、對于深度為k k，且只有度為，且只有度為0 0或或2 2的結點的二叉樹，結點數(shù)的結點的二叉樹，結點數(shù) 至少有多少？至多有多少？至少有多少？至多有多少？( (分析分析) )【解答解答】 結點數(shù)至多有：2k-1 結點數(shù)至少有：2k-1【分析分析】 對于結點數(shù)至多為多少的問題比較好回答，我們知道滿二叉樹中只有度為0或2的結點，所以結點數(shù)至多為同等深度的滿二叉樹的結點數(shù)。 對于結點數(shù)至少為多少的問題，由于

12、樹中只存在度為0或2的結點，即對一個結點而言，要么它沒有子結點，要么就有兩個子結點，所以在這樣的樹中，除第一層（根所在的層）外，每一層至少有兩個結點。第第5章例題章例題5 5、已知一棵二叉樹的中序序列為、已知一棵二叉樹的中序序列為BDCEAFHG BDCEAFHG ， 后序序列為后序序列為DECBHGFA DECBHGFA ，求對應的二叉樹。，求對應的二叉樹。【分析分析】 根據(jù)各種遍歷方法的定義，可知： 二叉樹先序序列=根+左子樹先序序列+右子樹先序序列； 二叉樹中序序列=左子樹中序序列+根+右子樹中序序列； 二叉樹后序序列=左子樹后序序列+右子樹后序序列+根； 從先序和后序序列中可以很容易的

13、知道那一個結點是根，而在中序序列中，可以根據(jù)根得到左、右子樹的中序序列，相應的也就知道左、右子樹的結點集合了?？梢愿鶕?jù)集合中的結點劃分先序或后序序列中除根以外的結點序列，從而得到左、右子樹的先序或后序序列。依次類推，便可以遞歸得到整棵二叉樹。中序序列左子樹中序序列 根 右子樹中序序列前序序列根 左子樹前序序列 右子樹前序序列第第5章例題章例題【解答解答】 構造這棵二叉樹的過程如下所示： 中序序列：BDCE A FHG后序序列：DECB HGF A中序：BDCE 后序：DECB 中序： FHG后序： HGF 中序： D C E 后序：D E C 中序： HG后序： HG 中序：D 后序：D 中序

14、：E 后序：E 中序：H 后序：H AFGHEDCB可以畫出這棵二叉樹為：第第5章例題章例題與上題有關的往屆考題：1、二叉樹的先序遍歷和中序遍歷為：先序遍歷：EFHIGJK； 中序遍歷：HFIEJKG 。該二叉樹根的右子樹的根是 （ ） A）E B）F C）G D）H2、某二叉樹結點的對稱序（中序）序列為ABCDEFG，后序序 列為BDCAFGE。該二叉樹結點的前序序列為 （ ） A）EGFACDB B）EACBDGF C）EAGCFBD D）EGACDFB 3、如果一棵二叉樹結點的前序序列是ABC，后序序列是CBA， 則該二叉樹 結點的對稱序序列 A) 必為ABC B) 必為ACB C) 必

15、為BCA D) 不能確定 【答案答案】 1、C 2、B 3、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

16、）完全相同 D）中序和后序相同，而與先序不同 8、在完全二叉樹中，若一個結點只有一個葉結點，則它沒 A）左子結點 B）左子結點和右子結點 C）右子結點 D）左子結點、右子結點和兄弟結點9、在下列存儲形式中，哪一個不是樹的存儲形式 A）雙親表示法 B）孩子鏈表表示法 B）孩子兄弟示法 D）順序存儲表示法 【答案答案】 7、C 8、C 9、D第第5章例題章例題填空：10、在樹中，一個結點的直接子結點的個數(shù)稱為該結點 的_ 。11、如果對于給定的一組權值，所構造出的二叉樹的帶權路徑 長度最小，則該樹稱為_ 。12、用數(shù)組A1.n順序存儲完全二叉樹的各結點, 則當i=(n-1)/2 時,結點Ai的右孩

17、子是結點_。13、完全二叉樹中某結點無左子樹，則它必是_。 【答案答案】 10、度、度 11、哈夫曼樹、哈夫曼樹(Huffman) 12、A2i+1 13、葉子、葉子第第5章例題章例題14、對于如圖所示的森林 （1）將其轉換為相應的二叉樹； （2）寫出該森林的先序遍歷序列和中序遍歷序列。【答案答案】A圖題 14BCEFDGHIJKLABCEFDGHIJKL先序序列為：先序序列為：ABDEFCGHIJK中序序列為：中序序列為：DEFBCAHIJGLK 第第5章例題章例題15、已知一棵樹的先根遍歷序列為ABCED，后根遍歷序列 為BECDA，求對應的樹?！痉治龇治觥?根據(jù)樹與二叉樹之間的轉換關系，

18、可知： 樹的先序序列 = 對應二叉樹先序序列 樹的后跟序列 = 對應二叉樹中序序列 因此，可以先這兩個序列構造對應的二叉樹，再將 二叉樹轉換為樹。【答案答案】ABCDEABCDE第第5章例題章例題16、設電文中出現(xiàn)的字母為A、B、C、D和E，每個字母在 電文中出現(xiàn)的次數(shù)分別9、27、3、5、和11。按哈夫曼 編碼，則C的編碼為 : A、10 B、110 C、1110 D、1111【分析分析】 先構造哈夫曼樹，再根據(jù)哈夫曼樹進行編碼。注意：在構造哈夫曼樹時，應注意左右孩子的排列。 A B C D E 9 27 3 5 11 8 9 27 11 8 17 27 11 17 28 27 28 55【

19、答案答案】 C55273511281789第第5章例題章例題 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（ ）倍。 A.1/2 B.1 C.2 D.4 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。 A.1/2 B.1 C.2 D.4 一個有n個頂點的無向圖最多有（ ）條邊。 A.n B.n(n-1) C.n(n-1)/2 D.2n 具有4個頂點的有向完全圖有（ ）條邊。 A.6 B.12 C.16 D.20【答案答案】 1、C 2、B 3、C 4、B第第7章例題章例題 對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示， 則該矩陣的大小是（ ）： A.n B.(n-1)

20、2 C.n-1 D.n2 已知一個圖如圖所示，若從頂點a出發(fā)按深度搜索法進行 遍歷，則可能得到的一種頂點序列為（ ）；按廣度搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。 A. abecdf B. acfebd C. aebcfd D. aedfcb A. abcedf B. abcefd C. aebcfd D. acfdeb【答案答案】 5、D 6、 D Babcedf第第7章例題章例題7、下面關于圖的存儲的敘述中正確的是 A）用相鄰矩陣法存儲圖，占用的存儲空間大小只 與圖中結點個數(shù)有關，而與邊數(shù)無關 B）用相鄰矩陣法存儲圖，占用的存儲空間大小只 與圖中邊數(shù)有關，而與結點個數(shù)無關 C）

21、用鄰接表法存儲圖，占用的存儲空間大小只與 圖中結點個數(shù)有關，而與邊數(shù)無關 D）用鄰接表法存儲圖，占用的存儲空間大小只與 圖中邊數(shù)有關，而與結點個數(shù)無關 【答案答案】 A第第7章例題章例題8、 對于下面有向圖 （1）可能的拓撲序列為 （ ） A) abcdef B) aebcdf C) abcfed D) abedcf （2）可以排成多少個不同的拓撲序列（ ） A) 2 B) 3 C) 4 D) 5【答案答案】 (1) D (2) B bacedf第第7章例題章例題1、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ） A)插入排序 B)選擇排序 C) 快速排序 D)歸并排序 2、在

22、所有的排序方法中，關鍵字比較的次數(shù)與記錄的初始排序次序無關的是（ ） A)起泡排序 B)希爾排序 C)插入排序 D)選擇排序 3、排序方法中，從未排序隊列中依次取出元素與已排序序列（初始時為第1個元素）中的元素進行比較，然后放入到已排序序列中的正確位置上，這種方法稱為（ ） A)起泡排序 B)選擇排序 C)插入排序 D)堆排序 4、下列排序方法中，（ ）是從未排序序列中依次挑選元素，并將其放入已排序序列（初始為空）的末尾。 A)希爾排序 B)歸并排序 C)選擇排序 D)插入排序【答案答案】 1、A 2、D 3、C 4、C第第8章例題章例題4、下列排序方法中，哪一個是穩(wěn)定的排序方法? A)直接選

23、擇排序 B)二分法插入排序 C)希爾排序 D)快速排序 。5、對n個記錄的文件進行堆排序，最壞情況下的執(zhí)行時間為 A) O(log2n ) B) O(n) C) O(nlog2n) D) O(n2)6、用直接插入排序方法對下面四個序列進行排序（由小到大）， 元素比較次數(shù)最少的是 A）94、32、40、90、80、46、21、69 B）32、40、21、46、69、94、90、80 C）21、32、46、40、80、69、90、94 D）90、69、80、46、21、32、94、40 7、用快速排序法對包含n個關鍵字的序列進行排序，最環(huán)情況下 的執(zhí)行時間為 A）O(log2n) B）O(n) C

24、）O(nlog2n) D）O(n2)【答案答案】 4、A 5、C 6、C 7、D第第8章例題章例題8、下列哪一個關鍵碼序列不符合堆的定義？ 9、已知一個序列為21，39，35，12，17，43，則利用堆 排序的方法建立的初始堆為（ ） A） 39，21，35，12，17，43 B） 43，39，35，12，17，21 C）43，39，35，21，17，12 D ） 43，35，39，17，21，12 10、一組記錄的關鍵字為46，79，50，38，42，80，利用快速 排序的方法，以第一個記錄為基準得到的一次劃分結果為 A） 38，42，46，50，79，80 B） 42，38，46，79，5

25、0，80 C ）42，38，46，50，79，80 D） 42，38，46，80，50，76 【答案答案】 8、C 9、B 10 、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

26、，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則所采用的排序方法是（ ） A）選擇排序 B） 快速排序 C ）歸并排序 D） 希爾排序 12、在插入排序、希爾排序、選擇排序、堆排序、快速排序、 歸并排序中，排序穩(wěn)定的有?！敬鸢复鸢浮?11、B 12、插入排序、歸并排序、插入排序、歸并排序第第8章例題章例題13、已知如下的程序代碼: for( i =1; i=0 & Ajx ) Aj+1=Aj; j=j-1； Aj+1=x； 1、這段代碼所描述的排序方法是_ 。 2、這段代碼所描述的排序方法的時間復雜度為_。 3、假設這段代碼開始執(zhí)行時,數(shù)組A中的

27、元素已經(jīng)按值的遞增 次序排好了序,則這段代碼的執(zhí)行時間為_?！敬鸢复鸢浮?1、插入排序、插入排序 2、O(n2) 3、O(n) 第第8章例題章例題1、以下哪一個術語與數(shù)據(jù)的存儲結構無關? A)棧 B)散列表 C)二叉樹 D)雙鏈表 2、對包含n個元素的散列表進行檢索，平均檢索長度 A)為O(log2n) B)為O(n) C)為O(nlog2n) D)不直接依賴于n3、對線性表進行二分法查找，其前提條件是 A）線性表以順序方式存儲，并且按關鍵碼值的檢索 頻率排好序 B）線性表以順序方式存儲，并且按關鍵碼值排好序 C）線性表以鏈接方式存儲，并且按關鍵碼值排好序 D）線性表以鏈接方式存儲，并且按關鍵

28、碼值的檢索 頻率排好序 【答案答案】 1、A 2、D 3、B第第9章例題章例題4、畫出對長度為10的有序表進行折半查找的一棵判定樹， 并求其等概率時查找成功的平均查找長度。【分析分析】【解答解答】 判定樹如圖所示。等概率時查找成功的平均查找長度 ASL succ =(1*1+2*2+3*4+4*3)/10 = 29/10 = 2.9 假設分別用1至10表示表中的10個結點，要畫出對此有序表進行折半查找的判定樹，須進行折半查找的過程，用第一次得到的mid結點5作為判定樹的根結點，用后面得到的兩個mid結點2和8為根結點構造根結點的兩棵子樹， 根據(jù)判定樹，平均查找長度即為各層的結點數(shù)和其所在層次數(shù)乘積的累加和。 57496318210第第9章例題章例題5、在順序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分法查找 關鍵碼值11, 所需的關鍵碼比較次數(shù)為( ). A) 2 B) 3 C) 4 D) 5 6、如果要求一個線性表既能較快地查找，又能適應動態(tài)變化 的要求，則可采用的方法是 ( ) A）分塊法 B）順