期末考試數(shù)據(jù)結(jié)構(gòu)試題與答案

數(shù)據(jù)結(jié)構(gòu)試題及答案

1、單選題

1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為(C)

A內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)

C線性結(jié)構(gòu)與非線性結(jié)構(gòu)D緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。

2、采用線性鏈表表示一個向量時，要求占用的存儲空間地址(D)

A必須是連續(xù)的B部分地址必須是連續(xù)的

C一定是不連續(xù)的D可連續(xù)可不連續(xù)

3、采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為

(D)o

AnBn/2C(hl)/2D(加1)/2

4、在一個單鏈表中，若q結(jié)點是夕結(jié)點的前驅(qū)結(jié)點，若在q與夕之間插入結(jié)點

s,則執(zhí)行(D)。

As-^link=p-^link;p-^link-s;

Bllink-s\s—link-q\

Cp-^link=link;s—link-p\

Dqflink=s;s—link-p\

5、如果想在4092個數(shù)據(jù)中只需要選擇其中最小的5個，采用(C)方

法最好。

A起泡排序B堆排序C錦標賽排序D快速排序

6、設(shè)有兩個串大和0,求夕在大中首次出現(xiàn)的位置的運算叫做(B)0

A求子串B模式匹配C串替換D串連接

7、在數(shù)組4中，每一個數(shù)組元素加i][j]占用3個存儲字，行下標,從1到8,

列下標J從1到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放

該數(shù)組至少需要的存儲字數(shù)是(c)。

A80B100C240D270

8、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用(A)o

A棧B隊列C循環(huán)隊列D優(yōu)先隊列

9、一個隊列的進隊列順序是1,2,3,4,則出隊列順序為(C)。

10、在循環(huán)隊列中用數(shù)組加0..廳1]存放隊列元素，其隊頭和隊尾指針分別為

front和rear,則當前隊列中的元素個數(shù)是(D)。

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

C(front-rear+ni)%mD(rear-front+//i)%m

Ik一個數(shù)組元素a[i]與(A)的表示等價。

A*(a+i)Ba+iC*a+iD&a+i

12、若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為(B)參數(shù)。

A指針B引用C值D變量

13、下面程序段的時間復(fù)雜度為(C)

for(inti=0;i<m;i++)

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

a[i]

A0(m2)BO(n')C0(m*n)D0(m+n)

14、下面程序段的時間復(fù)雜度為(B)

intf(unsignedintn){

if(n==0|n==1)return1;

elsereturnn*f(n-1);

A0(1)B0(n)C0(n2)D0(n!)

15、線性表若是采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址

(D)0

A必須是連續(xù)的

B部分地址必須是連續(xù)的

C一定是不連續(xù)的

D連續(xù)或不連續(xù)都可以

16、數(shù)據(jù)結(jié)構(gòu)的定義為(D,S),其中口是(B)的集合。

A算法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結(jié)構(gòu)

17、算法分析的目的是(A)0

A找出數(shù)據(jù)結(jié)構(gòu)的合理性

B研究算法中輸入和輸出的關(guān)系

C分析算法的效率以求改進

D分析算法的易懂性和文檔性

18、在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，

則執(zhí)行(B)0

As->link=p;p->link=s;

Bs->link=p->link;p->link=s;

Cs->link=p->link;p=s;

Dp->link=s;s->link=p;

19、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點是指針p所指結(jié)點

的直接前驅(qū)，若在*q與*P之間插入結(jié)點*s,則應(yīng)執(zhí)行下列哪一個操作(B)

As->link=p->link;p->link=s;Bq->link=s;s->link=p

Cp->link=s->link;s->link=p;Dp->link=s;s->link=q;

20、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).若想摘除結(jié)點*p的直接后繼，則應(yīng)執(zhí)

行下列哪一個操作(A)

Ap->link=p->link->link;

Bp=p->link;p->link=p->link->link;

Cp->link=p->link;Dp=p->link->link;

21、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,link），且rear是指向非空的帶表頭

結(jié)點的單循環(huán)鏈表的尾結(jié)點的指針。若想刪除鏈表第一個結(jié)點，則應(yīng)執(zhí)行下列

哪一個操作（D）

As=rear;rear=rear->link;deletes;

Brear=rear->link;deleterear;

Crear=rear->1ink->link;deleterear;

Ds=rear->link->link;rear->link->link=s->link;deletes;

22、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,link）,且first為指向鏈表表頭的指

針，current為鏈表當前指針，在循環(huán)鏈表中檢測current是否達到鏈表表尾的

語句是（D）o

Acurrent->link=nullBfirst->link=current

Cfirst=currentDcurrent->link=first

23、一個棧的入棧序列為a,b,c,則出棧序列不可能的是（C）0

Ac,b,aBb,a,cCc,a,bDa,c,b

24、棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是（A）o

Atop=0Btop=maxSizeCtop=maxSizeDtop=-l

25、棧和隊列的共同特點是（C）o

A都是先進后出B都是先進先出

C只允許在端點處插入和刪除D沒有共同點

26、假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r,則判斷隊空

的條件為（D）.

Af+l==rBr+l==fCf==0Df==r

27、當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（B）

An-2Bn-1CnDn+1

28、當利用大小為n的數(shù)組順序存儲一個棧時，假定用top==n表示?？?，則

向這個棧插入一個元素時，首先應(yīng)執(zhí)行()語句修改top指針。

Atop++;Btop―;Ctop=0;Dtop;

29、設(shè)鏈式棧中結(jié)點的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔槨Ｈ粝?/p>

摘除鏈式棧的棧頂結(jié)點，并將被摘除結(jié)點的值保存到x中，則應(yīng)執(zhí)行下列

(A)操作。

Ax=top->data;top=top->link;Btop=top->link;x=top->data;

Cx=top;top=top->link;Dx=top->data;

30、設(shè)循環(huán)隊列的結(jié)構(gòu)是：

constintMaxsize=100;

typedefintDataType;

typedefstruct{

DataTypedata[Maxsize];

Intfront,rear;

}Queue;

若有一個Queue類型的隊列Q,試問判斷隊列滿的條件應(yīng)是下列哪一個語句

(D)

AQ.front==Q.rear;BQ.front-Q.rear==Maxsize;

CQ.front+Q.rear==Maxsize;DQ.front==(Q.rear+1)%Maxsize;

31、設(shè)有一個遞歸算法如下：

intfact(intn)

{if(n<=0)return1;

elsereturnn*fact(n-l);

)

下面正確的敘述是(B)

A計算fact(n)需要執(zhí)行n次遞歸Bfact(7)=5040

C此遞歸算法最多只能計算到fact(8)D以上結(jié)論都不對

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

intx(intn){

if(n<=3)return1;

elsereturnx(n-2)+x(n-4)+l;

)

試問計算x(x(8))時需要計算(D)次x函數(shù)。

A8次B9次C16次D18次

33、設(shè)有廣義表D(a,b,D),其長度為(B),深度為(A)

卜8B3C2D5

34、廣義表A(a),則表尾為(C)

AaB(())C空表D(a)

35、下列廣義表是線性表的有(C)

AE(a,(b,c))BE(a,E)CE(a,b)D

E(a,L())

36＞遞歸表、再入表、純表、線性表之間的關(guān)系為(C)

A再入表》遞歸表》純表》線性表B遞歸表＞線性表》再入表》純表

C遞歸表》再入表〉純表〉線性表D遞歸表〉再入表＞線性表》純表

37、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是(B)的二叉

樹

A空或只有一個結(jié)點B高度等于其結(jié)點數(shù)

C任一結(jié)點無左孩子D任一結(jié)點無右孩子

38、對于任何一棵二叉樹T,如果其終端結(jié)點數(shù)為no.度為2的結(jié)點為n2.,則

(A)

An0=n2+lBn2=n0+lCn0=2n2+lDn2=2n0+l

39＞由權(quán)值分別為11,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)

路徑長度為(B)

A24B73C48D53

40、已知一個順序存儲的線性表，設(shè)每個結(jié)點需占m個存儲單元，若第一個結(jié)

點的地址為dal,則第I個結(jié)點的地址為(A)。

Adal+(I-l)*mBdal+I*mCdal-I*mDdal+(I+l)*m

41、34具有35個結(jié)點的完全二叉樹的深度為(A)

A5B6C7D8

42、對線性表進行折半搜索時，要求線性表必須(C)

A以鏈接方式存儲且結(jié)點按關(guān)鍵碼有序排列B以數(shù)組方式存儲

C以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列D以鏈接方式存儲

43、順序搜索算法適合于存儲結(jié)構(gòu)為(B)的線性表。

A散列存儲B順序存儲或鏈接存儲

C壓縮存儲D索引存儲

44、采用折半搜索算法搜索長度為n的有序表時，元素的平均搜索長度為

(C)

A0(n")B0(nlog2n)C0(log2n)D0(n)

45、對于一個具有n個頂點和e條邊的無向圖，進行拓撲排序時，總的時間為

(A)

AnBn+1Cn-lDn+e

46、判斷一個有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利

用(C)。

A求關(guān)鍵路徑的方法B求最短路徑的Dijkstra方法

C深度優(yōu)先遍歷算法D廣度優(yōu)先遍歷算法

47、在10階B-樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最多為(C),最少為(A)

A1B2C9D10

48、對包含n個元素的散列表進行搜索，平均搜索長度為(C)

A0(log2n)B0(n)C不直接依賴于nD上述都不對

2、填空題（）

1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)四

種

2、數(shù)據(jù)的存儲結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)四

種

3、一種抽象數(shù)據(jù)類型包括（數(shù)據(jù)）和（操作）兩個部分。

4、設(shè)有兩個串p和q,求P在q中首次出現(xiàn)的位置的運算稱為（模式匹配）

5、棧、隊列邏輯上都是（線性存儲）結(jié)構(gòu)。

6、線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是（一對一）的，圖中的數(shù)據(jù)元素之間的關(guān)

系是（多對多）的，樹形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是（一對多）的。

7、棧中存取數(shù)據(jù)的原則（后進先出），隊列中存取數(shù)據(jù)的原則（先進先出）

8、串是由（零個或多個）字符組成的序列。（長度為零的串）稱為空串，

（由一個或多個空格組成的串）稱為空格串。

9、設(shè)目標串T="abccdcdccbaa”，模式P="cdcc”則第（6）次匹配成功。

10、一維數(shù)組的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），存儲結(jié)構(gòu)是（順序存儲表示）。對于

二維數(shù)組，有（行優(yōu)先順序）和（列優(yōu)先順序）兩種不同的存儲方式，對于一個

二維數(shù)組A[m][n],若采用按行優(yōu)先存放的方式，則任一數(shù)組元素相對

于A[0][0]的地址為（n*i+j）o

11、向一個順序棧插入一個元素時，首先使（棧頂指針）后移一個位置，然后

把待插入元素（寫）到這個位置上。從一個順序棧刪除元素時，需要前移一位

（棧頂指針）。

12、在一個循環(huán)隊列Q中，判斷隊空的條件為（Q.front==Q.rear）,判斷隊滿

的條件為（（Q.rear+l）%MaxSize==q.front）

13、對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為（n-l）。

14、--棵高度為5的滿二叉樹中的結(jié)點數(shù)為（63）個，--棵高度為3滿四叉

樹中的結(jié)點數(shù)為（85）個。

15、若對一棵二叉樹從0開始進行結(jié)點編號，并按此編號把它順序存儲到一維

數(shù)組中，即編號為0的結(jié)點存儲到a[0]中，其余類推，則a[i]元素的左子女結(jié)

點為（2*i+l）,右子女結(jié)點為（2*i+2）,雙親結(jié)點（i>=l）為（「（計1）/2

16、在一個最大堆中，堆頂結(jié)點的值是所有結(jié)點中的（最大值），在一個最小堆

中，堆頂結(jié)點的值是所有結(jié)點中的（最小值）。

17、已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單

元，第一個元素的地址為LOC（al）,那么，L0C（ai）=LOC（al）+（iT）*k。

18、在霍夫曼編碼中，若編碼長度只允許小于等于4,則除掉已對兩個字符編碼

為0和10外，還可以最多對（4）個字符編碼。

19、設(shè)高度為h的空二叉樹的高度為-1,只有一個結(jié)點的二叉樹的高度為0,若

設(shè)二叉樹只有度為2上度為0的結(jié)點，則該二叉樹中所含結(jié)點至少有

（2h+l）個。

20、由一棵二叉樹的前序序列和（中序序列）可唯一確定這棵二叉樹。

21、以折半搜索方法搜索一個線性表時，此線性表必須是（順序）存儲的（有序）

表。

22、已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是（68）。若完全二

叉樹的第7有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是（235）

23、對于折半搜索所對應(yīng)的判定樹，它既是一棵（二叉搜索樹），又是一棵（理

想平衡樹）。

24、假定對長度n=50的有序表進行折半搜索，則對應(yīng)的判定樹高度為

（5）,判定樹中前5層的結(jié)點數(shù)為（31）,最后一層的結(jié)點數(shù)為（19）0

25、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（2）倍。在一個具

有n個頂點的無向完全圖中，包含有（n（n-l）/2）條邊，在一個具有n個頂

點的有向完全圖中，包含有（n（n-l））條邊。

26、對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別

為（n）和（n-1）o

27、設(shè)線性表中元素的類型是實型，其首地址為1024,則線性表中第6個元素

的存儲位置是（1044）o

28、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選擇（插入排序），若初始

數(shù)據(jù)基本反序，則最好選擇（選擇排序）。

29、算法是對特定問題的求解步驟的一種描述，它是（指令）的有限序列，每一

條（指令）表示一個或多個操作。

30、對于一個具有n個頂點肯e條邊的無向圖，進行拓樸排序時，總的進間為

（n）

31、構(gòu)造哈希函數(shù)有三種方法，分別為（平方取中）法、（除留余數(shù)）法、（折迭移

位）法。

32、處理沖突的三種方法，分別為（線性探測）、（隨機探測）、（鏈地址法）。

33、對于含有n個頂點和e條邊的無向連通圖，利用普里姆算法產(chǎn)生的最小生成

樹.，其時間復(fù)雜度為（0（n2））、利用克魯斯卡爾算法產(chǎn)生的最小生成樹，

其時間復(fù)雜度為（O（elo&e））

34、快速排序在平均情況下的時間復(fù)雜度為（。（nlogm））,在最壞情況下的

時間復(fù)雜度為（0（/））；快速排序在平均情況下的空間復(fù)雜度為（0（lo&n））,

在最壞情況下的空間復(fù)雜度為（0（n））o

35、假定一組記錄的排序碼為（46,79,56,38,40,80）,對其

進行歸并排序的過程中，第二趟排序后的結(jié)果是（［38465679］

［4080］）

36、假定一組記錄的排序碼為（46,79,56,38,40,80）,對其

進行快速排序的第一次劃分的結(jié)果是（［3840］46L56798

0］）。

37、一個結(jié)點的子樹的（個數(shù)）稱為該結(jié)點的度。度為（零）的結(jié)點

稱為葉結(jié)點或終端結(jié)點。度不為（零）的結(jié)點稱為分支結(jié)點或非終端結(jié)點。

樹中各結(jié)點度的（最大值）稱為樹的度。

38、設(shè)KkK」（l〈=i<=n,l〈=j〈=n,j<>i）且在排序前的序列中R領(lǐng)先于R」（i<j）,

若排序后的序列中艮仍領(lǐng)先于R”則這種排序方法是（穩(wěn)定的），反之是（不

穩(wěn)定的）。

40、在堆排序的過程中，對任一分支結(jié)點進行調(diào)整運算的時間復(fù)雜度為（0

（log2n））,整個排序過程的時間復(fù)雜度為（0（nlogzn））。

41、在索引表中，每個索引項至少包含有（關(guān)鍵碼值）域和（子表地址）域這兩

項。

42、假定一個線性表為

（“abed“，”baabd"，“beef“，“cfg“，“ahij“，”bkwte"，“ccdt“，"a

ayb”），若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子

表中，則得到的a,b,c三個子表的長度分別為（3）,（3）,（2）o

43、對于包含5。個關(guān)鍵碼的3階B-樹，其最小高度為（4）,最大高度為

（5）o

44、從一棵B-樹刪除關(guān)鍵碼的過程，若最終引起樹根結(jié)點的合并，則新樹比原

樹的高度（減1）

45、假定要對長度n=100的線性表進行散列存儲，并采用開散列法處理沖突，

則對于長度m=20的散列表，每個散列地址的同義詞子表的長度平均為（5）。

46、在散列存儲中，裝載因子a又稱為裝載系數(shù)，若用m表示散列表的長度，n

表示待散列存儲的元素的個數(shù)，則a等于（n/m）。

47、在有向圖的鄰接矩陣中，第i行中“1”的個數(shù)是第i個頂點的（出度），

第i列中“1”的個數(shù)是第i個頂點的（入度）。在無向圖的鄰接矩陣中，第i

行（列）中“1”的個數(shù)是第i個頂點的（度），矩陣中“1”的個數(shù)的一半是圖

中的（邊數(shù)）。

48、在對m階B-樹中，每個非根結(jié)點的關(guān)鍵碼數(shù)最少為（rm/2-1-1）個，最多

為（m-1）個，其子樹棵數(shù)最少為（「m/2-i）,最多為（m）。

3、判斷題

1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位（X）。

2、數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立

的（J）.

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

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

（V）o

5、線性表的邏輯順序與物理順序總是一致的（X）。

6、二維數(shù)組是其數(shù)組元素為線性表的線性表（X）。

7、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運算：插入、刪除、搜索（。

8、非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。（X）

9、空串與由空格組成的串沒有區(qū)別。（義）

10、將T在S中首次出現(xiàn)的位置作為T在S中的位置的操作稱為串的模式匹

配。（V）

11、深度為h的非空二叉樹的第h層最多有2h-l個結(jié)點（義）

12、完全二叉樹就是滿二叉樹。（X）

13、已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。

（V）

14、帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之

和。（V）

15、線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上

也相鄰。（-J)

16、若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點，

則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點。（J）

17、任一棵二叉搜索樹的平均搜索時間都小于用順序搜索法搜索同樣結(jié)點

的順序表的平均搜索時間。（X）

18、最優(yōu)二叉搜索樹一定是平衡的二叉搜索樹。（J）

19、AOE網(wǎng)是一種帶權(quán)的無環(huán)連通圖。（J）

20、對于同一組待輸入的關(guān)鍵碼集合，雖然各關(guān)鍵碼的輸入次序不同，但得到

的二叉搜索樹都是相同的（X）。

21、二叉排序樹可以是一棵空樹（J）

22、線性表中所有結(jié)點的類型必須相同。（J）

23、n個結(jié)點的有向圖，若它有n（n—l）條邊，則它一定是強連通的。

（V）

24、任何無環(huán)的有向圖，其結(jié)點都可以排在一個拓撲序列里。（J）

25、隊列邏輯上是一個下端口和上端能增加又能減少的線性表（義）

26、二叉樹是樹的一種特殊情況（V）

27、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空

間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)（J）。

28、鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適

用。（X）

29、連通分量是無向圖中的極小連通子圖。（X）

30、在AOE網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑。（X）

31、關(guān)鍵活動不按期完成就會影響整個工程的完成時間。（J）

32、平衡二叉樹的左右子樹深度之差的絕對值不超過1。（J）

33、快速排序是對起泡排序的一種改進。（V）

34、直接選擇排序穩(wěn)定。（X）

35、堆排序占用的輔助空間很大。（X）

36、在散列法中采取開散列法來解決沖突時，其裝載因子的取值一定在（0,

1）之間。（X）

37、B-樹是一種動態(tài)索引結(jié)構(gòu)，它既適用于隨機搜索，也適用于順序搜索。

（X）

38、在散列法中，一個可用散列函數(shù)必須保證絕對不產(chǎn)生沖突。（義）

39、任何一個關(guān)鍵活動延遲，那么整個工程將會延遲。（V）

40、任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成。（X）

四、運算應(yīng)用題

1、在一個有〃個元素的順序表的第，個元素（1WiW〃）之前插入一個新

元素時，需要向后移動多少個元素？

答案：需要向后移動n-J+1個元素

2、當一個棧的進棧序列為1234567時，可能的出棧序列有多少種？6457321

是否是合理的出棧序列？

答案:

1「7114*13*12*11*10*9*8

7+187*6*5*4*3*2*1

可能的出棧序列有

種，6457321不是合理的出棧序列。

3、簡單(直接)選擇排序是一種穩(wěn)定的排序方法嗎？試舉例說明？

答案：是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉出反例即可。

{275275*512061}i=1

(061275*512275}1=2

{061275*512275}7=3

{061275*275512}

4、設(shè)有序順序表為{10,20,30,40,50,60,70},采用折半搜索時，

搜索成功的平均搜索長度是多少？

答案：

ASLsucc=(1*1+2*2+3*4)/7=17/7

5、在結(jié)點個數(shù)為n(n>l)的各棵樹中，高度最小的樹的高度是多少？它有多少

個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)

點？多少個分支結(jié)點？

答案：結(jié)點個數(shù)為n時，高度最小的樹的高度為1,有2層；它有n-1個葉結(jié)

點，1個分支結(jié)點；高度最大的樹的高度為n-1,有n層；它有1個葉結(jié)點，n-1

個分支結(jié)點。

6、一棵高度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉結(jié)點，其余各

層上每個結(jié)點都有k棵非空子樹，如果按層次自頂向下，同一層自左向右，順

序從1開始對全部結(jié)點進行編號，試問:

(1)各層的結(jié)點個數(shù)是多少？

(2)編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少？

(3)編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少？

(4)編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？

(5)若結(jié)點個數(shù)為n,則高度h是n的什么函數(shù)關(guān)系？

答案：

(1)各層的結(jié)點個數(shù)是k‘(i=0,l,2,....,h)

(2)編號為i的結(jié)點的父結(jié)點(若存在)的編號是>-(i+k-2)/kJ

(3)編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是(iT)*k+m+l

(4)當(iTKk〈〉O時有右兄弟，右兄弟的編號為i+1

(5)若結(jié)點個數(shù)為n,則高度h和n的關(guān)系為:h=logk(n*(k-l)+l)-l(n=0

時h=-l)

7、寫出下列中綴表達式的后綴形式：

(1)A*-B+C

(2)(A+B)*D+E/(F+A*D)+C

(3)A&&B||!(E>F)｛注：按C++的優(yōu)先級)

(4)!(A&&!((B<C)||(C>D)))||(C<E)

答案：各中綴表達式的后綴形式如下：

(1)AB-*C+

(2)AB+D*EFAD*+/+C+

(3)AB&&EF>!||

(4)ABC<CD>||!&&!CE<|

8、畫出下列廣義表的圖形表示和它們的存儲表示:

(1)D(A(c),B(e),C(a,L(b,c,d)))

(2)J1(J2(JI,a,J3(J1)),J3(J1))

答案：廣義表（1）的圖形表示為:

廣義表（2）的圖形表示為:

廣義表（1）的存儲表示為:

廣義表（2）的存儲表示為:

9、題目：11、將下面的森林變換成二叉樹（7分）。

答案:

A

10、將算術(shù)表達式((a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。(7分)

11、根據(jù)所給有向圖，寫出一個拓撲序列。(5分)

答案:

其中的一個拓撲序列為:VI,V2,V3,V4,V5,V6,V7

12、將給定的圖簡化為最小的生成樹，要求從頂點1出發(fā)。（7分）

答案:

13、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為0.05,

0.29,0.07,0.08,0.14,0.23,0.03,O11試設(shè)計赫夫曼編碼。

答案：

為方便起見,設(shè)各種字符的權(quán)值w={5,29,7,8,14,23,3,11}。因為n=8,所以要

構(gòu)造的赫夫曼樹共有m=2n-l=2*8-l=15個結(jié)點。生成的赫夫曼樹為下圖所示:

1

赫夫曼編碼為：概率為0.23的字符編碼為：00

概率為0.11的字符編碼為：010

概率為0.05的字符編碼為：0110

概率為0.03的字符編碼為：0111

概率為0.29的字符編碼為：10

概率為0.14的字符編碼為：110

概率為0.07的字符編碼為：1110

概率為0.08的字符編碼為：1111

14、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是

EBCDAFHIGJ,試畫出這棵二叉樹，并給出這棵二叉樹的后序遍歷序列。

答案：根據(jù)前序序列和電座序列能得到唯?的二叉樹，所得二又樹如圖:

這棵二叉樹的后序遍歷序列為：EDbJJjGFA

15、在結(jié)點個數(shù)為n（n>l）的各棵樹中，高度最小的樹的高度是多少？它有多少

個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)

點？多少個分支結(jié)點？

答案：結(jié)點個數(shù)為n時，高度最小的樹的高度為1,有2層；它有n-1個葉結(jié)

點，1個分支結(jié)點；高度最大的樹的高度為n-1,有n層；它有1個口卜結(jié)點，nT

個分支結(jié)點。

16、對于一個高度為h的AVL樹，其最少結(jié)點數(shù)是多少？反之，對于一個有n

個結(jié)點的AVL樹，其最大高度是多少？最小高度是多少？

答案：設(shè)高度為h（空樹的高度為T）的AVL樹的最少結(jié)點為N”則N?=-IO

A是斐波那契數(shù)。乂設(shè)AVL樹有n個結(jié)點，則其最大高度不超過3/2*logKn+l）,

最小高度為「log2（n+l）

17、7-7設(shè)有序順序表中的元素依次為017,094,154,170,275,503,509,512,

553,612,677,765,897,908。試畫出對其進行折半搜索時的判定樹，并計算

搜索成功的平均搜索長度和搜索不成功的平均搜索長度。

答案：折半搜索時的判定樹為

76人Q0

ASLSUCc=l/14(l+2*2+3*4+4*7)=45/14

ASUSUCc=l/15(3*1+4*14)=59/15

18、試對下圖所示的AOE網(wǎng)絡(luò)

(1)這個工程最早可能在什么時間結(jié)束。

(2)求每個事件的最早開始時間Ve[i]和最遲開始時間Vl[i]o

(3)求每個活動的最早開始時間e()和最遲開始時間/()。

(4)確定哪些活動是關(guān)鍵活動。畫出由所有關(guān)鍵活動構(gòu)成的圖，指出哪些活動

加速可使整個工程提前完成。

答案：按拓樸有序的順序計算各個頂點的最早可能開始時間V。和最遲允許開始

時間V”然后再計算各個活動的最早可能開始時間e和最遲允許開始時間1,根

據(jù)1-e是否等于0來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。

①③②④⑤⑥

Vo01915293843

Vi01915373843

<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>

e00151919152938

L170152719273738

1-e1700801280

此工程最早完成時間為43,關(guān)鍵路徑為<1,3X3,2X2,5X5,6>

19、已知有五個待排序的記錄，其關(guān)鍵字分別為：256,301,751,129,

937,863,742,694,076,438請用快速排序的方法將它們從小到大排列。

答案：

第一次排序：(076,129),256,(751,937,863,742,694,301,439)

第二次排序：076,129,256,(438,301,694,742),751,(863,937)

第三次排序：076,129,256,301,438,(694,742),751,(863,937)

第四次排序：076,129,256,301,438,694,742,751,(863,937)

第五次排序：076,129,256,301,438,694,742,751,863,937

20、設(shè)有150個記錄要存儲到散列表中，并利用線性探查法解決沖突，要求

找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計多大？(設(shè)a是

散列表的裝載因子，則有ASLucc=(1+1/(1-a))/2)o

答案：已知要存儲的記錄數(shù)為n=150,查找成功的平均查找長度為ASL-W2,則

有：ASLsuee=1/2(1+1/(1-a))W2解得aW2/3,又有:a=n/m=150/m

兩式聯(lián)立得:150/m這2/3,解得:m2225.

所以散列表需要設(shè)計225個單位。

五、算法分析題

1、給出下列遞歸過程的執(zhí)行結(jié)果

voidunknown(intIF){

if（獷）{

unknown(曠1);

for(int7=1;i<=w\/++)cout<<w?f

cout<<endl;

}

)

調(diào)用語句為unknown(4)。

答案：

(1)1

22

333

4444

2、給出遞歸過程的執(zhí)行結(jié)果

voidunknown(intn){

COUt<<Z7%10;

if(int(z?/10))unknown(int(z?/10));

)

調(diào)用語句為unknown(582)o

答案：285

3、給出遞歸過程的執(zhí)行結(jié)果

intunknown(intm){

intvalue;

if(!")value-3;

elsevalue=unknown(zzrl)+5;

returnvalue;

執(zhí)行語句為cout<<unknown(3)。

答案：18

4、設(shè)有一個二維數(shù)組人加"],假設(shè)加0][0]存放位置在644(⑷，父2][2]存

放位置在676,山，每個元素占一個空間，問履3][3]加存放在什么位置？腳注皿

表示用10進制表示。

答案：設(shè)數(shù)組元素存放在起始地址為Loc(i,j)的存儲單元中。

因為：Loc⑵2)=Loc(0,0)+2*n+2=644+2*n+2=676

所以：n=(676-2-644)/2=15

所以：Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692

5、設(shè)單鏈表結(jié)構(gòu)為structListNode{

intdata;

ListNode*link;

)；

下面的程序是以單鏈表為存儲結(jié)構(gòu)，實現(xiàn)二路歸并排序的算法，要求鏈表

不另外占用存儲空間，排序過程中不移動結(jié)點中的元素，只改各鏈結(jié)點中的指

針，排序后r仍指示結(jié)果鏈表的第一個結(jié)點。在初始狀態(tài)下，所有待排序記錄

鏈接在一個以r為頭指針的單鏈表中。例如，

在算法實現(xiàn)時，利用了一個隊列做為輔助存儲，存儲各有序鏈表構(gòu)成的歸

并段的鏈頭指針。初始時，各初始歸并段為只有一個結(jié)點的有序鏈表。隊列的

數(shù)據(jù)類型為Queue,其可直接使用的相關(guān)操作有

■置空隊列操作：makeEmpty();

■將指針才加入到隊列的隊尾操作：EnQueue(ListNode*x);

■退出隊頭元素，其值由函數(shù)返回的操作：ListNode*DlQueue();

■判隊列空否的函數(shù)，空則返回1,不空則返回0：intIsEmpty()。

解決方法提示：

＞程序首先對待排序的單鏈表進行一次掃描，將它劃分為若干有序的子鏈

表，其表頭指針存放在一個指針隊列中。

＞當隊列不空時，從隊列中退出兩個有序子鏈表，對它們進行二路歸并,

結(jié)果鏈表的表頭指針存放到隊列中。

＞如果隊列中退出一個有序子鏈表后變成空隊列，則算法結(jié)束。這個有序

子鏈表即為所求。

在算法實現(xiàn)時有6處語句缺失，請閱讀程序后補上。

(1)兩路歸并算法

voidmerge(ListNode*ha,ListNode*hb,,ListNode檢,he){

ListNode*pa,*pb,*pc;

if(ha—data＜=h—data){he=ha;pa-ha-1ink;pb=hb\}

else{he=hb\pb=hb-*link\pa=ha\}

pc=hc\

while(pa&&pb)

ifpa-data＜=p—data)

(_________________

{pc—link=pa\pc=pay

pa-pa—1ink;

else

pc—link=pb\pc=pb\

pb-pb-^link;

)

if(pa)pc-link=pa\

elsepc—link-pb\

)；

(2)歸并排序主程序

voidmergesort(ListNode*r){

ListNode*s,t;QueueQ;

if(!r)return;

s-r\Q.EnQueue{r);

while(s){

t-s—link;

while(t!=0&&s—data<=t-data){s-t\

tflink：}

if(方){

s—link=0;s=Q.EnQueue{s);

)

while(!Q.IsEmpty{)){

r-Q.DIQueued);

if(2IsEmpty())break;

s=Q.DIQueued);

merge]r,s,Q.EnQueue{t}

t);

6、請讀下列程序，該程序是在單鏈表中刪除一個結(jié)點的算法，為空出的地方填

上正確的語句。(7分)

voiddemo2(LinkListhead,ListNode*p)

{//head是帶頭結(jié)點的單鏈表，刪除P指向的結(jié)點

ListNode*q=head;

while(q&&q->next!-p)q=q->next;

if(q)Error("*pnotinhead");

q->next=p~~>next;

free(p);

}

7、已知一完全二叉樹從根結(jié)點開始，自頂向下，同一層自左向右連續(xù)編號，

根結(jié)點的編號為0,閱讀以下程序請回答該程序所實現(xiàn)的功能：

template<classtype>

void1inkedtosequent(Bintreenode<Type>*t,typea[],inti){

if(t!=Null){

a[]=t->getData();

1inkedtosequent(t->getleftchiId(),a,2*i+l);

1inkedtosequent(t->getrightchild(),a,2*i+2);

})

主程序調(diào)用方式：1inkedtosequent(t.root,a,0);

答案：該程序的功能是：將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序

(數(shù)組)表示。

8、設(shè)散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決

沖突，對下列關(guān)鍵碼序列12,23,45,57,20,03,78,31,15,36造表。

(1)采用線性探查法尋找下一個空位，畫出相應(yīng)的散列表，并計算等概率

下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。

(2)采用雙散列法尋找下一個空位，再散列函數(shù)為RH{key)=(7*4經(jīng))%10+

1,尋找下一個空位的公式為H.=(H-+RH(ke。)%13,H,=H(key)□畫出

相應(yīng)的散列表，并計算等概率下搜索成功的平均搜索長度。

答案：使用散列函數(shù)H(key)=keymod13有:

H(12)=12,H(23)=10,H(45)=6,H(57)=5,H(20)=7,H(03)=3,H

(78)=0,H(31)=5,H(15)=2,H(36)=10

利用線性探查法造表：

0123456789101112

78150357452031233612

1111!14121

搜索成功的平均搜索長度為：

ASLsucc=l/10(1+1+1+1+1+1+4+1+2+1)=14/10

搜索不成功的平均搜索長度為：

ASUsuee=1/13(2+1+3+2+1+5+4+3+2+1+5+4+3)=36/13

利用雙散列法造表：

Hi=(Hi那(key))%13,仄=H(key)

0123456789101112

78150357452031362312

1111113511

9、閱讀下面程序，指出其算法的功能并求出其時間復(fù)雜度。

(1)intPrime(intn){

inti=2,x=(int)sqrt(n);

while(i<=x){

if(n%i==O)break;

i++；

)

if(i>x)return1;

elsereturn0;

)

(2)intsuml(intn){

intp=l,s=0;

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

{p*=i;s+=p;}

returns;

)

答案：(1)程序功能是判斷n是否是?個素數(shù)，若是則返回數(shù)值1,

否則返回數(shù)值0,該算法的時間復(fù)雜度為0(sqrt(n)).

(2)程序功能是計算該算法的時間復(fù)雜度為0(n).

10、判斷一個帶表頭結(jié)點的雙向循環(huán)鏈表L是否對稱相等的算法如下所示，請

在算法的處填入正確的語句。

intsymmetry(DblListDL){

intsym=l;

DblNodep=DL->rLink,q=DL->lLink;

While(p!=q&&p->1Link==q)&&sym=1)

if(p->data==q->data){

p-p->rLink;

q=q->lLink;

elsesym=O;

returnsym;}

11、閱讀下面程序，指出其算法的功能

ttinclude,stack,h”

intBaseTrans(intN,intB){

inti,result=O;Stack<int>S;

while(N!=0)(i=N%B;N=N/B;S.Push(i);}

while(!S.IsEmptyO){i=S.GetTopO;S.Pop();

result=result*10+i;}

returnresult;

)

答案：該算法是將一個非負的十進制整數(shù)N轉(zhuǎn)換為另一個基數(shù)為B的B進制

數(shù)。

12、閱讀下面程序，指出其算法的功能

template<classType>

voidBinaryTree<Type>::binsearchTree(BinTreeNode<Type>*t,int&bs){

if(t!=Null){

if((t->1etfchi1d==Nu11||t->data>t->leftchild->data)&&

(t->rightchild==NullI|t->data<t->rightchild->data)){

bs=l;

binsearchTree(t->leftchiId,bs);

if(bs)binsearchTree(t->rightchild,bs);

elsebs=O;

答案：該算法是判別給定的以二叉鏈表存儲的二叉樹是否是二叉搜索樹。采用

遞歸算法，對樹中的所有結(jié)點檢查是否左子樹上結(jié)點的關(guān)鍵碼都小于它的關(guān)鍵

碼，右子樹上結(jié)點的關(guān)鍵碼都大于它的關(guān)鍵碼。如滿足上述條件，則是二叉搜

索樹。

六、綜合算法題

1、試設(shè)計一個實現(xiàn)下述要求的查找運算函數(shù)￡。加加。設(shè)有一個帶表頭結(jié)點

的雙向鏈表〃每個結(jié)點有4個數(shù)據(jù)成員：指向前驅(qū)結(jié)點的指針〃介A