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

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

2、有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不 影響數(shù)據(jù)處理的效率D) 個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)， 且各種存儲(chǔ)結(jié)構(gòu)影響 數(shù)據(jù)處理的效率 (6) 數(shù)據(jù)的基本單位是()A) 數(shù)據(jù)項(xiàng)B) 數(shù)據(jù)類(lèi)型)。C) 算法D) 操)兩大類(lèi)。B) 順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)D) 初等結(jié)構(gòu)、構(gòu)造型C) 數(shù)據(jù)元素D) 數(shù)據(jù)變量(7) 下列程序的時(shí)間復(fù)雜度為(0；0；s<n) ； A) o (Vn)B) o (Qn)C) O (n)D) O(n2)(8)下列程序段的漸進(jìn)時(shí)間復(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ù)，則最后一行的語(yǔ)句頻度在最壞情況下是( )。A) 0(n)0(n2)(10)(1；B) 0()C) 0(n 3)D)在下面的程序段中，x的賦值語(yǔ)句的頻度為)。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ù)，則最后一行的語(yǔ)句頻度在最壞情況下是其中()。A) 0(n ) 0(n2) (12)(n)B) 0()3C) 0(n )D)設(shè)有一個(gè)遞歸算法如下:A) n1(13) /* 大于等于

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

5、 0(n) 和 0(n)(15)求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(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) 從一個(gè)長(zhǎng)度為 n 的順序表中刪除第w i W n)時(shí)，需向前移動(dòng)的元素的個(gè)數(shù)是(A)B)1C)1D)i(18) 已知一個(gè)有序表為( 13， 18， 24，i 個(gè)元素( 1 )。35， 47， 50， 62， 83， 90， 115， 1

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

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

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

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

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

11、4， 3，C) 4 ， 3， 2，(37)A)D)棧和隊(duì)列的共同點(diǎn)是(38)A)C)(39)C)都是先進(jìn)后出沒(méi)有共同點(diǎn))。B)D)1 ， 2， 3， 4，則隊(duì)列的輸都是先進(jìn)先出只允許在端點(diǎn)處插入和刪除元素 一個(gè)隊(duì)列的入隊(duì)序列是)。出序列是( 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)隊(duì)列的存儲(chǔ)空間，為隊(duì)頭指針，為隊(duì)尾指針，則執(zhí)行出對(duì)操作后其頭指針值為( )。A)C) (41)1(1)B) (1)%(1)D) (1)引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是( )A) 出隊(duì) 取隊(duì)尾元素 設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素，其頭尾指針?lè)謩e為

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

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) 便于進(jìn)行矩陣運(yùn)算C) 節(jié)省存儲(chǔ)空間度(46)對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是(B) 便于輸入和輸出D) 降低運(yùn)算的時(shí)間復(fù)雜對(duì)廣義表 (),(),()執(zhí)行操作 (L) 的結(jié)果是( ) 。A) ()D) ( ) (47)B) ()C) (f)設(shè)廣義表()，則L的長(zhǎng)度和深度分別為()。(48)2(49)(50)A) 1 和 1D) 2 和 3B) 1 和 3C) 1 和 2樹(shù)中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加

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

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

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

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

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

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

20、(),(),對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是( B)。 D)值總和(),()。C) D)面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)A)D) (78)A) 層次 (79)回路)。求節(jié)點(diǎn)的度求關(guān)鍵路徑B) 拓?fù)渑判駽) 求 最 短 路 徑先根圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的(B) 中根 C) 后根)次序遍歷。D)在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的的時(shí)間復(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>的拓?fù)湫蛄惺?A) V 1346257B) VC) VD) V(81) 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(A)從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B)短路徑C)最長(zhǎng)回路(82)A) n 2(83)數(shù)目是)。從源點(diǎn)到匯點(diǎn)的最最短回路有n個(gè)結(jié)點(diǎn)的有向完全圖的弧數(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在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖

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

23、y從頂點(diǎn) 出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是()。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) 已知圖的鄰接矩陣同上題 點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是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) 已知圖的鄰接矩陣同上題 點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是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)先點(diǎn)序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ù)算法，則從頂點(diǎn)發(fā)按深度訂遍歷的結(jié)列門(mén)(C) 0 3 2 1是)。D) 0 1 2 3(96)已知圖的鄰接表如下所示，0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是(根據(jù)算法，則從頂點(diǎn)%*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,點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是(D) 0 3 1 2(97)A)先序遍歷深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的B)中序遍歷C)。后序遍歷D) (98)A)D) (99)A)D)層次遍歷先序遍歷層次遍歷廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的( )。B) 中序遍歷 C) 后 序 遍 歷任何一個(gè)無(wú)向連通圖的最小生成樹(shù)( )。B) 一棵或多棵 C) 一 定 有 多 棵只有一棵 可能不存在 (注， 生成樹(shù)不唯一， 但最小生成樹(shù)唯一， 即邊權(quán)之和 或樹(shù)權(quán)最小的情況唯一) (100) 在分析折半查找的性能時(shí)常常加入失敗節(jié)點(diǎn)，即 外節(jié)點(diǎn)，從而形成擴(kuò)

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

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

28、4,56,79快速排序在最壞情況下的時(shí)間復(fù)雜度是D) O( 2n) )。B) O(n 2)C) O( 2n)列排序算法中不穩(wěn)定的是(B) 折半插入排序 C) 冒泡排序)。, 當(dāng)由關(guān)鍵字集合 構(gòu)建二叉排序樹(shù)時(shí) , 第一個(gè)插C) 41D) 62(56,23,78,92,88,67,19,34) 進(jìn)行 增量為 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、 排 序 方 法 對(duì) 35,84,21,47,15,27,68,25,20 進(jìn)行排序時(shí)， 如下：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) ，則 利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的第一次劃分 結(jié)果為( )。A) 38,40,46,56,79,8440,38,46,56,79,84(109)( A) O(n 22n)(110)A)

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

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

32、列哪種情況下最易發(fā)揮其長(zhǎng)處。A)B)C)D) (120)。)。被排序的數(shù)據(jù)中含有多個(gè)相同排序碼 被排序的數(shù)據(jù)已基本有序 被排序的數(shù)據(jù)完全無(wú)序 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊 對(duì)有 n 個(gè)記錄的表作快速排序，在最壞情況下， 算法的時(shí)間復(fù)雜度是(C) O( 2n)A) O(n)B) O(n 2)D) O(n 3)(121) 若一組記錄的排序碼為( 46, 79, 56, 38, 40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一 次劃分結(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)二叉排序樹(shù) B) 滿二叉樹(shù)C) 完 全 二 叉 樹(shù)D) 平衡二叉樹(shù)(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下列四個(gè)序列中，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) 快速排序方法在( 長(zhǎng)處。A) 要排序的數(shù)據(jù)量太大 多個(gè)相同值C) 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 本有序 (131) 對(duì)關(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 均不對(duì)。 哪一個(gè)是堆（B）。D)B)D)）情況下最不利于發(fā)揮其B） 要排序的數(shù)據(jù)中含有D） 要排序的數(shù)據(jù)已基16，32，12，60，2，5，72 快）。B）D)(132) 對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速 度最快的情形是(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)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī) 的 操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。中D是 數(shù)據(jù)元素D)(135) 和數(shù)據(jù)的(136) 構(gòu) 和(137)間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。(138) 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。(139) 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū) 結(jié)點(diǎn)，有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié) 后續(xù)結(jié)點(diǎn)，其后續(xù)其余每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)，其余(

38、140)任意多個(gè)(141)是順序(142)在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以O(shè)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別 、鏈?zhǔn)健⑺鞴瓟?shù)據(jù)的運(yùn)算最常用的有散列。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ù)的 存儲(chǔ)結(jié)構(gòu)運(yùn)算 這三個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是 線性結(jié) 非線性結(jié)構(gòu)。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之修改、查找、排序。時(shí)間 效率和 空間 效(143) 一個(gè)算法的效率可分為率。(144) 對(duì)于給定的n個(gè)元素

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

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

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

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

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

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

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