资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
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 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、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r, 不失一般性,设 p在q的左边。后序遍历必然先遍历到结点p,栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就是结点 p 和q的最近公共祖先。typedef struct BiTree 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.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性,假定 p在q的左侧, 遇结点p时,栈中元素均为p的祖先结点for(i=1;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.tag=1;bt=stop.t-rchild; / 沿右分枝向下遍历/ 结束while(bt!=null |top0)return(null);/、p无公共祖先/ 结束Ancestor3、给定n个村庄之间的交通图,若村庄i 和j 之间有道路,则将顶点 i 和j用边连接,边上的 Wij 表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短 ?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。(20分)4、假设以 I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I 和O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分) (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对( 1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回 true ,否则返回 false (假定被判定的操作序列已存入一维数组中)。5、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量pre(初值为 null )和全局变量 flag ,初值为 true 。若非二叉排序树,则置flag 为false 。#define true 1#define false 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; void JudgeBST(BTree t,int flag)/ 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由flag 得出结论。 if(t!=null & flag) Judgebst(t-llink,flag);/ 中序遍历左子树 if(pre=null )pre=t ;/ 中序遍历的第一个结点不必判断 else if(pre-datadata)pre=t ;/ 前驱指针指向当前结点 elseflag=flase; /不是完全二叉树 Judgebst (t-rlink,flag);/ 中序遍历右子树/JudgeBST 算法结束6、设从键盘输入一整数的序列:a1, a2, a3,an, 试编写算法实现:用栈结构存储输入的整数,当ai -1时,将ai 进栈;当 ai=-1 时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。设有一个背包可以放入的物品重量为S,现有n件物品,重量分别为 W1 ,W2 ,. ,Wn 。问能否从这 n件物品中选择若干件放入背包,使得放入的重量之和正好是 S。设布尔函数 Knap(S,n)表示背包问题的解,Wi(i=1,2,.,n)均为正整数,并已顺序存储地在数组W 中。请在下列算法的下划线处填空,使其正确求解背包问题。Knap(S,n)若S=0则Knaptrue否则若( S0且n1) 个整数存放到一维数组 R 中。设计一个尽可能高效(时间、空间)的算法,将R 中保存的序列循环左移 p(0pn)个位置,即将 R 中的数据(x0, x1, x2, , xn-1),变换为 (xp , xp1, , xn-1 ,x0 ,x1, , xp-1)。7、题目中要求矩阵两行元素的平均值按递增顺序排序,由于每行元素个数相等,按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和,放入一维数组中,然后选择一种排序方法,对该数组进行排序,注意在排序时若有元素移动,则与之相应的行中各元素也必须做相应变动。void Translation(float *matrix,int n )/ 本算法对 nn的矩阵matrix ,通过行变换,使其各行元素的平均值按递增排列。int i,j,k,l;float sum ,min; /sum暂存各行元素之和 float *p, *pi, *pk;for(i=0; in; i+) sum=0.0; pk=matrix+i*n; /pk指向矩阵各行第 1个元素. for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum; /将一行元素之和存入一维数组. /for ifor(i=0; in-1; i+) /用选择法对数组 p进行排序 min=*(p+i); k=i; /初始设第 i 行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /记新的最小值及行号.if(i!=k) /若最小行不是当前行 , 要进行交换 (行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1个元素. pi=matrix+n*i; /pi指向第i 行第1个元素. for(j=0;jn;j+) /交换两行中对应元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和. /if/for i free(p); /释放p数组./ Translation 算法分析 算法中使用选择法排序 , 比较次数较多 , 但数据交换 (移动)较少. 若用其它排序方法 , 虽可减少比较次数 , 但数据移动会增多 . 算法时间复杂度为 O(n2).8、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据,试建立一个带有头结点的循环链表,头指针为 h,要求链中数据从小到大排列,重复的数据在链中只保存一个.9、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用llink-rlink法存储。10、在有向图 G 中,如果 r到G 中的每个结点都有路径可达,则称结点r为G 的根结点。编写一个算法完成下列功能:(1)建立有向图 G 的邻接表存储结构;(2)判断有向图 G 是否有根,若有,则打印出所有根结点的值。11、本题要求建立有序的循环链表。从头到尾扫描数组A,取出Ai(0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai 的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束12、有一种简单的排序算法,叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示 )进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值为 c,那么,这个记录在新的有序表中的合适的存放位置即为c。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C 语言编写实现计数排序的算法; (3) (4分)对于有n个记录的表,关键码比较次数是多少? (4) (3分)与简单选择排序相比较,这种方法是否更好?为什么?13、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全局变量指针R ,指向层次序列待处理元素。算法中先处理根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中元素的数据结构定义如下:typedef struct int lvl; /层次序列指针,总是指向当前“根结点”在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点”的双亲结点的指针int lr; / 1双亲的左子树 2 双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/ 由二叉树的层次序列 leveln和中序序列 inn 生成二叉树。 n是二叉树的结点数if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; ilchild=null;s.lvl=+R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s);else if (i=n-1) /根结点无右子树,遍历序列的1n-1是左子树p-rchild=null; s.lvl=+R; s.l=1; s.h
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号