题目-1-4

-1-算法分析与设计期中练习一、选择题1.实践表明可操作性最好且最有实际价值的是（B）情况下的时间复杂性。A.最好B.最坏C.平均D.特殊2.算法的时间复杂性函数用T(n)表示，其中参数n是指（A）。A.问题规模B.运行时间C.输入量D.输出量3.函数105logn2+n2logn+n3的渐近表达式为（C）。A.logn2B.n2lognC.n3D.1054.二分搜索算法中，如果待查找元素x不在已排好序的n个元素中，则完成该搜索任务需用（B）时间。A.O(nlogn)B.O(logn)C.O(n)D.O(n2)5.Strassen矩阵乘法问题中，改进算法的计算复杂性关键在于（A）。A.减少矩阵乘法B.增加矩阵乘法C.减少矩阵加法D.增加矩阵加法6.最优子结构和重叠子问题是（A）算法的两个基本要素。A.动态规划B.贪心C.分支限界D.分治7.使用贪心算法解决活动安排问题时使用了（B）优先的贪心选择策略。A.最早开始活动B.最早结束活动C.时间最短活动D.时间最长活动8.f(n)=log7n,g(n)=100logn，满足f(n)=（）(g(n))。A.OB.C.9.f(n)=logn8,g(n)=log(100n)，满足f(n)=（）(g(n))。A.OB.C.10.f(n)=30(logn)10,g(n)=30n5,满足f(n)=（）(g(n))。A.OB.C.11.f(n)=105n,g(n)=log10n,满足f(n)=（）(g(n))。A.OB.C.12.f(n)=4n,g(n)=410(3n),满足f(n)=（）(g(n))。-2-A.OB.C.13.贪心法解装载问题时，采用的解题策略是（）。A.平均分配两艘轮船的载重B.按集装箱重量从轻至重装船C.将第一艘轮船尽可能装满D.将第二艘轮船尽可能装满二、简答题1.请列出5种不同阶的常见的算法时间复杂度，并按阶从低到高排列。2.使用分治法求解问题可分为哪三个步骤？三、算法复杂度分析题（答题请带简要过程）(1)(2)(3)(4)四、算法填空题请补全以下一般背包问题的贪心算法代码。voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//排序for(inti=1;i=n;i++)x[i]=0;//初始化数组xfloatc=M;补齐该部分代码}11)()5/(3)1(O)(2nnnOnTnT11)()3/(4)1(O)(nnnOnTnT11)()1()1(O)(nnnOnTnT11)()2/(6)1(O)(3nnnOnTnT