第一章測試研究數(shù)據(jù)結(jié)構(gòu)就是研究(

)。

A:數(shù)據(jù)的邏輯結(jié)構(gòu)

B:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)

C:數(shù)據(jù)的存儲結(jié)構(gòu)

D:數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

答案:B關(guān)于算法的說法，錯誤的是(

)。

A:算法的可行性是指指令不能有二義性

B:為解決某問題的算法和為該問題編寫的程序含義是相同的

C:算法最終必須由計算機程序?qū)崿F(xiàn)

D:其他三項都是錯誤的

答案:D數(shù)據(jù)的(

)包括集合、線性、樹和圖4種基本類型。

A:邏輯結(jié)構(gòu)

B:算法描述

C:基本運算

D:存儲結(jié)構(gòu)

答案:A數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈式、散列和(

)4種基本類型。

A:向量

B:集合

C:索引

D:數(shù)組

答案:C下面算法的時間復雜度為(

)。for(i=0;i<m;i++)for(j=0;j<n;j++)

A[i][j]=i*j;

A:O(n2)

B:O(m+n)

C:O(m×n)

D:O(m2)

答案:C以下（

）屬于設(shè)計一個“好”的算法應考慮達到的目標。

A:效率與低存儲量要求

B:健壯性

C:正確性

D:可讀性

答案:ABCD依據(jù)所有數(shù)據(jù)成員之間的邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為（

）。??

A:邏輯結(jié)構(gòu)

B:物理結(jié)構(gòu)

C:線性結(jié)構(gòu)

D:非線性結(jié)構(gòu)

答案:CD在存儲數(shù)據(jù)時，不僅要考慮存儲各數(shù)據(jù)元素的值，而且還要存儲數(shù)據(jù)元素之間的關(guān)系。

A:錯

B:對

答案:B在邏輯結(jié)構(gòu)定義的操作與具體實現(xiàn)有關(guān)。

A:對

B:錯

答案:B算法是對解題方法和步驟的描述。

A:對

B:錯

答案:A算法分析的兩個主要方面是時間復雜度和空間復雜度的分析。

A:對

B:錯

答案:A第二章測試線性表是（

）。

A:一個無限序列，不能為空。

B:一個有限序列，不能為空。

C:一個無限序列，可以為空。

D:一個有限序列，可以為空。

答案:D若某線性表中最常用的操作是取第i個元素和查找第i個元素的前驅(qū)，則采用（）存儲方法最節(jié)省時間。

A:循環(huán)鏈表

B:單鏈表

C:雙向鏈表

D:順序表

答案:D單鏈表中，增加一個頭結(jié)點的目的是為了（

）。

A:標識表結(jié)點中首結(jié)點的位置

B:方便運算的實現(xiàn)

C:使單鏈表至少有一個結(jié)點

D:說明單鏈表是線性表的鏈式存儲

答案:B在帶有頭結(jié)點的單鏈表Head中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（

）。

A:p->next=Head;

Head=p;

B:p->next=Head->next;

Head->next=p;

C:Head=p;p->next=Head;

D:p->next=Head;

p=Head;

答案:B在n個結(jié)點的順序表中，算法的時間復雜度是O(1)的操作是（）。

A:將n個元素從小到大排序

B:訪問第i個元素（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）

C:在第i個元素后插入一個新結(jié)點（1≤i≤n）

D:刪除第i個元素（1≤i≤n）

答案:B下列說法正確的有(

)。

A:所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系?

B:算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者通用

C:數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)

D:從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)

E:“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)相等

答案:ACD線性表的邏輯順序和存儲順序總是一致的。

A:錯

B:對

答案:A在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。

A:錯

B:對

答案:B順序存儲結(jié)構(gòu)只能存儲線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只能存儲非線性結(jié)構(gòu)。

A:對

B:錯

答案:B線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。

A:對

B:錯

答案:B鏈式存儲方式以指針表示元素間的邏輯關(guān)系。

A:對

B:錯

答案:A第三章測試在順序?？盏那闆r下不能進行出棧操作，否則將產(chǎn)生“下溢”。

A:錯

B:對

答案:B棧和隊列都是限制存取位置的線性表。

A:錯

B:對

答案:B若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行，則不可能得到出棧序列：a,f,e,d,c,b。

A:對

B:錯

答案:B入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時一般不需要考慮棧溢出的情況。

A:對

B:錯

答案:A同一個棧內(nèi)的各個數(shù)據(jù)元素類型可以不一致。

A:錯

B:對

答案:A以下說法中正確的是（

）

A:當隊列中無數(shù)據(jù)元素時，稱空隊列。

B:棧是一種操作不受限制的線性表。

C:棧是一種只允許在一端進行插入和刪除的線性表。

D:隊列被稱為“先進后出”表。

答案:AC以下說法中錯誤的是(

)?。

A:當top等于數(shù)組最大下標時則棧滿。

B:top=-1時為空棧，元素進棧時指針top不斷減1。

C:利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，這種形式的棧稱為順序棧。

D:棧不能對輸入序列部分或全局求逆。

答案:BD已知一個棧的進棧序列是a1,a2,a3….an.其輸出序列為1,2,3…n,若a3=1則a1為（

）

A:不可能是2

B:不可能是3

C:一定是2

D:可能是2

E:可能是3

答案:ACE棧的特點是（

）

A:先進后出

B:進優(yōu)于出

C:出優(yōu)于進

D:先進先出

答案:A設(shè)循環(huán)隊列的容量為20，序號從0到19，經(jīng)過一系列的入隊和出隊后，front=5,rear=10,問隊列中有多少個元素（采用節(jié)省一個隊列存儲空間的方式）。

A:4

B:5

C:7

D:6

答案:B一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（

）

A:1，4，3，2

B:4，3，2，1

C:1，2，3，4

D:3，2，4，1

答案:C一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應該設(shè)置（

）

A:棧

B:數(shù)組

C:?；蜿犃?/p>

D:隊列

答案:A設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（

）

A:判別棧元素的類型

B:對棧不作任何判別

C:必須判別棧是否為滿

D:必須判別棧是否為空

答案:D第四章測試KMP算法的特點是在模式匹配時指示主串的指針不會變小。

A:錯

B:對

答案:B空串與空格串是相同的。

A:對

B:錯

答案:B串的長度是指串中不同字符的個數(shù)。

A:對

B:錯

答案:B設(shè)有兩個串P和Q，其中Q是P的子串，把Q在P中首次出現(xiàn)的位置作為子串Q在P中的位置的算法稱為模式匹配算法。

A:對

B:錯

答案:A設(shè)模式串（子串）的長度為m，目標串（主串）的長度為n。當n≈m且處理只匹配一次的模式時，簡單模式匹配（BF）算法所花費的時間代價也可能會比KMP算法更節(jié)省。

A:對

B:錯

答案:A串是一種特殊的線性表，下列不能體現(xiàn)其特殊性的是（

）

A:數(shù)據(jù)元素可以是非字符數(shù)據(jù)

B:可以鏈接存儲

C:數(shù)據(jù)元素是字符型數(shù)據(jù)

D:可以順序存儲

答案:ABD以下說法中錯誤的是(

)?

A:串是一種特殊的線性表

B:串中的元素只能是字母

C:空串就是空白串

D:串的長度必須大于零

答案:BCD兩個串相等必須有（

）

A:串中的各位置字符任意

B:串長度相等

C:串長度不相等

D:串長度任意

E:串中各位置字符均對應相等

答案:BE若串S=”software”，其子串的數(shù)目是（

）

A:37

B:9

C:36

D:8

答案:A下面（

）不是“abcd321ABCD”的子串（

）

A:abcAB

B:abcd

C:321AB

D:21AB

答案:A已知模式串為“aaab”，其next數(shù)組值為（

）

A:-1,0,1,2

B:0,1,2,0

C:0,0,1,2

D:-1,1,0,0

答案:A設(shè)主串為“abccdcdccdbaa”，模式串為“cdcc”，用BF算法在第（

）次匹配成功。

A:4

B:7

C:5

D:6

答案:D設(shè)串s1=“ABCDEFG”，s2=“12345”，用字符數(shù)組從0下標位置存儲，函數(shù)strcat(s,t)返回s和t串的連接串，strsub(s,i,j)返回串s中從第i個字符開始的連續(xù)j個字符組成的子串，strlen(s)返回串s的長度，則strcat(strsub(s1,2,strlen(s2)),strsub(s1,strlen(s2),2))的結(jié)果是（

）

A:CDEFGFG

B:CDEFG12

C:BCDEFG1

D:CD12345

答案:A第五章測試稀疏矩陣壓縮存儲后，必會失去隨機存取功能。

A:對

B:錯

答案:A數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。

A:錯

B:對

答案:A數(shù)組的存儲結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元。

A:錯

B:對

答案:B廣義表中原子個數(shù)即為廣義表的長度。

A:錯

B:對

答案:A廣義表中元素的個數(shù)即為廣義表的深度。

A:錯

B:對

答案:A廣義表((a),(a))的表頭和表尾是（

）

A:((a))

B:(a)

C:b

D:a

答案:AB以下屬于特殊矩陣的是(

)?

A:下三角矩陣

B:對稱矩陣

C:上三角矩陣

D:對角矩陣

答案:ABCD以下不屬于數(shù)組操作的是(

)?

A:存取

B:修改

C:插入

D:刪除

E:查找

答案:CD對行下標由1到50、列下標由1到80的二維數(shù)組a，若該數(shù)組的起始地址為2000且每個元素占2個存儲單元，并以行為主序順序存儲，則元素a[45][68]的存儲地址為（

）

A:9175

B:9174

C:9172

D:9173

答案:B在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（

）

A:非零元素個數(shù)

B:行號

C:列號

D:元素值

答案:B設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（

）

A:28

B:19

C:10

D:55

答案:B設(shè)二維數(shù)組A[0~m][0~n]按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則a[i][j]的地址為（

）

A:p+((i-1)n+j-1)k

B:p+(in+j)k

C:p+((j-1)n+i-1)k

D:p+(jn+i-1)k

答案:B下面說法不正確的是（

）

A:廣義表的表尾總是一個廣義表

B:廣義表可以是一個多層次結(jié)構(gòu)

C:廣義表難以用順序結(jié)構(gòu)存儲

D:廣義表的表頭總是一個廣義表

答案:D第六章測試一棵完全二叉樹上有1001個結(jié)點，其葉子結(jié)點的個數(shù)是（）。

A:505

B:250

C:500

D:A～C都不對

答案:D一棵有124個葉結(jié)點的完全二叉樹最多有（）個結(jié)點。

A:250

B:249

C:247

D:248

答案:D在n個結(jié)點的線索二叉樹中，線索的數(shù)目為（）

A:n-1

B:n+1

C:2n

D:n

答案:B設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個結(jié)點。

A:26

B:25

C:13

D:12

答案:B樹的基本遍歷策略可分為先根遍歷和后根遍歷，而二叉樹的基本遍歷策略可分為先序、中序和后序這三種遍歷。我們把由樹轉(zhuǎn)化得到的二叉樹稱為該樹對應的二叉樹，則（）是正確的。

A:樹的先根遍歷與其對應的二叉樹先序遍歷序列相同

B:樹的后根遍歷與其對應的二叉樹后序遍歷序列相同

C:樹的先根遍歷與其對應的二叉樹中序遍歷序列相同

答案:A完全二叉樹（）。

A:不一定適合順序存儲結(jié)構(gòu)存儲

B:適合于順序存儲結(jié)構(gòu)存儲

C:某些結(jié)點有左子樹時則必有右子樹

D:葉子結(jié)點可在任一層出現(xiàn)

E:某些結(jié)點有右子樹時則必有左子樹

答案:BE對于二叉樹，下列描述正確的是（）

A:第k層上最多有2k-1個結(jié)點

B:n個結(jié)點共有n-1個非空指針域

C:高度為k的二叉樹結(jié)點數(shù)最多時一定是滿二叉樹

D:邊的個數(shù)比結(jié)點個數(shù)少1個

E:一定有度數(shù)為1的結(jié)點

F:葉子結(jié)點數(shù)目比度數(shù)為2的結(jié)點數(shù)目多1個

答案:BCDF關(guān)于哈夫曼編碼的說法正確的是（

）

A:WPL最小

B:編碼無二義性

C:兩個頻度相同的字符其編碼長度一定相等

D:不允許出現(xiàn)頻度相同的字符

E:是一種最佳編碼

答案:ABE存在這樣的二叉樹，對它采用任何次序進行遍歷得到的結(jié)果都相同。

A:對

B:錯

答案:A二叉樹就是結(jié)點度為2的有序樹。

A:對

B:錯

答案:B若一個結(jié)點是二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子樹的先序遍歷序列中的最后一個結(jié)點。

A:錯

B:對

答案:A

一棵含有n個結(jié)點的完全二叉樹，它的高度是?log2n?+1。

A:錯

B:對

答案:B線索二叉樹的左線索指向其某種遍歷序列的直接前驅(qū)結(jié)點，右線索指向其某種遍歷序列的直接后繼結(jié)點。

A:錯

B:對

答案:B第七章測試無向圖的鄰接矩陣是（

）矩陣。

A:稀疏矩陣

B:下三角陣

C:對稱

D:上三角陣

答案:C用鄰接表存儲的圖所用空間大?。?/p>

）

A:與邊數(shù)的平方有關(guān)

B:只與圖的頂點數(shù)有關(guān)與邊數(shù)的平方有關(guān)

C:與圖的頂點數(shù)和邊數(shù)都有關(guān)

D:只與圖的邊數(shù)有關(guān)

答案:C不論基于圖的鄰接表還是基于鄰接矩陣存儲，圖的廣度優(yōu)先遍歷算法類似于樹的（

）

A:層次遍歷

B:后序遍歷

C:先序遍歷

D:中序遍歷

答案:A一個連通圖的生成樹是包含該圖的所有頂點的（

）

A:極大子圖

B:極小子圖

C:極小連通子圖

D:極大連通子圖

答案:C具有n個頂點的連通有向圖中，至少需要（

）條邊。

A:n

B:n-1

C:2n

D:n+1

答案:A下列哪些算法是屬于圖的應用算法（

）

A:拓撲排序算法

B:哈夫曼（Huffman）算法

C:迪杰斯特拉（Dijkstra）算法

D:歐幾里德算法

E:克魯斯卡爾（Kruskal）算法

答案:ACE下列（

）算法可用于構(gòu)造圖的生成樹。

A:DFS

B:BFS

C:Prim

D:Floyd

E:kruskal

答案:ABCE下列（

）是構(gòu)造最短路徑的方法。

A:Kruskal

B:Floyd

C:Prim

D:Dijkstra

E:BFS

答案:BDn個結(jié)點的無向圖，若沒有頂點到自身的邊，也沒有一個頂點到另一個頂點的多重邊，此時若有n(n-1)/2條邊，則該無向圖一定是連通圖。

A:對

B:錯

答案:A用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用空間大小與圖的頂點數(shù)有關(guān)，與圖的邊數(shù)無關(guān)。

A:對

B:錯

答案:A對于任意一個圖，從它的某個頂點出發(fā)進行一次深度或者廣度遍歷可以訪問到該圖的每個頂點。

A:錯

B:對

答案:A對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。

A:錯

B:對

答案:A有向圖頂點v的度是其鄰接矩陣中第v行1的個數(shù)。

A:錯

B:對

答案:A第八章測試衡量一個查找算法執(zhí)行效率高低的最重要的指標是（）。

A:平均查找長度

B:所需的內(nèi)存大小

C:查找過程中關(guān)鍵字比較的最大次數(shù)

D:查找表中的元素個數(shù)

答案:A對線性表進行二分查找時，要求線性表必須

（

）。

A:采用順序存儲結(jié)構(gòu)

B:采用鏈接存儲結(jié)構(gòu)

C:采用鏈接存儲結(jié)構(gòu)且結(jié)點按查找關(guān)鍵字有序排列

D:采用順序存儲結(jié)構(gòu)且元素按查找關(guān)鍵字有序排列

答案:D哈希查找中的沖突是指（

）。.

A:兩個元素的關(guān)鍵字值相同

B:兩個元素的關(guān)鍵字值不同

C:兩個元素具有相同序號

D:不同關(guān)鍵字值對應相同的存儲地址

答案:D對于一棵二叉排序樹進行（）遍歷可得到按關(guān)鍵字有序排列的數(shù)據(jù)序列。

A:先序

B:后序

C:層序

D:中序

答案:D順序查找適合于采用（

）存儲結(jié)構(gòu)的線性表。

A:散列

B:壓縮

C:順序或鏈式

D:索引

答案:C下面關(guān)于哈希查找的說法中，正確的是()

A:采用鏈地址法處理沖突時，若規(guī)定采用頭插法進行插入，則插入任何一個元素的時間是相同的

B:用鏈地址處理沖突，適合表長不確定的情況

C:鏈地址法處理沖突的平均查找長度小于線性探測和二次探測

D:用鏈地址處理沖突，不會引起二次聚集的現(xiàn)象

E:采用鏈地址法處理沖突時，查找任何一個元素的時間都相同

答案:ABCD以下關(guān)于二叉排序樹的說法中，正確的是()

A:二叉排序樹中左子樹上所有結(jié)點的關(guān)鍵字值均小于它的根結(jié)點

B:二叉排序樹一定為一棵平衡二叉樹

C:在二叉排序樹上的查找過程與折半查找過程類似

D:二叉排序樹中右子樹上所有結(jié)點的關(guān)鍵字值均大于它的根結(jié)點

E:對某棵二叉排序樹進行中序遍歷，一定能得到按關(guān)鍵字升序排列的有序序列

答案:ACDE在一個結(jié)點值按照查找關(guān)鍵字有序排列的單鏈表上可以采用折半查找方法來提高查找速度。

A:錯

B:對

答案:A折半查找過程所對應的判定樹一定是一棵平衡二叉樹。

A:對

B:錯

答案:A在任意一個數(shù)據(jù)表上，采用折半查找一定比采用順序查找的查找速度快。

A:對

B:錯

答案:B在結(jié)點數(shù)確定的二叉排序樹上進行查找的平均查找長度與二叉樹的形態(tài)有關(guān)，最好的情況是二叉排序樹為平衡二叉樹的時候。

A:錯

B:對

答案:B折半查找的效率與二叉排序樹的查找效率是一樣的。

A:錯

B:對

答案:A第九章測試對同一組數(shù)據(jù)分別采用直接插入排序和折半插入排序進行排序，二者可能存在的不同之處在于（

）。

A:排序的總趟數(shù)

B:占用的輔助內(nèi)存空間大小

C:整個排序過程中的關(guān)鍵字比較次數(shù)

D:整個排序過程中的元素移動次數(shù)

答案:C希爾排序?qū)?/p>