數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-山東航空學(xué)院）知到智慧樹章節(jié)測試課后答案2024年秋山東航空學(xué)院

數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-山東航空學(xué)院）知到智慧樹章節(jié)測試課后答案2024年秋山東航空學(xué)院第一章單元測試

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

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

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

答案:數(shù)據(jù)的存儲結(jié)構(gòu)算法指的是（）

A:排序算法B:計算機(jī)程序

C:解決問題的計算方法D:解決問題的有限運(yùn)算序列

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

在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(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í)行時間為(n+n2)log2(n+2)，n為問題規(guī)模，則該算法的時間復(fù)雜度是（

）。

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

答案: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(logn)B:O(n2)

C:O(1)

D:O(n)

答案:O(n)

第二章單元測試

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

）。

A:插入和刪除不需要移動任何元素

B:不必事先估計存儲空間

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

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

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

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

A:對B:錯

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

A:對B:錯

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

)。

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

答案:刪除最后一個結(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:q->next=s;

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

答案:q->next=s;

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

)。

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

答案:用尾指針表示的循環(huán)單鏈表在一個單鏈表中,若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=s;D:s->link=p->link;p->link=s;

答案:s->link=p->link;p->link=s;在雙向鏈表存儲結(jié)構(gòu)中,刪除p所指的結(jié)點(diǎn)時須修改指針(

)。

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

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

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

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

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

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

p->prior->next=p->next;若事先不知道線性表的長度,則處理線性表時較好的存儲結(jié)構(gòu)是(

)。

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

答案:單鏈表向一個有127個元素的順序表中插入一個新元素并保存,原來順序不變,平均要移動(

)個元素。

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

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

)。

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

答案:144在一個以

h

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

指針指向鏈尾的條件是(

)。

A:p->next

==

NULLB:p->next->next

==

hC:p->data

==

-1D:p->next

==

h

答案:p->next

==

h在表頭指針為head

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

指向表中的某個結(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)時,要求內(nèi)存中可用存儲單元的地址(

)。

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

答案:連續(xù)不連續(xù)都可以在單鏈表中,指針p指向元素為x的結(jié)點(diǎn),實(shí)現(xiàn)“刪除x的后繼”的語句是(

)。

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

答案:p->next=p->next->next;可以用帶表頭結(jié)點(diǎn)的鏈表表示線性表,也可以用不帶表頭結(jié)點(diǎn)的鏈表表示線性表,前者最主要的好處是(

)。

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

答案:使空表和非空表的處理統(tǒng)一與單鏈表相比,雙向鏈表的優(yōu)點(diǎn)之一是(

)。

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

答案:順序訪問相鄰結(jié)點(diǎn)更加靈活如果最常用的操作是取第i個結(jié)點(diǎn)及其前驅(qū),最節(jié)省時間的存儲方式(

)。

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

答案:順序表線性鏈表不具有的特點(diǎn)是（

）。

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

答案:隨機(jī)訪問對順序存儲的線性表,設(shè)其長度為n,在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的(

)個元素。

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

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

A:對B:錯

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

)個指針域的值。

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

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

A:錯B:對

答案:錯

第三章單元測試

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

A:cabdefB:dcefba

C:fedcba

D:bcafed

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

若p1=3，則p2為（）

A:可能是2

B:可能是1

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

答案:可能是2

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

A:front+1==rear

B:front==rearC:front==0

D:(rear＋1)modMAXSIZE==front

答案:(rear＋1)modMAXSIZE==front隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。

A:對B:錯

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

)。

A:(rear-front+m)%mB:rear-front+1

C:rear-frontD:rear-front-1

答案:(rear-front+m)%m不論棧是用數(shù)組實(shí)現(xiàn)，還是用鏈表實(shí)現(xiàn)，入棧和出棧的時間復(fù)雜度均為O(n)。

A:對B:錯

答案:錯若棧采用順序存儲方式存儲，兩棧共享空間A[1..m]，top[i]代表第i個棧（i=1,

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

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

B:top[1]=top[2]

C:

top[1]+1=top[2]

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

答案:

top[1]+1=top[2]

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

）。

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

D:push,push,pop,pop,push,pop

答案:push,push,push,pop,pop,pop鏈棧與順序棧相比，有一個比較明顯的優(yōu)點(diǎn)是（）。

A:

插入操作更方便

B:會出現(xiàn)?？盏那闆r

C:刪除操作更方便D:通常不會出現(xiàn)棧滿的情況

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

A:棧B:線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)C:隊(duì)列

D:線性表的順序存儲結(jié)構(gòu)

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

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

答案:d,b,c,a,e有如下遞歸算法：int

fact(int

n){//n大于等于0

if(n<=0)

return

1;

else

return

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

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

答案:n+1設(shè)有一個遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

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

）。

A:n-1

B:n+2

C:n+1D:n

答案:n+1（

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

A:順序表

B:棧C:隊(duì)列

D:數(shù)組

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

A:錯B:對

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

A:對B:錯

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

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

答案:2->3->4

第四章單元測試

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

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

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

）確定。

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

Loc[i,j]=A[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)]×kA[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（i-1）/2+1D:

j（j-1）/2+i

答案:

j（j-1）/2+i

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

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

D:提高運(yùn)算速度

答案:減少存儲空間

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

A:對B:錯

答案:錯若廣義表S的表頭是空表，則S是一個空表。

A:對B:錯

答案:錯下面說法不正確的是（）。

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

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

A:26

25B:40

32C:2520D:26

22

答案:26

25GetHead

(

(p，h，w)

)=

A:pB:(p)C:()D:(h,w)

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

）。

A:head（tail（head（tail（L））））B:head（tail（tail（L）））C:tail（head（head（tail（L））））D:head（tail(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:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用

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

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

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

A:錯B:對

答案:錯二叉樹中每個結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。

A:錯B:對

答案:錯在只有度為0和度為2的二叉樹中

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

A:對B:錯

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

A:錯B:對

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

A:錯B:對

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

A:對B:錯

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

)棵樹。

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

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

)。

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

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

)。

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

答案:不發(fā)生改變設(shè)某棵二叉樹的高度為9,則該二叉樹上葉子結(jié)點(diǎn)最多有(

)。

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

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

)。

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

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

)是正確的。

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

答案:樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同某二叉樹的先序和后序遍歷序列正好相反,則該二叉樹一定是(

)。

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

答案:深度等于其結(jié)點(diǎn)數(shù)一棵二叉樹的高度為h,所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?,則這棵二叉樹最少有(

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

A:2h+1B:2hC:2h-1D:h+1

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

)。

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

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

,n在m前的條件是(

)。

A:n在m的左子樹上B:n是m的子孫C:n是m的祖先D:n

在m右子樹上

答案:n在m的左子樹上深度為5的二叉樹至多有(

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

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

答案:31由權(quán)值分別為

11、

8、

6、

2

、

5

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

)。

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

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

)

A:31B:71C:39

D:63

答案:39

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

)。

A:BDGCEFHAB:GDBEHFCAC:GDBECFHAD:BDGAECHF

答案:GDBEHFCA一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為(

)。

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

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

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

A:n1B:n1-1C:n2+n3D:其他情況

答案:n2+n3

第六章單元測試

任何一個無向連通圖的最小生成樹

A:一定有多棵

B:可能不存在

C:只有一棵D:一棵或多棵

答案:一棵或多棵用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用

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

A:樹B:棧

C:隊(duì)列D:圖

答案:隊(duì)列在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的

倍。

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

答案: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，V5，V2，V6，V7

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

C:

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

答案:

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

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

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

B:

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

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

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

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

A:錯B:對

答案:對如果有向圖的所有頂點(diǎn)可以構(gòu)成一個拓?fù)渑判?，則說明該有向圖存在回路。

A:錯B:對

答案:錯一個非空圖可以沒有邊，但不能沒有頂點(diǎn)。

A:錯B:對

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

A:錯B:對

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

A:n/2B:n(n+1)C: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的入度對一個無向圖進(jìn)行深度優(yōu)先搜索時，得到的搜索序列是唯一的。

A:對B:錯

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

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

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

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

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

A:只有aB:只有cC:a和cD:a和b

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

A:

圖中可能有回路

B:

圖中必定存在回路

C:

算法錯誤D:

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

答案:

圖中必定存在回路

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

A:

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

B:

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

C:

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

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

答案:

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

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

A:

5,1,2,3,6,4

B:

1,5,2,3,6,4

C:

5,2,1,6,3,4

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

答案:

5,2,1,6,3,4

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

）條邊。

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

答案:12在一個有權(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:4句C:1句D:2句

答案:2句

第七章單元測試

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

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

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

A:(d+1)/mB:d+1

C:(d+1)%mD:d

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

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

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

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

答案:O(n)對具有n個元素的有序表采用折半查找，則算法的時間復(fù)雜度為()。

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

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

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

答案:4二叉排序樹的左右子樹都是二叉排序樹。

A:錯B:對

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

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

答案:(n+1)/2具有12個關(guān)鍵字的有序表，折半查找的平均查找長度是（）。

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

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

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

答案:不存在特別好和特別壞的哈希函數(shù)，要視情況而定將10個元素散列到長度為100000的哈希表中，則（）產(chǎn)生沖突。

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

答案:仍可能會完全二叉樹肯定是平衡二叉樹。

A:對B:錯

答案:錯查找n個元素的有序表時，最有效的查找方法是（）。

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

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

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

答案:大部分情況下快有n個數(shù)據(jù)存在在一維數(shù)組a中，進(jìn)行順序查找時，這n個數(shù)據(jù)的排列有序或無序其平均查找長度不同。

A:錯B:對

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

A:錯B:對

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

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

答案:k(k+1)/2對包含N個元素的哈希表進(jìn)行查找，平均查找長度為

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

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

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

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

第八章單元測試

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

A:O(n)B:O(logn)

C:O(n2)

D:O(1)

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

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

C:快速排序，冒泡排序

D:

歸并排序，冒泡排序

答案:

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

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

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

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

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

(15，9，7，8，20，-1，4)進(jìn)行排序，第一趟