算法设计第三章作业题

作业内容:
1、手写作业:课后作业3.7练习题5、10、13、15题,把作业拍照后以学号+姓名命名发到群文件夹第三章作业目录下,作业提交截止时间:3月12日(周六)23:00。

  1. 13.假设二叉树采用二叉链存储结构进行存储。设计一个算法采用分治法求一棵二叉树bt中度为2的结点个数。
  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);
}


  1. 5.假设含有 n 个元素的待排序的数据 a 恰好是递减排列的,说明调用 QuickSort(a,0,n-1)递增排序的时间复杂度为 O(n2)
    解:由题意得递归树的高度应该为O(n),
    因此每一次划分对应的时间为O(n),
    由此得排序时间为O(n2)。(这里应该是n的平方,我这里打不出来)

  1. 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);
}


  1. 15.设有 n 个互不相同的整数,按递增顺序存放在数组 a[0..n-1]中,若存在一个下标
    i(0≤i<n),使得 a[i]=i。设计一个算法以 O(log2n)时间找到这个下标 i。
上一篇
---内容结束---