第四章。
4-1证明：归纳法证明定理结论正确。
记 d(v,w)是由 v到达某一可到达结点 w(w∈v) 的最短路径长度。
若 d(v,w)≤1,则显然这样的所有 w都将被访问。
假设对所有 d(v,w)≤r 的结点都可被访问。则当 d(v,w)=r+1时有：
设 w是 v中 d(v,w)=r+1的一个结点设 u是从 v到 w的最短路径上紧挨着 w的前一个结点。则有d(v,u)=r。所以，u可通过 bfs被访问到。
假设 u≠v,且 r≥1 。根据 bfs的处理规则，u将在被访问之前的某个时刻被放到未被检测结点队列 q上，而在另一时刻 u将从队列 q中移出。此时，所有邻接于 u且尚未被访问的结点将被访问。
若结点 w在这之前未被访问，则此刻将被访问到。
由上，定理得证。
图g1中关节点为，其连通图为g2；图g2中关节点无，故为双连通图。
第五章。5-4. solutiontype dandc1(int left,int right)
while(!small(left,right)&&left
int m=divide(left,right);
if(xelse if(x>p[m]) left=m+1;
else return s(p)
5-7. template
int sortablelist::bsearch(const t&x,int left,int right) const
if (left<=right)
return -1;第五章。
证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为，至多为。在不成功搜索的情况下，关键字之间的比较次数至少为，至多为。所以，算法的最好、最坏情况的时间复杂度为。
假定查找表中任何一个元素的概率是相等的，为，那么，不成功搜索的平均时间复杂度为，成功搜索的平均时间复杂度为。
其中，是二叉判定树的内路径长度，是外路径长度，并且。
12.（1）证明：当或或时，程序显然正确。
当n=right-left+1>2时，程序执行下面的语句：
int k=(right-left+1)/3;
stoogesort(left,right-k);
stoogesort(left+k,right);
stoogesort(left,right-k);
首次递归stoogesort(left,right-k);时，序列的前2/3的子序列有序。
当递归执行stoogesort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。
再次执行stoogesort(left,right-k);使序列的前2/3有序。
经过三次递归，最终使序列有序。
所以，这一排序算法是正确的。
2）最坏情况发生在序列按递减次序排列。，。
设，则。冒泡排序最坏时间复杂度为，队排序最坏时间复杂度为，快速排序最坏时间复杂度为。所以，该算法不如冒泡排序，堆排序，快速排序。
13. template
select (t&x,int k)
if(m>n) swap(m,n);
if(m+n int *p=new temp[k];
int mid,left=0,right=n-1,cnt=0,j=0,r=0;
for(int i=0;i
while(leftif(a[left]else cnt=left-1;
if(k>cnt)
if(cnt>0)
for(j=0;j
temp[j]=a[r];
r++;left=cnt;
k-=cnt;
elsetemp[j]=b[i];
left=0;
k--;else
for(j=0;j
temp[j]=a[r];
r++;left=cnt;
k-=cnt;
return temp[k-1];
第四五章作业答案
4 2解。1 使pcapcb的年产量选用a比较有利，设年产量x万台。则pca 20 8x p a，12 8 20 4.968 8x 20 39.744 x pca 30 6x p a，12 8 30 29.808 8x 20 39.744 x30 29.808 8x 解得x 1.0065万台。2 设...
《算法分析与设计》课程作业
题一。一 设计目的。1 掌握各种排序的基本思想。2 掌握各种排序方法的算法实现。3 掌握各种排序方法的优劣分析及花费的时间的计算。4 掌握各种排序方法所适应的不同场合。二 设计内容和要求。利用随机函数产生3000个随机整数，利用选择排序 起泡排序 快速排序 合并排序等排序方法进行排序，并统计每一种排...
算法分析作业答案
6.6 设a 1 n 是一个由n个整数组成的数组，x为一整数。给出一个分治算法，找出x在 a 现的频度，即x在a 现的次数。你的算法的时间复杂度是什么？输入 整数数组a 1 n 整数x 输出 x在数组a 1 n 现的频度。frequence a,1,h,x 过程 frequence a,low,hi...