2022年下半年河北省C++語言版高級

第第頁2022年下半年河北省C++語言版高級2022年下半年河北省C++語言版高級

1、冒泡排序算法是把大的元素向上移〔氣泡的上浮〕，也可以把小的元素向下移〔氣泡的下沉〕請給出上浮和下沉過程交替的冒泡排序算法。

48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進行排序，請寫出這種排序的算法?！沧ⅲ弘p向起泡排序即相鄰兩趟排序向相反方向起泡〕

2、已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7}

寫出G的拓撲排序的結(jié)果。

G拓撲排序的結(jié)果是：V1、V2、V4、V3、V5、V6、V7

3、設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、…、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。

51.借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。假設(shè)查找勝利，那么輸出該記錄在r數(shù)組中的位置及其值，否那么顯示“notfind”信息。請編寫出算法并簡要說明算法思想。

4、后序遍歷最末訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采納后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當(dāng)訪問到某結(jié)點時，棧中全部元素均為該結(jié)點的祖先。此題要找p和q的最近共同祖先結(jié)點r,不失一般性，設(shè)p在q的左邊。后序遍歷必定先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪粠椭鷹Ｖ?。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到幫助棧中去匹配，第一個匹配〔即相等〕的元素就是結(jié)點p和q的最近公共祖先。

typedefstruct

{BiTreet;inttag;//tag=0表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問

}stack;

stacks[],s1[];//棧，容量夠大

BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。

{top=0;bt=ROOT;

while(bt!=null||top0)

{while(bt!=nullbt!=pbt!=q)//結(jié)點入棧

{s[++top].t=bt;s[top].tag=0;bt=bt-lchild;}//沿左分枝向下

if(bt==p)//不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點

{for(i=1;i=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入幫助棧s1保存

if(bt==q)//找到q結(jié)點。

for(i=top;i0;i--)//；將棧中元素的樹結(jié)點到s1去匹配

{pp=s[i].t;

for(j=top1;j0;j--)

if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}

｝

while(top!=0s[top].tag==1)top--;//退棧

if(top!=0)｛s[top].tag=1;bt=s[top].t-rchild;｝//沿右分枝向下遍歷

}//結(jié)束whil

e(bt!=null||top0)

return(null);//ｑ、p無公共祖先

｝//結(jié)束Ancestor

5、#definema*size?？臻g容量

voidInOutS(int

2022年下半年河北省C++語言版高級

s[ma*size])

//s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。

{inttop=0;//top為棧頂指針，定義top=0時為?？?。

for(i=1;i=n;i++)//n個整數(shù)序列作處理。

{scanf(“%d”,*);//從鍵盤讀入整數(shù)序列。

if(*!=-1)//讀入的整數(shù)不等于-1時入棧。

if(top==ma*size-1){printf(“棧滿\n”);e*it(0);}

elses[++top]=*;//*入棧。

else//讀入的整數(shù)等于-1時退棧。

{if(top==0){printf(“?？誠n”);e*it(0);}

elseprintf(“出棧元素是%d\n”,s[top--])；}

}

}//算法結(jié)

6、給定n個村莊之間的交通圖，假設(shè)村莊i和j之間有道路，那么將頂點i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短?試設(shè)計一個解答上述問題的算法，并應(yīng)用該算法解答如下圖的實例。20分

voidHospital(AdjMatri*w,intn)

//在以鄰接帶權(quán)矩陣表示的n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠的村莊到醫(yī)院的路徑最短。

{for(k=1;k=n;k++)//求任意兩頂點間的最短路徑

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

for(j=1;j=n;j++)

if(w[i][k]+w[k][j]w[i][j])w[i][j]=w[i][k]+w[k][j];

m=MA*INT;//設(shè)定m為機器內(nèi)最大整數(shù)。

for(i=1;i=n;i++)//求最長路徑中最短的一條。

{s=0;

for(j=1;j=n;j++)//求從某村莊i〔1=i=n〕到其它村莊的最長路徑。

if(w[i][j]s)s=w[i][j];

if(s=m){m=s;k=i;}//在最長路徑中，取最短的一條。m記最長路徑，k記出發(fā)頂點的下標。

Printf(“醫(yī)院應(yīng)建在%d村莊，到醫(yī)院距離為%d\n”,i,m);

}//for

}//算法結(jié)束

對以上實例模擬的過程略。各行中最大數(shù)依次是9，9，6，7，9，9。這幾個最大數(shù)中最小者為6，故醫(yī)院應(yīng)建在第三個村莊中,離醫(yī)院最遠的村莊到醫(yī)院的距離是6。

1、對圖1所示的連通網(wǎng)G，請用Prim算法構(gòu)造其最小生成樹〔每選取一條邊畫一個圖〕。

7、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊復(fù)原。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。

voidSpnTree(AdjListg)

//用“破圈法”求解帶

權(quán)連通無向圖的一棵最小代價生成樹。

{typedefstruct{inti,j,w}node;//設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù)

nodeedge[];

scanf(%d%d,e,n);//輸入邊數(shù)和頂點數(shù)。

for

2022年下半年河北省C++語言版高級

(i=1;i=e;i++)//輸入e條邊：頂點，權(quán)值。

scanf(%d%d%d,edge[i].i,edge[i].j,edge[i].w);

for(i=2;i=e;i++)//按邊上的權(quán)值大小，對邊進行逆序排序。

{edge[0]=edge[i];j=i-1;

while(edge[j].wedge[0].w)edge[j+1]=edge[j--];

edge[j+1]=edge[0];}//for

k=1;eg=e;

while(eg=n)//破圈，直到邊數(shù)e=n-1.

{if(connect(k))//刪除第k條邊假設(shè)仍連通。

{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除

k++;//下條邊

}//while

}//算法結(jié)束。

connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，

8、請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的順次連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表指針。分析你的算法的時、空繁復(fù)度。

9、給出折半查找的遞歸算法，并給出算法時間繁復(fù)度性分析。

10、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡約有向回路，假設(shè)存在，那么以頂點序列的方式輸出該回路〔找到一條即可〕?！沧ⅲ簣D中不存在頂點到自己的弧〕

有向圖判斷回路要比無向圖繁復(fù)。利用深度優(yōu)先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfs〔v〕結(jié)束前涌現(xiàn)頂點u到v的回邊，那么圖中必有包含頂點v和u的回路。對應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點，假設(shè)我們找出u的下一鄰接點的狀態(tài)為1，就可以輸出回路了。

voidPrint(intv,intstart)//輸出從頂點start開始的回路。

{for(i=1;i=n;i++)

if(g[v][i]!=0visited[i]==1)//假設(shè)存在邊〔v,i〕，且頂點i的狀態(tài)為1。

{printf(“%d”,v);

if(i==start)printf(“\n”);elsePrint(i,start);break;}//if

}//Print

voiddfs(intv)

{visited[v]=1;

for(j=1;j=n;j++)

if(g[v][j]!=0)//存在邊(v,j)

if(visited[j]!=1){if(!visited[j])dfs(j);}//if

else{cycle=1;Print(j,j);}

visited[v]=2;

}//dfs

voidfind_cycle()//判斷是否有回路，有那么輸出鄰接矩陣。visited數(shù)組為全局變量。

{for(i=1;i=n;i++)visited[i]=0;

for(i=1;i=n;i++)if(!visited[i])dfs(i);

}//find_cycle

11、假設(shè)K1，…，Kn是n個關(guān)鍵詞，試解答：

試用二叉查找樹的插入算法建立

一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序為K1，K2，…，Kn時，用算法建立一棵以LLINK/RLINK鏈接表示的二叉查找樹。

12、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域ne*t。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中所

2022年下半年河北省C++語言版高級

有重復(fù)涌現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。

#includestdio.h

typedefchardatatype;

typedefstructnode{

datatypedata;

structnode*ne*t;

}listnode;

typedeflistnode*linklist;

/**/

/*刪除單鏈表中重復(fù)的結(jié)點*/

/**/

linklistdeletelist(linklisthead)

{listnode*p,*s,*q;

p=head-ne*t;

while(p)

{s=p;

q=p-ne*t;

while(q)

if(q-data==p-data)

{s-ne*t=q-ne*t;free(q);

q=s-ne*t;}

else

{s=q;/*找與P結(jié)點值相同的結(jié)點*/

q=q-ne*t;

}

p=p-ne*t;

}

returnhead;

}

13、對二叉樹的某層上的結(jié)點進行運算，采納隊列結(jié)構(gòu)按層次遍歷最相宜。

intLeafKlevel(BiTreebt,intk)//求二叉樹bt的第k(k1)層上葉子結(jié)點個數(shù)

{if(bt==null||k1)return(0);

BiTreep=bt,Q[];//Q是隊列，元素是二叉樹結(jié)點指針,容量足夠大

intfront=0,rear=1,leaf=0;//front和rear是隊頭和隊尾指針,leaf是葉子結(jié)點數(shù)

intlast=1,level=1;Q[1]=p;//last是二叉樹同層最右結(jié)點的指針，level是二叉樹的層數(shù)

while(front=rear)

{p=Q[++front];

if(level==k!p-lchild!p-rchild)leaf++;//葉子結(jié)點

if(p-lchild)Q[++rear]=p-lchild;//左子女入隊

if(p-rchild)Q[++rear]=p-rchild;//右子女入隊

if(front==last){level++;//二叉樹同層最右結(jié)點已處理,層數(shù)增1

last=rear;}//last移到指向下層最右一元素

if(levelk)return(leaf);//層數(shù)大于k后退出運行

}//while}//結(jié)束LeafKLevel

14、二路插入排序是將待排關(guān)鍵字序列r[1..n]中關(guān)鍵字分二路分別按序插入到幫助向量d[1..n]前半部和后半部〔注:向量d可視為循環(huán)表〕，其原那么為，先將r[l]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實現(xiàn)二路插入排序算法。

15、設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。

typedefstructnode{intdata;structnode*ne*t;}lklist;

voidintersection(lklist*ha,lklist*hb,lklist*hc)

{

lklist*p,*q,*t;

for(p=ha,hc=0;p!=0;p=p-ne*t)

{for(q=hb;q!=0;q=q-ne*t)if(q-data==p-data)break;

if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-ne*t=hc;hc=t;}

}

}

16、設(shè)T是一棵滿二叉樹，編寫一個將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞

歸算法。

17、請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。

18、題目中要求矩陣兩行元素的平均值按遞增順次排序，由于每行元素個數(shù)相等，按平均值排列與按每行元素之和排列是一個意思。所以應(yīng)先求出各行元素之和，放入一維數(shù)組中，然后選擇一種排序方

2022年下半年河北省C++語言版高級

法，對該數(shù)組進行排序，留意在排序時假設(shè)有元素移動，那么與之相應(yīng)的行中各元素也需要做相應(yīng)變動。

voidTranslation〔float*matri*，intn〕

//本算法對nn的矩陣matri*，通過行變換，使其各行元素的平均值按遞增排列。

{inti,j,k,l；

floatsum，min；//sum暫存各行元素之和

float*p,*pi,*pk;

for(i=0;in;i++)

{sum=0.0;pk=matri*+i*n;//pk指向矩陣各行第1個元素.

for(j=0;jn;j++){sum+=*(pk);pk++;}//求一行元素之和.

*(p+i)=sum;//將一行元素之和存入一維數(shù)組.

}//fori

for(i=0;in-1;i++)//用選擇法對數(shù)組p進行排序

{min=*(p+i);k=i;//初始設(shè)第i行元素之和最小.

for(j=i+1;jn;j++)if(p[j]min){k=j;min=p[j];}//記新的最小值及行號.

if(i!=k)//假設(shè)最小行不是當(dāng)前行,要進行交換(行元素及行元素之和)

{pk=matri*+n*k;//pk指向第k行第1個元素.

pi=matri*+n*i;//pi指向第i行第1個元素.

for(j=0;jn;j++)//交換兩行中對應(yīng)元素.

{sum=*(pk+j);*(pk+j)=*(pi+j);*(pi+j)=sum;}

sum=p[i];p[i]=p[k];p[k]=sum;//交換一維數(shù)組中元素之和.

}//if

}//fori

free(p);//釋放p數(shù)組.

}//Translation

[算法分析]算法中運用選擇法排序,比較次數(shù)較多,但數(shù)據(jù)交換(移動)較少.假設(shè)用其它排序方法,雖可減削比較次數(shù),但數(shù)據(jù)移動會增多.算法時間繁復(fù)度為O(n2).

19、4、voidLinkList_reverse(LinklistL)

//鏈表的就地逆置;為簡化算法,假設(shè)表長大于2

{

p=L-ne*t;q=p-ne*t;s=q-ne*t;p-ne*t=NULL;

while(s-ne*t)

{

q-ne*t=p;p=q;

q=s;s=s-ne*t;//把L的元素逐個插入新表表頭

}

q-ne*t=p;s-ne*t=q;L-ne*t=s;

}//LinkList_reverse

20、給出折半查找的遞歸算法，并給出算法時間繁復(fù)度性分析。

21、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。

#defineMA*100

typedefstructNode

{charinfo;structNode*llink,*rlink;}TNODE;

charpred[MA*],inod[MA*];

main(intargc,int**argv)

{TNODE*root;

if(argc3)e*it0;

strcpy(pred,argv[1]);strcpy(inod,argv[2]);

root=restore(pred,inod,strlen(pred));

postorder(root);

}

TNODE*restore(char*ppos,char*ipos,intn)

{TNODE*ptr；char*rpos;intk;

if(n=0)returnNULL;

ptr-info=(1)_______;

for((2)_______;rposipos+n;rpos++)if(*rpos==*ppos)break;

k=(3)_______;

ptr-llink=restore(ppos+1,(4)_______,k);

ptr-rlink=restore((5)_______+k,rpos+1,n-1-k);

returnptr;

}

postorder(TNODE*p

tr)

{if(ptr=NULL)return;

postorder(ptr-llink);postorder(ptr-rlink);printf(“%c”,ptr-info);

}

22、后序遍歷最末訪問根結(jié)點，即在遞歸算法中，根是壓在

2022年下半年河北省C++語言版高級

棧底的。采納后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當(dāng)訪問到某結(jié)點時，棧中全部元素均為該結(jié)點的祖先。此題要找p和q的最近共同祖先結(jié)點r,不失一般性，設(shè)p在q的左邊。后序遍歷必定先遍歷到結(jié)點p，棧中元素均為p的祖先。將棧拷入另一幫助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到幫助棧中去匹配，第一個匹配〔即相等〕的元素就是結(jié)點p和q的最近公共祖先。

typedefstruct

{BiTreet;inttag;//tag=0表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問

}stack;

stacks[],s1[];//棧，容量夠大

BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。

{top=0;bt=ROOT;

while(bt!=null||top0)

{while(bt!=nullbt!=pbt!=q)//結(jié)點入棧

{s[++top].t=bt;s[top].tag=0;bt=bt-lchild;}//沿左分枝向下

if(bt==p)//不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點

{for(i=1;i=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入幫助棧s1保存

if(bt==q)//找到q結(jié)點。

for(i=top;i0;i--)//；將棧中元素的樹結(jié)點到s1去匹配

{pp=s[i].t;

for(j=top1;j0;j--)

if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}

｝

while(top!=0s[top].tag==1)top--;//退棧

if(top!=0)｛s[top].tag=1;bt=s[top].t-rchild;｝//沿右分枝向下遍歷

}//結(jié)束while(bt!=null||top0)

return(null);//ｑ、p無公共祖先

｝//結(jié)束Ancestor

23、對二叉樹的某層上的結(jié)點進行運算，采納隊列結(jié)構(gòu)按層次遍歷最相宜。

intLeafKlevel(BiTreebt,intk)//求二叉樹bt的第k(k1)層上葉子結(jié)點個數(shù)

{if(bt==null||k1)return(0);

BiTreep=bt,Q[];//Q是隊列，元素是二叉樹結(jié)點指針,容量足夠大

intfront=0,rear=1,leaf=0;//front和rear是隊頭和隊尾指針,leaf是葉子結(jié)點數(shù)

intlast=1,level=1;Q[1]=p;//last是二叉樹同層最右結(jié)點的指針，level是二叉樹的層數(shù)

while(front=rear)

{p=Q[++front];

if(level==k!p-lchild!p-rchild)leaf++;//葉子結(jié)點

if(p-lchild)Q[++rear]=p-lchild;//左子女入隊

if(p-rchild)Q[++rear]=p-rchild;//右子女入隊

if(front==last){level++;//二叉樹同層最右結(jié)點已處理,層數(shù)增1

last=rear;}//last移到指向下層最右一元素

if(levelk)return(leaf);//層數(shù)大于k后退出運行

}//while}//結(jié)束LeafKLeve

l

24、請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。

25、在有向圖G中，假如r到G中的每個結(jié)點都有路徑可達，那么稱結(jié)點r為G的根結(jié)點。編寫一個算法完成以下功能：

〔1〕．建立有向圖G的鄰接表存儲結(jié)構(gòu)；

〔2〕．判斷有向圖G是否有根

2022年下半年河北省C++語言版高級

，假設(shè)有，那么打印出全部根結(jié)點的值。

26、4、voidLinkList_reverse(LinklistL)

//鏈表的就地逆置;為簡化算法,假設(shè)表長大于2

{

p=L-ne*t;q=p-ne*t;s=q-ne*t;p-ne*t=NULL;

while(s-ne*t)

{

q-ne*t=p;p=q;

q=s;s=s-ne*t;//把L的元素逐個插入新表表頭

}

q-ne*t=p;s-ne*t=q;L-ne*t=s;

}//LinkList_reverse

27、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊復(fù)原。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。

voidSpnTree(AdjListg)

//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。

{typedefstruct{inti,j,w}node;//設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù)

nodeedge[];

scanf(%d%d,e,n);//輸入邊數(shù)和頂點數(shù)。

for(i=1;i=e;i++)//輸入e條邊：頂點，權(quán)值。

scanf(%d%d%d,edge[i].i,edge[i].j,edge[i].w);

for(i=2;i=e;i++)//按邊上的權(quán)值大小，對邊進行逆序排序。

{edge[0]=edge[i];j=i-1;

while(edge[j].wedge[0].w)edge[j+1]=edge[j--];

edge[j+1]=edge[0];}//for

k=1;eg=e;

while(eg=n)//破圈，直到邊數(shù)e=n-1.

{if(connect(k))//刪除第k條邊假設(shè)仍連通。

{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除

k++;//下條邊

}//while

}//算法結(jié)束。

connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，

28、約瑟夫環(huán)問題〔Josephus問題〕是指編號為1、2、…，n的n〔n0〕個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，…，如此重復(fù)直到全部的人全部出列為止。現(xiàn)要求采納循環(huán)鏈表結(jié)構(gòu)設(shè)計一個算法，模擬此過程。

#includestdlib.h

typedefintdatatype;

typedefstructnode

{datatypedata;

structnode*ne*t;

}listnode;

typedeflistnode*linklist;

voidjose(linklisthead,ints,intm)

{linklistk1,pre,p;

intcount=1;

pre=NULL;

k1=head;/*k1為報數(shù)的起點*/

while(count!=s)/*找初始報數(shù)起點*/

{pre=k1;

k1=k1-ne*t;

count++;

}

while(k1-ne*t!=k1)/*當(dāng)循環(huán)鏈表中的結(jié)點個數(shù)大于1時*/

{p=k1;/*從k1開始報數(shù)*/

count=1;

while(count!=m)/*連續(xù)數(shù)m個結(jié)點*/

{pre=p;

p=p-ne*t;

count++;

}

pre-ne*t=p-ne*t;

/*輸出該結(jié)點，并刪除該結(jié)點*/

printf(%4d,p-data);

free(p);

k1=pre-ne*t;/*新的報數(shù)起點*/

}

printf(%4d,k1-data);/*輸出

2022年下半年河北省C++語言版高級

最末一個結(jié)點*/

free(k1);

}

main()

{linklisthead,p,r;

intn,s,m,i;

printf(n=);

scanf(%d,n);

printf(s=);

scanf(%d,s);

printf(m=,m);

scanf(%d,m);

if(n1)printf(n0);

else

{/*建表*/

head=(linklist)malloc(sizeof(listnode));/*建第一個結(jié)點*/

head-data=n;

r=head;

for(i=n-1;i0;i--)/*建立剩余n-1個結(jié)點*/

{p=(linklist)malloc(sizeof(listnode));

p-data=i;

p-ne*t=head;

head=p;

}

r-ne*t=head;/*生成循環(huán)鏈表*/

jose(head,s,m);/*調(diào)用函數(shù)*/

}

}

29、矩陣中元素按行和按列都已排序，要求查找時間繁復(fù)度為O〔m+n〕，因此不能采納常規(guī)的二層循環(huán)的查找。可以先從右上角〔i=a,j=d〕元素與*比較，只有三種狀況：一是A[i,j]*，這狀況下向j小的方向繼續(xù)查找；二是A[i,j]*，下步應(yīng)向i大的方向查找；三是A[i,j]=*，查找勝利。否那么，假設(shè)下標已超出范圍，那么查找失敗。

voidsearch(datatypeA[][],inta,b,c,d,datatype*)

//n*m矩陣A,行下標從a到b,列下標從c到d,本算法查找*是否在矩陣A中.

{i=a;j=d;flag=0;//flag是勝利查到*的標識

while(i=bj=c)

if(A[i][j]==*){flag=1;break;}

elseif(A[i][j]*)j--;elsei++;

if(flag)printf(“A[%d][%d]=%d”,i,j,*);//假定*為整型.

elseprintf(“矩陣A中無%d元素”，*)；

}算法search結(jié)束。

[算法爭論]算法中查找*的路徑從右上角開始，向下〔當(dāng)*A[i,j]〕或向左〔當(dāng)*A[i,j]〕。向下最多是m，向左最多是n。最正確狀況是在右上角比較一次勝利，最差是在左下角〔A[b,c]〕，比較m+n次，故算法最差時間繁復(fù)度是O(m+n〕。

30、此題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出A[i]〔0=in〕,然后到鏈表中去查找值為A[i]的結(jié)點，假設(shè)查找失敗，那么插入。

LinkedListcreat(ElemTypeA[],intn)

//由含n個數(shù)據(jù)的數(shù)組A生成循環(huán)鏈表，要求鏈表有序并且無值重復(fù)結(jié)點

{LinkedListh;

h=(LinkedList)malloc(sizeof(LNode));//申請結(jié)點

h-ne*t=h;//形成空循環(huán)鏈表

for(i=0;in;i++)

{pre=h;

p=h-ne*t;

while(p!=hp-dataA[i])

{pre=p;p=p-ne*t;}//查找A[i]的插入位置

if(p==h||p-data!=A[i])//重復(fù)數(shù)據(jù)不再輸入

{s=(LinkedList)malloc(sizeof(LNode));

s-data=A[i];pre-ne*t=s;s-ne*t=p;//將結(jié)點s鏈入鏈表中

}

}//for

return(h);

}算法結(jié)束

31、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域ne*t。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中全部重復(fù)涌現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。

#includestdio.h

typed

efchardatatype;

typedefstructnode{

datatypedata;

structnode*ne*t;

}listnode;

typedeflistnode*linklist;

/*

2022年下半年河北省C++語言版高級

*/

/*刪除單鏈表中重復(fù)的結(jié)點*/

/**/

linklistdeletelist(linklisthead)

{listnode*p,*s,*q;

p=head-ne*t;

while(p)

{s=p;

q=p-ne*t;

while(q)

if(q-data==p-data)

{s-ne*t=q-ne*t;free(q);

q=s-ne*t;}

else

{s=q;/*找與P結(jié)點值相同的結(jié)點*/

q=q-ne*t;

}

p=p-ne*t;

}

returnhead;

}

32、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域ne*t。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中全部重復(fù)涌現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。

#includestdio.h

typedefchardatatype;

typedefstructnode{

datatypedata;

structnode*ne*t;

}listnode;

typedeflistnode*linklist;

/**/

/*刪除單鏈表中重復(fù)的結(jié)點*/

/**/

linklistdeletelist(linklisthead)

{listnode*p,*s,*q;

p=head-ne*t;

while(p)

{s=p;

q=p-ne*t;

while(q)

if(q-data==p-data)

{s-ne*t=q-ne*t;free(q);

q=s-ne*t;}

else

{s=q;/*找與P結(jié)點值相同的結(jié)點*/

q=q-ne*t;

}

p=p-ne*t;

}

returnhead;

}

33、依據(jù)二叉排序樹中序遍歷所得結(jié)點值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點與其前驅(qū)結(jié)點值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre〔初值為null〕和全局變量flag，初值為true。假設(shè)非二叉排序樹，那么置flag為false。

#definetrue1

#definefalse0

typedefstructnode

{datatypedata;structnode*llink,*rlink;}*BTree;

voidJudgeBST〔BTreet,intflag〕

//判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。

{if〔t!=nullflag〕

{Judgebst〔t-llink,flag〕；//中序遍歷左子樹

if〔pre==null〕pre=t；//中序遍歷的第一個結(jié)點不必判斷

elseif〔pre-datat-data〕pre=t；//前驅(qū)指針指向當(dāng)前結(jié)點

else{flag=flase；}//不是完全二叉樹

Judgebst〔t-rlink,flag〕；//中序遍歷右子樹

}//JudgeBST算法結(jié)束

34、設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化

成對應(yīng)的二叉樹。

35、二叉樹的層次遍歷序列的第一個結(jié)點是二叉樹的根。事實上，層次遍歷序列中的每個結(jié)點都是“局部根”。確定根后，到二叉樹的中序序列中，查到該結(jié)點，該結(jié)點將二叉樹分為“左根右”三部分。假設(shè)左、右子樹均有，那么層次序列根結(jié)點的后面應(yīng)是左右子樹的根；假設(shè)中序序列中只有左子樹或只有

2022年下半年河北省C++語言版高級

右子樹，那么在層次序列的根結(jié)點后也只有左子樹的根或右子樹的根。這樣，定義一個全局變量指針R，指向?qū)哟涡蛄写幚碓亍Ｋ惴ㄖ邢忍幚砀Y(jié)點，將根結(jié)點和左右子女的信息入隊列。然后，在隊列不空的條件下，循環(huán)處理二叉樹的結(jié)點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：

typedefstruct

{intlvl;//層次序列指針，總是指向當(dāng)前“根結(jié)點”在層次序列中的位置

intl,h;//中序序列的下上界

intf;//層次序列中當(dāng)前“根結(jié)點”的雙親結(jié)點的指針

intlr;//1—雙親的左子樹2—雙親的右子樹

}qnode;

BiTreeCreat(datatypein[],level[],intn)

//由二叉樹的層次序列l(wèi)evel[n]和中序序列in[n]生成二叉樹。n是二叉樹的結(jié)點數(shù)

{if(n1){printf(“參數(shù)錯誤\n”);e*it(0);}

qnodes,Q[];//Q是元素為qnode類型的隊列，容量足夠大

init(Q);intR=0;//R是層次序列指針，指向當(dāng)前待處理的結(jié)點

BiTreep=(BiTree)malloc(sizeof(BiNode));//生成根結(jié)點

p-data=level[0];p-lchild=null;p-rchild=null;//填寫該結(jié)點數(shù)據(jù)

for(i=0;in;i++)//在中序序列中查找根結(jié)點，然后，左右子女信息入隊列

if(in[i]==level[0])break;

if(i==0)//根結(jié)點無左子樹，遍歷序列的1—n-1是右子樹

{p-lchild=null;

s.lvl=++R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);

}

elseif(i==n-1)//根結(jié)點無右子樹，遍歷序列的1—n-1是左子樹

{p-rchild=null;

s.lvl=++R;s.l=1;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);

}

else//根結(jié)點有左子樹和右子樹

{s.lvl=++R;s.l=0;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);//左子樹有關(guān)信息入隊列

s.lvl=++R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);//右子樹有關(guān)信息入隊列

}

while(!empty(Q))//當(dāng)隊列不空，進行循環(huán)，構(gòu)造二叉樹的左右子樹

{s=delqueue(Q);father=s.f;

for(i=s.l;i=s.h;i++)

if(in[i]==level[s.lvl])break;

p=(bitreptr)malloc(sizeof(binode));//申請結(jié)點空間

p-data=level[s.lvl];p-lchild=null;p-rchild=null;//填寫該結(jié)點數(shù)據(jù)

if(s.lr==1)father-lchild=p;

elsefather-rchild=p；//讓雙親的子女指針指向該結(jié)點

if(i==s.l)

{p-lchild=null;//處理無左子女

s.lvl=++R;s.l=i+1;s.f=p;s.lr=2;enqueue(Q,s);

}

elseif(i==s.h)

{p-rchild=null;//處理無右子女

s.lvl=++R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);

}

else{s.lvl=++R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);//左子樹有關(guān)信息入隊列

s.lvl=++R;s.l=i+1;s.f=p;s.lr=2;enqu

eue(Q,s);//右子樹有關(guān)信息入隊列

}

}//結(jié)束while(!empty(Q))

return(p);

}//算法結(jié)束

36、矩陣中元素按行和按列都已排序，要求查找時間繁復(fù)度為O〔m+n〕，因此不能采納常規(guī)的二層循環(huán)的查找?？梢韵葟挠疑辖恰瞚=a,j=d〕元素

2022年下半年河北省C++語言版高級

與*比較，只有三種狀況：一是A[i,j]*，這狀況下向j小的方向繼續(xù)查找；二是A[i,j]*，下步應(yīng)向i大的方向查找；三是A[i,j]=*，查找勝利。否那么，假設(shè)下標已超出范圍，那么查找失敗。

voidsearch(datatypeA[][],inta,b,c,d,datatype*)

//n*m矩陣A,行下標從a到b,列下標從c到d,本算法查找*是否在矩陣A中.

{i=a;j=d;flag=0;//flag是勝利查到*的標識

while(i=bj=c)

if(A[i][j]==*){flag=1;break;}

elseif(A[i][j]*)j--;elsei++;

if(flag)printf(“A[%d][%d]=%d”,i,j,*);//假定*為整型.

elseprintf(“矩陣A中無%d元素”，*)；

}算法search結(jié)束。

[算法爭論]算法中查找*的路徑從右上角開始，向下〔當(dāng)*A[i,j]〕或向左〔當(dāng)*A[i,j]〕。向下最多是m，向左最多是n。最正確狀況是在右上角比較一次勝利，最差是在左下角〔A[b,c]〕，比較m+n次，故算法最差時間繁復(fù)度是O(m+n〕。

37、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否那么稱為非法序列?！?5分〕

〔1〕A和D是合法序列，B和C是非法序列。

〔2〕設(shè)被判定的操作序列已存入一維數(shù)組A中。

intJudge(charA[])

//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否那么返回false。

{i=0;//i為下標。

j=k=0;//j和k分別為I和字母O的的個數(shù)。

while(A[i]!=‘\0’)//當(dāng)未到字符數(shù)組尾就作。

{switch(A[i])

{case‘I’:j++;break;//入棧次數(shù)增1。

case‘O’:k++;if(kj){printf(“序列非法\n”)；e*it(0);}

}

i++;//不論A[i]是‘I’或‘O’，指針i均后移。}

if(j!=k){printf(“序列非法\n”)；return(false);}

else{printf(“序列合法\n”)；return(true);}

}//算法結(jié)束。

38、設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列〔設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink〕。

39、設(shè)一棵二叉樹的結(jié)點結(jié)構(gòu)為(LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ANCESTOR〔ROOT，p,q,r〕,該算法找到p和q的最近共同祖先結(jié)點r。

40、我們可用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請給出用“破圈法”求解給定的帶權(quán)連通無向圖的一棵最小代價生成樹的具體算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。

41、有一個帶

2022年下半年河北省C++語言版高級

頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域ne*t。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中全部重復(fù)涌現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保留一個。

#includestdio.h

typedefchardatatype;

typedefstructnode{

datatypedata;

structnode*ne*t;

}listnode;

typedeflistnode*linklist;

/**/

/*刪除單鏈表中重復(fù)的結(jié)點*/

/**/

linklistdeletelist(linklisthead)

{listnode*p,*s,*q;

p=head-ne*t;

while(p)

{s=p;

q=p-ne*t;

while(q)

if(q-data==p-data)

{s-ne*t=q-ne*t;free(q);

q=s-ne*t;}

else

{s=q;/*找與P結(jié)點值相同的結(jié)點*/

q=q-ne*t;

}

p=p-ne*t;

}

returnhead;

}

42、將頂點放在兩個集合V1和V2。對每個頂點，檢查其和鄰接點是否在同一個集合中，如是，那么為非二部圖。為此，用整數(shù)1和2表示兩個集合。再用一隊列結(jié)構(gòu)存放圖中訪問的頂點。

intBPGraph(AdjMatri*g)

//判斷以鄰接矩陣表示的圖g是否是二部圖。

{ints[];//頂點向量，元素值表示其屬于那個集合〔值1和2表示兩個集合〕

intQ[];//Q為隊列，元素為圖的頂點，這里設(shè)頂點信息就是頂點編號。

intf=0,r,visited[];//f和r分別是隊列的頭尾指針,visited[]是訪問數(shù)組

for(i=1;i=n;i++){visited[i]=0;s[i]=0;}//初始化，各頂點未確定屬于那個集合

Q[1]=1;r=1;s[1]=1;//頂點1放入集合S1

while(fr)

{v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//預(yù)備v的鄰接點的集合號

if(!visited[v])

{visited[v]=1;//確保對每一個頂點，都要檢查與其鄰接點不應(yīng)在一個集合中

for(j=1,j=n;j++)

if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//鄰接點入隊列

elseif(s[j]==s[v])return(0);}//非二部圖

}//if(!visited[v])

}//while

return(1);}//是二部圖

[算法爭論]題目給的是連通無向圖，假設(shè)非連通，那么算法要修改。

43、設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。

44、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡約有向回路，假設(shè)

存在，那么以頂點序列的方式輸出該回路〔找到一條即可〕?！沧ⅲ簣D中不存在頂點到自己的弧〕

有向圖判斷回路要比無向圖繁復(fù)。利用深度優(yōu)先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfs〔v〕結(jié)束前涌現(xiàn)頂點u到

2022年下半年河北省C++語言版高級

v的回邊，那么圖中必有包含頂點v和u的回路。對應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點，假設(shè)我們找出u的下一鄰接點的狀態(tài)為1，就可以輸出回路了。

voidPrint(intv,intstart)//輸出從頂點start開始的回路。

{for(i=1;i=n;i++)

if(g[v][i]!=0visited[i]==1)//假設(shè)存在邊〔v,i〕，且頂點i的狀態(tài)為1。

{printf(“%d”,v);

if(i==start)printf(“\n”);elsePrint(i,start);break;}//if

}//Print

voiddfs(intv)

{visited[v]=1;

for(j=1;j=n;j++)

if(g[v][j]!=0)//存在邊(v,j)

if(visited[j]!=1){if(!visited[j])dfs(j);}//if

else{cycle=1;Print(j,j);}

visited[v]=2;

}//dfs

voidfind_cycle()//判斷是否有回路，有那么輸出鄰接矩陣。visited數(shù)組為全局變量。

{for(i=1;i=n;i++)visited[i]=0;

for(i=1;i=n;i++)if(!visited[i])dfs(i);

}//find_cycle

45、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊復(fù)原。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。

voidSpnTree(AdjListg)

//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。

{typedefstruct{inti,j,w}node;//設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù)

nodeedge[];

scanf(%d%d,e,n);//輸入邊數(shù)和頂點數(shù)。

for(i=1;i=e;i++)//輸入e條邊：頂點，權(quán)值。

scanf(%d%d%d,edge[i].i,edge[i].j,edge[i].w);

for(i=2;i=e;i++)//按邊上的權(quán)值大小，對邊進行逆序排序。

{edge[0]=edge[i];j=i-1;

while(edge[j].wedge[0].w)edge[j+1]=edge[j--];

edge[j+1]=edge[0];}//for

k=1;eg=e;

while(eg=n)//破圈，直到邊數(shù)e=n-1.

{if(connect(k))//刪除第k條邊假設(shè)仍連通。

{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除

k++;//下條邊

}//while

}//算法結(jié)束。

connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，

46、已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7}

寫出G的拓撲排序的結(jié)果。

G拓撲排序的結(jié)果是：V1、V2、V4、V3、V5、V6、V7

47、設(shè)T是一棵滿二叉樹，編寫一個將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。

48

、依據(jù)二叉排序樹中序遍歷所得結(jié)點值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點與其前驅(qū)結(jié)點值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre〔初值為null〕和全局變量flag，初值為true。假設(shè)非二叉排序樹，那么置flag為false。

#definetrue1

#definefalse

2022年下半年河北省C++語言版高級

0

typedefstructnode

{datatypedata;structnode*llink,*rlink;}*BTree;

voidJudgeBST〔BTreet,intflag〕

//判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。

{if〔t!=nullflag〕

{Judgebst〔t-llink,flag〕；//中序遍歷左子樹

if〔pre==null〕pre=t；//中序遍歷的第一個結(jié)點不必判斷

elseif〔pre-datat-data〕pre=t；//前驅(qū)指針指向當(dāng)前結(jié)點

else{flag=flase；}//不是完全二叉樹

Judgebst〔t-rlink,flag〕；//中序遍歷右子樹

}//JudgeBST算法結(jié)束

49、設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.

typedefstructnode

{intdata;structnode*lchild,*rchild;}node;

intN2,NL,NR,N0;

voidcount(node*t)

{if(t-lchild!=NULL)if(1)___N2++;elseNL++;

elseif(2)___NR++;else(3)__;

if(t-lchild!=NULL)(4)____;if(t-rchild!=NULL)(5)____;

}

26.樹的先序非遞歸算法。

voide*ample(b)

btree*b;

{btree*stack[20],*p；

inttop;

if(b!=null)

{top=1;stack[top]=b;

while(top0)

{p=stack[top];top--;

printf(“%d”,p-data);

if(p-rchild!=null)

{(1)___;(2)___;

}

if(p-lchild!=null)

(3)___;(4)__;

}}}}

50、設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列〔設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink〕。

51、設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。

typedefstructnode{intdata;structnode*ne*t;}lklist;

voidintersection(lklist*ha,lklist*hb,lklist*hc)

{

lklist*p,*q,*t;

for(p=ha,hc=0;p!=0;p=p-ne*t)

{for(q=hb;q!=0;q=q-ne*t)if(q-data==p-data)break;

if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-ne*t=hc;hc=t;}

}

}

52、兩棵空二叉樹或僅有根結(jié)點的二叉樹相像；對非空二叉樹，可判左右子樹是否相像，采納遞歸算法。

intSimilar(BiTreep,q)//判斷二叉樹p和q是否相像

{if(p==nullq==null)return(1);

elseif(!pq||p!q)return(0);

elsereturn(Similar(p-lchild,q-lchild)Similar(p-rchild,q-rchild))

}//結(jié)束Similar

53、數(shù)組A和B的元素分別有序，欲將兩數(shù)組合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要留意A和

B數(shù)組指針的運用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復(fù)制到C中即可。

voidunion(intA[],B[],C[],m,n)

//整型數(shù)組A和B各有m和n個元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。

{i=0;j=n-1;k=0

2022年下半年河北省C++語言版高級

;//i，j，k分別是數(shù)組A,B和C的下標，因用C描述，下標從0開始

while(imj=0)

if(a[i]b[j])c[k++]=a[i++]elsec[k++]=b[j--];

while(im)c[k++]=a[i++];

while(j=0)c[k++]=b[j--];

}算法結(jié)束

4、要求二叉樹按二叉鏈表形式存儲。15分

〔1〕寫一個建立二叉樹的算法。〔2〕寫一個判別給定的二叉樹是否是完全二叉樹的算法。

BiTreeCreat()//建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)

{ElemType*；BiTreebt;

scanf(“%d”,*);//此題假定結(jié)點數(shù)據(jù)域為整型

if(*==0)bt=null;

elseif(*0)

{bt=(BiNode*)malloc(sizeof(BiNode));

bt-data=*;bt-lchild=creat();bt-rchild=creat();

}

elseerror(“輸入錯誤”)；

return(bt);

}//結(jié)束BiTree

intJudgeComplete(BiTreebt)//判斷二叉樹是否是完全二叉樹,如是，返回1，否那么，返回0

{inttag=0;BiTreep=bt,Q[];//Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大

if(p==null)return(1);

QueueInit(Q);QueueIn(Q,p);//初始化隊列，根結(jié)點指針入隊

while(!QueueEmpty(Q))

{p=QueueOut(Q);//出隊

if(p-lchild!tag)QueueIn(Q,p-lchild);//左子女入隊

else{if(p-lchild)return0;//前邊已有結(jié)點為空，本結(jié)點不空

elsetag=1;//首次涌現(xiàn)結(jié)點為空

if(p-rchild!tag)QueueIn(Q,p-rchild);//右子女入隊

elseif(p-rchild)return0;elsetag=1;

}//while

return1;}//JudgeComplete

54、設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結(jié)點個數(shù)N2;只有非空左兒子的個數(shù)NL;只有非空右兒子的結(jié)點個數(shù)NR和葉子結(jié)點個數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.

typedefstructnode

{intdata;structnode*lchild,*rchild;}node;

intN2,NL,NR,N0;

voidcount(node*t)

{if(t-lchild!=NULL)if(1)___N2++;elseNL++;

elseif(2)___NR++;else(3)__;

if(t-lchild!=NULL)(4)____;if(t-rchild!=NULL)(5)____;

}

26.樹的先序非遞歸算法。

voide*ample(b)

btree*b;

{btree*stack[20],*p；

inttop;

if(b!=null)

{top=1;stack[top]=b;

while(top0)

{p=stack[top];top--;

printf(“%d”,p-data);

if(p-rchild!=null)

{(1)___;(2)___;

}

if(p-lchild!=null)

(3)___;(4)__;

}}}}

55、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡約有向回路，假設(shè)存在，那么以頂點序列的方式

輸出該回路〔找到一條即可〕?！沧ⅲ簣D中不存在頂點到自己的弧〕

有向圖判斷回路要比無向圖繁復(fù)。利用深度優(yōu)先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfs〔v〕結(jié)束前涌現(xiàn)頂點u到v的回邊，那么圖中必有包含

2022年下半年河北省C++語言版高級

頂點v和u的回路。對應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點，假設(shè)我們找出u的下一鄰接點的狀態(tài)為1，就可以輸出回路了。

voidPrint(intv,intstart)//輸出從頂點start開始的回路。

{for(i=1;i=n;i++)

if(g[v][i]!=0visited[i]==1)//假設(shè)存在邊〔v,i〕，且頂點i的狀態(tài)為1。

{printf(“%d”,v);

if(i==start)printf(“\n”);elsePrint(i,start);break;}//if

}//Print

voiddfs(intv)

{visited[v]=1;

for(j=1;j=n;j++)

if(g[v][j]!=0)//存在邊(v,j)

if(visited[j]!=1){if(!visited[j])dfs(j);}//if

else{cycle=1;Print(j,j);}

visited[v]=2;

}//dfs

voidfind_cycle()//判斷是否有回路，有那么輸出鄰接矩陣。visited數(shù)組為全局變量。

{for(i=1;i=n;i++)visited[i]=0;

for(i=1;i=n;i++)if(!visited[i])dfs(i);

}//find_cycle

56、數(shù)組A和B的元素分別有序，欲將兩數(shù)組合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要留意A和B數(shù)組指針的運用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復(fù)制到C中即可。

voidunion(intA[],B[],C[],m,n)

//整型數(shù)組A和B各有m和n個元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。

{i=0;j=n-1;k=0;//i，j，k分別是數(shù)組A,B和C的下標，因用C描述，下標從0開始

while(imj=0)

if(a[i]b[j])c[k++]=a[i++]elsec[k++]=b[j--];

while(im)c[k++]=a[i++];

while(j=0)c[k++]=b[j--];

}算法結(jié)束

4、要求二叉樹按二叉鏈表形式存儲。15分

〔1〕寫一個建立二叉樹的算法。〔2〕寫一個判別給定的二叉樹是否是完全二叉樹的算法。

BiTreeCreat()//建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu)

{ElemType*；BiTreebt;

scanf(“%d”,*);//此題假定結(jié)點數(shù)據(jù)域為整型

if(*==0)bt=null;

elseif(*0)

{bt=(BiNode*)malloc(sizeof(BiNode));

bt-data=*;bt-lchild=creat();bt-rchild=creat();

}

elseerror(“輸入錯誤”)；

return(bt);

}//結(jié)束BiTree

intJudgeComplete(BiTreebt)//判斷二叉樹是否是完全二叉樹,如是，返回1，否那么，返回0

{inttag=0;BiTreep=bt,Q[];//Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大

if(p==null)return(1);

QueueInit(Q);QueueIn(Q,p);//初始化隊列，根結(jié)點指針入隊

while(!QueueEmpty(Q))

{p=QueueOut(Q);//出隊

i