第一章測(cè)試下列敘述中正確的是（

）

A:算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果

B:所謂算法就是計(jì)算方法

C:算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間

D:程序可以作為算法的一種描述方法

答案:D數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)（

）

A:對(duì)

B:錯(cuò)

答案:A在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（

）

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

B:動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

C:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

D:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

答案:A與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（

）

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

B:運(yùn)算實(shí)現(xiàn)

C:存儲(chǔ)結(jié)構(gòu)

D:存儲(chǔ)實(shí)現(xiàn)

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

）

A:數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B:數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

C:數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

D:一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

答案:D下面代碼段的時(shí)間復(fù)雜度是（）。s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

A:O(1)

B:O(logn)

C:O(

n2

)

D:O(n)

答案:C下面代碼段的時(shí)間復(fù)雜度是（）。x=0;

for(i=1;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

A:O(n)

B:O(logn)

C:O(n3)

D:O(n2)

答案:DNlogN2和NlogN具有相同的增長速度。（

）

A:錯(cuò)

B:對(duì)

答案:BN2logN2和NlogN2具有相同的增長速度。（

）

A:錯(cuò)

B:對(duì)

答案:A斐波那契數(shù)列FN的定義為：F0=0，F(xiàn)1=1，F(xiàn)N=FN?1+FN?2，N=2,3,…。用遞歸函數(shù)計(jì)算FN的時(shí)間復(fù)雜度是O(N!)。

A:錯(cuò)

B:對(duì)

答案:A第二章測(cè)試下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)（）

A:線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作

B:線性表采用鏈接存儲(chǔ)，便于插入和刪除操作

C:線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元

D:線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元

答案:A在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)下列哪個(gè)操作，其算法的時(shí)間復(fù)雜度是O(n)？

A:刪除開始結(jié)點(diǎn)

B:在地址為p的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)

C:刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn)

D:遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn)

答案:D鏈表不具有的特點(diǎn)是（）

A:可隨機(jī)訪問任一個(gè)元素

B:所需空間與線性表長度成正比

C:插入刪除不需要移動(dòng)元素

D:不必事先估計(jì)存儲(chǔ)空間

答案:A帶頭結(jié)點(diǎn)的單鏈表L為空的條件是（）

A:L->next==NULL;

B:L->next->next==NULL;

C:L==NULL;

D:L->next==L;

答案:A在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（）

A:p->next=s;p->next=s->next;

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

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

D:p->next=s;s->next=p->next;

答案:C在長度為n的順序表的表尾插入一個(gè)新元素的時(shí)間復(fù)雜度為（）

A:O(

n

)

B:O(

1

)

C:O(

logn

)

D:O(

n2

)

答案:B單鏈表中，增加頭結(jié)點(diǎn)的目的是為了()

A:說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

B:使單鏈表至少有一個(gè)結(jié)點(diǎn)

C:方便運(yùn)算的實(shí)現(xiàn)

D:標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

答案:C線性表的邏輯順序與物理順序總是一致的（）

A:錯(cuò)

B:對(duì)

答案:A取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)(

)

A:錯(cuò)

B:對(duì)

答案:A線性表的長度是線性表所占用的存儲(chǔ)空間的大小（）

A:錯(cuò)

B:對(duì)

答案:A第三章測(cè)試設(shè)有六列火車，編號(hào)為1，2，3，4，5，6，順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)，問下列輸出序列中，哪個(gè)是不可能出現(xiàn)的（

）。

A:1,2,3,4,5,6

B:3,1,2,6,5,4

C:3,2,1,6,5,4

D:6,5,4,3,2,1

答案:B棧和隊(duì)列都是運(yùn)算受限的線性表。（

）

A:對(duì)

B:錯(cuò)

答案:A當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示棧空，則表示棧滿的條件是top==1。（

）

A:錯(cuò)

B:對(duì)

答案:A元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是（

）。

A:6

B:5

C:3

D:4

答案:D已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0..n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是（

）。

A:n-1,n-1

B:n-1,0

C:0,0

D:0,n-1

答案:D數(shù)組Q[n]用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（

）。

A:(n+f-r)%n

B:n+r-f

C:r-f

D:(n+r-f)%n

答案:D若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是（

）。

A:V[top]=x;top++;

B:top++;V[top]=x;

C:top–;V[top]=x;

D:V[top]=x;top–;

答案:C設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（

）。

A:6

B:3

C:2

D:4

答案:B循環(huán)隊(duì)列放在一維數(shù)組A[0…M-1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是（

）。

A:隊(duì)空：end1==(end2+1)；隊(duì)滿：end2==(end1+1)mod(M-1)

B:隊(duì)空：end1==end2；隊(duì)滿：end1==(end2+1)modM

C:隊(duì)空：end1==end2；隊(duì)滿：end2==(end1+1)mod(M-1)

D:隊(duì)空：end2==(end1+1)modM；隊(duì)滿：end1==(end2+1)modM

答案:B用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（

）。

A:僅修改尾指針

B:頭、尾指針可能都要修改

C:僅修改頭指針

D:頭、尾指針都要修改

答案:B第四章測(cè)試由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的樹（）

A:2

B:4

C:5

D:3

答案:A一棵樹高為K的完全二叉樹至少有(

)個(gè)結(jié)點(diǎn)

A:

B:

C:

D:

答案:D將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào)，根為1號(hào)，按從上到下、從左到右順序結(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙親結(jié)點(diǎn)編號(hào)為（

）

A:21

B:20

C:42

D:40

答案:B對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹,其高度為（）

A:

B:

C:不確定

D:

答案:C給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3、1、7、5、6、2、4，則其遍歷方式是（）

A:RNL

B:LRN

C:NRL

D:RLN

答案:A如果T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點(diǎn)的先序就是T2中結(jié)點(diǎn)的（）

A:先序

B:層次

C:后序

D:中序

答案:A下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）

A:{11,10,001,101,0001}

B:{0,10,110,1111}

C:{00,010,0110,1000}

D:{b,c,aa,ac,aba,abb,abc}

答案:A二叉樹先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是（）

A:E

B:F

C:G

D:H

答案:C以下說法錯(cuò)誤的是（）

A:若初始森林中共有N棵二叉樹，最終求得的哈夫曼樹中共有2N-1個(gè)結(jié)點(diǎn)

B:一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近

C:若初始森林中共有N棵二叉樹，進(jìn)行2N-1次合并后才能剩下最終的哈夫曼樹

D:哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)

答案:C若一棵二叉樹的任一非葉子結(jié)點(diǎn)的度為2，則該二叉樹為滿二叉樹（）

A:錯(cuò)

B:對(duì)

答案:A若某二叉樹的葉子結(jié)點(diǎn)數(shù)為1，則其先序序列和后序序列一定相反（）

A:錯(cuò)

B:對(duì)

答案:B完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。（

）

A:對(duì)

B:錯(cuò)

答案:A利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（

）

A:空

B:指向最右孩子

C:指向最左孩子

D:非空

答案:A第五章測(cè)試用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)。（）

A:錯(cuò)

B:對(duì)

答案:B有向圖的鄰接矩陣是對(duì)稱的。（）

A:對(duì)

B:錯(cuò)

答案:B設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。

A:n(n-1)/2

B:0

C:n(n+1)/2

D:n-1

答案:A下列關(guān)于無向連通圖特征的敘述中，正確的是：（）1.所有頂點(diǎn)的度之和為偶數(shù)2.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減13.至少有一個(gè)頂點(diǎn)的度為1

A:只有2

B:1和3

C:1和2

D:只有1

答案:D對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，所有頂點(diǎn)鄰接表的邊結(jié)點(diǎn)總數(shù)為（）。

A:e/2

B:e

C:n+e

D:2e

答案:D給定一有向圖的鄰接表如下。從頂點(diǎn)V1出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則得到的頂點(diǎn)序列為()。

A:V1,V5,V4,V7,V6,V3,V2

B:V1,V5,V4,V7,V6,V2,V3

C:V1,V5,V6,V4,V7,V2,V3

D:V1,V2,V3,V4,V7,V6,V5

答案:A在圖中自a點(diǎn)開始進(jìn)行廣度優(yōu)先搜索算法可能得到的結(jié)果為（）。

A:a,e,b,c,f,d

B:a,e,d,f,c,b

C:a,b,e,c,d,f

D:a,c,f,e,b,d

答案:C任何一個(gè)帶權(quán)無向連通圖的最小生成樹（）。

A:是不唯一的

B:有可能不存在

C:是唯一的

D:有可能不唯一

答案:D對(duì)于下列的網(wǎng)，使用克魯斯卡爾算法求最小生成樹，依次得到的邊集是（）。

A:{（A，D），（B，C），（E，A），（C，E）}

B:{（A，D），（D，E），（B，C），（C，E）}

C:{（A，D），（D，E），（E，C），（C，B）}

D:{（A，D），（A，B），（A，E），（E，C）}

答案:B使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點(diǎn)1到其它各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)頂點(diǎn)是（）。

A:5,2,4,3,6

B:5,2,3,6,4

C:5,2,3,4,6

D:5,2,6,3,4

答案:B第六章測(cè)試二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。（

）

A:對(duì)

B:錯(cuò)

答案:B查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。（

）

A:對(duì)

B:錯(cuò)

答案:B在查找樹（二叉排序樹）中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。（

）

A:錯(cuò)

B:對(duì)

答案:A采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（

）

A:錯(cuò)

B:對(duì)

答案:B對(duì)一棵二叉排序樹按先序方法遍歷得出的結(jié)點(diǎn)序列是從小到大的序列。（

）

A:對(duì)

B:錯(cuò)

答案:B已知一個(gè)長度為16的順序表L,其元素按關(guān)鍵字有序排列,若采用折半查找法查找一個(gè)不存在的元素,則比較次數(shù)最多的是（

）。

A:7

B:6

C:5

D:4

答案:C對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是(

）。

A:12,25,71,68,33,34

B:92,20,91,34,88,35

C:95,22,91,24,94,71

D:21,89,77,29,36,38

答案:C在任意一棵非空二叉排序樹T1中，刪除某結(jié)點(diǎn)v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關(guān)于T1與T3的敘述中，正確的是（

）。I.若v是T1的葉結(jié)點(diǎn)，則T1與T3不同II.若v是T1的葉結(jié)點(diǎn)，則T1與T3相同III.若v不是T1的葉結(jié)點(diǎn)，則T1與T3不同IV.若v不是T1的葉結(jié)點(diǎn)，則T1與T3相同

A:僅II、IV

B:僅I、III

C:僅I、IV

D:僅II、III

答案:D對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7作為散列函數(shù)，則哈希地址為0的元素有（

）個(gè)

A:1

B:3

C:4

D:2

答案:C適用于折半查找的查找表存儲(chǔ)方式及元素排列要求為(

)

A:鏈接方式存儲(chǔ)，元素?zé)o序

B:鏈接方式存儲(chǔ)，元素有序

C:順序方式存儲(chǔ)，元素有序

D:順序方式存儲(chǔ)，元素?zé)o序

答案:C有一個(gè)有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，當(dāng)用折半查找方法查找值82的結(jié)點(diǎn)時(shí)，（）次比較后查找成功。

A:1

B:4

C:8

D:2

答案:B將{5,2,7,3,4,1,6}依次插入初始為空的二叉排序樹。則該樹的后序遍歷結(jié)果是:（）

A:5,4,3,7,6,2,1

B:1,4,2,6,3,7,5

C:1,2,3,4,6,7,5

D:1,4,3,2,6,7,5

答案:D有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐步插入數(shù)據(jù)形成二叉排序樹，若希望高度最小，應(yīng)選擇下列（）的序列輸入。

A:45，24，53，12，37，96，30

B:30，24，12，37，45，96，53

C:37，24，12，30，53，45，96

D:12，24，30，37，45，53，96

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

A:采用鏈地址法處理沖突時(shí)，查找每個(gè)元素的時(shí)間是相同的

B:采用鏈地址法處理沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個(gè)元素的時(shí)間是相同的

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

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

答案:A第七章測(cè)試快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。

A:對(duì)

B:錯(cuò)

答案:B堆排序是穩(wěn)定的排序方法。

A:對(duì)

B:錯(cuò)

答案:B在初始數(shù)據(jù)表已經(jīng)有序時(shí)，快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。

A:對(duì)

B:錯(cuò)

答案:B在用堆排序算法排序時(shí)，如果要進(jìn)行增序排序，則需要采用“大根堆”。

A:對(duì)

B:錯(cuò)

答案:A比較次數(shù)與排序的初始狀態(tài)無關(guān)