4.
5.
(5) a).5个元素找中间元需要6次比较
A1 a2 a3 a4 a5 先从a1 a2 a3 a4中找最大元设为a4，需要3次，由于a4大于三个元素，因此不是中间元。A1 a2 a3 a5中找次大元，需要4次，又由于a1 a2比较了两次，多比较了一次，因此一共需要6次。 b).7个元素找中间元需要11次比较
由于五个元素找中间元需要六次比较，设a3为中间元，那么 A6 a7分别与a3比较，需要2次；
若a6 a7一个大于a3一个小于a3则a3就是中间元
若a6 a7都大于或都小于a3，在a6 a7 a4 a5中找最小元或在a1 a2 a6 a7中找最大元，需要3次。所以一共需要6+2+3=11次. c).9个元素找中间元需要16次比较 1—2—3 需3次 4—5—6 需3次 7—8—9 需3次
2，5，8找中间元 需要3次
由于1、2、8、9不可能是中间元，从3、7、4、5、6中找中间元，需要2+2次。共需要16次。
d).11个元素找中间元需要20次比较。 1—2—3—4—5 排序需要7次 6—7—8—9—10 排序需要7次 3—8比较需要1次
对1，2，9，10均不可能成为中间元，七个元素中找中间元，需要11次，又由于3—4—5 6—7—8 有序，可以省去6次比较，共需要7+7+1+11-6=20 输入n个元素，输出m个最小的元素（其中n>>m）
(1)将所有n个元素放在数组A中从第n个位置开始的空间里(作为树的叶子)，之后n个元素两两一组(A[i],A[i+1])进行比较，使用较小元素的索引作为这两个节点的父亲结点(A[i/2])，之后向上一次建树。这样可以建立起一棵树T，T的内部结点都是索引值，叶子节点保存实际的数值。
(2) 输出当前树T的根节点root指向的值，之后将该值设置成+∞ ，对树T中root指向的值从叶子节点到根节点经过的路径进行调整，使之满足父结点是两个儿子当中值较小者的索引。
(3)反复执行第2步，直到找够m个最小元素 对于如下输入序列，画出红黑树的生成过程。 1，6， 4， 8， 9， 7， 2， 5， 3
6.
红黑树证明：
1).高度为h的红黑树T的内部黑节点数至少为2^h-1 2)高度为h的红黑树T的内部节点数至多为4^h-1 3）任意黑色节点的深度最多是其黑色深度的2倍
3）设一个黑色节点的深度为h，即它到达根节点经过的边数为h，也就是说经过的节点数（包括根节点且不包括该黑色节点本身）为h。 由于红黑树中不会出现红色节点有红色的子节点，故每一个红色节点一定会连向至少一个黑色节点。
设所经过的红色节点数为x，黑色节点数为y，则x <= y，故h = x+y <= y+y = 2y，而该黑色节点的黑色深度即为y，说明该黑色节点的深度h <= 2y，即小于其黑色深度的2倍，命题得证。 7. 动态数组规划
当需要增大数组时，将当前数组大小乘4，或者将当前数组大小乘2。评价这两种方法在时间和空间上的表现。
解析：假定在有向序列中插入第（n+1）个元素时需要双倍扩充数组。 设复制一个元素到新序列中耗时为t。
由于数组经过多次（假设为k次）扩充和复制，所以总耗时 T = t*(n + n/2 + n/4 +…+n/2k-1) <= 2nt 同理，对于四倍复制，总耗时
T = t*(n + n/4 + n/16 +…+n/4k-1) <= 4nt/3 对于空间消耗，两倍复制会分配原来数组大小的两倍空间，而四倍复制会分配原来数组大小的四倍空间
1.给出Prim算法描述、程序、时间复杂度分析、并证明正确性。
a) 算法描述：假设V是图的顶点集合，TE为最小生成树中边的集合，则prim算法通过一下步骤可以得到最小生成树。
1.初始化：U={u0}，TE={}，此步骤设立一个只有结点u0的节点集U和一个空边集TE作为最小生成树的初始状态，在随后算法执行中，这个状态会不断的发生变化，直到得到最小生成树为止。
2.在所有u属于U，v属于V-U的边（u,v）属于E中，找一条权最小的边（u0,v0），将此边加进集合TE中，并将此边的非U中的顶点加入U中。
此步骤的功能是在边集E中找一条边，要求这条边满足一下条件：首先边的两个顶点要分别在顶点集合U和V-U中，其次边权要最小，找到这条变以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点放入U中。这一步骤算法要执行多次，每次执行，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态集合。 3.如果U=V，则算法结束，否则重复步骤2.
b) prim算法是基于顶点来实现最小生成树的，我们假设使用邻接矩阵来存储图的，在prim
算法实现的过程中，我们需要知道以下两类信息
1.集合T1内各顶点到集合T2中个顶点的权值最小边的权值 //其中T2集合是表示这些集合中的点已经是最小生成树中的点了
2.集合T1内个顶点距离集合T2中哪个顶点的距离最小 为此，我们用两个数组来实现上面两类信息 lowcost[maxn]:用来实现1. nearvex[maxn]:用来实现2.
实际上如果只是要计算最小生成树的最小代价是不需要使用nearvex[maxn]这个数组的，这个数组只是用来记录在构造最小生成树中的顶点的顺序。 prim算法的思想：
初始：lowcost[k]=edge[v0][k] , nearvex[k]=v0;其中v0指的是从哪点来构造最小生成树。
当lowcost[i]=-1时我们让它表示i顶点加入到了T2集合， 什么样的情况下我们将i结点加入到T2集合呢？
我们选择那些在T1集合中，距离T2集合中点最小的lowcost[k],将该点k加入到集合T2中，
加入后我们应该改变那些在T1集合中点到T2集合中的最小权值，如果edge[k][i] 则将lowcost[i]=edge[k][i];nearvex[i]=k;这就完成了一次操作，进行n-1次后，就能构成一个最小生成树 #include 6 int edge[maxn][maxn]; 7 int lowcost[maxn]; 8 int nearvex[maxn]; 9 void prim(int u0) 10 { 11 int sumweight=0; 12 int i,j; 13 for(i=1;i<=n;i++)//顶点是从1开始 14 { 15 lowcost[i]=edge[u0][i]; 16 nearvex[i]=u0; 17 } 18 lowcost[u0]=0; 19 nearvex[u0]=-1; 20 for(i=1;i 22 int min=inf; 23 int v=-1; 24 for(j=1;j<=n;j++) 25 { 26 if(nearvex[j]!=-1&&lowcost[j] 28 min=lowcost[j]; 29 v=j; 30 } 31 } 32 if(v!=-1) 33 { 34 printf(\,nearvex[v],v,lowcost[v]); 35 nearvex[v]=-1; 36 sumweight+=lowcost[v]; 37 for(j=1;j<=n;j++) 38 { 39 if(nearvex[j]!=-1&&edge[v][j] 42 lowcost[j]=edge[v][j]; 43 nearvex[j]=v; 44 } 45 } 46 } 47 } 48 printf(\,sumweight); 49 } 50 int main() 51 { 52 int i,j; 53 int u,v,w; 54 scanf(\,&n,&m); 55 memset(edge,0,sizeof(edge)); 56 for(i=1;i<=m;i++) 57 { 58 scanf(\,&u,&v,&w); 59 edge[u][v]=edge[v][u]=w; 60 } 61 for(i=1;i<=n;i++) 62 { 63 for(j=1;j<=n;j++) 64 { 65 if(i==j) 66 edge[i][j]=0; 67 else if(edge[i][j]==0) 68 edge[i][j]=inf; 69 70 } 71 } 72 prim(1);//从顶点1中构造最小生成树 73 return 0; 74 } Prim算法正确性证明： 证：设计算机给出的MST为T1，存在最优的最小生成树T2*，它是在最小生成树与T1相同边的数量最多的那棵MST。假定e2=xy为与T2*中且不在T1中具有权值最小的边。记在T1中，从根结点A到x的路径为Px1x2..xs(x1=A,xs=x)，从根节点A到y的路径为Py1y2…yt(y1=A,yt=y) 不妨假设算法在执行过程中，A先到达x，再到达y 因为Y是通过yt-1 yt进入T1，所以W(yt-1yt)<=W(xy)，否则xy先进入T1,