孫夫雄數(shù)據(jù)結(jié)構習題

1、數(shù)據(jù)結(jié)構習題一、 單選題1 . 研究數(shù)據(jù)結(jié)構就是研究A) 數(shù)據(jù)的邏輯結(jié)構B) 數(shù)據(jù)的邏輯結(jié)構和存儲結(jié)構C) 數(shù)據(jù)的存儲結(jié)構D) 數(shù)據(jù)的邏輯結(jié)構、存儲結(jié)構及其數(shù)據(jù)在運算上的實現(xiàn)2 .下面關于算法的說法，錯誤的是 。A) 算法最終必須由計算機程序?qū)崿F(xiàn) XB) 為解決某問題的算法與為該問題編寫的程序含義是相同的程序=算法+數(shù)據(jù)結(jié)構C) 算法的可行性(確定性)是指指令不能有二義性D) 以上幾個都是錯誤的3 .計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備5個特性輸入、輸出、。A) 可執(zhí)行性、可移植性和可擴充性B) 可執(zhí)行性、有窮性和確定性C) 確定性、有窮性和穩(wěn)定性D) 易讀性、穩(wěn)定性和

2、確定性4 . 以下屬于邏輯結(jié)構的概念是 。A) 順序表B) 哈希表C) 有序表D) 單鏈表5 .具有線性結(jié)構的數(shù)據(jù)結(jié)構是 。A) 圖B) 樹C) 廣義表D) 棧6 .數(shù)據(jù)的存儲結(jié)構包括順序、鏈接、散列和 種基本類型。A) 向量B) 數(shù)組C) 集合D) 索引7 .根楣數(shù)據(jù)元素之間關系的不同特性，以下4類基本邏輯結(jié)構反映了4類基本數(shù)據(jù)組織形式。下列解釋錯誤的是 。A) 集合中任何兩個結(jié)點之間都有邏輯關系，但組織形式松散B) 線性結(jié)構中結(jié)點按邏輯關系依次存儲成一行C) 樹型結(jié)構具有分支、層次特性，其形態(tài)有點像自然界中的樹D) 圖狀結(jié)構中各個結(jié)點按邏輯關系互相纏繞，任何兩個結(jié)點都可以鄰接8 .在數(shù)據(jù)結(jié)

3、構中，從邏輯上可以把數(shù)據(jù)結(jié)構分成 。A) 動態(tài)結(jié)構和靜態(tài)結(jié)構B) 緊湊結(jié)構和非緊湊結(jié)構C) 線性結(jié)構和非線性結(jié)構D) 內(nèi)部結(jié)構和外部結(jié)構9 .與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的。A) 存儲結(jié)構B) 存儲實現(xiàn)C) 邏輯結(jié)構D) 運算實現(xiàn)10 .以下說法錯誤的是 。A) 程序設計的實質(zhì)是算法設計B) 數(shù)據(jù)的邏輯結(jié)構是數(shù)據(jù)的組織形式，基本運算規(guī)定了數(shù)據(jù)的基本操作方式C) 運算實現(xiàn)是完成運算功能的算法或這些算法的設計D) 算法設計思想總是與數(shù)據(jù)的某種相應存儲形式相聯(lián)系11 .某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用 存儲方式最節(jié)省運算時間。A

4、) 單鏈表B) 僅有頭指針的單循環(huán)鏈表C) 雙鏈表D) 僅有尾指針的單循環(huán)鏈表12 .單鏈表的主要優(yōu)點是 。A) 便于隨機查詢B) 存儲密度高C) 邏輯上相鄰的元素在物理上也是相鄰的D) 插入和刪除比較方便13 .線性表采用鏈式存儲時，其地址 。A) 必須連續(xù)B) 一定不連續(xù)C) 部分連續(xù)D) 連續(xù)與否均可14 .對于一個線性表，既要求能夠較快地進行插入和刪除，又要求存儲結(jié)構能夠反映數(shù)據(jù)元素之間的邏輯關系，則應該 。A) 以順序方式存儲B) 以鏈接方式存儲C) 以散列方式存儲D) 以上均可15 .若線性表中最常用的操作是取第i個的前趨元素，采用 存儲方式最節(jié)省時間。A) 順序表B) 單鏈表C)

5、 雙鏈表D) 單循環(huán)鏈表16 .若用單鏈表來表示隊列，則應該選用 。A) 帶尾指針的非循環(huán)鏈表B) 帶尾指針的循環(huán)鏈表C) 帶頭指針的非循環(huán)鏈表D) 帶頭指針的循環(huán)鏈表17 .若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列， 且當rear和front的值分 別為0和3。從隊列中出隊一個元素，再進隊兩個元素后，rear和front的值分別為A)1和5B)2和4C)4和2D)5和118 .設棧的輸入序列是(1、2、3, 4),則 不可能輸出的序列。A) 1243B) 2134C) 1432D) 431219. 一個棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列的A) 23415B) 54132C

6、) 23145D) 1543220.設棧S和隊列Q的初始狀態(tài)為空，元素 e1、e2、e3、e4、e5和e6依 次通過棧S, 一個元素出棧后即進入隊列 Q若6個元素出隊的序列是 e2、 e4、e3、e6、e5、e1,則棧S的容量至少應該是 。A) 6B) 4C) 3D) 221 . 一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞增歸算法應該設 置 。A) 堆棧B) 隊列C) 堆?；蜿犃蠨) 數(shù)組22 .設棧的輸入序列是1、2、n,若輸出序列的第一個元素是n,則第i個輸出元素 。A) 不確定B) n-i+lC) cD) n-i23 .假定一個順序循環(huán)隊列的隊首和隊尾指針分別用front和rear表示,則判

7、隊空的條件是。A) front+1=rearB) front=rear+1C) front=OD) front=rear24 .假定一個順序循環(huán)隊列存儲于數(shù)組an中，其隊首和隊尾指針分別用front和rear表示，則判斷隊滿的條件是 。A) (rear-1) %n=frontB) rear=(front-1) %/nC) (rear+1) % n=frontD) rear=(front+1) %/n25 .采用 數(shù)據(jù)結(jié)構設計一個判別表達式中左、右括號是否配的算法最佳。A) 線性表的順序存儲結(jié)構B) 隊列C) 線性表的鏈式存儲結(jié)構D) 棧26 .在下列算法描述中，涉及到隊運算的算法是 。A) 表

8、達式求值算法B) 深度優(yōu)先搜索C) 二叉樹前中后序遍歷D) 廣度優(yōu)先搜索27 .當利用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為 。A) N-2B) N-1C) ND) N+l28 .鏈棧與順序棧相比有一個明顯的優(yōu)點，即 。A) 插入操作更加方便B) 通常不會出現(xiàn)棧滿的情況C) 不會出現(xiàn)?？盏那闆rD) 刪除操作更加方便29 . 一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二 叉樹一定滿足 。A) 所有的結(jié)點均無左孩子B) 所有的結(jié)點均無右孩子C) 只有一個葉子結(jié)點D) 是任意一棵二叉樹30 . 一棵完全二叉樹上有 1001個結(jié)點，其中葉子結(jié)點的個數(shù)是 。A) 250B)

9、 500C) 505D) 50131 .以下說法正確的是 。A) 若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點,則它必是該子樹后序遍歷序列中的最后一個結(jié)點B) 若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點，則它必是該子樹中序遍歷序列中的最后一個結(jié)點C) 在二叉樹中，具有兩個子女的父結(jié)點，在中序遍歷序列中，它的后繼結(jié)點最多只能有一個子女結(jié)點D) 在二叉樹中，具有一個子女的父結(jié)點，在中序遍歷序列中，它沒有后繼子女結(jié)點32 .以下說法錯誤的是 。A) 哈夫曼樹是帶權路徑長度最短的樹,路徑上權值較大的結(jié)點離根較近B) 若一個二叉樹的樹葉是某子樹中序遍歷序列中的第一個結(jié)點，則它必是該子樹后序遍歷

10、序列中的第一個結(jié)點C) 己知二叉樹的前序遍歷和后序遍歷并不能惟一地確定這棵樹，因為不知道樹的根結(jié)點是哪一個D) 在前序遍歷二叉樹的序列中，任何結(jié)點其子樹的所有結(jié)點都是直接跟在該結(jié)點之后的33 .二叉樹在線索化后，仍不能有效求解的問題是 。A) 前序線索二叉樹中求前序后繼B) 中序線索二叉樹中求中序后繼C) 中序線索二叉樹中求中序前趨D) 后序線索二叉樹中求后序后繼34 .若二叉樹采用鏈式存儲結(jié)構，要交換其所有分支結(jié)點左、右子樹的位置，利用 遍歷方法最合適。A) 前序B) 中序C) 后序D) 層次35 . 一棵有124個葉結(jié)點的完全叉樹，最多有 個結(jié)點。A) 247B) 248C) 249D)

11、25036 .設a、b為一棵二叉樹上的兩個結(jié)點。在中序遍歷時，a在b前面的條件是A) a在b的右方B) a在b的左方C) a是b的祖先D) a是b的子孫37 .在一棵具有n個結(jié)點的完全二叉樹中，分枝結(jié)點的最大編號 為 。A) (n+1)/2)下限取整B) (n-1)/2)下限取整C) (n/2)下限取整D) (n/2)上限取整38 .在N個結(jié)點的線索二叉樹中，線索的數(shù)目為 。A) N-1B) NC) N+1D) 2N39 .設深度為K的二叉樹上只有度為0和2的結(jié)點，則這類二叉樹上所含的結(jié)點總數(shù)至少為 。A) K+1B) 2KC) 2K-1D) 2K+140 .設有13個值，用它們組成一棵哈夫曼

12、樹，則該哈夫曼樹共有 個 結(jié)點。A) 13B) 12C) 26D) 2541 .以下說法錯誤的是 。A) 存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相IB) 二叉樹是樹的特殊情形C) 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的D) 在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹42 .若二叉樹是 則從二叉樹的任一結(jié)點出發(fā)到根的路徑上 所經(jīng)過的結(jié)點序列按其關鍵字有序。A) 二叉排序樹B) 哈夫曼樹C) 堆D) 退化二叉樹43 . 一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右的順序存儲在一維數(shù)組 A1 . . n)中，則二叉樹中第i個結(jié)點(i從1開始用上述方

13、 法編號)的右孩子在數(shù)組 A中的位置是。A) A2i (2i W nB) A2i+1) (2i+1 n)C) Ai/2D)條件不充分，無法確定44 .將有關二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是。A) 4B) 5C) 6D) 745 .下列有關二叉樹的說法正確的是 。A) 二叉樹的度為2B) 一棵二叉樹度可以小于 2C) 二叉樹中至少有一個結(jié)點的度為 2D) 二叉樹中任一個結(jié)點的度都為 246 .某二叉樹中序序列為ABCDEFG后序序列為BDCAFG E則前序序列是 ,A) EGFACDBB) EACBDGFC) EAGCFBDD) 上面的都不對47 .對二叉排序樹

14、進行 遍歷，可以得到該二叉樹所有結(jié)點構成的排序序列A) 前序B) 中序C) 后序D) 按層次48 . 的遍歷仍需要棧的支持。A) 前序線索樹B) 中序線索樹C) 后序線索樹D) 層次遍歷49 .在一棵深度為h的完全二叉樹中，所含結(jié)點的個數(shù)不小A) B) C)D) 50.A) B)C)2hh+122h-12h-1在一棵具有n個結(jié)點的二叉樹第2i2i+1i-1i層上，最多具有個結(jié)點。D) 2n51 .樹最適合用來表示 。A) 有序數(shù)據(jù)元素B)無序數(shù)據(jù)元素C)元素之間具有分支層次關系的數(shù)據(jù)D)元素之間無聯(lián)系的數(shù)據(jù)52 .以下說法錯誤的是 。A) 一般在哈夫曼樹中，權值越大的葉子離根結(jié)點越近B)哈大曼

15、樹中沒有度數(shù)為1的分支結(jié)點C)若初始森林中共有 n棵二叉樹，最終求得的哈夫曼樹中共有2n-1個結(jié)八、D)若初始森林中共有 n棵二叉樹，進行 2n-1次合并后才能剩下最終的 哈夫曼樹53 .以下說法錯誤的是 。A) 二叉樹可以是空HB) 二叉樹的任一結(jié)點都可以有兩棵子樹C) 二叉樹與樹具有相同的樹形結(jié)構D) 二叉樹中任一結(jié)點的兩棵子樹有次序之分54 .某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是 的二叉樹。A) 空或只有一個結(jié)點B) 任一結(jié)點無左子樹C) 高度等于其結(jié)點數(shù)D) 任一結(jié)點無右子樹55 .設無向圖的頂點個數(shù)為n,則該無向圖最多有 條邊。A) n-1B) n(n-1)/2C)

16、 n(n+1)/2D) 02E) n56 .采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的 。A) 中序遍歷B) 先序遍歷C) 后序遍歷D) 按層次遍歷57 .采用鄰接表存儲的圖，其廣度優(yōu)先遍歷類似于二叉樹的 。A) 按層次遍歷B) 中序遍歷C) 后序遍歷D) 先序遍歷 ，58 . 一個圖中包含有七個連通分量，若按深度優(yōu)先(DFS)遍歷，必須調(diào)用次深度優(yōu)先遍歷算法。A) kB) 1C) k-1D) k+159 .下列說法中不正確的是 A) 無向圖中的極大連通子圖稱為連通分量B) 連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C) 圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點D

17、) 有向圖的遍歷不可采用廣度優(yōu)先搜索方法60 .具有n個頂點的有向圖最多有 條邊。A) nB) n(n-1)C) n(n+1)D) n261 .在有向圖G的拓撲序列中，若頂點 Vi在頂點Vj之前，則下列情況下 不可能出現(xiàn)的是。A) G 中有弧 B) G中有一條從Vi到Vj的路徑C) G中沒有弧D) G中有一條從Vj到Vi的路徑62 . 一個n個頂點的連通無向圖，其邊的個數(shù)至少為 。A) n-1B) nC) n+lD) nlog 2n63 .下列說法中，正確的有 。A) 最小生成樹也是哈夫曼樹。B) 最小生成樹惟一2C) 普里姆(Prim)最小生成樹算法時間復雜度為O(n )D) 克魯斯卡爾(K

18、ruskal)最小生成樹算法比普里姆算法更適合于邊稠密的網(wǎng)64 .判定一個有向圖是否存在回路，除了可以利用拓撲排序的方法外，還可以利用 。A) 求關鍵路徑的方法B) 求最短路徑的 Dijkstra 方法C) 深度優(yōu)先遍歷算法D) 廣度優(yōu)先遍歷算法65 .在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s,則所有頂點的入度之和為 。A) sB) s-1C) s+lD) n66.在一個無向圖中，若兩個頂點之間的路徑長度為k條邊，則該路徑上的頂點數(shù)為。A) kB) k+lC) k+2D) 2k67 . 一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù) 為。A) 0B) 1C) nD) n+16

19、8 .對于一個有向圖，若一個頂點的入度為k1、出度為k2,則對應鄰接表中該頂點單鏈表中的結(jié)點數(shù)為。A) klB) k2C) k1-k2D) k1+k269.對于一個有向圖，若一個頂點的入度為kl、出度為k2,則對應逆鄰接表中該頂點單鏈表中的結(jié)點數(shù)為 。A) klB) k2C) k1-k2D) k1+k270 .對于一個無向圖，下面 的說法是正確的。A) 每個頂點的入度等于出度B) 每個頂點的度等于其入度與出度之和C) 每個頂點的入度為 0D) 每個頂點的出度為 071 .為了方便地對圖狀結(jié)構的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結(jié)構宜 采用。A) 順序存儲B) 鏈式存儲C) 索引存儲D) 散列存儲

20、72 .設有一個按各元素的值排好序的線性表且長度大于2,對給定的值X,分別用順序查找法和二分查找法查找一個與K相等的元素，比較次數(shù)分別是s和b:在查找不成功的情況下，正確的 s和b的數(shù)量關系是 。A) 總有s=bB) 總有sbC) 總有slink 。22 .表長為0的線性表稱為 空表。23 .用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234,為了得到1342出棧順序，相應的 S和X操作串為sxssxsxx 。24 .用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量m加1后在數(shù)組有效下標范圍內(nèi)循環(huán)，可采用的表達式是m= (m+1)%n25 .表達式求值是 棧數(shù)據(jù)結(jié)構應用的一個典型例子26 .用數(shù)組Q(其下標在O. n-1中，共有n個元素)表示一個循環(huán)隊列， front為當前隊頭元素的前一位置，rear為隊尾元素的位置。假定隊列元素個數(shù)總小于n,求隊列中元素個數(shù)的公式是 (rear-front+n)%n。27 .用鏈表表示的隊列，長度為 n,若只設頭指針，則出隊和入隊的時間 復雜度分別是O(n) 和O(1)。28 .隊列是特殊的線性表，其特殊性在于在表的一端進行插入，在另一端進行刪除。29 . 一個循環(huán)隊列存于am中，假定隊首和隊尾指針分別為front和rear ,fron