2021年贵州省C++语言版大纲

1、2021年贵州省c+语言版大纲 2021年贵州省c+语言版大纲 1、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数n2;只有非空左儿子的个数nl;只有非空右儿子的结点个数nr和叶子结点个数n0。n2、nl、nr、n0都是全局量，且在调用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、设有两个集合a和集合

3、b，要求设计生成集合c=ab的算法，其中集合a、b和c用链式存储结构表示。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 栈空间容量void inouts(int smaxsize)/s是元素为整数的栈，本算法进行入栈和退栈操作。int top=0; /top为栈顶指针，定义top=0时为栈空。for(i=1; i=n; i+) /n个整数序列作处理。scanf(“%d”,x); /从键盘读入整数序列。if(x!=-1) / 读入的整数不等于-1时入栈。if(top=maxsize-1)printf(“栈满n”);exit(0);else s+top=x; /x入栈。else /读入的整数等于-1时退栈。if(top=0)printf(“栈空n”);exi

5、t(0);else printf(“出栈元素是%dn”,stop-)；/算法结4、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#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、后序遍历最终访问根结点，即在递归算法中，根是压在栈底的。采纳后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中全部元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必定先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一帮助

8、栈中。再连续遍历到结点q时，将栈中元素从栈顶开头逐个到帮助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typedef structbitree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大bitree ancestor(bitree root,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=root;while(bt!=null |top0)while(bt!=null bt!=p bt!=q) /结点入栈s+top.t=bt; stop.t

9、ag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i=top;i+) s1i=si; top1=top; /将栈s的元素转入帮助栈s1 保存if(bt=q) /找到q 结点。for(i=top;i0;i-)/；将栈中元素的树结点到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; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束ancestor6、4、void linklist_reverse(linklist l)/链表的就地逆置;为简化算法,假设表长大于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、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中全部重复消失的结点，使得info域相等的结点只保留一个。#include stdio.htypedef char datatype;typedef struct nodedatatype data;struct node * next; listnode;typedef listnode* linklist;/*-*/* 删除单链表中重复的结点 */*-*/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结点值相同的结点*/q=q-next;p=p-next;return head;9、设一棵二叉树的结点结构为 (llink,info,rlink),root为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ancestor（root，p,q,r）,该算法找到p和q的最近共同祖先结

13、点r。10、由于后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入帮助栈中，帮助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则帮助栈中内容即为所求。void longestpath(bitree bt)/求二叉树中的第一条最长路径长度bitree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点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) /当前结点的右分枝已遍历if(!stop-lc !stop-rc) /只有到叶子结点时，才查看路径长度if(toplongest) for(i=1;i=top;i+) li=si; longest=top; top-;/保留当前最长路径到l栈，记住最高栈顶指针，退栈else if(top0) tagtop=1; p=stop.rc; /沿右子分枝向下/while(p!=null|top0)/结束longestpath11、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的挨次连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表

15、指针。分析你的算法的时、空简单度。12、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为s1，s2，sm,后序序列是p1,p2,，pm。因后序序列最终一个元素pm是根，则在中序序列中可找到与pm相等的结点（设二叉树中各结点互不相同）si(1im)，因中序序列是由中序遍历而得，所以si是根结点，s1，s2，si-1是左子树的中序序列，而si+1,si+2,sm是右子树的中序序列。若i=1，则s1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则s2

16、，s3，sm和p1，p2，pm-1可以唯一确定右子树，从而也确定了二叉树。若i=m,则sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则s1，s2，sm-1和p1，p2，pm-1唯一确定左子树，从而也确定了二叉树。最终，当1im时，si把中序序列分成s1，s2，si-1和si+1,si+2,，sm。由于后序遍历是“左子 2021年贵州省c+语言版大纲 树右子树根结点”，所以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、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为s1，s2，sm,后序序列是p1,p2,，pm。因后序序列最终一个元素pm是根，则在中序序列中可找到与pm相等的结点（设二叉树中各结点互不相同）si(1im)，因中序序列是由中序遍历而得，所以si是根结点，s1，s2，si-1是左子树的中序序列，而si+1,si+2,sm是右子树的中序序列。若i=1，则s1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则s2，

18、s3，sm和p1，p2，pm-1可以唯一确定右子树，从而也确定了二叉树。若i=m,则sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则s1，s2，sm-1和p1，p2，pm-1唯一确定左子树，从而也确定了二叉树。最终，当1im时，si把中序序列分成s1，s2，si-1和si+1,si+2,，sm。由于后序遍历是“左子树右子树根结点”，所以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、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）a和d是合法序列，b和c 是非法序列。（2）设被判定的操作序列已存入一维数组a中。int judge(char a)/推断字符数组a中的输入输出序列是否是合法序列。如是，返回true，否则返回false。i=0; /i为下标。j=k=0; /j和k分别为i和字母o的的个数。while(ai!=0) /当未到字符数组尾就作。switch(ai)casei: j+; break; /入栈次数增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);/算法结束。15、两棵空二叉树或仅有根结点的二叉树相像；对非空二叉树， 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)/结束similar16、假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）a和d是合法序列，b和c 是非法序列。（2）设被判定的操作序列已存入一维数组a中。int judge(char a)/推断字符数组a中的输入输出序列是否是合法序列。如是，返回true，否则返回false。i=0; /i为下标。j=k=0; /j和k分别为i和字母o的的个数。while(ai!=0)

22、/当未到字符数组尾就作。switch(ai)casei: j+; break; /入栈次数增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);/算法结束。17、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种

23、排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）18、设t是一棵满二叉树，编写一个将t的先序遍历序列转换为后序遍历序列的递归算法。19、对一般二叉树，仅依据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，依据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。void pretopost(elemtype pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最终结点的下标。if(h1=l1)posth2=prel1; /根结点ha

24、lf=(h1-l1)/2; /左或右子树的结点数pretopost(pre,post,l1+1,l1+half,l2,l2+half-1) /将左子树先序序列转为后序序列pretopost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /pretopost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最终叶子结点的rchild为空 2021年贵州省c+语言版大纲 。 linkedlist head,p

25、re=null; /全局变量linkedlist inorder(bitree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为headif(bt)inorder(bt-lchild); /中序遍历左子树if(bt-lchild=null bt-rchild=null) /叶子结点if(pre=null) head=bt; pre=bt; /处理第一个叶子结点elsepre-rchild=bt; pre=bt; /将叶子结点链入链表inorder(bt-rchild); /中序遍历左子树pre-rchild=null; /设置链表尾return(head); /inor

26、der时间简单度为o(n),帮助变量使用head和pre,栈空间简单度o(n)20、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）21、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29. 试找出满意下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同22、请编写一个判别给定二叉

27、树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。23、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。48.有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的拓扑排序的结果。g拓扑排序的结果是：v1、v2、v4

28、、v3、v5、v6、v725、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的具体算法，并用程序实现你所给出的算法。注：圈就是回路。26、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到帮助向量d1.n前半部和后半部（注:向量d可视为循环表），其原则为，先将rl赋给d1，再从r2 记录开头分二路插入。编写实现二路插入排序算法。27、 将顶点放在两个集合v1和v2。对每个顶点，检查其和邻 2021年贵州省c+语言版大纲

29、接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int bpgraph (adjmatrix g)/推断以邻接矩阵表示的图g是否是二部图。int s; /顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）int q;/q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。int f=0,r,visited; /f和r分别是队列的头尾指针,visited是访问数组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;/预备v的邻接点的集合号if (!visitedv)visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应在一个集合中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、约瑟夫环问题（josephus问题）是指编号为1、2、，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开头按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开头报数，数到第m的人又出列，如此重复直到全部的人全部出