海南省简介 2013海南省数据简介入门.doc

海南省简介 2013海南省数据简介入门 导读：就爱阅读网友为您分享以下“2013海南省数据简介入门”资讯，希望对您有所帮助，感谢您对92的支持! 1、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={lt;V1,V2gt;,lt;V1,V3gt;,lt;V1,V4gt;,lt;V2,V5gt;,lt;V3,V5gt;,lt;V3,V6gt;,lt;V4,V6gt;,lt;V5,V7gt;,lt;V6,V7gt;} 写出G的拓扑排序的结果。 G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 2、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 29. ① 试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 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(kgt;j){printf(“序列非法\n”)；exit(0);} } i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {printf(“序列非法\n”)；return(false);} else {printf(“序列合法\n”)；return(true);} }//算法结束。 4、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(kgt;1) 层上叶子结点个数 {if(bt==null || klt;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(frontlt;=rear) {p=Q[++front]; if(level==k !p-gt;lchild !p-gt;rchild) leaf++; //叶子结点 if(p-gt;lchild) Q[++rear]=p-gt;lchild; //左子女入队 if(p-gt;rchild) Q[++rear]=p-gt;rchild; //右子女入队 if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(levelgt;k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel 5、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t-gt;lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t-gt;lchild!=NULL)(4)____; if (t-gt;rchild!=NULL) (5