2023河南省数据分析加强

1、1、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置下标。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，假设局部平台长度i-j大于l时，那么修改最长平台的长度kl=i-j和其在b中的起始位置k=j，直到b数组结束，l即为所求。void Platform (int b , int N) /求具有N个元素的整型数组b中最长平台的长度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最长平台i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d，l，k)

2、；/ Platform2、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。3、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小

3、代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 scanf(%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=

4、0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，4、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre初值为null和全局变量flag，初值为true。假设非二叉排序树，那么置flag为false。#define true 1#define false 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; voi

5、d JudgeBSTBTree t,int flag/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 ift!=null & flag Judgebstt-llink,flag；/ 中序遍历左子树 ifpre=nullpre=t；/ 中序遍历的第一个结点不必判断 else ifpre-datadatapre=t；/前驱指针指向当前结点 elseflag=flase； /不是完全二叉树 Judgebst t-rlink,flag；/ 中序遍历右子树/JudgeBST算法结束5、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和

6、后半部注:向量d可视为循环表，其原那么为，先将rl赋给d1，再从r2 记录开始分二路插入。编写实现二路插入排序算法。6、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29. 试找出满足以下条件的二叉树1先序序列与后序序列相同 2中序序列与后序序列相同3先序序列与中序序列相同 4中序序列与层次遍历序列相同7、设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，.，Wn。

7、问能否从这n件物品中选择假设干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,.，n)均为正整数，并已顺序存储地在数组W中。请在以下算法的下划线处填空，使其正确求解背包问题。Knap(S，n)假设S=0那么Knaptrue否那么假设S0且n1)个整数存放到一维数组R中。设计一个尽可能高效时间、空间的算法，将R中保存的序列循环左移p0pnext;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把L的元素逐个插入新表表头 q-next=p;s-

8、next=q;L-next=s;/LinkList_reverse9、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。 for(i=1; ilchild!=NULL) if (1)_ N2+; else NL+;else if (2)_ NR+; else (3)_ ;if(t-lchild!=NULL)(4)_; if (t-rchild!=NULL) (5)_; 26.树的先序非递归算法。void example(b) btre

9、e *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)_;11、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录

10、存放于数组rl.h中。假设查找成功，那么输出该记录在r数组中的位置及其值，否那么显示“not find信息。请编写出算法并简要说明算法思想。12、约瑟夫环问题Josephus问题是指编号为1、2、，n的nn0个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnod

11、e;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*当循环链表中的结点个数大于1时*/ p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ pre=p; p=p-next; co

12、unt+; pre-next=p-next; /*输出该结点，并删除该结点*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的报数起点*/ printf(%4d,k1-data); /*输出最后一个结点*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0

13、;i-) /*建立剩余n-1个结点*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ 13、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。此题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元

14、素从栈顶开始逐个到辅助栈中去匹配，第一个匹配即相等的元素就是结点p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大BiTree Ancestor(BiTree 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-lc

15、hild; /沿左分枝向下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的最近共同的祖先已找到)；return (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无公共祖先/结束Ancestor14、冒泡排序算法是把大的元素向上移气泡的上浮，也可以把小的元素向下移气泡的下沉请给出