2022年山西省资料总结高阶.docx

2022年山西省资料总结高阶 1、二叉树的层次遍历序列的第一个结点是二叉树的根实际上，层次遍历序列中的每个结点都是“区域性根”确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三局部 若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根这样，定义一个全域性变数指标r，指向层次序列待处理元素演算法中先处理根结点，将根结点和左右子女的资讯入伫列 然后，在伫列不空的条件下，迴圈处理二叉树的结点伫列中元素的资料结构定义如下： typedef struct qnode; bitree creat(datatype in,level,int n) //由二叉树的层次序列level[n]和中序序列in[n]生成二叉树 n是二叉树的结点数 qnode s,是元素为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; iif (in[i]==level[0]) break; if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树 else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树 else //根结点有左子树和右子树 while (!empty(q)) //当伫列不空，进行迴圈，构造二叉树的左右子树 else if (i== else }//结束while (!empty(q)) return(p); }//演算法结束 2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连线，边上的wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的演算法，并应用该演算法解答如图所示的例项。

20分） 3、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查询方法用二分查询，要求计算出查询关键字62时的比较次数并计算出查询胜利时的平均查询长度 4、二部图（bipartite graph） g=（v，e）是一个能将其结点集v分为两不相交子集v 1和v2=v-v1的无向图，使得：v1中的任何两个结点在图g中均不相邻，v2中的任何结点在图g中也均不相邻 （1）．请各举一个结点个数为5的二部图和非二部图的例子 （2）．请用c或pascal编写一个函式bipartite判断一个连通无向图g是否是二部图，并分析程式的时间複杂度设g用二维阵列a来表示，大小为n*n（n为结点个数）请在程式中加必要的注释 若有必要可直接利用堆叠或伫列操作 5、有一个带头结点的单连结串列，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指标域next假设单连结串列已建立，设计演算法删除单连结串列中全部重複出现的结点，使得info域相等的结点只保存一个 #include typedef char datatype; typedef struct node listnode; typedef listnode* linklist; /* 删除单连结串列中重複的结点 */ linklist deletelist(linklist head) else p=p->next; }return head;} 2022年山西省资料总结深入 1 证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

29 试找出满足以下条件的二叉树 1 先序序列与后序序列一样 2 中序序列... 2022年山西省考面试答题技巧 版权全部，翻版必究 中公训练临汾分校面试答题切忌走套路 採用套路答题，在肯定程度上能够帮 生提高面试适应性，但并没有从根本上 提高学生的答题...2022年山西省资料总结大纲 1 设t是给定的一棵二叉树，下面的递迴程式count t 用于求得 二叉树t中具有非空的左，右两个儿子的结点个数n2 只有非空左儿子的个数n...。