2023河南省数据分析深入

1、1、在有向图G中，如果r到G中的每个结点都有路径可达，那么称结点r为G的根结点。编写一个算法完成以下功能：1建立有向图G的邻接表存储结构；2判断有向图G是否有根，假设有，那么打印出所有根结点的值。2、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) /求二叉树bt 的第k(k1) 层上叶子结点个数if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针

2、, leaf是叶子结点数int last=1,level=1; Q1=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数while(frontlchild & !p-rchild) leaf+; /叶子结点 if(p-lchild) Q+rear=p-lchild; /左子女入队 if(p-rchild) Q+rear=p-rchild; /右子女入队 if(front=last) level+; /二叉树同层最右结点已处理,层数增1 last=rear; /last移到指向下层最右一元素if(levelk) return (leaf); /层数大于k 后退出运行 /whi

3、le /结束LeafKLevel3、(1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild)25. (1)t-rchild!=null (2)t-rchild!=null (3)N0+ (4)count(t-lchild) (5)count(t-rchild)26. .(1)top+ (2) stacktop=p-rchild (3)top+ (4)stacktop=p-lchild27. (1)*ppos / 根结点2rpos=ipos (3)rposipos (4)ipos (5)ppos+14、

4、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。5、给定n个村庄之间的交通图，假设村庄i和j之间有道路，那么将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如下列图的实例。20分void Hospital(AdjMatrix w,int n) /在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 for (k=1;k=n;k+) /求任意两顶点间的最短路径 for (i

5、=1;i=n;i+) for (j=1;j=n;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;j=n;j+) /求从某村庄i1=is) s=wij; if (s=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离为%dn,i,m); /for/算法结束对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在

6、第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网G，请用Prim算法构造其最小生成树每选取一条边画一个图。6、二部图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*nn为结点个数。请在程序中加必要的注释。假设有必要可直接利用堆栈或队列操作。【

7、7、有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,写出G的拓扑排序的结果。G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7 8、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组rl.h中。假设查找成功，那么输出该记录在r数组中的位置及其值，否那么显示“not find信息。请编写出算法并简要说明算法思想。9、将顶点放在两个集合V1和V2。对每个

8、顶点，检查其和邻接点是否在同一个集合中，如是，那么为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) /判断以邻接矩阵表示的图g是否是二部图。 int s; /顶点向量，元素值表示其属于那个集合值1和2表示两个集合 int Q;/Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。 int f=0,r,visited; /f和r分别是队列的头尾指针,visited是访问数组 for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各顶点未确定属于那个集合 Q1=1; r=1; s1=1;/顶

9、点1放入集合S1while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/准备v的邻接点的集合号 if (!visitedv) visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j=n;j+) if (gvj=1)if (!sj) sj=jh; Q+r=j; /邻接点入队列 else if (sj=sv) return(0); /非二部图 /if (!visitedv)/while return(1); /是二部图算法讨论 题目给的是连通无向图，假设非连通，那么算法要修改。10、连通图的生成树包括图中的全部n个顶点和足

10、以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 sca

11、nf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边假设仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，11、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根

12、结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTORROOT，p,q,r,该算法找到p和q的最近共同祖先结点r。12、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i=n; i+) /n个整数序列作处理。 scanf(“%d,&x); /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1时入栈。 if(top=maxsize-1)printf(“栈满n);exi

13、t(0);else s+top=x; /x入栈。 else /读入的整数等于-1时退栈。 if(top=0)printf(“栈空n);exit(0); else printf(“出栈元素是%dn,stop-)； /算法结13、给定n个村庄之间的交通图，假设村庄i和j之间有道路，那么将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如下列图的实例。20分void Hospital(AdjMatrix w,int n) /在以邻接带权矩阵表

14、示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 for (k=1;k=n;k+) /求任意两顶点间的最短路径 for (i=1;i=n;i+) for (j=1;j=n;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;j=n;j+) /求从某村庄i1=is) s=wij; if (s=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离

15、为%dn,i,m); /for/算法结束对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网G，请用Prim算法构造其最小生成树每选取一条边画一个图。14、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; i=n; i+) /n个整数序列作处理。 scanf(“%d,&x); /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1时入栈。 if(top=maxs