《江西省数据分析入门》由会员分享，可在线阅读，更多相关《江西省数据分析入门（10页珍藏版）》请在金锄头文库上搜索。
1、1、我们用l代表最长平台的长度,用k批示最长平台在数组b中的起始位置(下标)。用j记住局部平台的起始位置，用i批示扫描b数组的下标,i从0开始，依次和后续元素比较，若局部平台长度（ij)不小于l时，则修改最长平台的长度k(l=ij)和其在b中的起始位置（k=j),直到数组结束，即为所求。vi Platform（n b, n N)/求具有个元素的整型数组b中最长平台的长度。=;k0;0;i=0;while(in-1）while(il) j+;k=j; /局部最长平台i;j=i; /新平台起点pintf(“最长平台长度%,在b数组中起始下标为%d”，k);/ Pafor2、设从键盘输入一整数的序列
2、：a,a, a3,an,试编写算法实现:用栈构造存储输入的整数，当i-1时，将i进栈；当a=-1时,输出栈顶整数并出栈。算法应对异常状况（入栈满等)给出相应的信息。设有一种背包可以放入的物品重量为S，既有件物品，重量分别为W1,W2，.,n。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数na（,n)表达背包问题的解,Wi（i=1，.，n)均为正整数,并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其对的求解背包问题。nap（S，n）若S=则Kaptrue否则若（S0且n1)则napfalse否则若Knap(1) ， _=true则pit(W);Kn u
3、否则 KnapKnp(2） _, _ 设有一种顺序栈S,元素s1， s，s3, s4, s5， s依次进栈，如果6个元素的出栈顺序为s2， , 4, s6, s5,s,则顺序栈的容量至少应为多少?画出具体进栈、出栈过程。假定采用带头结点的单链表保存单词，当两个单词有相似的后缀时，则可共享相似的后缀存储空间。例如：设sr和str2是分别指向两个单词的头结点，请设计一种尽量的高效算法,找出两个单词共同后缀的起始位置，分析算法时间复杂度。将(）个整数寄存到一维数组R中。设计一种尽量高效（时间、空间）的算法,将R中保存的序列循环左移p(0padjvex=0） dfs(p-advex)；p=-ne; /
4、while vstdv=0; num-; /恢复顶点v/dfoid udgeRot（)/判断有向图与否有根,有根则输出之。 atc int i;fo (i=1；0) while() stop=p；tagp=0； p=pLc; /沿左分枝向下f(tgtop=1） /目前结点的右分枝已遍历 if（!stop& !so-Rc） /只有到叶子结点时，才查看途径长度if（toplogest) for（=1；i=tp;i+) lis; longet=top;top-;/保存目前最长途径到栈，记住最高栈顶指针,退栈 else if（top0） tagtop=1； =stop.Rc; /沿右子分枝向下 /ie
5、（!=nll|top0)/结束LongestPath6、二叉树的层次遍历序列的第一种结点是二叉树的根。事实上,层次遍历序列中的每个结点都是“局部根”。拟定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层顺序列根结点的背面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层顺序列的根结点后也只有左子树的根或右子树的根。这样,定义一种全局变量指针R,指向层顺序列待解决元素。算法中先解决根结点,将根结点和左右子女的信息入队列。然后,在队列不空的条件下，循环解决二叉树的结点。队列中元素的数据构造定义如下:tpederuct it lvl; /层
6、顺序列指针,总是指向目前“根结点”在层顺序列中的位置intl,h; /中序序列的下上界int ； /层顺序列中目前“根结点”的双亲结点的指针it lr; /1双亲的左子树 2双亲的右子树qnode; BiTre Creat(dtape ,lvel,int n)/由二叉树的层顺序列levln和中序序列inn生成二叉树。 n是二叉树的结点数i(n1) rinf(“参数错误n”); exit(0);node s,Q; /是元素为qnde类型的队列,容量足够大 nt(Q)； int R0； /R是层顺序列指针，指向目前待解决的结点 BiTreep=(BiTre）malloc(sieof(iNode）)
7、; 生成根结点 -daa=evl; plchld=null; -rcil=nul； /填写该结点数据r (i0; in; +) /在中序序列中查找根结点，然后,左右子女信息入队列 i(ni=eel0） break；i(=0) /根结点无左子树，遍历序列的1n-1是右子树p-lchild=nll; s.vl=+R; s.=+;s.=n-1; s.p; .lr2;queu（Q,s); ee i（i=n-1） /根结点无右子树，遍历序列的1n-1是左子树prchld=null； s.lv=+; .l=1； .=i-1; s.fp;s.lr=1; nqeue(Q,s）; els/根结点有左子树和右子树
8、.l=+; .l=0; s.h=i; s.f=p； lr=1;eueu(,）;/左子树有关信息入队列.v=+； .l=i+1；sh=n；s.=p;.l=2;nquee(Q,);/右子树有关信息入队列while (!empty(Q) 当队列不空，进行循环,构造二叉树的左右子树 =equeu(）； faher=s.f; fo (s.l; idatalevellvl; -lchild=null; p-rchid=nll； /填写该结点数据if (.lr） father-lcildp; lse farrchid=;让双亲的子女指针指向该结点 i (i=s.l) p-lchld=nll; /解决无左子女
9、.lv=+R; .l=i+1;s.f=p; s.r=2; nueu（,s); elsei （=h) -rcil=ll； 解决无右子女 s.vl=+R; h=i-1; f=p; s.l; euee（,s); eles.lvl=+R; sh=i-1； s.f=p; s.lr; nqeu(Q,）;/左子树有关信息入队列 s.lvl=+R；s.l=i+1; s.f=p; .l=; eueue(,s);/右子树有关信息入队列 /结束whie (!ey(Q）)return();/算法结束、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n-条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条目前权值最大的边后,就去测试图与否仍连通,若不再连通，则将该边恢复。若仍连通，继续向下删;直到剩n-1条边为止。 vd SpTe (AdList ) /用“破圈法”求解带权连通无向图的一棵最小代价生
