2021年貴州省C++語言版大綱

1、2021年貴州省c+語言版大綱 2021年貴州省c+語言版大綱 1、設(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. typedef struct nodeint data; struct node *lchild,*rchild;node;int n2,nl,nr,n0;void count(node *t)if (t-lchild!=null) if (1)_ n2+; else

2、nl+;else if (2)_ nr+; else (3)_ ;if(t-lchild!=null)(4)_; if (t-rchild!=null) (5)_;26.樹的先序非遞歸算法。void example(b)btree *b; btree *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;if (p-lchild!=null)(3)_; (4)_;2、設(shè)有兩個集合a和集合

3、b，要求設(shè)計生成集合c=ab的算法，其中集合a、b和c用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。typedef struct node int data; struct node *next;lklist;void intersection(lklist *ha,lklist *hb,lklist *hc)lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-nex

4、t=hc; hc=t;3、#define maxsize ?？臻g容量void inouts(int smaxsize)/s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。int top=0; /top為棧頂指針，定義top=0時為?？?。for(i=1; i=n; i+) /n個整數(shù)序列作處理。scanf(“%d”,x); /從鍵盤讀入整數(shù)序列。if(x!=-1) / 讀入的整數(shù)不等于-1時入棧。if(top=maxsize-1)printf(“棧滿n”);exit(0);else s+top=x; /x入棧。else /讀入的整數(shù)等于-1時退棧。if(top=0)printf(“?？課”);exi

5、t(0);else printf(“出棧元素是%dn”,stop-)；/算法結(jié)4、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#define max 100typedef struct nodechar info; struct node *llink, *rlink; tnode;char predmax,inodmax;main(int argc,int *argv) tnode *root;if(argc3) exit 0;strcpy(pre

6、d,argv1); strcpy(inod,argv2);root=restore(pred,inod,strlen(pred);postorder(root);tnode *restore(char *ppos,char *ipos,int n) tnode *ptr； char *rpos; int k;if(n=0) return null;ptr-info=(1)_;for(2)_ ; rposipos+n;rpos+) if(*rpos=*ppos) break;k=(3)_;ptr-llink=restore(ppos+1, (4)_,k );ptr-rlink=restore (

7、5)_+k,rpos+1,n-1-k 2021年貴州省c+語言版大綱 ); return ptr;postorder(tnode*ptr) if(ptr=null) return;postorder(ptr-llink); postorder(ptr-rlink); printf(“%c”,ptr-info);5、后序遍歷最終訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采納后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當(dāng)訪問到某結(jié)點時，棧中全部元素均為該結(jié)點的祖先。本題要找p和q 的最近共同祖先結(jié)點r ,不失一般性，設(shè)p在q的左邊。后序遍歷必定先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪粠椭?/p>

8、棧中。再連續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開頭逐個到幫助棧中去匹配，第一個匹配（即相等）的元素就是結(jié)點p 和q的最近公共祖先。typedef structbitree t;int tag;/tag=0 表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問stack;stack s,s1;/棧，容量夠大bitree ancestor(bitree root,p,q,r)/求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。top=0; bt=root;while(bt!=null |top0)while(bt!=null bt!=p bt!=q) /結(jié)點入棧s+top.t=bt; stop.t

9、ag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點for(i=1;i=top;i+) s1i=si; top1=top; /將棧s的元素轉(zhuǎn)入幫助棧s1 保存if(bt=q) /找到q 結(jié)點。for(i=top;i0;i-)/；將棧中元素的樹結(jié)點到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp);while(top!=0 stop.tag=1) top-; /退棧if (top!=0)stop.

10、tag=1;bt=stop.t-rchild; /沿右分枝向下遍歷/結(jié)束while(bt!=null |top0)return(null);/、p無公共祖先/結(jié)束ancestor6、4、void linklist_reverse(linklist l)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2p=l-next;q=p-next;s=q-next;p-next=null;while(s-next)q-next=p;p=q;q=s;s=s-next; /把l的元素逐個插入新表表頭q-next=p;s-next=q;l-next=s;/linklist_reverse7、給出折半查找的遞歸算法，并

11、給出算法時間簡單度性分析。8、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域next。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中全部重復(fù)消失的結(jié)點，使得info域相等的結(jié)點只保留一個。#include stdio.htypedef char datatype;typedef struct nodedatatype data;struct node * next; listnode;typedef listnode* linklist;/*-*/* 刪除單鏈表中重復(fù)的結(jié)點 */*-*/linklist deletelist(linklist head

12、) listnode *p,*s,*q;p=head-next;while(p)s=p;q=p-next;while(q)if(q-data 2021年貴州省c+語言版大綱 =p-data) s-next=q-next;free(q);q=s-next;else s=q; /*找與p結(jié)點值相同的結(jié)點*/q=q-next;p=p-next;return head;9、設(shè)一棵二叉樹的結(jié)點結(jié)構(gòu)為 (llink,info,rlink),root為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ancestor（root，p,q,r）,該算法找到p和q的最近共同祖先結(jié)

13、點r。10、由于后序遍歷棧中保留當(dāng)前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入幫助棧中，幫助棧始終保存最長路徑長度上的結(jié)點，直至后序遍歷完畢，則幫助棧中內(nèi)容即為所求。void longestpath(bitree bt)/求二叉樹中的第一條最長路徑長度bitree p=bt,l,s; /l, s是棧，元素是二叉樹結(jié)點指針，l中保留當(dāng)前最長路徑中的結(jié)點int i，top=0,tag,longest=0;while(p | top0) while(p) s+top=p；tagtop=0; p=p-lc; /沿左分枝向下if(tagt

14、op=1) /當(dāng)前結(jié)點的右分枝已遍歷if(!stop-lc !stop-rc) /只有到葉子結(jié)點時，才查看路徑長度if(toplongest) for(i=1;i=top;i+) li=si; longest=top; top-;/保留當(dāng)前最長路徑到l棧，記住最高棧頂指針，退棧else if(top0) tagtop=1; p=stop.rc; /沿右子分枝向下/while(p!=null|top0)/結(jié)束longestpath11、請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的挨次連成一個單鏈表，表頭指針為head。 二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表

15、指針。分析你的算法的時、空簡單度。12、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當(dāng)n=1時，只有一個根結(jié)點，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。設(shè)中序序列為s1，s2，sm,后序序列是p1,p2,，pm。因后序序列最終一個元素pm是根，則在中序序列中可找到與pm相等的結(jié)點（設(shè)二叉樹中各結(jié)點互不相同）si(1im)，因中序序列是由中序遍歷而得，所以si是根結(jié)點，s1，s2，si-1是左子樹的中序序列，而si+1,si+2,sm是右子樹的中序序列。若i=1，則s1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點數(shù)是m-1,則s2

16、，s3，sm和p1，p2，pm-1可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點數(shù)是m-1，則s1，s2，sm-1和p1，p2，pm-1唯一確定左子樹，從而也確定了二叉樹。最終，當(dāng)1im時，si把中序序列分成s1，s2，si-1和si+1,si+2,，sm。由于后序遍歷是“左子 2021年貴州省c+語言版大綱 樹右子樹根結(jié)點”，所以p1,p2,pi-1和pi,pi+1,pm-1是二叉樹的左子樹和右子樹的后序遍歷序列。因而由s1，s2，si-1和p1，p2，pi-1 可唯一確定二叉樹的左子樹，由si+1,si+2,，sm和pi,pi+1,，pm

17、-1可唯一確定二叉樹的右子樹 。13、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當(dāng)n=1時，只有一個根結(jié)點，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。設(shè)中序序列為s1，s2，sm,后序序列是p1,p2,，pm。因后序序列最終一個元素pm是根，則在中序序列中可找到與pm相等的結(jié)點（設(shè)二叉樹中各結(jié)點互不相同）si(1im)，因中序序列是由中序遍歷而得，所以si是根結(jié)點，s1，s2，si-1是左子樹的中序序列，而si+1,si+2,sm是右子樹的中序序列。若i=1，則s1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點數(shù)是m-1,則s2，

18、s3，sm和p1，p2，pm-1可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點數(shù)是m-1，則s1，s2，sm-1和p1，p2，pm-1唯一確定左子樹，從而也確定了二叉樹。最終，當(dāng)1im時，si把中序序列分成s1，s2，si-1和si+1,si+2,，sm。由于后序遍歷是“左子樹右子樹根結(jié)點”，所以p1,p2,pi-1和pi,pi+1,pm-1是二叉樹的左子樹和右子樹的后序遍歷序列。因而由s1，s2，si-1和p1，p2，pi-1可唯一確定二叉樹的左子樹，由si+1,si+2,，sm和pi,pi+1,，pm-1可唯一確定二叉樹的右子樹 。14、

19、假設(shè)以i和o分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）（1）a和d是合法序列，b和c 是非法序列。（2）設(shè)被判定的操作序列已存入一維數(shù)組a中。int judge(char a)/推斷字符數(shù)組a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。i=0; /i為下標(biāo)。j=k=0; /j和k分別為i和字母o的的個數(shù)。while(ai!=0) /當(dāng)未到字符數(shù)組尾就作。switch(ai)casei: j+; break; /入棧次數(shù)增1。caseo: k+; if(kj)

20、printf(“序列非法n”)；exit(0);i+; /不論ai是i或o，指針i均后移。if(j!=k) printf(“序列非法n”)；return(false);else printf(“序列合法n”)；return(true);/算法結(jié)束。15、兩棵空二叉樹或僅有根結(jié)點的二叉樹相像；對非空二叉樹， 2021年貴州省c+語言版大綱 可判左右子樹是否相像，采納遞歸算法。 int similar(bitree p,q) /推斷二叉樹p和q是否相像if(p=null q=null) return (1);else if(!p q | p !q) return (0);else return(s

21、imilar(p-lchild,q-lchild) similar(p-rchild,q-rchild)/結(jié)束similar16、假設(shè)以i和o分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）（1）a和d是合法序列，b和c 是非法序列。（2）設(shè)被判定的操作序列已存入一維數(shù)組a中。int judge(char a)/推斷字符數(shù)組a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。i=0; /i為下標(biāo)。j=k=0; /j和k分別為i和字母o的的個數(shù)。while(ai!=0)

22、/當(dāng)未到字符數(shù)組尾就作。switch(ai)casei: j+; break; /入棧次數(shù)增1。caseo: k+; if(kj)printf(“序列非法n”)；exit(0);i+; /不論ai是i或o，指針i均后移。if(j!=k) printf(“序列非法n”)；return(false);else printf(“序列合法n”)；return(true);/算法結(jié)束。17、冒泡排序算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的冒泡排序算法。48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進(jìn)行排序，請寫出這種

23、排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）18、設(shè)t是一棵滿二叉樹，編寫一個將t的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。19、對一般二叉樹，僅依據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，依據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。void pretopost(elemtype pre ,post,int l1,h1,l2,h2)/將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最終結(jié)點的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點ha

24、lf=(h1-l1)/2; /左或右子樹的結(jié)點數(shù)pretopost(pre,post,l1+1,l1+half,l2,l2+half-1) /將左子樹先序序列轉(zhuǎn)為后序序列pretopost(pre,post,l1+half+1,h1,l2+half,h2-1) /將右子樹先序序列轉(zhuǎn)為后序序列 /pretopost32. .葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最終葉子結(jié)點的rchild為空 2021年貴州省c+語言版大綱 。 linkedlist head,p

25、re=null; /全局變量linkedlist inorder(bitree bt)/中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為headif(bt)inorder(bt-lchild); /中序遍歷左子樹if(bt-lchild=null bt-rchild=null) /葉子結(jié)點if(pre=null) head=bt; pre=bt; /處理第一個葉子結(jié)點elsepre-rchild=bt; pre=bt; /將葉子結(jié)點鏈入鏈表inorder(bt-rchild); /中序遍歷左子樹pre-rchild=null; /設(shè)置鏈表尾return(head); /inor

26、der時間簡單度為o(n),幫助變量使用head和pre,?？臻g簡單度o(n)20、冒泡排序算法是把大的元素向上移（氣泡的上?。部梢园研〉脑叵蛳乱疲馀莸南鲁粒┱埥o出上浮和下沉過程交替的冒泡排序算法。48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進(jìn)行排序，請寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）21、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。29. 試找出滿意下列條件的二叉樹1）先序序列與后序序列相同 2）中序序列與后序序列相同3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同22、請編寫一個判別給定二叉

27、樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。23、冒泡排序算法是把大的元素向上移（氣泡的上?。?，也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的冒泡排序算法。48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進(jìn)行排序，請寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）24、已知有向圖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的拓?fù)渑判虻慕Y(jié)果。g拓?fù)渑判虻慕Y(jié)果是：v1、v2、v4

28、、v3、v5、v6、v725、我們可用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請給出用“破圈法”求解給定的帶權(quán)連通無向圖的一棵最小代價生成樹的具體算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。26、二路插入排序是將待排關(guān)鍵字序列r1.n中關(guān)鍵字分二路分別按序插入到幫助向量d1.n前半部和后半部（注:向量d可視為循環(huán)表），其原則為，先將rl賦給d1，再從r2 記錄開頭分二路插入。編寫實現(xiàn)二路插入排序算法。27、 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰 2021年貴州省c+語言版大綱

29、接點是否在同一個集合中，如是，則為非二部圖。為此，用整數(shù)1和2表示兩個集合。再用一隊列結(jié)構(gòu)存放圖中訪問的頂點。 int bpgraph (adjmatrix g)/推斷以鄰接矩陣表示的圖g是否是二部圖。int s; /頂點向量，元素值表示其屬于那個集合（值1和2表示兩個集合）int q;/q為隊列，元素為圖的頂點，這里設(shè)頂點信息就是頂點編號。int f=0,r,visited; /f和r分別是隊列的頭尾指針,visited是訪問數(shù)組for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各頂點未確定屬于那個集合q1=1; r=1; s1=1;/頂點1放入集合s1while

30、(fr)v=q+f; if (sv=1) jh=2; else jh=1;/預(yù)備v的鄰接點的集合號if (!visitedv)visitedv=1; /確保對每一個頂點，都要檢查與其鄰接點不應(yīng)在一個集合中for (j=1,j=n;j+)if (gvj=1)if (!sj) sj=jh; q+r=j; /鄰接點入隊列else if (sj=sv) return(0); /非二部圖/if (!visitedv)/whilereturn(1); /是二部圖算法爭論 題目給的是連通無向圖，若非連通，則算法要修改。28、約瑟夫環(huán)問題（josephus問題）是指編號為1、2、，n的n（n0）個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開頭按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開頭報數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到全部的人全部出