tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 韩语学习 >>

2010西藏自治区数据要领基础


1、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编写 一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; (2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 2、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列 可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否则称为非法序列。 ( 15 分) (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回 true,否则返回 false(假定被判定的操作序列已存入一维数组中) 。 3 、二路插入排序是将待排关键字序列 r[1..n] 中关键字分二路分别按序插入到辅助向量 d[1..n]前半部和后半部(注: 向量 d 可视为循环表) ,其原则为,先将 r[l]赋给 d[1] ,再从 r[2] 记录开始分二路插入。编写实现二路插入排序算法。 4、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 n=1 时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当 n=m-1 时结论成立,现证明当 n=m 时结论成立。 设中序序列为 S1 , S2, ?, Sm, 后序序列是 P1,P2,?, Pm。 因后序序列最后一个元素 Pm 是根, 则在中序序列中可找到与 Pm 相等的结点(设二叉树中各结点互不相同)Si(1 ≤i≤m) ,因中 序序列是由中序遍历而得,所以 Si 是根结点,S1,S2 ,?,Si-1 是左子树的中序序列,而 Si+1,Si+2, ?,Sm 是右子树的中序序列。 若 i=1,则 S1 是根,这时二叉树的左子树为空,右子树的结点数是 m-1, 则{S2,S3,?,Sm} 和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若 i=m,则 Sm 是根, 这时二叉树的右子树为空, 左子树的结点数是 m-1, 则 {S1 , S2, ?, Sm-1} 和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。 最后,当 1<i<m 时,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} 可唯一确定二叉树的右子树 。 5、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) // 求二叉树 bt 的第 k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0); BiTree p=bt,Q[]; //Q 是队列,元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和 rear 是队头和队尾指针 , leaf 是叶子结点数 int last=1,level=1; Q[1]=p; //last 是二叉树同层最右结点的指针,level 是二叉树的层 数 while(front<=rear) {p=Q[++front]; if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队

if(p->rchild) Q[++rear]=p->rchild; if(front==last) {level++; last=rear; } if(level>k) return (leaf); }//while 6 、 已 }//结束 LeafKLevel 知 有 向 图 G=(V,E) , 其 中

//右子女入队

//二叉树同层最右结点已处理,层数增 1 //last 移到指向下层最右一元素 // 层数大于 k 后退出运行

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、 V3、V5、 V6、V7



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com