青島大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題

數(shù)據(jù)結(jié)構(gòu)

單選1.

中綴表達(dá)式的后綴“2”(3+4)7”表達(dá)式是()其中#表示一個(gè)數(shù)值的結(jié)束。

A.2#3#4#1#'+-

B.2#3#4#+-1#-

C.2#3#4#"+1#-

D.-+~2#3#4#l#

［答案］B

單選2.

一個(gè)含有n個(gè)頂點(diǎn)的無向連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是()。

A.對(duì)稱矩陣

B.非對(duì)稱矩陣

C.稀疏矩陣

D.稠密矩陣

［答案］A

判斷3.

堆排序是一種穩(wěn)定的排序算法。

A.正確

B.錯(cuò)誤

［答案］B

單選4.

如果對(duì)含有n(N>l)個(gè)元素的線性表的運(yùn)算只有4種:刪除第一個(gè)元素；刪除最后一個(gè)元素；

在第一個(gè)元素前面插入新元素；在最后一個(gè)元素后面插入新元素。則最好使用以下哪種存儲(chǔ)

結(jié)構(gòu)，并簡(jiǎn)要說明理由。

(1)只有尾節(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單鏈表

(2)只有尾節(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表

(3)只有頭結(jié)點(diǎn)指針沒有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表

(4)既有頭節(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表

［答案］(3)理由：實(shí)現(xiàn)上述4種運(yùn)算的時(shí)間復(fù)雜度均為0(1)

多選5.

計(jì)算機(jī)算法必須具備()等特性。

A.可行性，確定性

B.可行性，可移植性

C.輸入，輸出

D.有窮性

E.易讀性

F.穩(wěn)定性

［答案］ACD

判斷6

哈希查找法中解決沖突問題的常用方法是除留余數(shù)法。

A.正確

B.錯(cuò)誤

［答案］B

單選7.

一棵含有n個(gè)結(jié)點(diǎn)的線索二叉樹中，其線索個(gè)數(shù)為()。

A.n

B.n-1

C.n+1

D.n

［答案］C

單選8

設(shè)有100個(gè)元素的有序表，用折半查找時(shí)，不成功時(shí)最大的比較次數(shù)是()。

A.25

B.50

C.10

D.7

［答案］D

判斷9

用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小值與圖中的

頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。

A.正確

B.錯(cuò)誤

［答案］A

單選10

一顆深度為h(h>=l)的完全二叉樹至少有()個(gè)節(jié)點(diǎn)。

A.2"(h-1)

B.2-h

C.2*h+l

D.2"(h-1)+1

[答案]B

問答11

有一顆二叉樹排序樹按先序遍歷得到的序列為(12,5,2,8,6,10,16,15,18,20)。

回答以下問題。

(1)畫出該二叉樹排列數(shù)。

(2)給出該二叉排序樹的中序遍歷序列。

(3)求在等概率下的查找成功和不成功情況下的平均查找長(zhǎng)度。

[答案](1)

(2)(2,5,6,8,10,12,15,16,18,20)

(3)ASL成功=(13+2*2+4*3+3*4)/10=29/10

ASL不成功=(5*3+6*4/11)=39/11

單選12.

若一個(gè)棧采用數(shù)組s[0..n-l]存放其元素，初始時(shí)棧頂指針為n,則以下元素x進(jìn)棧的正確

操作是()。

A.top++;s[top]=x;

B.s[top]=x;top++;

C.top—;S[top]=x;

D.s[top]=x;top一;

[答案]C

判斷13.

使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間。

A.正確

B.錯(cuò)誤

[答案]A

論述題14.

設(shè)A和B是兩個(gè)結(jié)點(diǎn)個(gè)數(shù)分別為m和n的單鏈表(帶頭結(jié)點(diǎn))，其中元素遞增有序。設(shè)計(jì)-

個(gè)盡可能高效的算法求A和B的交集，要求不破壞A、B的結(jié)點(diǎn)，將交集存放在單鏈表C中。

給出你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

［答案］

多選15

以下說法正確的是()。

A.二叉樹的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹。

B.二叉樹的子樹無左右之分。

C.二叉樹只能進(jìn)行鏈?zhǔn)酱鎯?chǔ)。

D.樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支.

［答案］AD

判斷16.

如果有向圖中各個(gè)頂點(diǎn)的度都大于2,則該圖中必有回路。

A.正確

B.錯(cuò)誤

［答案］B

單選17

二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為()。

A.2"K-1

B.2K+1

C.2K-1

D.27K-1)

［答案］D

判斷18.

如果采用如下方法定義一維字符數(shù)組：intmaxSize=30;char*a=newchar［maxSize］;則這種數(shù)

組在程序執(zhí)行過程中不能擴(kuò)充。

A.正確

B.錯(cuò)誤

［答案］B

多選19.

下列屬于算法的重要特征的是()。

A.有窮性

B.確定性

C.可行性

I).輸入和輸出

［答案］ABCD

論述20

單選2L

設(shè)無向連通圖有n個(gè)頂點(diǎn)e條邊，若滿足()則圖中一定有回路。

A.e>=n

B.e<n

C.e=n-l

D.2e>=n

［答案］A

多選22.

依據(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)

［答案］AD

單選23.

數(shù)據(jù)結(jié)構(gòu)是指()。

A.一種數(shù)據(jù)類型

B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

C.一組性質(zhì)相同的數(shù)據(jù)元素的集合

D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

［答案］D

單選24.

以下序列是堆的是()。

A.{75,65,30,15,25,45,20,10}

B.(75,65,45,10,30,25,20,15}

C.{75,45,65,30,15,25,20,10}

D{75,45,65,10,25,30,20,15}

［答案］C

判斷25.

任何一棵二叉樹的葉結(jié)點(diǎn)在三種遍歷中的相對(duì)次序是不變的。

A.正確

B.錯(cuò)誤

[答案]A

單選26.

以下算法的時(shí)間復(fù)雜度為()。

voidfun(intn)

{inti=l;

while(i<=n)

i++；

)

A.0(n)

B.0(Vn)

C.0(nlog2n)

D.0(log2n)

[答案]A

判斷27.

線性表的邏輯順序總是與其物理順序-致。

A.正確

B.錯(cuò)誤

[答案]B

判斷28.

在長(zhǎng)度為n的順序表中，求第i個(gè)元素的直接前驅(qū)算法的時(shí)間復(fù)雜度為0(1)。

A.正確

B.錯(cuò)誤

[答案]A

判斷29.

對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了節(jié)省存儲(chǔ)空間。

A.正確

B.錯(cuò)誤

[答案]A

單選30.

設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),

每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置?腳注(10)表示用10進(jìn)制表示()。

A.688

B.678

C.692

D.696

［答案］c

判斷31.

對(duì)具有n個(gè)結(jié)點(diǎn)的堆進(jìn)行插入一個(gè)元素運(yùn)算的時(shí)間復(fù)雜度為0(n)。

A.正確

B.錯(cuò)誤

［答案］B

單選32.

樹最適合用來表示()。

A.有序數(shù)據(jù)元素

B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)

D.元素之間無聯(lián)系的數(shù)據(jù)

［答案］C

單選33.

在一棵m階B樹中刪除一個(gè)關(guān)鍵字會(huì)引起合并，則該結(jié)點(diǎn)原有()個(gè)關(guān)鍵字。

A.1

B.［m/2］

C.「m/2」-1

D.［m/2］+1

［答案］C

判斷34.

當(dāng)向一個(gè)最小堆插入-一個(gè)具有最小值的元素時(shí)，該元素需要逐層向上調(diào)整，直到被調(diào)整到

堆頂位置為止。

A.正確

B.錯(cuò)誤

［答案］A

判斷35.

對(duì)平衡二叉樹進(jìn)行中根遍歷，可得到結(jié)點(diǎn)的有序排列。

A.正確

B.錯(cuò)誤

［答案］A

單選36.

以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？()

A.隊(duì)列

B.棧

C.線性表

D.二叉樹

［答案］D

多選37

下列說法正確的有()。

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

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

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

D.同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的

個(gè)數(shù)相等

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

F.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體

［答案］BCF

單選38.

對(duì)于AOE網(wǎng)的關(guān)犍路徑，以下敘述()是正確的。

A.任何一個(gè)關(guān)鍵活動(dòng)提前完成，則整個(gè)工程一定會(huì)提前完成

B.完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最短路徑長(zhǎng)度

D.任何一個(gè)活動(dòng)持續(xù)時(shí)間的改變可能會(huì)影響關(guān)鍵路徑的改變

［答案］D

單選39

在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表L中，刪除元素值為x的結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為()。

A.0(n)

B.0(Vn)

C.0(nlog2n)

D.0(n'2)

［答案］A

單選40.

設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列為

()?

A.q=p->next;p->data=q->data;p->next=q->next;free(q);

B.q=p->next;q->data=p->data;p>next=q->next;free(q);

C.q=p->next;q->data=p->data;p->next=q->next;free(q);

D.q=p->next;p->data=q->data;free(q);

［答案］A

多選41.

線性表的特點(diǎn)正確的()

A.存在唯一的一個(gè)被稱作”第一一個(gè)”的數(shù)據(jù)元素。

B.不存在唯一的一一個(gè)被稱作”第一一個(gè)“的數(shù)據(jù)元素。

C.存在唯一的一個(gè)被稱作”最后一個(gè)“的數(shù)據(jù)元素。

D.不存在唯一-的——個(gè)被稱作”最后-個(gè)“的數(shù)據(jù)元素。

［答案］AC

單選42.

下列四種排序中()的空間復(fù)雜度最大。

A.快速排序

B.冒泡排序

C.希爾排序

D.堆

［答案］A

單選43.

用某種排序方法對(duì)數(shù)據(jù)序列

{24,88,21,48,15,27,69,35,20}進(jìn)行遞增排序,元素序列的變化情況如下:

{24,88,21,48,15,27,69,35,20}(2)

{20,15,21,24,48,27,69,35,88}(3)

{15,20,21,24,35,27,48,69,88}(4)

{15,20,21,24,27,35,48,69,88}則所采用的排序方法是0,

A.快速排序

B.簡(jiǎn)單選擇排序

C.直接插入排序

D.歸并排序

［答案］A

判斷44.

在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的后一一個(gè)位置。

A.正確

B.錯(cuò)誤

［答案］B

單選45.

設(shè)環(huán)形隊(duì)列中數(shù)組的下標(biāo)為O~NT,其隊(duì)頭、隊(duì)尾指針分別為front和rear(front指向隊(duì)

列中隊(duì)頭元素的前一一個(gè)位置，rear指向隊(duì)尾元素的位置)，則其元素個(gè)數(shù)為()。

A.rear-front

B.rear-front-1

C.(rear-front)%N+1

D.(rear-front+N)%N

［答案］D

多選46.

下面關(guān)于線性表的敘述正確的是()。

A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間

B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)

D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

［答案］ABC

多選47.

算法設(shè)計(jì)的要求包括()

A.正確性

B.可讀性

C.健壯性

D.確定性

［答案］ABC

問答題48.

有人提出這樣的一種從圖G中頂點(diǎn)u開始構(gòu)造最小生成樹的方法:假設(shè)G=(V,E)是一個(gè)具有

n個(gè)頂點(diǎn)的帶權(quán)連通無向圖，T=(U,TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T

的邊集，則由G構(gòu)造從起始頂點(diǎn)u出發(fā)的最小生成樹T的步驟如下：

(1)初始化U={u}。以u(píng)到其他頂點(diǎn)的所有邊為候選邊。

(2)重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被加入到U中。

從候選邊中挑選權(quán)值最小的邊加入到TE,設(shè)該邊在V-U中的頂點(diǎn)是v,將v加入U(xiǎn)中?？疾?/p>

頂點(diǎn)V,將v與V-U頂點(diǎn)集中的所有邊作為新的候選邊。若此方法求得的T是最小生成樹，

請(qǐng)予以證明。若不能求得最小邊，請(qǐng)舉出反例。

［答案］

答:此方法不能求得最小生成樹。例如，對(duì)于如圖9.37(a)所示的帶權(quán)連通無向圖，按照

上述方法從頂點(diǎn)0開始求得的結(jié)果為圖9.37(b)所示的樹，顯然它不是最小生成樹，正確

的最小生成樹如圖9.37(c)所示。

在有些情況下，上述方法無法求得結(jié)果，例如對(duì)于如圖9.37(d)所示的帶權(quán)連通無向圖，

從頂點(diǎn)0出發(fā)，找到頂點(diǎn)1(邊(0,1)),從頂點(diǎn)1出發(fā)，找到頂點(diǎn)3(邊(1,3)),再?gòu)捻?/p>

點(diǎn)3出發(fā)，找到頂點(diǎn)0(邊(3,0)),這樣構(gòu)成回路，就不能求得最小生成樹了。

單選49.

用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)().

A.僅修改頭指針

B.頭、尾指針都要修改

C.僅修改尾指針

D.頭、尾指針可能都要修改

[答案]D

單選50.

在一棵m階B-樹中刪除一個(gè)關(guān)鍵字會(huì)引起合并，則該結(jié)點(diǎn)原有()個(gè)關(guān)鍵字。

A.1

B.[m/2]

C.[m/2]-l

D.[m/2]+l

[答案]C

判斷51.

當(dāng)待排序序列初始有序時(shí)，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜性為0(n)。

A.正確

B.錯(cuò)誤

[答案]B

判斷52.

內(nèi)部排序是指排序過程在內(nèi)存中進(jìn)行的排序。

A.正確

B.錯(cuò)誤

［答案］A

問答題53.

已知一棵度為4的樹中，其度為0、1、2、3的結(jié)點(diǎn)數(shù)分別為14、4、3、2,求該樹的結(jié)點(diǎn)總

數(shù)n和度為4的結(jié)點(diǎn)個(gè)數(shù)，并給出推導(dǎo)過程。

［答案］

單選54.

設(shè)一棵哈夫曼樹中有1999個(gè)結(jié)點(diǎn)，該哈夫曼樹用于對(duì)()個(gè)字符進(jìn)行編碼.

A.999

B.998

C.1000

D.1001

［答案］C

單選55.

哈希查找方法一般適用于()情況下的查找。

A.查找表為鏈表

B.查找表為有序表

C.關(guān)鍵字集合比地址集合大得多

D.關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系。

［答案］D

論述題56.

假設(shè)一個(gè)連通圖采用鄰接表G存儲(chǔ)結(jié)構(gòu)表示。設(shè)計(jì)一個(gè)算法，求起點(diǎn)u到終點(diǎn)v的經(jīng)過頂點(diǎn)

k的所有路徑。

［答案］

解法1,深度優(yōu)先*i為的『遞，1餌法思想是：采用個(gè)■序板SiU?！ū辉L問過

先將頂點(diǎn)V進(jìn)板，修改其訪問林忐，在棧小空時(shí)循環(huán)：出棧頂點(diǎn)j.訪問之，將其所《

的輻接點(diǎn)進(jìn)棧,并同時(shí)修改它們的訪問標(biāo)志.對(duì)應(yīng)的W法如下.

voidDFS1(AGraph?G,intv)

(intvisitedlMAXV]rl.j;

intSt[MAXV)rtop-Ij

ArcNode*pj

for<i?0;i<G->n;i**)〃訪“標(biāo)志數(shù)細(xì)置初依

vi8ited[i]?0;

top**;

St(top]-v;//初始頂點(diǎn)過棧

visited(v]-l;〃修改訪問標(biāo)志

while(top>-l>〃極不空時(shí)循環(huán)

<j-St(topJ;top-一;//Hitt

prlntf<-%dj);〃訪問力點(diǎn)j

p-G->adjllst(j].firstarc;〃找第個(gè)密接點(diǎn)

while(p!二NULL)

(if(vi?ited(p->adjvexJ~?0>〃構(gòu)未訪問過的郭隹點(diǎn)進(jìn)枝

{top**;

St(top]-p->ad3vex;

visited(p->adovex)-1;//修改訪問標(biāo)上

p-p->nextarc;〃找下?個(gè)鄰接點(diǎn)

DFSI作遞以燈法思路滑處,但和DFS算法相比產(chǎn)生的訪問序列是不同的.例女

如圖9.9所示的鄰接衣.從原點(diǎn)。開始遍歷時(shí).DFSW法是先輸出0.切找到H鄰接

2、3,即按fttt邊單鏈我中忖點(diǎn)的順序進(jìn)行處理的?而DFS1環(huán)法中由于是采用棧保7

過的鄰接度點(diǎn).所以是按照邊華能表中埼點(diǎn)的逆序進(jìn)行處理因此，DFS(GO)的喻H

0、I.2、3、4?血DFSI(GO)的輸出結(jié)果為0、3、4.2、1(實(shí)際上深度優(yōu)先遍歷月

??的)?

解法2：根仿DFS通仃算法中p指針的變化過程,得到如卜非遞打環(huán)法：

voidDFS2(AGraph?GUntv)〃■漁仃潭皮優(yōu)先遍歷算法

<AxcNodeep;

ArcNode?St(MAXV);

intvisited[MAXVJ;

inttop?-lrw,i;

for(i?0;l<G->n;〃切問標(biāo)志數(shù)用置初值

visited(i)?0;

printf(*%dLv”〃訪向v『點(diǎn)

vlsited(v)?l;〃置已仿何標(biāo)＜n

top**;〃將《USv的第個(gè)鋪接點(diǎn)選棧

St(top]?G->?djlist(vj.flrstarcj

新編數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析

while(top>-l)〃棧不空循環(huán)

{p=St[top];

〃出棧一個(gè)頂點(diǎn)為當(dāng)前頂點(diǎn)

top一;

while(p!=NULL)//循環(huán)遍歷其鄰接頂點(diǎn)

{w=p->adjvex;//該鄰接頂點(diǎn)的編號(hào)為W

if(visited[w]?=0)〃若該頂點(diǎn)未訪問過

{printf(n%d”，w)//訪問w頂點(diǎn)