题目-1-4.doc

算法分析与设计期中练习 一、选择题 1. 实践表明可操作性最好且最有实际价值的是（ B ）情况下的时间复杂性。 A.最好 B.最坏 C.平均 D.特殊 2. 算法的时间复杂性函数用T n 表示，其中参数n是指（ A ）。 A.问题规模 B.运行时间 C.输入量 D.输出量 3. 函数105logn2+n2logn+n3的渐近表达式为（ C ）。 A.logn2 B.n2logn C.n3 D. 105 4. 二分搜索算法中，如果待查找元素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. O B. C. 9. f n logn8,g n log 100n ，满足f n （ ） g n 。 A. O B. C. 10. f n 30 logn 10,g n 30n5,满足f n （ ） g n 。 A. O B. C. 11. f n 105n,g n log10n,满足f n （ ） g n 。 A. O B. C. 12. f n 4n ,g n 410 3n ,满足f n （ ） g n 。 A. O B. C. 13. 贪心法解装载问题时，采用的解题策略是（ ）。 A. 平均分配两艘轮船的载重 B. 按集装箱重量从轻至重装船 C. 将第一艘轮船尽可能装满 D. 将第二艘轮船尽可能装满 二、简答题 1. 请列出5种不同阶的常见的算法时间复杂度，并按阶从低到高排列。 2. 使用分治法可分为步骤？ void Knapsack int n,float M,float v[],float w[],float x[] Sort n,v,w ; //排序 for int i 1;i n;i++ x[i] 0; //初始化数组x float c M; 补齐该部分代码 - 2 -