2007年11月軟件設(shè)計師模擬試題（4）下午試卷

 
圖 3
s
●試題三
閱讀下列函數(shù)說明和C函數(shù)，將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【函數(shù)3說明】
函數(shù)DeleteNode(Bitree*r,int e)的功能是：在樹根結(jié)點指針為r的二叉查找(排序)樹上刪除鍵值為e的結(jié)點，若刪除成功，則函數(shù)返回0，否則函數(shù)返回-1。二叉查找樹結(jié)點的類型定義為：
typedef struct Tnode{
int data;/*結(jié)點的鍵值*/
struct Tnode*Lchild,*Rchild;/*指向左、右子樹的指針*/
}*Bitree;
在二叉查找樹上刪除一個結(jié)點時，要考慮三種情況：
①若待刪除的結(jié)點p是葉子結(jié)點，則直接刪除該結(jié)點;
②若待刪除的結(jié)點p只有一個子結(jié)點，則將這個子結(jié)點與待刪除結(jié)點的父結(jié)點直接連接，然后刪除結(jié)點p;
③若待刪除的結(jié)點p有兩個子結(jié)點，則在其左子樹上，用中序遍歷尋找關(guān)鍵值最大的結(jié)點s ,用結(jié)點s的值代替結(jié)點p的值，然后刪除結(jié)點s，結(jié)點s必屬于上述①、②情況之一。
【函數(shù)3】
int DeleteNode(Bitree*r,int e){
Bitree p=*r,pp,s,c;
while(  (1)  ){/*從樹根結(jié)點出發(fā)查找鍵值為e的結(jié)點*/
pp=p;
if(e＜p-＞data)p=p-＞Lchild;
else p=p-＞Rchild;
}
if(!p)return-1;/*查找失敗*/
if(p-＞Lchild &&p-＞Rchild) { /*處理情況③*/
s=  (2)  ;pp=p;
while(  (3)  ){pp=s;s=s-＞Rchild;}
p-＞data=s-＞data;p=s;
}
/*處理情況①、②*/
if(  (4)  )c=p-＞Lchild;
else c=p-＞Rchild;
if(p==*r)*r=c;
else if(  (5)  )pp-＞Lchild=c;
else pp-＞Rchild=c;
free(p);
return 0;
}

2007計算機軟件水平考試沖刺專題

2007計算機軟件水平考試模擬試題匯總

希望與其他軟考考生進行交流？點擊進入軟考論壇>>>

進入考試吧博客記錄下自己的備考?xì)v程吧

更多信息請訪問：考試吧軟件水平考試欄目