東北大學(xué)繼續(xù)教育學(xué)院

數(shù)據(jù)結(jié)構(gòu)HX復(fù)習(xí)題

一、單選題

1.表達(dá)式a*(b+c)-d的后綴表達(dá)式是

A.abcd*+一B.abc*+d-

C.abc+*d-D.-+*abcd

2.某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點(diǎn)一定是

A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)

C.任一結(jié)點(diǎn)無左孩子D.任一結(jié)點(diǎn)無右孩子

3.下面的說法中正確的是

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

(2)按二叉樹定義，具有三個(gè)結(jié)點(diǎn)的二叉樹共有6種。

A.(1),(2)B.(1)

C.(2)D.(1),(2)都錯(cuò)

4.樹有先序遍歷和后序遍歷，樹可以轉(zhuǎn)化為對(duì)應(yīng)的二叉樹。下面的說法正確的是

A.樹的后序遍歷與其對(duì)應(yīng)的二叉樹的先序遍歷相同

B.樹的后序遍歷與其對(duì)應(yīng)的二叉樹的中序遍歷相同

C.樹的先序序遍歷與其對(duì)應(yīng)的二叉樹的中序遍歷相同

D.以上都不對(duì)

5.下列說法正確的是

(1)二又樹按某種方式線索化后，任一結(jié)點(diǎn)均有指向前趨和后繼的線索

(2)二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處于在子孫結(jié)點(diǎn)前

(3)二叉排序樹中任一結(jié)點(diǎn)的值大于其左孩子的值，小于右孩子的值

A.(1)(2)(3)B.(1)(2)

C.(1)(3)D.都不對(duì)

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

A.2-1B.2K+1

C.2K-1D.2卜,

7.以下說法不正確的是

A.無向圖中的極大連通子圖稱為連通分量

B.連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)

C.圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn)

D.有向圖的遍歷不可采用廣度優(yōu)先搜索

8.有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中

A.第i行1的元素之和B.第i列1的元素之和

C.第i行0的元素個(gè)數(shù)D.第i列非0的元素個(gè)數(shù)

9.設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有多少條邊才能確保是一個(gè)連通圖？

A.5B.6

C.7D.8

10..下圖的鄰接表中，從頂點(diǎn)VI出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列是

A.V1V2V3V4V5B.V1V2V3V5V4

C.V1V4V3V5V2D.V1V3V4V5V2

11.抽象數(shù)據(jù)類型的三個(gè)組成部分分別為

A.數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作

B.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

C.數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型

D.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

12.要求相同邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為

A.數(shù)據(jù)元素具有同一的特點(diǎn)

B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相同，而且其對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

C.每個(gè)數(shù)據(jù)元素都一樣

D.僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相同

13.下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是

A.Vn,n!,2",n：i'

B.n/2,2",n108",2,0°

C.2",logn,I?*,n3/2

D.2嗎logn,2n,n"

14.在下列哪種情況下，線性表應(yīng)當(dāng)采用鏈表表示為宜

A.經(jīng)常需要隨機(jī)地存取元素

B.經(jīng)常需要進(jìn)行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間

D.表中元素的個(gè)數(shù)不變

15.設(shè)指針p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱性可表示為

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

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

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

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

16.已知指針p和q分別指向某帶頭結(jié)點(diǎn)的單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針

s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為

A.s->next=q；p->next=s->next；

B.s->next=p；q->next=s->next；

C.p->next=s->next；s->next=q；

D.q->next=s->next；s->next=p；

17.棧和隊(duì)列的共同特點(diǎn)是

A.只允許在端點(diǎn)處插入和刪除元素

B.都是先進(jìn)后出

C.都是先進(jìn)先出

D.沒有共同點(diǎn)

18.對(duì)于鏈隊(duì)列，在進(jìn)行插入運(yùn)算時(shí).

A.僅修改頭指針

B.頭、尾指針都要修改

C.僅修改尾指針

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

19.設(shè)有一個(gè)順序棧的入棧序列是1、2、3,則3個(gè)元素都出棧的不同排列個(gè)數(shù)為

A.4B.5

C.6D.7

20.設(shè)一個(gè)棧的輸入序列為A,B,C,D,則借助一個(gè)棧所得到的輸出序列不可能是

A.A,B,C,DB.D,C,B,A

C.A,C,D,BD.D,A,B,C

參考答案:

題號(hào)12345678910

答案CBBBDDDAAD

題號(hào)11121314151617181920

答案AB1)BC1)ADB1)

二、填空題

1.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（）。

i=l;

WHILE（i<n）

i=i*2;

2.假設(shè)帶星嘉的非空單循環(huán)鏈表中僅設(shè)尾指針L,則在第1個(gè)結(jié)點(diǎn)之前插入指針s所指結(jié)

點(diǎn)的語句依次是（）。

3.無表頭結(jié)點(diǎn)的鏈隊(duì)列Q為空的條件是（）o

4.設(shè)Q[0..NT]為循環(huán)隊(duì)列，其頭、尾指針分別為P和R,則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為

（）o

5.一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（）o

6.在AOV網(wǎng)中，存在環(huán)意味著某項(xiàng)活動(dòng)以自己為先決條件；對(duì)程序的數(shù)據(jù)流圖來說，它表

明存在（）。

7.有向圖G可拓?fù)渑判虻呐袆e條件是（）0

8.如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是()。

9.應(yīng)用回溯與分支限界法解決實(shí)際問題時(shí)，在搜索過程中利用判定函數(shù)，也稱為

()?

10.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸

出受限的雙端隊(duì)列得到的輸出序列是().，

參考答案：

1.log2n2.s->nest=L->next->next；L->next->next=S3.Q->real==Q->front=NULL

4.(R-P+N)%N5.106.死循環(huán)7.不存在環(huán)8.49.限界函數(shù)10.4231

三、應(yīng)用題

1.比較線性表和棧的基本操作的不同點(diǎn)。

2.有一個(gè)二叉樹按層次順序存放在一維數(shù)組中，如下圖所示:

試求：(1)該樹的后序遍歷序列。

(2)畫出該樹的后序線索樹。

1234567891011

ACBED

3.分析順序查找算法的“監(jiān)視哨”設(shè)置作用

4.對(duì)n個(gè)整數(shù)的序列進(jìn)行直接選擇排序。

(1)算法描述。

(2)并給出實(shí)例(5249803614586123)的排序過程。

參考答案：

1.主要區(qū)別是對(duì)插入和刪除操作的限制。

如線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除；而隊(duì)列只允許在表尾一端進(jìn)行插入，在

表頭一端進(jìn)行刪除；所以也稱隊(duì)列為受限的線性表。表頭為隊(duì)列頭；表尾為隊(duì)列尾。

插入刪除

線性表Insert(L,i,x)Delete(L,i)

(1WiWn+1)(IWiWn)

隊(duì)列Insert(L,n+1,x)Delete(L,1)

2.(1)后序遍歷序列CEDBA

3.為了考慮查找不成功的情況，在每次進(jìn)行關(guān)鍵字的比較前，首先要判斷循環(huán)變量i是否數(shù)

組越界，這對(duì)算法來說是必要的。如果每步省略數(shù)組下標(biāo)是否越界的判斷，則可以大大

提高算法運(yùn)行的效率。為此，可以利用預(yù)留的0號(hào)單元，作為所設(shè)的“監(jiān)視哨”控制循

環(huán)變量i的出界。

假設(shè)數(shù)據(jù)從后向前比較，監(jiān)視哨設(shè)在數(shù)組低端L.elem[0]=k

將算法中的判斷語句

while(i<=L.length&&Lelem[i]!=k)++i;

改為while(L.elem[i]!=k)―i;

這樣，當(dāng)在查找表中不存在其關(guān)鍵字等于給定值的數(shù)據(jù)元素時(shí)，i必等于0,并且這樣的

處理并不影響查找成功的情況。

4.(1)直接選擇算法描述：

[1]第1趟，從n個(gè)記錄中，經(jīng)過比較選出關(guān)鍵字值為最小的記錄，并與第1個(gè)記錄交

換位置。

[2]第2趟，從余下的n-1個(gè)記錄中選擇出當(dāng)前關(guān)鍵字最小的排序，并與第2個(gè)記錄

交換位置。

[3]第i趟，在無序的第i個(gè)到第n個(gè)的n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，與

第i個(gè)記錄進(jìn)行互換。

[4]以此類推，直至第n-1趟排序結(jié)束。

(2)初始狀態(tài)5249803614586123

i=l[14]49803652586123

i=2[1423]803652586149

i=3[142336]8052586149

i=4[14233649]52586180

i=5[1423364952]586180

i=6[142336495258]6180

i=7[14233649525861]80

排序結(jié)果[1423364952586180]

四、算法閱讀題

設(shè)計(jì)算法實(shí)現(xiàn)以鏈表作存儲(chǔ)結(jié)構(gòu)，將線性表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換，即

⑸，…,a1Mb?-,b?)改變成(b[,…,b?,a”)。閱讀算法，在橫線處填入語句或注釋。

voidexchange_L(Linklist&L,intm){

//本算法實(shí)須單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)的整體互換

if(m&&L->next){//鏈表不空且

p=L->next;

⑴

while(k<m&&p){//(2)

p=p->next;++k;

}//while

if(p&&⑶){//n!=0時(shí)才需要修改指針

ha=L->next;//以指針ha記a1結(jié)點(diǎn)的位置

(4)=p->next;//將bl結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后

p->next=NULL;//設(shè)a,0的后繼為空

q=L->next;//令q指向bi結(jié)點(diǎn)

while(q->next)

q=q->next;//查找b?結(jié)點(diǎn)

q->next=ha;//(5)

}〃if(P)

}//if(m)

}//exchange_L

參考答案

(1)k=1;

(2)查找第a.個(gè)結(jié)點(diǎn)

(3)p->next

(4)L->next

(5)將第al結(jié)點(diǎn)鏈接到bn結(jié)點(diǎn)之后

五、算法設(shè)計(jì)題

設(shè)計(jì)算法purge_Sq實(shí)現(xiàn)刪除順序表SqList中重復(fù)元素，指出其算法的時(shí)間復(fù)雜度。

參考答案：

voidpurge_Sq(SqList&L){//刪除順序表L中的重復(fù)元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length;++i){〃順序考察表中每個(gè)元素

j=0;

while(j<=k&&L.elem[j]!=L.elem[i])

++j；//在新表中查詢是否存在和L.elem[i]相同的元素

if(k==-l||j>k)//k=-l表明當(dāng)前考察的是第一個(gè)元素

L.elem[++k]=L.elem[i];

}//for

L.length=k+1;//修改表長(zhǎng)

}//purge_Sq

此算法的時(shí)間復(fù)雜度為0(L.length2)1.

六、算法設(shè)計(jì)題(本題10分)

設(shè)計(jì)算法從圖的鄰接表結(jié)構(gòu)轉(zhuǎn)換成鄰接矩陣結(jié)構(gòu)的算法。

參考答案：

voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm){

〃將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示。

for(i=l;i<=n;i++)〃設(shè)圖有n個(gè)頂點(diǎn)，鄰接矩陣初始化。

for(j=l;j<=n;j++)gm[i][j]=0;

for(i=l;i<=n;i++){

p=gl[i].firstarc;〃取第一個(gè)鄰接點(diǎn)。

while(p){//下一個(gè)鄰接點(diǎn)

gm[i][p->adjvex]=l;

p=p->next;

}//while

}//for

}//AdjListToAdjMatrix

七、綜合題

1、閱讀算法，在橫線處填入語句或注釋。

voidexchange_L(Linklist&L,intm){

//本算法實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)的整體互換

if(m&&L->next){//鏈表非空

p=L->next;

⑴

while(k<m&&p){//(2)

p=p->next;++k;

}//while

if(p&&(3)){

ha=L->next;//記a1結(jié)點(diǎn)的位置

L->next=p->next;//將bl結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后

p->next=(4);

q=L->next;//令q指向b】結(jié)點(diǎn)

while(q->next)

q=q->next;//查找b”結(jié)點(diǎn)

q->next=(5)

}//if(p)

}//if(m)

}//exchange_L

參考答案

(1)k=1;

(2)查找第a,?個(gè)結(jié)點(diǎn)

(3)p->next

(4)NULL

(5)ha;

2.一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式，以二叉鏈表形式存儲(chǔ)在二叉樹T中，設(shè)計(jì)算法F1

實(shí)現(xiàn)求值，并指出遍歷的方式。

參考答案：

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

k=1;

intFl(BiTrecT){

if(!T)return0;

if(!T—IchiId&&!T—rchild)〃判斷是否為葉子結(jié)點(diǎn)

return(T->data);

Lv=Fl(T->lchild);Rv=Fl(T->rchild);

switch(T—data){〃求值運(yùn)算

case'+':V=Lv+Rv;break;

case':V=Lv-Rv;break;

case,*':V=Lv*Rv;break;

case'/':V=lv/Rv;break;

}//switch

returnV;〃返回值

}//Fl

(2)后序遍歷二叉樹求值。

3.設(shè)計(jì)算法實(shí)現(xiàn)以逆鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖的拓?fù)渑判?。逆鄰接表存?chǔ)結(jié)構(gòu)定義如下:

頂點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)結(jié)構(gòu)

vexda