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

杭電期末試卷復(fù)習(xí)題

一、單選題(每題2分，共20分)

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

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

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

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

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

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

A.僅修改頭指針B.頭、尾指針都要修改

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

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

A.隊(duì)列B.棧C.線性表D.二叉樹

4.4.設(shè)有一個二維數(shù)組A[詞[用，假設(shè)⑼存放位置在644(”》,A⑵⑵存放位置在676,助，每個

元素占一個空間，問A⑶[3]＜助存放在什么位置？腳注(助表示用10進(jìn)制表示。CC

A.688B.678C.692D.696

5.5.樹最適合用來表示(C)。C

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

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

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

A.2kD.2k''

7.7.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[l]中，現(xiàn)進(jìn)行二分查找，

則查找A[3]的比較序列的下標(biāo)依次為(B)D

A.1,2,3B.9,5,2,3

C.9,5,3D.9,4,2,3

8.8.對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為BC

A.O(1)B.O(n)C.O(log2n)D.O(n2)

9.9.對于線性表(7,34,55,25,64,46,20,10)進(jìn)行散列存儲時，若選用H(K)=K%9

作為散列函數(shù)，則散列地址為1的元素有(D)個，D

A.1B.2C.3D.4

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

二、填空題(每空1分，共26分)

1.I.通常從四個方面評價算法的質(zhì)量：正確性、易讀性、強(qiáng)壯性和高效性。

2.2.一個算法的時間復(fù)雜度為("3+”2]og2”+i4")/"2,其數(shù)量級表示為O(n)。

3.3.假定一棵樹的廣義表表示為A(C,D(E,F,G),H(I,J)),則樹中所含的結(jié)點(diǎn)數(shù)為9個，

樹的深度為3,樹的度為3。

4.4.后綴算式923+-102/-的值為。中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為

5.5.若用鏈表存儲?棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針.在

這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有2n個指針域，其中有n-l個指針域是存放

了地址，有n+1個指針是空指針。

6.6.對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有

c個和2e個。

7.7.AOV網(wǎng)是一種有向無回路的圖。

8.8.在一個具有n個頂點(diǎn)的無向完全圖中，包含有n(n-l)/2條邊，在一個具有n個頂點(diǎn)的

有向完全圖中，包含有n(n-l)條邊。

9.9.假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為

一個子表，則得到的四個子表分別為(12,40)、()

、(74)和(23,55,63)<,

10.10.向一棵B/對插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度增加一

11.11.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為O(log2n)，整個堆排

序過程的時間復(fù)雜度為O(nlog2n

12.12.在快速排序、堆排序、歸并排序中，歸并_排序是穩(wěn)定的。

三、運(yùn)算題(每題6分，共24分)

1.1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next,試寫出該線性表。

A01234567

data605078903440

next3572041

2.2.請畫出圖10的鄰接矩陣和鄰接表。

3.3.己知一個圖的頂點(diǎn)集V和邊集E分別為：

V={1,2,3,4,567};

E=((l,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依

次得到的各條邊。

4.4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。

四、閱讀算法(每題7分，共14分)

1.1.LinkListmynote(LinkListL)

{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

if(L&&L->next){

q=L；L=L->next；p=L；

S1：while(p->next)p=p->next；

S2：p—>next=q；q—>next=NULL；

}

returnL；

I

請回答下列問題：

(1)說明語句S1的功能；

(2)說明語句組S2的功能；

(3)設(shè)鏈表表示的線性表為(ai,a2,…,即)，寫出算法執(zhí)行后的返回值所表示的線性表。

2.2.voidABC(BTNode*BT)

(

ifBT(

ABC(BT->left);

ABC(BT->right);

cout?BT->data?'\

)

I

該算法的功能是：

五、算法填空(共8分)

二叉搜索樹的查找——遞歸算法：

boolFind(BTrecNode*BST,EIcmTypc&item)

(

if(BST==NULL)

returnfalse;〃查找失敗

else{

if(item==BST->data){

item二BST->data;〃查找成功

returntrue;}

elseif(item<BST->data)

returnFind(_BST->eft_,item);

elsereturnFind(_BST->ight____,item);

}//if

}

六、編寫算法(共8分)

統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。

intCountX(LNode*HL,ElemTypex)

參考答案

單選題(每題2分，共20分)

填空題(每空1分，共26分)

正確性易讀性強(qiáng)壯性高效率

2.2.O(n)

3.3.933

4.4.-134X*+2Y*3/-

5.5.2nn-1n+1

6.6.e2e

7.7.有向無回路

8.8.n(n-l)/2n(n-l)

9.9.(12,40)()(74)(23,55,63)

10.10.增加1

11.11.O(log2n)O(nlog2n)

12.12.歸并

三、運(yùn)算題(每題6分，共24分)

1.1.線性表為：(78,50,40,60,34,90)

'01110'

10101

11011

10101

2.2.鄰接矩陣：01110

鄰接表如圖11所示：

圖11

3.3.用克魯斯卡爾算法得到的最小生成樹為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

4.4.見圖12

四、④,興盤鼻僦

i.i.(10旬鏈表的尾結(jié)！3?@?@QG

(2)將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)發(fā)「

(3)返回的線性表為(a2,a3j“,a?,ai)9也

2.2.遞歸地后序遍歷鏈?zhǔn)酱鎯Β遣鏄洹?/p>

五、算法填空(每名工行燼分)

trueBST->left------?B(^ight臺)

六、六、爐短界淙48分)

intCountX(LNode*HL,Elen/g\/4)

{inti=0;LNode*p=HL^Z/為器

while(p!=NULL)

{if(P->data=x)i++;

p=p->next;

"/while,出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù)

returni;

)//CountX

一、一、單選題(每小題2分，共8分)

1、1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度(即x與元

素的平均比較次數(shù)，假定查找每個元素的概率都相等)為(B)oC

AnBn/2C(n+l)/2D(n-l)/2

2、2、在一個單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入一個s所指的結(jié)點(diǎn)，則

執(zhí)行(D)o

As->link=p->link;p-*-link=s;Bp->link=s;s_>link=q;

Cp-*link=s-*link;s-*link=p;Dq-link=s;s-*link=p;

3、3、棧的插入和刪除操作在(A)進(jìn)行。

A棧頂B棧底C任意位置D指定位置

4、4、由權(quán)值分別為11,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為(B)

A24B71C48D53

二、二、填空題(每空1分，共32分)

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

2、2、一種抽象數(shù)據(jù)類型包括—數(shù)據(jù)描述和一操作聲名兩個部分。

3,3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next,則該線性表為一(38.

56,25,60,42,74,)______________________

a012345678

605642387425

4376201

4、4、在以

HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為

和?

5、5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的

,該循環(huán)隊(duì)列的最大長度為。

6、6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用--------------表示；當(dāng)堆棧采用鏈接存儲

結(jié)構(gòu)時，棧頂元素的值可用表示。

7、7、一棵高度為5的二叉樹中最少含有個結(jié)點(diǎn)，最多含有個結(jié)點(diǎn)；

一棵高度為5的理想平衡樹中，最少含有個結(jié)點(diǎn)，最多含有個結(jié)點(diǎn)。

8、8、在圖的鄰接表中，每個結(jié)點(diǎn)被稱為,通常它包含三個域：一是；

二是;三是■>

9、9、在一個索引文件的索引表中，每個索引項(xiàng)包含對應(yīng)記錄的和兩項(xiàng)數(shù)據(jù)。

10,10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))),則樹中所含的

結(jié)點(diǎn)數(shù)為個，樹的深度為，樹的度為,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為,

孩子結(jié)點(diǎn)為.

11、11、在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為，整個堆排

序過程的時間復(fù)雜度為。

12、12、在對m階的13_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項(xiàng)(葉子結(jié)點(diǎn)中的

索引項(xiàng)為關(guān)鍵字和空指針)后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于個，則必須把它分裂為

個結(jié)點(diǎn)。

三、三、運(yùn)算題(每小題6分，共24分)

1、1、已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫出對其進(jìn)行快速排序的每

一次劃分結(jié)果。

2、2、一個線性表為B=(12,23,45,57,20,03,78.31,15,36),設(shè)散列表為HT(0..12],散

列函數(shù)為H(key)=key%13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查

找成功的平均查找長度。

3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,

試寫出這棵二叉樹的后序遍歷結(jié)果。

4、4、已知一個圖的頂點(diǎn)集V各邊集G如下：

V=(0,1,2,3,4,5,6,7,8,9)；

E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8).(5,6),(5,8),(5,9),(6,7),

(7,8),(8,9))

當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點(diǎn)Vo出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和

按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。

假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。

圖深度優(yōu)先序列廣度優(yōu)先序列

鄰接矩陣表示時

鄰接表表示時

四、四、閱讀算法，回答問題(每小題8分，共16分)

1、假定從鍵盤上輸入一批整數(shù)，依次為：786345309134-1,請寫出輸出結(jié)果。

consstintstackmaxsize=30;

typedefintelemtype;

structstack{

elemtypestack[stackmaxsize];

inttop;

)；

#include

Voidmain()

{

stacka;

initstack(a);

intx;

cin?x;

while(x!=-1){

push(a,x);

cin?x;

)

while(Jstackempty(a))

cout?pop(a)；

cout?end1;

)

該算法的輸出結(jié)果為：

2、閱讀以下二叉樹操作算法，指出該算法的功能。

Template<calsstype>voidBinTree<Type>：:

unknown(BinTreeNode<Type>*t){

BinTreeNode<Type>*p=t,*temp;

if(p!=NULL){

temp=p-*leftchild;

p-*leftchild=pfrightchild;

p-rightchiId=temp;

unknown(p-*leftchild);

undnownCp-*rightchild);

)

)

該算法的功能是：________________________________

五、五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)

對順序存儲的有序表進(jìn)行二分查找的遞歸算法。

intBinsch(ElemTypeA[],intlow,inthigh.KeyTypeK)

(

if(low<=high)

{

intmid=1

if(K==A[midJ.key)

returnmid;

elseif(K<A[mid].key)

return2

else

return3

)

else

return4

六、六、編寫算法(10分)

編寫算法，將一個結(jié)點(diǎn)類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序?yàn)?/p>

3|1.....3n-l>an，則逆序鏈接后變?yōu)?，an，3n-l，......3|o

Voidcontrary(Lnode*&HL)

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

一、單選題(每小題2分，共8分)

題號1234

答案CDAB

二、填空題(每空1分，共32分)

1：集合、線性、樹、圖；

2：數(shù)據(jù)描述、操作聲名；

3：(38,56,25,60,42,74)；

4：HL-*next=NULL；HL=HL-*next；

5：前一個位置；n-1；

6：—data;

7：531

8：邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；

9：索引值域、開始位置域：

10：10、3、3、B、I和J；

11：O(log2n)、O(nlog2n);

12：m、m-1

三、運(yùn)算題(每小題6分，共24分)

1、

劃分次序劃分結(jié)果

第一次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

0123456789101112

78150357452031233612

查找成功的平均杳找長度：ASLsucc

3、此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA

4、

圖深度優(yōu)先序列廣度優(yōu)先序列

鄰接矩陣表示時0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9

鄰接表表示時0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5

四、閱讀算法，回答問題（每小題8分，共16分）

1、1、該算法的輸入結(jié)果是：349130456378

2、2、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。

五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）

1是

：（low+high）/2;

2是

：Binsch（A,low,mid-1,K）;

3是

：（）

是BinschA,mid+1,high,K;

4

：-1;

六、編寫算法（10分）

根據(jù)編程情況，酌情給分。

（

Lnode*P=HL;

HL=NULL;

While（p!=null）

f

Lnode*q=p;

P=p-*next:

qfnext=HL;

HL=q;

）

）

第一部分選擇題（30分）

一、一、項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項(xiàng)中只有一個選

項(xiàng)是符合題目要求的，請將正確選項(xiàng)前的字母填在題后的括號內(nèi)。

1.算法指的是（）

A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法

C.排序算法D.解決問題的有限運(yùn)算序列

2.線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（）

A.必須是不連續(xù)的

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)

3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（）

A.0(1)B.0(n)C.O(m)D.0(m+n)

4.由兩個棧共享一個向量空間的好處是：（）

A.減少存取時間，降低下溢發(fā)生的機(jī)率

B.節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率

C.減少存取時間，降低上溢發(fā)生的機(jī)率

D.節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率

5.設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其

頭指針front值為（）

A.front=front+1B.front=(front+1)%(m-1)

C.front=(front-1)%mD.front=(front+l)%m

6.如下陳述中正確的是（)

A.串是一種特殊的線性表B.串的長度必須大于零

C.串中元素只能是字母D.空串就是空白串

7.若目標(biāo)串曲長度為n,模式串的長度為[n/3],則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（）

A.0(3)

B.0(n)C.0(n2)D.0(n3)

8.一個非空廣義表的表頭（)

A.不可能是子表B.只能是子表

C.只能是原子D.可以是子表或原子

9.假設(shè)以帶行表的二元組表表示稀疏矩陣，則和下列行表

02335

對應(yīng)的稀疏矩陣是（)

10.在一棵度為3的樹中，度為3的結(jié)點(diǎn)個數(shù)為2,度為2的結(jié)點(diǎn)個數(shù)為1,則度為0的結(jié)點(diǎn)個數(shù)為（）

A.4B.5C.6D.7

11.在含n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）

A.eB.2eC.n2-eD.n2-2e

12.假設(shè)一個有n個頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個頂點(diǎn)環(huán)相關(guān)的所有弧的時間復(fù)雜度

是（）

A.0(n)B.0(e)C.O(n+e)D.O(n*e)

13.用某種排序方法對關(guān)鍵字序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序時,序列的變化情

況如下:

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則所采用的排序方法是（)

A.選擇排序B.希爾排序C.歸并排序D.快速排序

14.適于對動態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是()

A.有序表B.分塊有序表C.三叉排序樹D.線性鏈表

15.不定長文件是指()

A.文件的長度不固定B.記錄的長度不固定

C.字段的長度不固定D.關(guān)鍵字項(xiàng)的長度不固定

第二部分非選擇題(共70分)

二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)不寫解答過程，

將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。

16.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

17.在一個帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為

head=c

18.棧頂?shù)奈恢檬请S著操作而變化的。

19.在串S="structure”中，以t為首字符的子串有個。

20.假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元

素a5則B[31]中存放的元素是。

21.已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有個葉子結(jié)點(diǎn)。

Q22.已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相

應(yīng)的廣度優(yōu)先遍歷序列為__。

義9Y23.在單鏈表上難以實(shí)現(xiàn)的排序方法有和。

(?)Q(g)24.在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時所需進(jìn)行的關(guān)

鍵字比較次數(shù)為。

25.多重表文件和倒排文件都?xì)w屬于文件。

三、解答題(本大題共4小題，每小題5分，共20分)

26.畫出下列廣義表的共享結(jié)構(gòu)圖形表示

P=(((z),(x,y)>,((x,y),x),(z))

27.請畫出與下列二又樹對應(yīng)的森林。

28.已知一個無向圖的頂點(diǎn)集為｛a,b,c,d,e)，其鄰接矩陣如下所示

a(1)畫出該圖的圖形；

b(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。

c29.已知一個散列手如下圖所可：

d3520334859

e0123456789101112

其散列函數(shù)為1I(1<?丫)$€丫％13,處理沖突的方法為雙重散列法，探查序列為:

hi=(h(key)+i*h1(key))%mi=()/,???，m—1

其中

hl(key)=key%ll+l

回答下列問題：

(1)對表中關(guān)鍵字35,20,33和48進(jìn)行查找時，所需進(jìn)行的比較次數(shù)各為多少？

(2)該散列表在等概率查找時查找成功的平均查找長度為多少？

四、算法閱讀題(本大題共4小遍，贏題'5s分，共20分)

30.下列算法的功能是比較兩彳翟串最卜冗$其返回值為：

1當(dāng)S]>s

comstr(si,S2)=2

請?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。

intcomstr(LinkStringsi,LinkStrings2)

{//si和s2為兩個鏈串的頭指針

while(sl&&s2)(

if(sl—>date<s2—>date)retum_1：

if(sl—>date>s2—>date)return1；

①：

②：

I

if(?)return—1；

if(?)retum1；

⑤；

)

?

②

③

④

⑤

31.閱讀下面的算法

LinkListmynote(LinkListL)

{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

if(L&&L->next){

q=L；L=L->next；p=L；

SI：while(p->next)p=p—>next；

S2：p—>next=q；q—>next=NULL；

)

returnL；

(

請回答下列問題：

(1)說明語句SI的功能；

(2)說明語句組S2的功能；

(3)設(shè)鏈表表示的線性表為(ai,a2,…,而)，寫出算法執(zhí)行后的返回值所表示的線性表。

fr皿⑴、⑴32.假設(shè)兩個隊(duì)列共享一個循環(huán)向量空間(參見右下圖),

其類型Queue2定義如下：

frontfOJ

rear[0j,

typedefstruct{

DatcTypcdata[MaxSize]；

intfront[2],rear[2]；

)Qucuc2；

對于i=0或1,fro皿i]和rear[i]分別為第i個隊(duì)列的頭指針和尾指針。請對以下算法填空，實(shí)現(xiàn)第i個

隊(duì)列的入隊(duì)操作。

intEnQueue(Queue2*Q,imi,DateTypex)

{//若第i個隊(duì)列不滿，則元素X入隊(duì)列，并返回1；否則返回0

if(i<O||i>l)return0；

if(Q—>rear[i]==Q—>front[01returnO；

Q—>data[?]=x；

Q—>rear[i]=[?];

returnI；

)

①

②

③

33.已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。

typedefstructnode{

DatcTypcdata；

Structnode*next；

JListNodc；

typedefListNode*LinkList；

LinkListLeafhead=NULL：

VoidInorder(BinTreeT)

(

LinkLists；

If(T){

Inorder(T—>lchild)；

If((!T->lchild)&&(!T->rchild)){

s=(ListNode*)malloc(sizeof(ListNode))；

s—>data=T—>data；

s—>next=Leafhead；

Leafhead=s；

I

Inorder(T—>rchild)；

對于如下所示的二叉樹

(1)畫出執(zhí)行上述算法后所建立的結(jié)構(gòu);

(2)說明該算法的功能。

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

34.閱讀下列函數(shù)arrange()

intarrange(inta[],intLintx)

{//l和h分別為數(shù)據(jù)區(qū)的下界和上界

inti,j,t;

i=l:j=h；

while(i<j)(

while(i<j&&a|j]>=x)j—；

while(i<j&&a[j]>=x)i++；

if(i<j)

{t=a[j]：a[j]=a[i]；a[i]=t；)

}

if(a[i]<x)retunii；

elseretumi_1；

)

(1)寫出該函數(shù)的功能；

(2)寫一個調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素進(jìn)行重新排列，將所有負(fù)數(shù)

均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并

返【可數(shù)組中零元素的個數(shù)。

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

一、一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)

1.D2.B3.C4.B5.D

6.A7,C8,D9,A10.C

11.D12.C13.D14.C15.B

二、填空題(本大題共10小題，每小題2分，共20分)

16.存儲(或存儲結(jié)構(gòu))一>next—>next

18.進(jìn)棧和退棧19.12

20.a4.?21.384

22.abefcdg

23.快速排序、堆排序、希爾排序

24.225.多關(guān)鍵字

三、解答題(本大題共4小題，每小題5分，共20分)

26.仄

?殺卜

27puV

?zxyyxy

該圖的圖形為:

28.a

深度優(yōu)先遍歷序列為：abdcc

廣度優(yōu)先遍歷序列為：abedc

29.(1)對關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、]^dj

1；ASL-3+2+1+1+2_9

(2)平均查找長度55

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

30.①Sl=Si—>ncxt

②s2=s2—>next

③s2(或s2!=NULL或s2&&!sl)

④si(或sl!=NULL或sl&&!s2)

⑤return0

31.(1)查詢鏈表的尾結(jié)點(diǎn)

(2)將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)

(3)返回的線性表為(a2,a3「,,an,ai)

32.①(i+l)%2(或1—i)

②Q—>rear[i]

③(Q—>rear[i]+)%Maxsize

33.(\)Leafhead----?F------?H-----?G------?DA

(2)中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個以Lcafhead為頭指針的逆序單鏈

表(或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個鏈表)。

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

34.(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a□中的元素并返回分界值i,使所有Vx的元素均落在

上，使所有2x的元素均落在a[i+l..h]上。

(2)intf(intb[],intn)或intf(inlb[],intn)

{{

intp,q；intp,q；

p=arrange(b,0,n—1,0)；p=arrange(b,0,n—1,1)；

q=arrange(b,p+l,n-1,1)；q=arrange(b,0,p,0):

returnq-p；returnp-q；

}}

課程測試試題(卷)

..............以下為教師填寫.............

I、命題院(部)：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

IK課程名稱：數(shù)據(jù)結(jié)構(gòu)

Ilk測試學(xué)期：20—20學(xué)年度第學(xué)期

IV、測試對象：學(xué)院專業(yè)級班

V、問卷頁數(shù)（A4）：頁

VI、答卷頁數(shù)（A4）：頁

VII、考試方式：閉卷（開卷、閉卷或課程小論文，請?zhí)顚懬宄?/p>

Vi