作业内容:
1、手写作业:课后作业3.7练习题5、10、13、15题,把作业拍照后以学号+姓名命名发到群文件夹第三章作业目录下,作业提交截止时间:3月12日(周六)23:00。
- 13.假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉树bt中度为2的结点个数。
- 解:由题意得
f(bt)=0 当 bt=NULL
f(bt)=f(bt->lchild)+f(bt->rchild)+1 若 bt≠NULL && bt 为双分支结点
f(bt)=f(bt->lchild)+f(bt->rchild) else
int Nodes(BTNode *bt){
int n=0;
if (bt==NULL) return 0;
if (bt->lchild!=NULL && bt->rchild!=NULL)
n=1;
return Nodes(bt->lchild)+Nodes(bt->rchild)+n;
}
int main(){
BTNode *bt;
Int a[]={5,2,3,4,1,6};
Int b[]={2,3,5,1,4,6};
int n=sizeof(a)/sizeof(a[0]);
bt=CreateBTree(a,b,n);
printf("二叉树bt:");
DispBTree(bt);
printf("\n");
printf(Nodes(bt));
DestroyBTree(bt);
}
- 5.假设含有 n 个元素的待排序的数据 a 恰好是递减排列的,说明调用 QuickSort(a,0,n-1)递增排序的时间复杂度为 O(n2)
解:由题意得递归树的高度应该为O(n),
因此每一次划分对应的时间为O(n),
由此得排序时间为O(n2)。(这里应该是n的平方,我这里打不出来)
- 10.设计一个算法,采用分治法求一个整数序列中的最大最小元素。
void DivideConquer(int sum[], int low, int high, int& maxe, int& mine)
{
if (low == high)
{
maxe = sum[low];
mine = sum[low];
}
else if (low == high - 1)
{
maxe = max(sum[low], sum[high]);
mine = min(sum[low], sum[high]);
}
else
{
int mid = (low + high) / 2;
int lmaxe, lmine;
DivideConquer(sum, low, mid, lmaxe, lmine);
int rmaxe, rmine;
DivideConquer(sum, mid + 1, high, rmaxe, rmine);
maxe = max(lmaxe, rmaxe);
mine = min(lmine, rmine);
}
}
int main()
{
int a[] = { 4,34,1,2,5 ,100,55,59 };
int n = sizeof(a) / sizeof(a[0]);
int maxe, mine;
DivideConquer(a, 0, n - 1, maxe, mine);
printf("最大值为%d, 最小值为%d\n", maxe, mine);
}
- 15.设有 n 个互不相同的整数,按递增顺序存放在数组 a[0..n-1]中,若存在一个下标
i(0≤i<n),使得 a[i]=i。设计一个算法以 O(log2n)时间找到这个下标 i。