《青海省数据分析高级知识》由会员分享，可在线阅读，更多相关《青海省数据分析高级知识（9页珍藏版）》请在金锄头文库上搜索。
1、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)_
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、后序遍历最后访问根结点，即在递归算法中，根是压在
3、栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找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
4、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的最近共同的祖先已找到”)；ret
5、urn (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个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短 ?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实
6、例。（20分）4、假设以 I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分） （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（ 1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true ，否则返回 false （假定被判定的操作序列已存入一维数组中）。5、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设
7、全局指针变量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
8、）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件物
9、品中选择若干件放入背包，使得放入的重量之和正好是 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、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行
10、元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。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个元素.
11、 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
12、(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，要求链中数据从小到大排列
13、，重复的数据在链中只保存一个.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) /重复数据不
14、再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束12、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示 )进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为c
15、。 (1) (3分)给出适用于计数排序的数据表定义; (2) (7分)使用Pascal或C 语言编写实现计数排序的算法； (3) (4分)对于有n个记录的表，关键码比较次数是多少? (4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?13、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针
16、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
