數(shù)據(jù)結(jié)構(gòu)試題,模擬考試題8

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

單選題

在數(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）。

AnBn/2C（n-l）/2D（n+l）/2

4、在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入結(jié)點s,則執(zhí)行

（D）。

Asflink=pflink;pfink=s;

Bp—link=s;s—link=q;

Cpflink=sflink;s->link=p;

Dq—link=s;link=p;

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

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

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

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

7、在數(shù)組A中，每一個數(shù)組元素占用3個存儲字,行下標i從1至U8,列下標j從1

到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中,則存放該數(shù)組至少需要的存儲字

數(shù)是（C）。

A80B100C240D270

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

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

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

10、在循環(huán)隊列中用數(shù)組存放隊列元素，其隊頭和隊尾指針分別為front和rear,

則當前隊列中的元素個數(shù)是（D）。

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

C(front-rear+m)%mD(rear-front+m)%m

11、一個數(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-H-)

a[i][j]=i*j;

AO(m2)BO(n2)CO(m*n)DO(m+n)

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

int^unsignedintn){

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

elsereturnn*f(n-l);

)

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

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

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）。

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

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

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

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

18、在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（B）。

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->link->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）。

Acurrent->link=nullBfirst->link=current

Cfirst=currentDcurrent->link=first

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

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

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

Atop=0Btop=maxSizeCtop=maxSizeDtop="l

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

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

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

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

(D).

ARl==rBr+l==fC4=0Df==r

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

An-2Bn-1CnDn+1

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

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

Atop-H-;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計算fhct(n)需要執(zhí)行n次遞歸Bfhct⑺=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)

A8B3C2D5

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

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

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

AE(a,(b,c))BE(a,E)CE(a,b)DE(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ù)為n0,度為2的結(jié)點為n2.，則（A）

An0=n2+lBn2=nO+1Cn0=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）

AO（n2）BO（nlog2n）CO（log2n）DO（n）

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

AnBn+1Cn-1Dn+e

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

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

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

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

AIB2C9D10

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

AO（log2n）BO（n）C不直接依賴于nD上述都不對

填空題（）

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ù)）和（操作）兩個部分。

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

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

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

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

棧中存取數(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-1）。

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）為（「（i-l）/2-I）.

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

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

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

素的地址為LOC（al）,那么，LOC（ai尸LOC（al）+（i-l）*k。

18、在霍夫曼編碼中，若編碼長度只允許小于等于4,則除掉已對兩個字符編碼為。和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）。

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

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

有（n（n-l））條邊。

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

（n-1）?

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

是（1044）。

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ù)雜度為（0

（elog2e））

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

（0（n2））；快速排序在平均情況下的空間復(fù)雜度為（0（log2n））,在最壞情況下的空間

復(fù)雜度為（0（n））.

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

序的過程中，第二趟排序后的結(jié)果是（[38465679][40803）

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

序的第一次劃分的結(jié)果是（[3840]46[567980]）。

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

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

大值）稱為樹的度。

38、設(shè)Ki=Kj（l<=i<=n,l<=jv=n,joi）且在排序前的序列中Ri領(lǐng)先于Rj（i<j）,若排序后的序

列中Ri仍領(lǐng)先于Rj,則這種排序方法是（穩(wěn)定的），反之是（不穩(wěn)定的）。

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

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

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

42、假定一個線性表為（“abcd",“baabd”,”bce「,"ca”,“ahij",“bkwte”,“ccdt",“aayb”），若按照字

符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子

表的長度分別為（3）,（3）,（2

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

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ù)最少為（Fm/2-1-1）個，最多為（m-1）個，

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

判斷題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（4）

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

的前序遍歷結(jié)果序列的最后一個結(jié)點。（4）

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

索時間。（X）

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

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

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

都是相同的（X）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)鍵活動延遲，那么整個工程將會延遲。2

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

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

1、在一個有n個元素的順序表的第i個元素（1<i<n）之前插入一個新元素時，需要向后

移動多少個元素？

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

當一個棧的進棧序列為1234567時，可能的出棧序列有多少種？6457321是否是合理的出棧

序列？

答案：

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

1-114*13*12*11*10*9*8

——C，4=-*----------------------------=429

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

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

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

{275275*512061}i=1

{061275*512275}i=2

{061275*512275}i=3

(061275*275512}

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

度是多少？

答案：ASLsucc=（l*l+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ù)是ki（i=0,l,2,....,h）

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

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

（4）當時有右兄弟，右兄弟的編號為i+1

（5）若結(jié)點個數(shù)為n,則高度h和n的關(guān)系為：h=logk（n*（k-1）+1）-1（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、畫出下列廣義表的圖形表示和它們的存儲表示:

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

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

答案：廣義表(1)的圖形表示為：

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

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

D

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

答案:

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,0.11試設(shè)計赫夫曼編碼。

答案：

為方便起見，設(shè)各種字符的權(quán)值w={5,29,7,8,14,23,3,11}。因為n=8,所以要構(gòu)造的赫夫曼樹

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

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

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

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

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

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

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

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

答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹，所得二叉樹如圖：

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

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é)點，n-1個分支結(jié)點。

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

AVL樹，其最大高度是多少？最小高度是多少？

答案：設(shè)高度為h(空樹的高度為-1)的AVL樹的最少結(jié)點為Nh,則Nh=Fh+3-l。

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

最小高度為Flog2(n+l)-]-lo

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

765,897,908o試畫出對其進行折半搜索時的判定樹，并計算搜索成功的平均搜索長度和搜

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

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

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

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

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

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

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

工程提前完成。

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

后再計算各個活動的最早可能開始時間e和最遲允許開始時間1,根據(jù)1-e是否等于0來確定

答案：

第一次排序：(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),75L(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是散列表的裝載因子，則有

ASLsucc=(1+1/(1-a))/2)。

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

ASLsucc=1/2(1+1/(1-a))<2解得aW2/3，又有：a=n/m=150/m

兩式聯(lián)立得：150/mW2/3,解得：m2225.

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

五、算法分析題

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

voidunknown(intw){

if(w){

unknown(w-1);

for(inti=1;i<=w;i++)cout?w?'

cout?endl;

}

)

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

答案：

(1)1

22

333

4444

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

voidunknown(intn){

cout?n%10;

if(int(n/10))unknown(int(n/10));

}

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

答案：285

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

intunknown(intm){

intvalue;

if(!m)value=3;

elsevalue=unknown(m-1)+5;

returnvalue;

}

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

答案：18

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

(10),每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進

制表小。

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

因為：Loc(2,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();

■將指針x加入到隊列的隊尾操作：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<=hb-*data){he=ha;pa=ha-*link;pb=hb;}

else{he=hb;pb=hb->link;pa=ha;}

pc=he;

while(pa&&pb)

if(pafdata<=pbfdata)

{pc->link=pa;pc=pa;

pa=p-flink__________________；

else

{peflink=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.EsQueue(r)];

while(s){

t=sflink;

while(t!=0&&s~^data<=t->data){s=t;t=t->link;}

if(t){

s-*link=0;s=t;Q.EnQueue(s);

while(!Q.IsEmpty()){

r=Q.DlQueue();

if(Q.IsEmpty())break;

s=Q.DlQueue();

merge(r,s,t);|Q.EnQueue(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(tc*pnotinhead^^);

q->next=p->next;

free(p);

)

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

閱讀以卜程序請回答該程序所實現(xiàn)的功能：

template<classtype>

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

if(t!=Null){

a[]=t->getData();

linkedtosequent(t->getleftchild(),a,2*i+l);

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

}}

主程序調(diào)用方式：Iinkedtosequent(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*key)%10+1,尋找下一個

空位的公式為Hi=(Hi-1+RH(key))%13,Hl=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

1111114121

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

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

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

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

利用雙散列法造表：

Hi=(Hi-1+RH(key))%13^Hi=H(key)

0123456789101112

78150357452031362312

1111113511

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

intPrime(intn){

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

while(i<=x){

if(n%i==O)break;

if

}

iRi>x)return1;

elsereturn0;

}

(2)intsum1(intn){

intp=l,s=O;

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

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

returns;

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

0,該算法的時間復(fù)雜度為O(sqrt(n)).

(2)程序功能是計算Eni=li!,該算法的時間復(fù)雜度為O(n).

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

處填入正確的語句。

intsymmetry(DbIListDL){

intsym=l;

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

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

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

p=p->rLink;

q=q->lLink;

)

elsesym=0;

returnsym;}

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

#include"stack.h"

intBaseTrans(intN,intB)