期末考試數(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)與動(dòng)態(tài)結(jié)構(gòu)

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

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

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

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

3、采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí)，搜索成功的平均搜索長(zhǎng)度為

(D)o

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

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

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個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè)，采用(C)方

法最好。

A起泡排序B堆排序C錦標(biāo)賽排序D快速排序

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

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

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

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

該數(shù)組至少需要的存儲(chǔ)字?jǐn)?shù)是(c)。

A80B100C240D270

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

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

9、一個(gè)隊(duì)列的進(jìn)隊(duì)列順序是1,2,3,4,則出隊(duì)列順序?yàn)?C)。

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

front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是(D)。

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

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

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

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

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

A指針B引用C值D變量

13、下面程序段的時(shí)間復(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、下面程序段的時(shí)間復(fù)雜度為(B)

intf(unsignedintn){

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

elsereturnn*f(n-1);

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

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

(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分析算法的效率以求改進(jìn)

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

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

則執(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é)點(diǎn)結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)

的直接前驅(qū)，若在*q與*P之間插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行下列哪一個(gè)操作(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é)點(diǎn)結(jié)構(gòu)為(data,link).若想摘除結(jié)點(diǎn)*p的直接后繼，則應(yīng)執(zhí)

行下列哪一個(gè)操作(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é)點(diǎn)的結(jié)構(gòu)為（data,link），且rear是指向非空的帶表頭

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

哪一個(gè)操作（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é)點(diǎn)的結(jié)構(gòu)為（data,link）,且first為指向鏈表表頭的指

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

語(yǔ)句是（D）o

Acurrent->link=nullBfirst->link=current

Cfirst=currentDcurrent->link=first

23、一個(gè)棧的入棧序列為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、棧和隊(duì)列的共同特點(diǎn)是（C）o

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

C只允許在端點(diǎn)處插入和刪除D沒(méi)有共同點(diǎn)

26、假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為f和r,則判斷隊(duì)空

的條件為（D）.

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

27、當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（B）

An-2Bn-1CnDn+1

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

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

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

29、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔?。若?/p>

摘除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到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)隊(duì)列的結(jié)構(gòu)是：

constintMaxsize=100;

typedefintDataType;

typedefstruct{

DataTypedata[Maxsize];

Intfront,rear;

}Queue;

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

(D)

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

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

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

intfact(intn)

{if(n<=0)return1;

elsereturnn*fact(n-l);

)

下面正確的敘述是(B)

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

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

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

intx(intn){

if(n<=3)return1;

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

)

試問(wèn)計(jì)算x(x(8))時(shí)需要計(jì)算(D)次x函數(shù)。

A8次B9次C16次D18次

33、設(shè)有廣義表D(a,b,D),其長(zhǎng)度為(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、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是(B)的二叉

樹(shù)

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

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

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

(A)

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

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

路徑長(zhǎng)度為(B)

A24B73C48D53

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

點(diǎn)的地址為dal,則第I個(gè)結(jié)點(diǎn)的地址為(A)。

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

41、34具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(A)

A5B6C7D8

42、對(duì)線性表進(jìn)行折半搜索時(shí)，要求線性表必須(C)

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

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

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

A散列存儲(chǔ)B順序存儲(chǔ)或鏈接存儲(chǔ)

C壓縮存儲(chǔ)D索引存儲(chǔ)

44、采用折半搜索算法搜索長(zhǎng)度為n的有序表時(shí)，元素的平均搜索長(zhǎng)度為

(C)

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

45、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，進(jìn)行拓?fù)渑判驎r(shí)，總的時(shí)間為

(A)

AnBn+1Cn-lDn+e

46、判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利

用(C)。

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

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

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

A1B2C9D10

48、對(duì)包含n個(gè)元素的散列表進(jìn)行搜索，平均搜索長(zhǎng)度為(C)

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

2、填空題（）

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

種

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

種

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

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

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

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

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

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

8、串是由（零個(gè)或多個(gè)）字符組成的序列。（長(zhǎng)度為零的串）稱為空串，

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

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

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

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

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

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

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

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

（棧頂指針）。

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

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

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

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

樹(shù)中的結(jié)點(diǎn)數(shù)為（85）個(gè)。

15、若對(duì)一棵二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維

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

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

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

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

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

元，第一個(gè)元素的地址為L(zhǎng)OC（al）,那么，L0C（ai）=LOC（al）+（iT）*k。

18、在霍夫曼編碼中，若編碼長(zhǎng)度只允許小于等于4,則除掉已對(duì)兩個(gè)字符編碼

為0和10外，還可以最多對(duì)（4）個(gè)字符編碼。

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

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

（2h+l）個(gè)。

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

21、以折半搜索方法搜索一個(gè)線性表時(shí)，此線性表必須是（順序）存儲(chǔ)的（有序）

表。

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

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

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

想平衡樹(shù)）。

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

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

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

有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有（n（n-l）/2）條邊，在一個(gè)具有n個(gè)頂

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

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

為（n）和（n-1）o

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

的存儲(chǔ)位置是（1044）o

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

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

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

條（指令）表示一個(gè)或多個(gè)操作。

30、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)肯e條邊的無(wú)向圖，進(jìn)行拓樸排序時(shí)，總的進(jìn)間為

（n）

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

位）法。

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

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

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

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

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

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

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

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

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

［4080］）

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

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

0］）。

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

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

樹(shù)中各結(jié)點(diǎn)度的（最大值）稱為樹(shù)的度。

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、在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為（0

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

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

項(xiàng)。

42、假定一個(gè)線性表為

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

ayb”），若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子

表中，則得到的a,b,c三個(gè)子表的長(zhǎng)度分別為（3）,（3）,（2）o

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

（5）o

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

樹(shù)的高度（減1）

45、假定要對(duì)長(zhǎng)度n=100的線性表進(jìn)行散列存儲(chǔ)，并采用開(kāi)散列法處理沖突，

則對(duì)于長(zhǎng)度m=20的散列表，每個(gè)散列地址的同義詞子表的長(zhǎng)度平均為（5）。

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

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

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

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

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

中的（邊數(shù)）。

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

為（m-1）個(gè)，其子樹(shù)棵數(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)具備三種基本運(yùn)算：插入、刪除、搜索（。

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

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

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

配。（V）

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

12、完全二叉樹(shù)就是滿二叉樹(shù)。（X）

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

（V）

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

和。（V）

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

也相鄰。（-J)

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

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

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

的順序表的平均搜索時(shí)間。（X）

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

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

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

的二叉搜索樹(shù)都是相同的（X）。

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

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

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

（V）

24、任何無(wú)環(huán)的有向圖，其結(jié)點(diǎn)都可以排在一個(gè)拓?fù)湫蛄欣?。（J）

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

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

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

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

28、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適

用。（X）

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

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

31、關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。（J）

32、平衡二叉樹(shù)的左右子樹(shù)深度之差的絕對(duì)值不超過(guò)1。（J）

33、快速排序是對(duì)起泡排序的一種改進(jìn)。（V）

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

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

36、在散列法中采取開(kāi)散列法來(lái)解決沖突時(shí)，其裝載因子的取值一定在（0,

1）之間。（X）

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

（X）

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

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

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

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

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

元素時(shí)，需要向后移動(dòng)多少個(gè)元素？

答案：需要向后移動(dòng)n-J+1個(gè)元素

2、當(dāng)一個(gè)棧的進(jìn)棧序列為1234567時(shí)，可能的出棧序列有多少種？6457321

是否是合理的出棧序列？

答案:

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

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

可能的出棧序列有

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

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

答案：是不穩(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},采用折半搜索時(shí)，

搜索成功的平均搜索長(zhǎng)度是多少？

答案：

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

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

個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)

點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？

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

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

個(gè)分支結(jié)點(diǎn)。

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

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

序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào)，試問(wèn):

(1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少？

(2)編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少？

(3)編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少？

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

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

答案：

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

(2)編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是>-(i+k-2)/kJ

(3)編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是(iT)*k+m+l

(4)當(dāng)(iTKk〈〉O時(shí)有右兄弟，右兄弟的編號(hào)為i+1

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

時(shí)h=-l)

7、寫出下列中綴表達(dá)式的后綴形式：

(1)A*-B+C

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

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

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

答案：各中綴表達(dá)式的后綴形式如下：

(1)AB-*C+

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

(3)AB&&EF>!||

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

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

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

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

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

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

廣義表（1）的存儲(chǔ)表示為:

廣義表（2）的存儲(chǔ)表示為:

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

答案:

A

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

11、根據(jù)所給有向圖，寫出一個(gè)拓?fù)湫蛄小?5分)

答案:

其中的一個(gè)拓?fù)湫蛄袨?VI,V2,V3,V4,V5,V6,V7

12、將給定的圖簡(jiǎn)化為最小的生成樹(shù)，要求從頂點(diǎn)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è)計(jì)赫夫曼編碼。

答案：

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

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

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、已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是

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

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

這棵二叉樹(shù)的后序遍歷序列為：EDbJJjGFA

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

個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)

點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？

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

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

個(gè)分支結(jié)點(diǎn)。

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

個(gè)結(jié)點(diǎn)的AVL樹(shù)，其最大高度是多少？最小高度是多少？

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

A是斐波那契數(shù)。乂設(shè)AVL樹(shù)有n個(gè)結(jié)點(diǎn)，則其最大高度不超過(guò)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。試畫出對(duì)其進(jìn)行折半搜索時(shí)的判定樹(shù)，并計(jì)算

搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。

答案：折半搜索時(shí)的判定樹(shù)為

76人Q0

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

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

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

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

(2)求每個(gè)事件的最早開(kāi)始時(shí)間Ve[i]和最遲開(kāi)始時(shí)間Vl[i]o

(3)求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間/()。

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

加速可使整個(gè)工程提前完成。

答案：按拓樸有序的順序計(jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間V。和最遲允許開(kāi)始

時(shí)間V”然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間1,根

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

①③②④⑤⑥

Vo01915293843

Vi01915373843

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

e00151919152938

L170152719273738

1-e1700801280

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

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

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

答案：

第一次排序：(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個(gè)記錄要存儲(chǔ)到散列表中，并利用線性探查法解決沖突，要求

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

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

答案：已知要存儲(chǔ)的記錄數(shù)為n=150,查找成功的平均查找長(zhǎng)度為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è)計(jì)225個(gè)單位。

五、算法分析題

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

voidunknown(intIF){

if（獷）{

unknown(曠1);

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

cout<<endl;

}

)

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

答案：

(1)1

22

333

4444

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

voidunknown(intn){

COUt<<Z7%10;

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

)

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

答案：285

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

intunknown(intm){

intvalue;

if(!")value-3;

elsevalue=unknown(zzrl)+5;

returnvalue;

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

答案：18

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

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

表示用10進(jìn)制表示。

答案：設(shè)數(shù)組元素存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中。

因?yàn)椋篖oc⑵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;

)；

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

不另外占用存儲(chǔ)空間，排序過(guò)程中不移動(dòng)結(jié)點(diǎn)中的元素，只改各鏈結(jié)點(diǎn)中的指

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

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

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

并段的鏈頭指針。初始時(shí)，各初始?xì)w并段為只有一個(gè)結(jié)點(diǎn)的有序鏈表。隊(duì)列的

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

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

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

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

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

解決方法提示：

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

表，其表頭指針存放在一個(gè)指針隊(duì)列中。

＞當(dāng)隊(duì)列不空時(shí)，從隊(duì)列中退出兩個(gè)有序子鏈表，對(duì)它們進(jìn)行二路歸并,

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

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

子鏈表即為所求。

在算法實(shí)現(xiàn)時(shí)有6處語(yǔ)句缺失，請(qǐng)閱讀程序后補(bǔ)上。

(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、請(qǐng)讀下列程序，該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法，為空出的地方填

上正確的語(yǔ)句。(7分)

voiddemo2(LinkListhead,ListNode*p)

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

ListNode*q=head;

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

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

q->next=p~~>next;

free(p);

}

7、已知一完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始，自頂向下，同一層自左向右連續(xù)編號(hào)，

根結(jié)點(diǎn)的編號(hào)為0,閱讀以下程序請(qǐng)回答該程序所實(shí)現(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);

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

(數(shù)組)表示。

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

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

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

下搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。

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

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

相應(yīng)的散列表，并計(jì)算等概率下搜索成功的平均搜索長(zhǎ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

搜索成功的平均搜索長(zhǎng)度為：

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

搜索不成功的平均搜索長(zhǎng)度為：

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、閱讀下面程序，指出其算法的功能并求出其時(shí)間復(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是否是?個(gè)素?cái)?shù)，若是則返回?cái)?shù)值1,

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

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

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

在算法的處填入正確的語(yǔ)句。

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;

)

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

數(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;

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

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

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

索樹(shù)。

六、綜合算法題

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

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