当前位置:首页 >> 韩语学习 >>

2015年澳门特别行政区重要数据摘要


1、设 T 是一棵满二叉树,编写一个将 T 的先序遍历序列转换为后序遍历序列的递归算法。 2、 我们可用 “破圈法” 求解带权连通无向图的一棵最小代价生成树。 所谓 “破圈法” 就是 “任 取一圈,去掉圈上权最大的边” ,反复执行这一步骤,直到没有圈为止。请给出用“破圈法” 求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算 法。注:圈就是回路。 3、假设以 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(A[i]!=‘\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增 1。 case‘O’: k++; if(k>j){printf(“序列非法\n”);exit(0);} } i++; //不论 A[i]是‘I’或‘O’ ,指针 i 均后移。} if(j!=k) {printf(“序列非法\n”);return(false);} else {printf(“序列合法\n”);return(true);} }//算法结束。 4、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结 点都是 “局部根” 。 确定根后, 到二叉树的中序序列中, 查到该结点, 该结点将二叉树分为 “左 根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序 列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。 这样,定义一个全局变量指针 R,指向层次序列待处理元素。算法中先处理根结点,将根结 点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中 元素的数据结构定义如下: typedef struct { int lvl; //层次序列指针,总是指向当前“根结点”在层次序列中的位置 int l,h; //中序序列的下上界 int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列 level[n]和中序序列 in[n]生成二叉树。 n 是二叉树的结点数 {if (n<1) {printf(“参数错误\n”); exit(0);} qnode s,Q[]; //Q 是元素为 qnode 类型的队列,容量足够大 init(Q); int R=0; //R 是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点

p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 for (i=0; i<n; i++) //在中序序列中查找根结点,然后,左右子女信息入队列 if (in[i]==level[0]) break; if (i==0) //根结点无左子树,遍历序列的 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); } else if (i==n-1) //根结点无右子树,遍历序列的 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 //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { 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)); //申请结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据 if (s.lr==1) father->lchild=p; else father->rchild=p; //让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; //处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (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);//左子树有关信息入队 列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列 } }//结束 while (!empty(Q)) return(p); }//算法结束


相关文章:
2012年澳门特别行政区分析数据摘要.pdf
2012年澳门特别行政区分析数据摘要 - 1、设有一组初始记录关键字为(45,8
2012年澳门特别行政区基础数据摘要.txt
2012年澳门特别行政区基础数据摘要_计算机软件及应用_IT/计算机_专业资料。1、...文档贡献者 vedwlolc811845 贡献于2015-11-30 相关文档推荐 暂无相关推荐文档...
2013年澳门特别行政区学习数据库摘要.doc
2013年澳门特别行政区学习数据摘要 - 1、若第 n 件物品能放入背包,则问
2015年澳门特别行政区数据基础理论纲要.doc
2015年澳门特别行政区数据基础理论纲要 - 1、题目中要求矩阵两行元素的平均值
2015年澳门特别行政区数据库入门基础.doc
2015年澳门特别行政区数据库入门基础_韩语学习_外语学习_教育专区。2015年澳门特别行政区数据库入门基础 1、我们用 l 代表最长平台的长度,用 k 指示最长平台在...
2011年澳门特别行政区数据摘要.txt
2011年澳门特别行政区数据摘要_数学_小学教育_教育专区。2011年澳门特别行政区数据摘要 1、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列...
2015三级澳门特别行政区资质要求(必备资料).pdf
2015三级澳门特别行政区资质要求(必备资料)_天文/地理_自然科学_专业资料。
2014年澳门特别行政区重要数据深入.txt
2014年澳门特别行政区重要数据深入 - 1、本题应使用深度优先遍历,从主调函数
2015澳门特别行政区会计基础(必备资料).txt
2015澳门特别行政区会计基础(必备资料)_韩语学习_...编制及时【答案解析】会计报表各项目的数据必须建立在...混合式【答案解析】利润表的格式主要有多步式和单...
2015年澳门特别行政区信息系统项目管理师知识大全.txt
2015年澳门特别行政区信息系统项目管理师知识大全_韩语学习_外语学习_教育专区。...监理规划 14、由于建设工程项目大量数据处理的需要,在当今时代应重视利用信息技术...
2012澳门特别行政区数据简介加强.doc
2012澳门特别行政区数据简介加强 - 1、约瑟夫环问题(Josephus 问题
2013年澳门特别行政区数据分析加强.pdf
2013年澳门特别行政区数据分析加强 - 1、二部图(bipartite gra
2013年澳门特别行政区数据概述入门.txt
2013年澳门特别行政区数据概述入门 - 1、题目中要求矩阵两行元素的平均值按递
2015年澳门特别行政区市场营销策划师(中级)考试技巧、....txt
2015年澳门特别行政区市场营销策划师(中级)考试技巧、答题原则 - 1、按照《WBSA个人认证规范》规定:企划员(初级商务策划师)在策划思维方面主要应具备...
关于澳门特别行政区会展业的发展研究.doc
关于澳门特别行政区会展业的发展研究 - 关于澳门特别行政区博彩业的发展研究 摘要:澳门博彩业历史悠久,跨越了三个世纪。作为澳门经济的主要支柱,博彩业长期以来 ...
2015年澳门特别行政区安全工程师管理知识考点:常用的安....txt
2015年澳门特别行政区安全工程师管理知识考点:常用的安全评价方法(必备资料) 1、某公司是一家工程建设公司,多年来积累了大量的安全生产数据,该公司拟用统计图方式...
2015年澳门特别行政区法律硕士(非法学)考研考试技巧与口诀.txt
2015年澳门特别行政区法律硕士(非法学)考研考试技巧与口诀 - 1、关于罪数的
2015澳门特别行政区小学数学试卷.pdf
2015澳门特别行政区小学数学试卷_韩语学习_外语学习_教育专区。2015澳门特别行政区小学数学试卷 1、如果从初三(1) 、(2) 、(3)班中随机抽取一个班与初三(4)...
2015澳门特别行政区初中数学试卷.pdf
2015澳门特别行政区初中数学试卷_韩语学习_外语学习_教育专区。2015澳门特别行政区初中数学试卷 1、 1 小时 15 分=( )小时 5.05 公顷=( )平方米 2、 如图,...
2015澳门特别行政区公务员考试公共基础知识最新考试试....doc
2015澳门特别行政区公务员考试公共基础知识最新考试试题库(完整版)_韩语学习_外语学习_教育专区。2015澳门特别行政区公务员考试公共基础知识最新考试试题库(完整版) ...
更多相关标签: