数据结构与算法数据结构.pdf

《数据结构与算法数据结构.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高等数据结构与算法图1最小-最大堆a.我们如何找到最小元和最大元？b.给出一个算法将一个新节点插入到该最小-最大堆中。答：（a）最小元即为根节点A，最大元即为A的左右孩子中的较大值；（b）假设插入节点为t,此堆的根节点记为P，其中P->next表示P的孩子，P->data表示节点P所储存的值。算法：t自根节点向下合并，每一次与节点比较后，从新赋值的t向右路径继续向下合并，直到其不再遇到节点为止（即最终的t成为叶子节点）。（1）t=max{t,P->data}，此时P->data=min{t,P->data},P=P->next;（2）t=min{t,P->

2、data}，此时P->data=max{t,P->data},P=p->next;（3）顺序重复上面两个步骤，当P=NULL，将t=P->data,结束。答：左式堆的任意节点作为根节点都是左式堆，合并的时候以右路径为突破口，尽量不破坏左部的良好特性。基本方法：（1）将合并堆的两根节点进行比较，较大的与较小根结点的右孩子合并。1（2）较小堆的右分支与先前合并进来的堆仍然是两个左式堆，递归调用（1）直到输出结果（在这里，当所比较的根节点中较小的如果没有右孩子，其较大的根节点带着堆就充当了较小根节点的右分支，递归结束）。输出结果：答：问题相当于“给出某一数组，其

3、中仅含有0，1，2三种元素，请按升序排列”这一问题。现设此数组为a[n];算法：1.从i=0：n-1，逐一检查a[i],当其为0时，i++;当其不为0时，令j=i,从j=i+1:n中找到第一个零元a[x],利用中间变量t将a[x]与a[i]交换顺序，并记下此时的j值，同时退出小循环。2.遍历i值，直到所有的零元被安放在数组的前部；3.寻找到第一个不是零元的下标i’,此时和前面的方式一样，只不过其条件改为是否为1，从而将后面的数组也能够排列好。算法复杂度分析：大循环中虽然嵌套了小循环，但由于小循环j值起点为上次循环终止的后继，终点为找到所需0元的下标+1（实

4、际上就是下一次小循环的起点），故而实际上其算法复杂度应为O(N),第三部的算法复杂度同样为O(N),则此算法符合题意。程序代码：#includeusingnamespacestd;intkeyword(int,int&,int);inta[15],n;intmain(){inti,k=0;intj=0;intm=0;2intl=0;cout<<"请输入n值：";cin>>n;cout<<"请输入序列：";for(i=0;i>a[i];}for(i=0;i

5、==1){j=i;keyword(i,j,0);}elsekeyword(i,j,0);}}for(i=0;i

6、(a[x]==c){y=a[i];a[i]=a[x];a[x]=y;break;}}j=x;returnj;}运行结果：答：使用回溯法，把有向图用邻接表表示，根据上面给图中每条边的流量空间为剩余流量空间，初始化整个图的最大流量max为0，首先计算从源节点出发所有路的流量总和和汇合到终点T的所有路的流量4的总和，用穷举法遍历所有的从源节点S到目的节点T且每条边的剩余流量空间大于0的路径，到找到一条从源节点到目的节点的路径，比较这条路径中的每条边的剩余流量中最小值，找出这条路径的瓶颈值neck，这条路径以该瓶颈值大小的流量在这条路上从源节点S流到终点T，相应把

7、这条路径上的每条边上剩余流量空间减去这个瓶颈值作为每条边的当前的剩余流量空间，且max=max+neck继续寻找，直到找不到符合条件的路径为止。最后得出这个图的最大流量为max.S→A→B→C→T1;S→D→E→F→T1;S→D→A→B→C→T1;S→G→H→E→F→T2;S→D→E→C→T2;S→G→H→I→T4;所以这个图最大流量是11.答：先将单词按值从小到大排列：Iaanditor。二叉查找树的规则：如果有左子树，则左子树的值小于根节点的值，如果有右子树，则右子树的值大于根节点的值。概率大的单词尽量往根节点排。在满足二叉树及概率大的单词尽量往根节点

8、排这两个要求的最优二叉数如下：andIitora5