數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-濱州學(xué)院）智慧樹知到課后章節(jié)答案2023年下濱州學(xué)院

數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-濱州學(xué)院）智慧樹知到課后章節(jié)答案2023年下濱州學(xué)院濱州學(xué)院

第一章測試

數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的表示是指（）

A:數(shù)據(jù)的邏輯結(jié)構(gòu)B:數(shù)據(jù)結(jié)構(gòu)C:數(shù)據(jù)的存儲結(jié)構(gòu)D:數(shù)據(jù)元素之間的關(guān)系

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

算法指的是（）

A:解決問題的計(jì)算方法B:排序算法C:解決問題的有限運(yùn)算序列

D:計(jì)算機(jī)程序

答案:解決問題的有限運(yùn)算序列

在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的數(shù)據(jù)結(jié)構(gòu)是（）

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

C:存儲結(jié)構(gòu)D:邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

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

算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（）。

A:正確性B:高效性C:可讀性D:健壯性

答案:正確性

已知某算法的執(zhí)行時(shí)間為(n+n2)log2(n+2)，n為問題規(guī)模，則該算法的時(shí)間復(fù)雜度是（

）。

A:O(nlogn)B:O((n+n^2)logn)C:O(n^2logn)D:O(n^2)

答案:O(n^2logn)

下面算法將一維數(shù)組a中的數(shù)據(jù)逆序存放到原數(shù)組中，空間復(fù)雜度為（）。for(i=0;i<n;i++)

b[i]

=

a[n-i-1];for(i=0;i<n;i++)

a[i]

=

b[i];

A:O(n)B:O(n2)

C:O(1)

D:O(logn)

答案:O(n)

第二章測試

鏈表不具備的特點(diǎn)是（

）。

A:可隨機(jī)訪問任意一個(gè)結(jié)點(diǎn)

B:所需空間與其長度成正比

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

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

答案:可隨機(jī)訪問任意一個(gè)結(jié)點(diǎn)

線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎尽?/p>

A:對B:錯(cuò)

答案:錯(cuò)

順序存儲結(jié)構(gòu)的缺點(diǎn)是不便于修改,插入和刪除需要移動(dòng)很多結(jié)點(diǎn)。

A:對B:錯(cuò)

答案:對

在設(shè)頭、尾指針的單鏈表中,與長度n有關(guān)的操作是(

)。

A:刪除第一個(gè)結(jié)點(diǎn)B:在p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C:刪除最后一個(gè)結(jié)點(diǎn)D:在第一個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)

答案:刪除最后一個(gè)結(jié)點(diǎn)

設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B間插入結(jié)點(diǎn)X的操作序列為(

)。

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

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

答案:q->next=s;

s->next=p;

對于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為(

)。

A:用頭指針表示的循環(huán)單鏈表B:用尾指針表示的循環(huán)單鏈表C:順序表D:單鏈表

答案:用尾指針表示的循環(huán)單鏈表

在一個(gè)單鏈表中,若p所指節(jié)點(diǎn)不是最后節(jié)點(diǎn),在p之后插入s所指節(jié)點(diǎn),則執(zhí)行(

)。

A:s->link=p;p->link=s;B:p->link=s;s->link=p;C:s->link=p->link;p->link=s;D:s->link=p->link;p=s;

答案:s->link=p->link;p->link=s;

在雙向鏈表存儲結(jié)構(gòu)中,刪除p所指的結(jié)點(diǎn)時(shí)須修改指針(

)。

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

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

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

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

p->next->prior=p;

答案:p->next->prior=p->prior;

p->prior->next=p->next;

若事先不知道線性表的長度,則處理線性表時(shí)較好的存儲結(jié)構(gòu)是(

)。

A:順序表B:單鏈表C:靜態(tài)鏈表D:B和C

答案:單鏈表

向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保存,原來順序不變,平均要移動(dòng)(

)個(gè)元素。

A:63.5B:7C:63D:8

答案:63.5

某線性表采用順序存儲結(jié)構(gòu),每個(gè)元素占4個(gè)存儲單元,首地址為100,則第12個(gè)元素的存儲地址為(

)。

A:148B:147C:145D:144

答案:144

在一個(gè)以

h

為頭的單循環(huán)鏈表中,p

指針指向鏈尾的條件是(

)。

A:p->next->next

==

hB:p->data

==

-1C:p->next

==

NULLD:p->next

==

h

答案:p->next

==

h

在表頭指針為head

且表長大于1的單向循環(huán)鏈表中,指針p

指向表中的某個(gè)結(jié)點(diǎn),若p->next->next=head,則(

)。

A:p指向頭結(jié)點(diǎn)B:*p的直接后繼是尾結(jié)點(diǎn)C:p指向尾結(jié)點(diǎn)D:*p的直接后繼是頭結(jié)點(diǎn)

答案:*p的直接后繼是尾結(jié)點(diǎn)

線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲單元的地址(

)。

A:連續(xù)不連續(xù)都可以B:部分地址必須是連續(xù)的C:必須是連續(xù)的D:一定是不連續(xù)的

答案:連續(xù)不連續(xù)都可以

在單鏈表中,指針p指向元素為x的結(jié)點(diǎn),實(shí)現(xiàn)“刪除x的后繼”的語句是(

)。

A:p=p->next;B:p->next=p;C:p=p->next->next;D:p->next=p->next->next;

答案:p->next=p->next->next;

可以用帶表頭結(jié)點(diǎn)的鏈表表示線性表,也可以用不帶表頭結(jié)點(diǎn)的鏈表表示線性表,前者最主要的好處是(

)。

A:節(jié)省存儲空間B:可以加快對表的遍歷C:可以提高存取元素的速度D:使空表和非空表的處理統(tǒng)一

答案:使空表和非空表的處理統(tǒng)一

與單鏈表相比,雙向鏈表的優(yōu)點(diǎn)之一是(

)。

A:順序訪問相鄰結(jié)點(diǎn)更加靈活B:插入、刪除操作更加簡單C:可以隨機(jī)訪問D:可以省略表頭指針或表尾指針

答案:順序訪問相鄰結(jié)點(diǎn)更加靈活

如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū),最節(jié)省時(shí)間的存儲方式(

)。

A:單鏈表B:單循環(huán)鏈表C:順序表D:雙向鏈表

答案:順序表

線性鏈表不具有的特點(diǎn)是（

）。

A:插入與刪除時(shí)不必移動(dòng)元素B:所需空間與線性表長度成正比C:隨機(jī)訪問D:不必事先估計(jì)所需存儲空間大小

答案:隨機(jī)訪問

對順序存儲的線性表,設(shè)其長度為n,在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的(

)個(gè)元素。

A:nB:n/2C:(n-1)/2D:(n+1)/2

答案:n/2

鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí),在鏈表中比在順序存儲結(jié)構(gòu)中效率高。

A:錯(cuò)B:對

答案:對

在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中,若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn),則需要相繼修改(

)個(gè)指針域的值。

A:3B:5C:4D:2

答案:4

具有線性關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有a<b的關(guān)系。

A:錯(cuò)B:對

答案:錯(cuò)

第三章測試

設(shè)abcdef以所給次序進(jìn)棧，若在進(jìn)棧操作時(shí)允許退棧，則下列得不到的序列為（）

A:cabdefB:dcefba

C:fedcba

D:bcafed

答案:cabdef

若已知一個(gè)棧的進(jìn)棧序列是1，2，3……n，其輸出序列是p1，p2，p3，pn，

若p1=3，則p2為（）

A:一定是2B:可能是1

C:一定是1D:可能是2

答案:可能是2

假定循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)滿的條件為（）。

A:front==0

B:(rear＋1)modMAXSIZE==frontC:front==rearD:front+1==rear

答案:(rear＋1)modMAXSIZE==front

隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。

A:對B:錯(cuò)

答案:對

循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是(

)。

A:rear-frontB:(rear-front+m)%mC:rear-front-1

D:rear-front+1

答案:(rear-front+m)%m

不論棧是用數(shù)組實(shí)現(xiàn)，還是用鏈表實(shí)現(xiàn)，入棧和出棧的時(shí)間復(fù)雜度均為O(n)。

A:錯(cuò)B:對

答案:錯(cuò)

若棧采用順序存儲方式存儲，兩棧共享空間A[1..m]，top[i]代表第i個(gè)棧（i=1,

2）的棧頂，棧1的底在A[1]，棧2的底在A[m]，則棧滿的條件是（）。

A:top[1]+top[2]=m

B:

top[1]+1=top[2]

C:top[1]=top[2]

D:|top[2]-top[1]|=0

答案:

top[1]+1=top[2]

輸入序列為ABC，若出棧的順序?yàn)镃BA時(shí)，經(jīng)過的棧操作為（

）。

A:push,pop,push,push,pop,popB:push,pop,push,pop,push,pop

C:push,push,pop,pop,push,popD:push,push,push,pop,pop,pop

答案:push,push,push,pop,pop,pop

鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（）。

A:刪除操作更方便B:

插入操作更方便

C:會出現(xiàn)棧空的情況

D:通常不會出現(xiàn)棧滿的情況

答案:通常不會出現(xiàn)棧滿的情況

設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A:棧B:線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)C:線性表的順序存儲結(jié)構(gòu)

D:隊(duì)列

答案:棧

某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但只允許在一端進(jìn)行出隊(duì)操作，若有元素a,b,c,d,e依次入隊(duì)后再進(jìn)行出隊(duì)操作，則不可能得到的出隊(duì)序列是（）。

A:e,c,b,a,dB:b,a,c,d,eC:d,b,a,c,eD:d,b,c,a,e

答案:d,b,c,a,e

有如下遞歸算法：int

fact(int

n){//n大于等于0

if(n<=0)

return

1;

else

return

n*fact(n-1);}則計(jì)算fact(n)需調(diào)用該函數(shù)的次數(shù)是（）。

A:n+1B:n-1C:n+2D:n

答案:n+1

設(shè)有一個(gè)遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（

）。

A:n+2

B:n+1C:nD:n-1

答案:n+1

（

）的一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語言中實(shí)現(xiàn)遞歸。

A:數(shù)組

B:隊(duì)列

C:順序表

D:棧

答案:棧

通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。

A:錯(cuò)B:對

答案:錯(cuò)

棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?/p>

A:錯(cuò)B:對

答案:對

若已知一隊(duì)列用單向鏈表表示，該單向鏈表的當(dāng)前狀態(tài)（含3個(gè)對象）是：1->2->3，其中x->y表示x的下一節(jié)點(diǎn)是y。此時(shí)，如果將對象4入隊(duì)，然后隊(duì)列頭的對象出隊(duì)，則單向鏈表的狀態(tài)是：（）。

A:4->1->2B:2->3->4C:1->2->3D:狀態(tài)不唯一

答案:2->3->4

第四章測試

設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第1個(gè)元素，其存儲地址為1，每個(gè)元素占用1個(gè)地址空間，則a85的地址為（）。

A:40B:33C:13D:18

答案:33

對于以行為主序的存儲結(jié)構(gòu)來說．在數(shù)組A[c1..d1,c2..d2]中，c1和d1分別為數(shù)組A的第一維下標(biāo)的下、上界，c2和d2分別為第二維下標(biāo)的下、上界．每個(gè)數(shù)據(jù)元素占k個(gè)存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由（

）確定。

A:Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]×kB:

Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kC:Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kD:

Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]×k

答案:Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×k

A[N，N]是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組T[N（N+1）/2]中，則對任一上三角元素a[i][j]對應(yīng)T[k]的下標(biāo)k是

A:i（i-1）/2+j

B:

i（j-i）/2+1

C:

j（j-1）/2+i

D:

j（i-1）/2+1

答案:

j（j-1）/2+i

對矩陣壓縮存儲是為了（）

A:方便運(yùn)算B:提高運(yùn)算速度C:減少存儲空間

D:方便存儲

答案:減少存儲空間

操作取廣義表的表尾就是將廣義表中最后一個(gè)元素值返回。

A:錯(cuò)B:對

答案:錯(cuò)

若廣義表S的表頭是空表，則S是一個(gè)空表。

A:錯(cuò)B:對

答案:錯(cuò)

下面說法不正確的是（）。

A:廣義表難以用順序存儲結(jié)構(gòu)實(shí)現(xiàn)B:廣義表可以看作是一個(gè)多層次結(jié)構(gòu)C:廣義表的表尾總是一個(gè)廣義表D:廣義表的表頭總是一個(gè)廣義表

答案:廣義表的表頭總是一個(gè)廣義表

有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式以行序?yàn)橹餍虼鎯?，A[1][1]為第一元素，其存儲地址為1，每個(gè)元素占一個(gè)地址空間，則A[7][5]和A[5][6]的存儲地址分別為（）

A:40

32B:26

25C:2520D:26

22

答案:26

25

GetHead

(

(p，h，w)

)=

A:(h,w)B:()C:pD:(p)

答案:p

已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項(xiàng)t的運(yùn)算是（

）。

A:head（tail（head（tail（L））））B:tail（head（head（tail（L））））C:head（tail(head（tail（tail（L）））)）

D:head（tail（tail（L）））

答案:head（tail(head（tail（tail（L）））)）

第五章測試

二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以

。

A:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲

B:它不能用順序存儲結(jié)構(gòu)存儲

C:它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲

D:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用

答案:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲

二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。

A:錯(cuò)B:對

答案:錯(cuò)

二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。

A:對B:錯(cuò)

答案:錯(cuò)

在只有度為0和度為2的二叉樹中

,設(shè)度為0的結(jié)點(diǎn)有n0個(gè),度為2的結(jié)點(diǎn)有n2個(gè),則有n0=n2+1。

A:對B:錯(cuò)

答案:對

樹中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)減1。

A:錯(cuò)B:對

答案:對

設(shè)森林F中有4棵樹,第1、2、3、4棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3、n4,當(dāng)把森林F轉(zhuǎn)換成一棵二叉樹后,其根結(jié)點(diǎn)的左子樹中有n1個(gè)結(jié)點(diǎn)。

A:錯(cuò)B:對

答案:錯(cuò)

設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m,則結(jié)點(diǎn)總數(shù)為2m-1。

A:錯(cuò)B:對

答案:對

某二叉樹中序序列為BDAECF,后序序列為DBEFCA,則二叉樹對應(yīng)的森林包括(

)棵樹。

A:1B:2C:4D:3

答案:3

若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn),5個(gè)度為1的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)的個(gè)數(shù)是(

)。

A:11B:不能確定C:15D:9

答案:11

任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序(

)。

A:不發(fā)生改變B:不能確定C:發(fā)生改變D:其余選項(xiàng)都不對

答案:不發(fā)生改變

設(shè)某棵二叉樹的高度為9,則該二叉樹上葉子結(jié)點(diǎn)最多有(

)。

A:256B:511C:512D:1023

答案:256

若完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為100,則第60個(gè)結(jié)點(diǎn)的度為(

)。

A:0B:不確定C:2D:1

答案:0

樹的基本遍歷策略分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹,其中結(jié)論(

)是正確的。

A:樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同B:樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C:樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同D:其余選項(xiàng)都不對

答案:樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同

某二叉樹的先序和后序遍歷序列正好相反,則該二叉樹一定是(

)。

A:深度等于其結(jié)點(diǎn)數(shù)B:二叉排序樹C:完全二叉樹D:空或只有一個(gè)結(jié)點(diǎn)

答案:深度等于其結(jié)點(diǎn)數(shù)

一棵二叉樹的高度為h,所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?,則這棵二叉樹最少有(

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

A:2hB:2h-1C:2h+1D:h+1

答案:2h-1

如果一棵二叉樹中所有結(jié)點(diǎn)的值都大于其左子樹中的所有結(jié)點(diǎn)的值,且小于其右子樹中所有結(jié)點(diǎn)的值,現(xiàn)欲得到各個(gè)結(jié)點(diǎn)的遞增序列,采用的方法是(

)。

A:后序遍歷B:前序遍歷C:中序遍歷D:層次遍歷

答案:中序遍歷

設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷中

,n在m前的條件是(

)。

A:n在m的左子樹上B:n

在m右子樹上C:n是m的祖先D:n是m的子孫

答案:n在m的左子樹上

深度為5的二叉樹至多有(

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

A:16B:31C:10D:32

答案:31

由權(quán)值分別為

11、

8、

6、

2

、

5

的葉子結(jié)點(diǎn)生成一棵哈夫曼樹,它的帶權(quán)路徑長度為(

)。

A:71B:48C:53D:24

答案:71

如果一個(gè)完全二叉樹最底下一層為第六層(根為第一層)且該層共有8個(gè)葉結(jié)點(diǎn),那么該完全二叉樹共有多少個(gè)結(jié)點(diǎn)?(

)

A:63B:39

C:71D:31

答案:39

某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF,則后序遍歷序列為（

)。

A:BDGCEFHAB:GDBECFHAC:BDGAECHFD:GDBEHFCA

答案:GDBEHFCA

一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為(

)。

A:11至1025之間B:10至1024之間C:11D:10

答案:11至1025之間

設(shè)森林中有三棵樹,第一、二、三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為n1、n2、n3,那么將森林轉(zhuǎn)換成二叉樹后,其根結(jié)點(diǎn)的右子樹上有(

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

A:n1B:n2+n3C:其他情況D:n1-1

答案:n2+n3

第六章測試

任何一個(gè)無向連通圖的最小生成樹

A:可能不存在

B:只有一棵C:一定有多棵

D:一棵或多棵

答案:一棵或多棵

用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用

來實(shí)現(xiàn)算法的。

A:樹B:棧

C:圖D:隊(duì)列

答案:隊(duì)列

在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的

倍。

A:1/2B:4C:1D:2

答案:1

已知有向圖G=(V,E)，其中V={V1，V2，V3，V4，V5，V6，V7},E={<V1，V2>，<V1，V3>,<V1，V4>,<V2，V5>,<V3，V5>,<V3，V6>,<V4，V6>,<V5，V7>,<V6，V7>}，G的拓?fù)溆行蛐蛄惺牵ǎ?/p>

A:

V1，V3，V4，V6，V2，V5，V7B:V1，V2，V5，V3，V4，V6，V7

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

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

答案:

V1，V3，V4，V6，V2，V5，V7

對于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(gè)（）。

A:由n-1條權(quán)值之和最小的邊構(gòu)成的子圖

B:由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖

C:由n-1條權(quán)值之和最小的邊構(gòu)成的連通子圖

D:

由n-1條權(quán)值最小的邊構(gòu)成的子圖

答案:由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖

用鄰接矩陣存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間與圖中結(jié)點(diǎn)的個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。

A:錯(cuò)B:對

答案:對

如果有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判颍瑒t說明該有向圖存在回路。

A:對B:錯(cuò)

答案:錯(cuò)

一個(gè)非空圖可以沒有邊，但不能沒有頂點(diǎn)。

A:錯(cuò)B:對

答案:對

有n-1條邊的圖肯定都是生成樹。

A:對B:錯(cuò)

答案:錯(cuò)

n個(gè)頂點(diǎn)的完全有向圖含有邊的數(shù)目是（）。

A:n(n+1)B:n/2C:n(n-1)D:n*n

答案:n(n-1)

在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點(diǎn)v在鏈表中出現(xiàn)的次數(shù)是（）。

A:依附于頂點(diǎn)v的邊數(shù)B:頂點(diǎn)v的入度C:頂點(diǎn)v的度D:頂點(diǎn)v的出度

答案:頂點(diǎn)v的入度

對一個(gè)無向圖進(jìn)行深度優(yōu)先搜索時(shí)，得到的搜索序列是唯一的。

A:對B:錯(cuò)

答案:錯(cuò)

G是一個(gè)非連通無向圖，有28條邊，則G至少有（）個(gè)頂點(diǎn)。

A:9B:7C:8D:10

答案:9

對于一個(gè)有n個(gè)頂點(diǎn)，e條邊的有向圖，采用鄰接表存儲，對其進(jìn)行廣度優(yōu)先搜索，算法的時(shí)間復(fù)雜度是（）。

A:O(n*e)B:O(n)C:O(e)D:O(n+e)

答案:O(n+e)

下列關(guān)于無向連通圖的敘述中，正確的是（）。所有頂點(diǎn)的度數(shù)之和是偶數(shù)邊數(shù)大于頂點(diǎn)數(shù)減1至少有一個(gè)頂點(diǎn)的度是1

A:a和cB:只有aC:只有cD:a和b

答案:只有a

在TopSort（拓?fù)渑判颍┖瘮?shù)中，如果外循環(huán)還沒結(jié)束，就已經(jīng)找不到“未輸出的入度為0的頂點(diǎn)”，則說明

A:

圖中可能有回路

B:

圖中必定存在回路

C:

算法錯(cuò)誤D:

該圖有頂點(diǎn)不連通

答案:

圖中必定存在回路

使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加入到最小生成樹中的邊依次是（）

A:

(a,e),(b,e),(c,e),(b,d),(b,f)

B:

(b,f),(b,d),(b,e),(a,e),(c,e)

C:

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

(b,f),(b,d),(a,e),(c,e),(b,e)

答案:

(b,f),(b,d),(a,e),(c,e),(b,e)

下列選項(xiàng)中，不是如下有向圖的拓?fù)湫蛄械氖?/p>

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

5,2,1,6,3,4

C:

1,5,2,3,6,4

D:

5,1,2,3,6,4

答案:

5,2,1,6,3,4

如果無向完全圖G中有78條邊，則G的生成樹有（

）條邊。

A:12B:32C:77D:14

答案:12

在一個(gè)有權(quán)無向圖中，如果頂點(diǎn)b到頂點(diǎn)a的最短路徑長度是10，頂點(diǎn)c與頂點(diǎn)b之間存在一條長度為3的邊。那么下列說法中有幾句是正確的？I.

c與a的最短路徑長度就是13II.

c與a的最短路徑長度就是7III.

c與a的最短路徑長度不超過13IV.

c與a的最短路徑不小于7

A:3句B:2句C:1句D:4句

答案:2句

第七章測試

有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)用二分法查找值82的結(jié)點(diǎn)時(shí)，（）次比較后查找成功。

A:2B:1

C:8D:4

答案:4

若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個(gè)元素第一次計(jì)算的哈希地址為d，則下一次的哈希地址為()。

A:dB:(d+1)%mC:(d+1)/mD:d+1

答案:(d+1)%m

若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計(jì)算哈希地址，則元素64的哈希地址為()。

A:8B:13C:4D:12

答案:12

從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜度為()。

A:O(n)B:O(1)C:O(logn)D:O(n^2)

答案:O(n)

對具有n個(gè)元素的有序表采用折半查找，則算法的時(shí)間復(fù)雜度為()。

A:O(1)B:O(n)C:O(n^2)D:O(logn)

答案:O(logn)

對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個(gè)元素的比較次數(shù)為()。

A:3B:6C:5D:4

答案:4

二叉排序樹的左右子樹都是二叉排序樹。

A:錯(cuò)B:對

答案:對

若查找每個(gè)元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為()。

A:n+1B:(n+1)/2C:nD:(n-1)/2

答案:(n+1)/2

具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長度是（）。

A:3.1B:2.5C:5D:4

答案:3.1

下面關(guān)于哈希查找的說法正確的是（）。

A:除留余數(shù)法是所有哈希函數(shù)中最好的B:若需要在一個(gè)哈希表中刪去一個(gè)元素，不管何種方法解決沖突都只要將該元素刪去即可C:哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小D:不存在特別好和特別壞的哈希函數(shù)，要視情況而定

答案:不存在特別好和特別壞的哈希函數(shù)，要視情況而定

將10個(gè)元素散列到長度為100000的哈希表中，則（）產(chǎn)生沖突。

A:仍可能會B:一定不會C:一定會

答案:仍可能會

完全二叉樹肯定是平衡二叉樹。

A:對B:錯(cuò)

答案:錯(cuò)

查找n個(gè)元素的有序表時(shí)，最有效的查找方法是（）。

A:順序查找B:折半查找C:二叉排序樹D:分塊查找

答案:折半查找

當(dāng)在一個(gè)有序順序存儲表中查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可以用順序查找，但前者比后者的查找速度（）。

A:一定快B:取決于表遞增還是遞減C:大部分情況下快D:一定慢

答案:大部分情況下快

有n個(gè)數(shù)據(jù)存在在一維數(shù)組a中，進(jìn)行順序查找時(shí)，這n個(gè)數(shù)據(jù)的排列有序或無序其平均查找長度不同。

A:對B:錯(cuò)

答案:錯(cuò)

n個(gè)結(jié)點(diǎn)的二叉排序樹有多種形態(tài)，其中高度最小的二叉排序樹是最佳的。

A:錯(cuò)B:對

答案:對

假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這k個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行（）次探測。

A:kB:k(k+1)/2C:k+1D:k-1

答案:k(k+1)/2

對包含N個(gè)元素的哈希表進(jìn)行查找，平均查找長度為

A:不確定B:O(N)C:O(1)D:O(logN)

答案:不確定

含有25個(gè)結(jié)點(diǎn)的二叉排序樹上，查找關(guān)鍵字為35的結(jié)點(diǎn)，則依次比較的關(guān)鍵字序列有可能是

A:18,36,28,46,35B:28,36,18,46,35C:46,36,18,28,35D:46,28,18,36,35

答案:46,36,18,28,35

第八章測試

如果對n個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的進(jìn)程中，為尋找最小值元素所需要的時(shí)間復(fù)雜度為（）

A:O(1)B:O(n)C:O(n2)

D:O(logn)

答案:O(n)

下列排序算法中，其中（）是穩(wěn)定的。

A:快速排序，堆排序B:簡單選擇排序，歸并排序

C:

歸并排序，冒泡排序D:快速排序，冒泡排序

答案:

歸并排序，冒泡排序

下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。

A:[27，38，18]49[93，73]

B:[93，38，18]49[27，73]C:[27，38，73]49[93，18]

D:[27，38，93]49[18，73]

答案:[27，38，18]49[93，73]

(15，9，7，8，20，-1，4)進(jìn)行排序，第一趟排序后的序列變?yōu)?/p>