數(shù)據(jù)結(jié)構(gòu)期末考試試卷（B卷）

第一學(xué)期

開課單位：軟件學(xué)院，考試形式：閉、開卷，允許帶入場(chǎng)

科目：數(shù)據(jù)結(jié)構(gòu)班級(jí):軟件工程姓名:學(xué)號(hào)：

題序—■二三四五六七八九總分

得分

評(píng)卷人

I.基本概念部分（共60分）

1下圖所示是單鏈表結(jié)點(diǎn)的刪除過程，在fence結(jié)點(diǎn)后面刪除一個(gè)值

為10的結(jié)點(diǎn)，已知fence->next是指向fence的后繼結(jié)點(diǎn)，Itmp是

一個(gè)值為NULL的鏈表結(jié)點(diǎn)指針，請(qǐng)把這一刪除過程用代碼表示出來:

（4分）

fence

⑻

(b)

這一過程的代碼:

Itmp=fence->next;

fence->next=ltmp->next;

2下圖所示是雙鏈表結(jié)點(diǎn)的插入過程，在fence結(jié)點(diǎn)后面插入一個(gè)值

為10的Itmp結(jié)點(diǎn)，已知fence->next是指向fence的后繼結(jié)點(diǎn)，

fence->prev是指向fence的前驅(qū)結(jié)點(diǎn)，請(qǐng)把這一插入過程用代碼表

示出來：（8分）

fence

^4l20lt|^l23|-

Insert10:~FT1

這一過程的代碼:

ltmp->next=fence->next;

1tmp->next->prev=Itmp;

fence->next=Itmp;

ltmp->prev=fence;

3畫出下圖中的BST刪除值7以后的形狀。（8分）

2437

40

11.1.6刪除

對(duì)刪除來說，我們考慮包含被刪除元素的節(jié)點(diǎn)P的三種情況：1）p是樹葉；2）

P只有一個(gè)非空子樹；3）p有兩個(gè)非空子樹。

情況1）可以用丟棄樹葉節(jié)點(diǎn)的方法來處理。要?jiǎng)h除圖ll-3b所示樹中的35,

只要把其父節(jié)點(diǎn)的左孩子域置為零，然后刪除該節(jié)點(diǎn)即可，刪除后結(jié)果如圖

H-3a所示。要從樹中刪除80,只要把節(jié)點(diǎn)40的右孩子域置為零并丟棄節(jié)點(diǎn)

80,其結(jié)果如圖11Tb所示。

接下來考察情況2）。如果p沒有父節(jié)點(diǎn)（即p是根節(jié)點(diǎn)），則將p丟棄，p的

唯一子樹的根節(jié)點(diǎn)成為新的搜索樹的根節(jié)點(diǎn)。如果P有父節(jié)點(diǎn)PP，則修改PP的

指針，使得PP指向P的唯一孩子，然后刪除節(jié)點(diǎn)P。例如，如果希望從圖lb3b

的樹中刪除關(guān)鍵值為5的元素，則修改該元素父節(jié)點(diǎn)的左孩子域，使其指向關(guān)鍵

值為2的節(jié)點(diǎn)。

最后，要?jiǎng)h除一個(gè)左右子樹都不為空的節(jié)點(diǎn)中的元素，只需將該元素替換為它的

左子樹中的最大元素或右子樹中的最小元素。

4畫出對(duì)下列存儲(chǔ)于數(shù)組中的值執(zhí)行buildheap后得到的最大值堆:

（8分）

105123218794

129107418532

或

5給出下圖從頂點(diǎn)1開始的BFS樹。（8分）

直接在下面的頂點(diǎn)中畫出來即可:

6給出下圖從頂點(diǎn)1開始的最大支撐樹。（8分）

直接在下面的頂點(diǎn)中畫出來即可:

7插入排序函數(shù)的算法如下：(8分)

voidinssort(intA口，intn){

inttmp;

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

(

for(intj=i;j>06&A[j]<A[j-1];j—){

tmp=A[j];

A[j]=A[j-1];

A[j-1]=tmp;

〃外層循環(huán)，打印一下中間結(jié)果

for(intk=0;k<n;k++)printfC%d，/,A[k]);

printf('\n");

對(duì)數(shù)組

intA[]={9,12,3,7,90,15};

應(yīng)用上面的排序算法進(jìn)行排序的部分中間打印結(jié)果如下，請(qǐng)補(bǔ)充使之完整:

第1次外層循環(huán)的中間結(jié)果:912379015

第2次外層循環(huán)的中間結(jié)果：391279015

第3次外層循環(huán)的中間結(jié)果：379129015

第4次外層循環(huán)的中間結(jié)果：379129015

第5次外層循環(huán)的中間結(jié)果：379121590

8樹的順序表示法中，有一種方法使用特殊標(biāo)記“)”來標(biāo)記子結(jié)點(diǎn)

表的結(jié)束。所有葉子結(jié)點(diǎn)后面都跟著一個(gè)“)”(因?yàn)樗鼈儧]有子結(jié)點(diǎn)),

一個(gè)葉子結(jié)點(diǎn)如果是其父結(jié)點(diǎn)的最后一個(gè)子結(jié)點(diǎn)，則其后將有兩個(gè)或

更多連續(xù)的

對(duì)于上圖，則其結(jié)點(diǎn)表為："RAC)D)E))BF)))”；

現(xiàn)有結(jié)點(diǎn)表為“XPC)Q)RV)M))))"，請(qǐng)畫出樹的形狀。(8分)

II.算法填空部分(每空一條語句或表達(dá)式，填在本大題后面的標(biāo)號(hào)

線上，每空2分，共30分)

1已知q是一個(gè)非空隊(duì)列，s是一個(gè)空棧。僅用棧和隊(duì)列的ADT函數(shù)

編寫一個(gè)算法，使得q中的元素倒置，函數(shù)的原型及部分代碼如下，

請(qǐng)補(bǔ)足代碼使之功能完整。

template<classElem>

Queue<Elem>*reverseQueue(Queue<Elem>*q){

Stack<int>*s;〃聲明一個(gè)棧指針

intel;

〃實(shí)例化一個(gè)棧

s=newLStack<int>(20);

〃把隊(duì)列中的元素入棧

while(q->dequeue(el))(1);

〃把棧中的元素入隊(duì)

while(s->pop(el))(2);

returnq;

)

⑴s->push(el)

(2)q->enqueue(el)

2編寫一個(gè)算法，傳入?yún)?shù)為二叉樹根結(jié)點(diǎn)的指針，并按照層次順序

將結(jié)點(diǎn)的值打印出來。層次順序首先打印根結(jié)點(diǎn)，接著是第1層的所

有結(jié)點(diǎn)，再接著是第2層的所有結(jié)點(diǎn)，以此類推。下面給出了部分代

碼，請(qǐng)補(bǔ)齊使之完整。

template<classElem>

voidhirarchyPrint(BinNode<Elem>*rt){

intptr;

Queue<int>*q;

BinNode<int>*btr;

q=newLQueue<int>();

〃把所有的結(jié)點(diǎn)指針值入隊(duì)

if(rt!=NULL)q->enqueue((int)rt);

while(q->length()>0){

q->dequeue(ptr);

btr=(BinNode<int>*)ptr;

cout?，zz，?btr->val()?zz〃；

if(btr->left()!=NULL)q->enqueue((3));

if(btr->right()!=NULL)q->enqueue((4));

cout<<endl;

}

(3)(int)btr->left()

(4)(int)btr->right()

3編寫一個(gè)遞歸函數(shù)printRange,傳入一個(gè)BST,一個(gè)較小值和一個(gè)

較大值，按照順序打印出介于兩個(gè)值之間的所有結(jié)點(diǎn)。函數(shù)

printRange應(yīng)盡可能少地訪問BST的結(jié)點(diǎn)。下面給出了部分代碼，

請(qǐng)補(bǔ)齊使之完整。

template<classKey,classElem,classKEComp>

voidprintRange(BinNode<Elem>*root,Keylow,Keyhi){

if(root==NULL){

(5);//return

F

else{

//

if(KEComp::It(hi,root->val())){

〃僅在左子樹中遞歸

(6);//printRange(root->left(),low,hi);

}else{

if(KEComp::It(low,root->val())){

cout<<z，z，<<(root->val()).key();

printRange(root->left(),low,hi);

printRange(root->right0,low,hi);

)

else{

if(KEComp::eq(1ow,root->val())){

}

〃僅在右子樹中遞歸

(7);//printRange(root->right(),low,hi);

)

)

}

)

4編寫一個(gè)函數(shù)，它以一棵樹的根為輸入，返回一棵二叉樹。提示：

樹使用左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)表示法。下面給出了部分代碼，請(qǐng)補(bǔ)齊

使之完整。

template<classElem>

BinNode<Elem>*TreeToBinTree(GTNode<Elem>*rt){

BinNodePtr<Elem>*bptr=NULL;

if(rt!=NULL){

〃以當(dāng)前樹結(jié)點(diǎn)值為值構(gòu)造一個(gè)二叉樹的結(jié)點(diǎn)

bptr=newBinNodePtr(rt->value0,NULL,NULL);

〃把樹的最左子結(jié)點(diǎn)為根的樹構(gòu)造成二叉樹的左子樹

bptr->setLeft((8))；//TreeToBinTree(rt->leftmost_child())

〃把樹的右兄弟結(jié)點(diǎn)為根的樹構(gòu)造成二叉樹的右子樹

bptr->setRight((9))；//TreeToBinTree(rt->right_sibling())

)

else{

returnNULL;

)

return(10)；//bptr

)

5寫一個(gè)算法以確定有n個(gè)頂點(diǎn)的無向圖是否包含回路，代碼已經(jīng)給

出，其中空位的地方需要你來補(bǔ)上。

〃判斷是否存在環(huán)的方法,檢查所有可能的連通分量

#defineUNVISITED0

SdefineVISITED1

boolisExistRing(Graph*G){

boolbr=false;

for(intv=0;?;v++){//v<G->n()

〃考慮圖的所有頂點(diǎn)

if(0^==UNVISITED){//G->getMark(v)

br=br|LookRing(G,0,-1);

returnbr;

/*

*從頂點(diǎn)pre開始,利用深度優(yōu)先搜索

*在同一個(gè)連通分量類，如果找到了一個(gè)曾經(jīng)被訪問過的頂點(diǎn)

*即說明此無向圖存在環(huán)

*/

boolLookRing(Graph*G,intv,intpre){

boolbr=false;

O^G->setMark(v,VISITED);〃設(shè)置該頂點(diǎn)被訪問

for(intw=G->first(v);w<Q4)G->e()_;w=G->next(v,w)){

if(09==VISITED){//G->getMark(w)

if(w!=pre)

br=true;〃存在環(huán)

}else

br=br||L