數(shù)據(jù)結(jié)構(gòu)試題庫答案

1、數(shù)據(jù)結(jié)構(gòu)試題及答案 一、單項選擇題 (1) 一個算法應(yīng)該是(A) 程序C) 要滿足五個基本屬性(2) 算法指的是(A) 計算機程序C) 排序算法 列。)。)。B)B)D)問題求解步驟的描述 D) A 和 C解決問題的計算方法 解決問題的有限運算序(3) 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的 (A) 存儲結(jié)構(gòu) B) 邏輯結(jié)構(gòu)作(4) 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(A) 動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)構(gòu)C) 線性結(jié)構(gòu)、非線性結(jié)構(gòu) 結(jié)構(gòu) (5) 下列敘述中正確的是 ( ) 。A) 個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B) 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C) 一個邏輯數(shù)據(jù)結(jié)構(gòu)可以

2、有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不 影響數(shù)據(jù)處理的效率D) 個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)， 且各種存儲結(jié)構(gòu)影響 數(shù)據(jù)處理的效率 (6) 數(shù)據(jù)的基本單位是()A) 數(shù)據(jù)項B) 數(shù)據(jù)類型)。C) 算法D) 操)兩大類。B) 順序結(jié)構(gòu)、鏈式結(jié)D) 初等結(jié)構(gòu)、構(gòu)造型C) 數(shù)據(jù)元素D) 數(shù)據(jù)變量(7) 下列程序的時間復(fù)雜度為(0；0；s<n) ； A) o (Vn)B) o (Qn)C) O (n)D) O(n2)(8)下列程序段的漸進時間復(fù)雜度為(1<)(1<= m;)Aij = i*j ；0(m2)A)B ) 0(n2)C) 0(m*n)D()(9)0 ；(1<)(1<

3、;)程序段如下:其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是( )。A) 0(n)0(n2)(10)(1；B) 0()C) 0(n 3)D)在下面的程序段中，x的賦值語句的頻度為)。i> ；(1； j> ；)1；A) 0(2 n)D) 0( 2n)(11)(1； j> ；B)0( n)2C) 0(n )程序段 (1; i<=1;(aj>a1 j；aj= a1; a1= t;為正整數(shù)，則最后一行的語句頻度在最壞情況下是其中()。A) 0(n ) 0(n2) (12)(n)B) 0()3C) 0(n )D)設(shè)有一個遞歸算法如下:A) n1(13) /* 大于等于

4、0 */(*=0 ) 1 ;n* (1)；則計算(n)需要調(diào)用該函數(shù)的次數(shù)為(B) 1C) 2)。D)下述程序段中語句的頻度是(0；)。(1<)(0<)A) (m 1)( m 1)B) m(m 1)2C) (m 2)(m21)D) m(m 1)2(14)若某線性表中最常用的操作是在最后一個元素 之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存 儲方式是(A)單鏈表)。B)僅有頭指針的單循環(huán)鏈表C)雙鏈表D)僅有尾指針的單循環(huán)鏈表(1)求循環(huán)鏈表中當前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是)。(A) 0(n)和 0(1) B) 0(1)和 0(1) C) 0(1)和 0(n) D)

5、 0(n) 和 0(n)(15)求單鏈表中當前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是( )。A) 0 (n)和 0( 1)B) 0( 1)和 0 (1)C) 0( 1)和 0( n )D) 0(n)和 0( n )(16)。非空的單循環(huán)鏈表的頭指針為，尾指針為，則下 列條件成立的是(A) >C) >B) >> D) >>(17) 從一個長度為 n 的順序表中刪除第w i W n)時，需向前移動的元素的個數(shù)是(A)B)1C)1D)i(18) 已知一個有序表為( 13， 18， 24，i 個元素( 1 )。35， 47， 50， 62， 83， 90， 115， 1

6、34)，當二分檢索值為 90 的元素時，檢索 成功需比較的次數(shù)是(A)1B)2C)3D)4(19)假設(shè)以行優(yōu)先順序存儲三維數(shù)組 R696 ，其的地址為 2100，且每個元素占 4 個存儲單 2836 的元素是()。B) R334 C) R435)。中元素 R000 元，則存儲地址為 A) R333 D) R434(20)設(shè)有一個10階的對稱矩陣 A采用壓縮存儲方式以行序為主序存儲， a00 為第一個元素，其存儲地址為0，每個元素占有 1 個存儲地址空間，則 a45 的地址為(A) 13)。(21)B) 35 C) 17 D) 36 線性表采用鏈式存儲時，節(jié)點的存儲的地址)。(必須是不連續(xù)的必須

7、是連續(xù)的A)C) 相連續(xù) (22)A) 便于隨機存取 順序表少B) 連續(xù)與否均可D) 和頭節(jié)點的存儲地址)。用鏈表表示線性表的優(yōu)點是(B) 花費的存儲空間比C) 數(shù)據(jù)元素的物理順序與邏輯順序相同 除(23) 鏈表不具有的特點是(A) 插入、刪除不需要移動元素 一元素C) 不必事先估計存儲空間 性長度成正比D)。B)D)(24) 在長度為 n 的順序表中刪除第 i時，元素移動的次數(shù)為 ( )。便于插入與刪可隨機訪問任所需空間與線個元素(1 w i w n)A) 1D)(25) 采用順序搜索方法查找長度為 n 的順序表示，搜 索成功的平均搜索長度為(A) n B) 2D) (1)/2B) i)。C

8、) 1C) (1)/2(26) 將長度為n的單鏈表鏈接在長度為 m的單鏈表之 后的算法的時間復(fù)雜度為( )。C) O(m)A) O(1)B) O(n)D) O()(27) 若不帶頭結(jié)點的單鏈表的頭指針為，則該鏈表為空的判定條件是 ( )。A) B) > C) D) >(28) 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用()存儲方式最節(jié)省運算時間。B) 僅有頭指針的單循環(huán)A) 單鏈表鏈表D) 僅有尾指針的單循環(huán)C) 雙鏈表 鏈表(29) 若允許表達式內(nèi)多種括號混合嵌套，則為檢查表 達式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是 ( A) 棧叉排

9、序樹(30)。B) 線性表C) 隊列D)順序棧S中為棧頂指針，指向棧頂元素所在的位 置，為存放棧的數(shù)組，則元素 e 進棧操作的主要語句為 (A) ；)。1；B) 1；1；C) 1；(31)D) 1 ；循環(huán)隊列中，用數(shù)組025存放數(shù)據(jù)元素，指示隊頭元素的前一個位置，指示隊尾元素的當前位置，設(shè)當)。前為 20，為 12，則當前隊列中的元素個數(shù)為(B) 16 C) 17 D) 18 鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是A) 8)。)。(32)(B) 通常不會出現(xiàn)棧滿A) 插入操作更加方便 的情況C) 不會出現(xiàn)棧空的情況 D) 刪除操作更加方便(33) 一個遞歸的定義可以用遞歸過程求解，也可以用

10、非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞 歸過程(B) 較慢相同C)A) 較快D) 不定n,其輸(34)出序列為D) 不A) i 確定一個棧的入棧序列是，則棧的不可能的輸出序列(34) 是(A)(36)若已知一個棧的入棧序列是p123,，若p仁,則為(B) C) 11,2,3,4)。B) C) D) 若進棧序列為 1 ， 2， 3， 4， 5， 6，且進棧和出棧 ( ) 。B) 3， 2， 4， 1， 6， D) 2， 3， 5， 1， 6， )。后進后1，1，5， 65， 6對于棧操作數(shù)據(jù)的原則是B) 后進先出先進先出 不分順序可以穿插進行，則不可能出現(xiàn)的出棧序列是A) 2，

11、4， 3，C) 4 ， 3， 2，(37)A)D)棧和隊列的共同點是(38)A)C)(39)C)都是先進后出沒有共同點)。B)D)1 ， 2， 3， 4，則隊列的輸都是先進先出只允許在端點處插入和刪除元素 一個隊列的入隊序列是)。出序列是( A) 4,3,2,1 D) 3,2,4,1 (40)B) 1,2,3,4C)1,4,3,2設(shè)數(shù)組 m 作為循環(huán)隊列的存儲空間，為隊頭指針，為隊尾指針，則執(zhí)行出對操作后其頭指針值為( )。A)C) (41)1(1)B) (1)%(1)D) (1)引起循環(huán)隊列隊頭位置發(fā)生變化的操作是( )A) 出隊 取隊尾元素 設(shè)以數(shù)組Am存放循環(huán)隊列的元素，其頭尾指針分別為

12、和，則當前隊列中的元素個數(shù)為(A) () B ) 1C) () D ) ()B) 入隊)。C) 取隊頭元素D)(42) 二維數(shù)組 A1218 采用列優(yōu)先的存儲方法，若每個元素各占 3 個存儲單元，且 A00 地址為 150，則元素 A97 的地址為 ( )。A) 429B) 432D) 438C) 435(43) 設(shè)有一個 10 階的對稱矩陣 A1010 ，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數(shù)組B 中，A00A) 3265(44)存入B0中，貝y A85在B中(B) 33C) 41B)位置。D)若對n階對稱矩陣A以行序為主序方式將其下三 角形的元素 ( 包括主對角線上所有元素 )

13、依次存放于一維數(shù)組 B 1.(n(1)/2 ( ) 。A) i*(1)/2 j*(1)/2(45)中，則在B中確定(ivj )的位置k 的關(guān)系為B) j*(1)/2C) i*(1)/2)。D)A) 便于進行矩陣運算C) 節(jié)省存儲空間度(46)對稀疏矩陣進行壓縮存儲目的是(B) 便于輸入和輸出D) 降低運算的時間復(fù)雜對廣義表 (),(),()執(zhí)行操作 (L) 的結(jié)果是( ) 。A) ()D) ( ) (47)B) ()C) (f)設(shè)廣義表()，則L的長度和深度分別為()。(48)2(49)(50)A) 1 和 1D) 2 和 3B) 1 和 3C) 1 和 2樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加

14、)。A) 0B)1C) -1D)在一棵具有 n 個結(jié)點的二叉鏈表中，所有結(jié)點的空域個數(shù)等于A) nD) 2*n)。B) n-1C) 1某二叉樹的先序序列和后序序列正好相反，則該)的二叉樹。二叉樹一定是A) 空或只有一個結(jié)點B) 高度等于其節(jié)點數(shù)C) 任一結(jié)點無左孩子D) 任一結(jié)點無右孩子(51)含有 10個結(jié)點的二叉樹中， 度為 0 的結(jié)點數(shù)為 4，則度為 2 的結(jié)點數(shù)為(A)3 B)4(52) 除第一層外， 層結(jié)點個數(shù)的( )A)1/2 倍(53)C)5D)6滿二叉樹中每一層結(jié)點個數(shù)是上一D) 3 對一棵有 100 個結(jié)點的完全二叉樹按層編 編號為 49 的結(jié)點，它的父結(jié)點的編號為(A)24

15、 B)25 C)98 (54) 是( )B)1 倍C) 2 倍)D)99可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點A)根結(jié)點無左孩子B)根結(jié)點無右孩子C)根結(jié)點有兩個孩子D)根結(jié)點沒有孩子(55) 設(shè)高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié) 點，則此類二叉樹中所包含的結(jié)點數(shù)至少為(A) 2hB) 2h-1C) 21D) 1(56)。在一棵度為 3 的樹中，度為 3 的節(jié)點個數(shù)為 2，度為2的節(jié)點個數(shù)為1，則度為0的節(jié)點個數(shù)為()。A) 4B) 5C) 6D) 7(57) 設(shè)森林F對應(yīng)的二叉樹為 B,它有m個結(jié)點，B 的根為P，P的右子樹結(jié)點個數(shù)為n,森林F中第一棵 子 樹 的結(jié)點個數(shù)

16、是(A)B)-1不足，無法確定)。C) 1D)條件(58) 將一株有100個節(jié)點的完全二叉樹從上到下，從 左到右依次進行編號，根節(jié)點的編號為1,則編號為49的節(jié)點 的左孩子編號為()。A)98B) 89C) 50D)沒有孩子(59)F列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是(A )234567S910 11 J2A.估A%)C(60)AC) 數(shù)據(jù) (61)樹最適合用來表示(有序數(shù)據(jù)元素元素之間具有分支層次關(guān)系的數(shù)據(jù))。B)無序數(shù)據(jù)元素D)元素之間無聯(lián)系的在一個非空二叉樹的中序遍歷序列中，根結(jié)點的右邊(A)只有右子樹上的所有結(jié)點 的部分結(jié)點B)只有右子樹上C) 只有左子樹的上的部分結(jié)點 的所有結(jié)點 (

17、62)任何一棵二叉樹的葉結(jié)點在先序、歷序列中相對次序( 不發(fā)生改變 以上都不對D)只有左子樹上中序和后序遍A)D) (63)。B) 發(fā)生改變C)不能確定在有 n 個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為A)21 (64)。不確定B) 2nC) 21D)權(quán)值為 1,2,6,8帶權(quán)路徑長度是(A) 18(65)結(jié)點，則(A) 1(66)。B) 28 對一個滿二叉樹， )。B) 1=2n的四個結(jié)點構(gòu)成的哈夫曼樹的C) 19D) 29m個樹葉，k個分枝結(jié)點，n個C) 1D) 21在含有 n 個頂點和 e 條邊的無向圖的鄰接矩陣 中，零元素的個數(shù)為(A) e B) 2en2-2e(67) 若采用鄰接矩陣翻存

18、儲一個 n 個頂點的無向圖， 則該鄰接矩陣是一個( )。A) 上三角矩陣 B) 稀疏矩陣 C)D) 對稱矩陣(68)的(A) 1/24(69)。C) n 2D)對角矩陣在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù) )倍。B) 1C) 2D)在一個有向圖中，所有頂點的入度之和等于所有 頂點的出度之和的( )倍。A) 1/2 B) 14(70)對于含 n 個頂點和 e 條邊的圖，采用鄰接矩陣表示的空間復(fù)雜度為( )。C) 2D)A) O(n)B) O(e) C) O()D) O(n 2)(71) 如果求一個連通圖中以某個頂點為根的高度最 小的生成樹，應(yīng)采用(A) 深度優(yōu)先搜索算法C) 求最小生成樹的

19、算法(72)A) 1(73)A) 1 條有向邊D) n(1) 條有向邊 (74)n 個頂點的連通圖至少中含有B) n C) 1n 個頂點的完全有向圖中含有B) n 條有向邊)。B) 廣度優(yōu)先搜索算法D) 拓撲排序算法)。D) 0 )。(C) n(1)/2 條有向邊假設(shè)一個有 n 個頂點和 e 條弧的有向圖用鄰接表 表示，則刪除預(yù)某個頂點相關(guān)的所有弧的時間復(fù)雜度是( A) O(n) O(n*e) (75)一個(A) 頂點序列D) 邊的條數(shù) (76)B) O(e)C) O()在無向圖中定義頂點域之間的路徑為從到達的)。B) 邊序列C) 權(quán)A) (77)無向圖 (), 其中： , (),(),(),

20、(),(),對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是( B)。 D)值總和(),()。C) D)面哪一方法可以判斷出一個有向圖是否有環(huán)A)D) (78)A) 層次 (79)回路)。求節(jié)點的度求關(guān)鍵路徑B) 拓撲排序C) 求 最 短 路 徑先根圖的廣度優(yōu)先搜索類似于樹的(B) 中根 C) 后根)次序遍歷。D)在圖采用鄰接表存儲時，求最小生成樹的的時間復(fù)雜度為 ( ) 。A) O(n)B) O()O(n3)(80) 已 知 有 向 圖 () ， 其 中<V12>,<V13>,<V14>,C) O(n2)算法D)V1234567 ，vV25><V

21、35>vV36>vV46><V57>vV67>的拓撲序列是(A) V 1346257B) VC) VD) V(81) 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中(A)從源點到匯點的最長路徑B)短路徑C)最長回路(82)A) n 2(83)數(shù)目是)。從源點到匯點的最最短回路有n個結(jié)點的有向完全圖的弧數(shù)是(B) 2nC) n(1)D) 2n(1)設(shè)圖的鄰接鏈表如題12圖所示，則該圖的邊的D)。A) 4(84)的A) 1/2D) 4(85)()。1V,2V13V,4V4*L_23113A2A>*4 A4 I A83題圖B)5C)10D)20在一個圖中，所有頂點的度數(shù)之和等于圖

22、的邊數(shù) )倍。B) 1C)頂點的出度之和的(A) 1/2D) 4(86)A) 14D) 112(87)在一個有向圖中，所有頂點的入度之和等于所有 )倍。B) 1C)有8個結(jié)點的無向圖最多有( )條邊。B) 28C)有8個結(jié)點的無向連通圖最少有()條邊。5656A) 5D) 8 (88)A) 14D) 112(89)用(A)棧D)圖(90)用(A)棧D)圖(91)B) 6C)有8個結(jié)點的有向完全圖有( )條邊。B) 28C)用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采 來實現(xiàn)算法的。B)隊列C)用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采 來實現(xiàn)算法的。B)隊列C)已知圖的鄰接矩陣，根據(jù)算法思想，貝

23、y從頂點 出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是()。A) 0 2 4 3 1 5 60111101100100110001001100110101101000011011100010B)0 1 3 6 5 4 2C) 0 4 2 3 1 6 5D) 0 3 6 1 5 4 2建議：0 1 3 4 2 5 6(92) 已知圖的鄰接矩陣同上題 點0出發(fā)，按深度優(yōu)先遍歷的結(jié)點序列是A) 0 2 4 3 1 5 6B) 0 1 3 5 6 4 26 5 D) 0 1 3 4 2 5 6(93) 已知圖的鄰接矩陣同上題 點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是8,8,根據(jù)算法，則從頂)。C) 0 4 2 3 1根

24、據(jù)算法，則從頂 )。C) 0 4 2 3 1根據(jù)算法，則從頂 )。A) 0 2 4 36 5 D) 0 1 (95)0出優(yōu)先點序B) 0 1 3 5 6 4 21 6 52 3 4 5 6已知圖的鄰接表如下所示，C) 0 1 2 3 4A) 1 3 2*V)OOB) 0 2 3 1根據(jù)算法，則從頂點發(fā)按深度訂遍歷的結(jié)列門(C) 0 3 2 1是)。D) 0 1 2 3(96)已知圖的鄰接表如下所示，0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是(根據(jù)算法，則從頂點%*3A) 0 3 2 1B) 0 1 2 3C)A) 0 2 4 3 6 5 1B) 0 1 3 6 4 2 55 6 D) 0 1 3 4 2

25、 5 6(建議：0 1 2 3 4 5 6)(94)已知圖的鄰接矩陣同上題 8,點0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點序列是(D) 0 3 1 2(97)A)先序遍歷深度優(yōu)先遍歷類似于二叉樹的B)中序遍歷C)。后序遍歷D) (98)A)D) (99)A)D)層次遍歷先序遍歷層次遍歷廣度優(yōu)先遍歷類似于二叉樹的( )。B) 中序遍歷 C) 后 序 遍 歷任何一個無向連通圖的最小生成樹( )。B) 一棵或多棵 C) 一 定 有 多 棵只有一棵 可能不存在 (注， 生成樹不唯一， 但最小生成樹唯一， 即邊權(quán)之和 或樹權(quán)最小的情況唯一) (100) 在分析折半查找的性能時常常加入失敗節(jié)點，即 外節(jié)點，從而形成擴

26、充的二叉樹。 若設(shè)失敗節(jié)點 i 所在層次為， 那么查找失敗到達失敗點時所做的數(shù)據(jù)比較次數(shù)是( )。A) 1 B) 2 C) 1 D)(101) 向一個有 127 個元素原順序表中插入一個新元素 并保存原來順序不變，平均要移動( )個元素。A) 8 B) 63.5 C) 637(102)( ) 。由同一組關(guān)鍵字集合構(gòu)造的各棵二叉排序樹D)A)B)C)D) (103)A)其形態(tài)不一定相同，但平均查找長度相同 其形態(tài)不一定相同，平均查找長度也不一定相同 其形態(tài)均相同，但平均查找長度不一定相同 其形態(tài)均相同，平均查找長度也都相同 衡量查找算法效率的主要標準是( )。B) 所需的存儲量 C) 平 均 查

27、 找 長 度元素的個數(shù)D) 算法難易程度 (104) 是( )。A) 有序表 B) 分塊有序表D) 快速排序(3) 能進行二分查找的線性表 , 必須以(A) 順序方式存儲，且元素按關(guān)鍵字有序B) 鏈式方式存儲，且元素按關(guān)鍵字有序C) 順序方式存儲，且元素按關(guān)鍵字分塊有序適合對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)C) 二叉排序樹)。D) 鏈式方式存儲，且元素按關(guān)鍵字分塊有序 (105) 為使平均查找長度達到最小 05,11,21,25,37,40,41,62,84 入的關(guān)鍵字應(yīng)為( )A) 5B)37(106)對關(guān)鍵字序列)。)。B) 40,38,46,79,5684 )D) 40,38,46,8

28、4,56,79快速排序在最壞情況下的時間復(fù)雜度是D) O( 2n) )。B) O(n 2)C) O( 2n)列排序算法中不穩(wěn)定的是(B) 折半插入排序 C) 冒泡排序)。, 當由關(guān)鍵字集合 構(gòu)建二叉排序樹時 , 第一個插C) 41D) 62(56,23,78,92,88,67,19,34) 進行 增量為 3 的一趟希爾排序的結(jié)果為B)A) (19,23,56,34,78,67,88,92) 23,56,78,66,88,92,19,34)D)C) (19,23,34,56,67,78,88,92) (19,23,67,56,34,78,92,88)關(guān)鍵字序列序列的變化情況(107) 用 某 種

29、 排 序 方 法 對 35,84,21,47,15,27,68,25,20 進行排序時， 如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84 則采用的方法是(B) 希爾排序C) 堆排序A) 直接選擇排序D) 快速排序(108) 一組記錄的排序碼為 (46,79,56,38,40,84) ，則 利用快速排序的方法，以第一個記錄為基準得到的第一次劃分 結(jié)果為( )。A) 38,40,46,56,79,8440,38,46,56,79,84(109)( A) O(n 22n)(110)A)

30、 直接選擇排序D) 快速排序(109) 對待排序的元素序列進行劃分，將其分為左、右 兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序 列為空或只剩下一個元素為止。這樣的排序方法是A)D)(112)直接選擇排序冒泡排序B) 直接插入排序C) 快速排序個不同的數(shù)據(jù)進行排序，至多需要比較A)D)(113)(825)次。B)C) 10排序算法定其最終位置的算法是(A)選擇排序中，第一趟排序后，任一兀素都不能確)。C)冒泡排序B)快速排序D) 插入排序(114)A)直接插入排序)。D) 選排序算法中，不穩(wěn)定的排序是(B)冒泡排序C)堆排序擇排序(115) 排序方法中，從未排序序列中依次取出元素與已

31、排序序列(初始時為空)中的元素進行比較，將其放入已排序 序列的正確位置上的方法，稱為().A) 希爾排序B) 冒 泡排序C) 插入排序D) 選擇排序(116) 從未排序序列中挑選元素，并將其依次插入已排 序序列(初始時為空)的一端的方法，稱為(A) 希爾排序B) 歸并排序 C)D) 選擇排序(117) 對n個不同的排序碼進行冒泡排序，情況下比較的次數(shù)最多。 ()。插入排序在下列哪種A) 從小到大排列好的B) 從大到小排列好的C) 元素無序D) 元素基本有序(118) 對n個不同的排序碼進行冒泡排序，在兀素無序 的情況下比較的次數(shù)為( )。1B) nn(1)/2A)D)(119)C)快速排序在下

32、列哪種情況下最易發(fā)揮其長處。A)B)C)D) (120)。)。被排序的數(shù)據(jù)中含有多個相同排序碼 被排序的數(shù)據(jù)已基本有序 被排序的數(shù)據(jù)完全無序 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊 對有 n 個記錄的表作快速排序，在最壞情況下， 算法的時間復(fù)雜度是(C) O( 2n)A) O(n)B) O(n 2)D) O(n 3)(121) 若一組記錄的排序碼為( 46, 79, 56, 38, 40,84)，則利用快速排序的方法，以第一個記錄為基準得到的一 次劃分結(jié)果為(A) 38, 40, 46, 56, 79, 84 B)46 , 79, 56, 84C) 40, 3846, 84, 56, 79(1

33、22)， 46, 56, 79, 84列關(guān)鍵字序列中，40, 38,D)是堆。B)94,40, 38,23, 31,(123)堆是一種( )排序。A)插入 B) 選擇C) 交換D)歸并(124)堆的形狀是一棵( )。A)二叉排序樹 B) 滿二叉樹C) 完 全 二 叉 樹D) 平衡二叉樹(125)若一組記錄的排序碼為(46, 79, 56, 38, 40,84)，則利用堆排序的方法建立的初始堆為( )。A) 79, 46, 56, 38, 40, 84B) 84, 79, 56, 38,40, 46C) 84, 79, 56, 46, 40, 38D) 84, 56, 79, 40,46, 38

34、(126)下述幾種排序方法中，要求內(nèi)存最大的是D)16,23, 53,()。A) 16, 72, 31, 23, 94, 5372, 16, 53C) 16, 53, 23, 94，31, 7231, 94, 72A) 插入排序D) 選擇排序 (127) 有一組數(shù)據(jù)( 15，9， 堆排序的篩選方法建立的初始堆為(A) -1 ，4， 8，20，9C) -1 ，4， (128)B） 快速排序C） 歸 并 排 序7，8，7，9，20，7，15，78，20，15，7，951下列四個序列中，A) 75,65,30,15,25,45,20,10 75,65,45,10,30,25,20,15C) 75,4

35、5,65,30,15,25,20,1075,45,65,10,25,30,20,15 (129) 以下序列不是堆的是A) (100,85,98,77,80,60,82,40,20,10,66) (100,98,85,82,80,77,66,60,40,20,10)C) (10,20,40,60,66,77,80,82,85,98,100) (100,85,40,77,80,60,66,98,82,10,20) (130) 快速排序方法在( 長處。A) 要排序的數(shù)據(jù)量太大 多個相同值C) 要排序的數(shù)據(jù)個數(shù)為奇數(shù) 本有序 (131) 對關(guān)鍵碼序列 28， 速排序，從小到大一次劃分結(jié)果為A) (2,

36、5,12,16)26(60,32,72) (5,16,2,12)28(60,32,72)C) (2,16,12,5)28(60,32,72) (5,16,2,12)28(32,60,72)8，20，-1，7，4），用 ）。B） -1 ，7，15，7，4，D） A ，B，C 均不對。 哪一個是堆（B）。D)B)D)）情況下最不利于發(fā)揮其B） 要排序的數(shù)據(jù)中含有D） 要排序的數(shù)據(jù)已基16，32，12，60，2，5，72 快）。B）D)(132) 對下列關(guān)鍵字序列用快速排序法進行排序時，速 度最快的情形是(A) 21,25,5,17,9,23,30B)25,23,30,17,21,5,9）。C) 2

37、1,9,17,30,25,23,55,9,17,21,23,25,30二、填空題(133)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機 的 操作對象以及它們之間的關(guān)系和運算等的學科。中D是 數(shù)據(jù)元素D)(135) 和數(shù)據(jù)的(136) 構(gòu) 和(137)間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。(138) 在線性結(jié)構(gòu)中，第一個結(jié)點點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒有余每個結(jié)點有且只有1個后續(xù)結(jié)點。(139) 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū) 結(jié)點，有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。沒有前驅(qū)結(jié)點，其余每個結(jié) 后續(xù)結(jié)點，其后續(xù)其余每個結(jié)點結(jié)點，其余(

38、140)任意多個(141)是順序(142)在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以O(shè)數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別 、鏈式、索弓數(shù)據(jù)的運算最常用的有散列。5種，它們分別是插入刪除、以及它們之間的(134)數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R),其 的有限集合，R是D上的關(guān)系有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu)運算 這三個方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié) 非線性結(jié)構(gòu)。線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之修改、查找、排序。時間 效率和 空間 效(143) 一個算法的效率可分為率。(144) 對于給定的n個元素

39、,可以構(gòu)造出的邏輯結(jié)構(gòu)有 集合，線性表，樹，圖四種。(145) 順序映象的特點是借助兀素在存儲器中的 相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象的特點是借助是 指示元素存儲地址的 指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個算法的設(shè)計取決于選定 邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。(146) 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合 上的一組操作的總稱。(147) 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子 集。(148) 如果操作不改變原邏輯結(jié)構(gòu)的“值”，而只是從中提取某些信息作為運算結(jié)果，則稱該類運算為 型運算。引用(149) 算法的健壯特性是指做為一個好的算法

40、，輸入的數(shù)據(jù)非法時，也能適當?shù)刈龀稣_反應(yīng)或進行相應(yīng)的處理， 而不會產(chǎn)生一些莫名其妙的輸出結(jié)果。(150) 算法分析不是針對實際執(zhí)行時間的精確的算出算法執(zhí)行具體時間的分析，而是針對算法中語句的 執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。相同，稱作算法的漸進時間(151) T(n)(f(n)，它表示隨問題規(guī)模n的增大算法的執(zhí)行時間 的增長率和f(n)的增長率 復(fù)雜度，簡稱時間復(fù)雜度。(152) 若算法執(zhí)行時所需要的輔助空間相對于輸入數(shù)據(jù)量而言是原地工作，輔助空間為 0(1)。L中，第一個元素結(jié)點的指針個常數(shù)，則稱這個算法為(153) 在帶有頭結(jié)點的單鏈表中是 。 >(154) 在一個帶

41、頭節(jié)點的單循環(huán)鏈表中，P指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針可用 P表示為。>>(155) 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為()，為指針域，已知指針指向單鏈表中為x的結(jié)點，指針指向為y的新結(jié)點，若將結(jié)點y插入結(jié)點x 之后，則需要執(zhí)行以下語句:>>>(156) 對于棧操作數(shù)據(jù)的原則是 。后進先出。()(157) 設(shè)以數(shù)組Am存放循環(huán)隊列的元素，其頭尾指針分別為和， 則當前隊列中的元素個數(shù)為(158) 若已知一個棧的入棧序列是123,4n,其輸出序列為p123,，若p1=,則為(159) 隊列是被限定為只能在表的一端進行插入運 算，在表的另一端進行刪除運算的線性表。(160)

42、 通常程序在調(diào)用另一個程序時，都需要使用一個 棧來保存被調(diào)用程序內(nèi)分配的局部變量。形式參數(shù)的存儲空間以及返回地址。(161) 棧下溢是指在棧空時進行出棧操作。(162) 用P表示入棧操作，D表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的P和D的操作串為。個元(163) 在具有n個單元的循環(huán)隊列中，隊滿共有1素。(164) 隊列是被限定為只能在表的一端進行插入運(165)(166) 律。(167) 素按算，在表的另一端進行刪除運算的線性表。在稀疏矩陣表示所對應(yīng)的三元組線性表中，每個三元組元行為主序，列號為輔序的次序排列。aoo地址為循環(huán)隊列的引入，目的是為了克服假溢出

43、。 所謂稀疏矩陣指的是非零元很少(tvvm*n)且分布沒有規(guī)(168) 二位數(shù)組Xn按行優(yōu)先順序存儲在內(nèi)存中，元素(aoo),每個元素在內(nèi)存中占d個字節(jié)，元素的地址計算公式為()=_(aoo) + (i*)*d。(169) 去除廣義表(a123,)中第1個元素，由其余元素構(gòu)成 的廣義表稱為的表尾。(170) 樹內(nèi)個結(jié)點的度 最大值稱為樹的度。(171) 一個二叉樹第5層節(jié)點最多有16個。(172) 已知完全二叉樹T的第5層只有7個結(jié)點，則該樹共有11 個葉子結(jié)點。(173) 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為 no,度為2的結(jié)點 的個數(shù)為N2,則有no 2+1。(174) 假設(shè)用于通信的電文

44、由8個字母組成，其頻率分別為7,19,2,6,32,3,27,10。設(shè)計哈夫曼編碼，其中字母的編碼長度最大是 5 位。(175) 一棵具有257個結(jié)點的完全二叉樹，它的深度為。9不是惟(176) 圖的深度優(yōu)先遍歷序列 一的。(177)此圖的數(shù)據(jù)元素之間時一種(178)的入度。(179)度數(shù)之和為鄰接矩陣 、 深度優(yōu)先遍歷。出度如果n個頂點的圖是一個環(huán)，則它有(以任意一頂點為起點，得到1條邊)n個頂點e條邊的圖，若采用鄰接矩陣存儲，則 _O O(n2)n個頂點e條邊的圖，若采用鄰接表存儲，則空O 0()在圖中，任何兩個結(jié)點之間都可能存在關(guān)系，因 多對多的關(guān)系。在有向圖中，以頂點v為終點的邊的數(shù)目

45、稱為v 一個無向圖有n個頂點，e條邊，則所以頂點的2e O(180) 圖有鄰接表等存儲結(jié)構(gòu)，遍歷圖有 廣度優(yōu)先遍歷等方法。(181)(181) 有向圖G用鄰接表矩陣存儲，其第i行的所有非 零元素之和等于頂點i的(183)棵生成樹。(184)空間復(fù)雜度為(185)(186) 設(shè)有一稀疏圖 G則G采用表存儲較省空間。(187) 設(shè)有一稠密圖G則G采用矩陣存儲較省空間。(188)有向圖。(189)頂點出發(fā)的方法是(190)一的。(191)圖的逆鄰接表存儲結(jié)構(gòu)只適用于鄰接鄰接已知一個圖的鄰接矩陣表示，刪除所有從第i個將鄰接矩陣的第i行全部置0 O 圖的深度優(yōu)先遍歷序列 不是惟n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)0(n2);若采用鄰接表先遍歷算法的時間復(fù)雜度為_存儲時，該算法的時間復(fù)雜度為0()O(192) n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復(fù)雜度為 0( n2);若采用鄰接表存儲，該算法 的時間復(fù)雜度為 0()間復(fù)雜度為_圖的生成樹的樹高比生成樹的樹高(193) 小或相等(194) 用普里姆()算法求具有n個頂點e條邊的圖的最小生成樹的時間復(fù)雜度為 0(n2);用克魯斯卡爾()算法的時間復(fù)雜 度是0(2e)(195)O