算法分析与设计学习通超星期末考试答案章节答案2024年

算法分析与设计学习通超星期末考试章节答案2024年/star3/origin/e76a7f9b8f7ae1543445394686a02f3b.png

答案:错问题的计算时间下界为Ω(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。

答案:对/ananas/latex/p/3202708

答案:对Θ符号比O符号和Ω符号都精确，f(n)=Θ(g(n)），只要g(n)既是f(n)的上界又是f(n)的下界。

答案:错一个算法的时间用Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。

答案:对一个算法的时间用O符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。

答案:错算法分析是分析算法占用计算机资源的情况，即分析算法的时间复杂度。

答案:错算法是把人类找到的求解问题的方法，用算法要素过程化、形式化、机械化地表示出来。

答案:对如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是可靠的。

答案:错算法操作的对象是数据，数据间的（）就是数据的数据结构。

答案:逻辑关系;存储方式;处理方式描述算法的形式包括（）。

答案:自然语言;程序设计语言;伪代码;流程图算法中的控制结构指的是各操作之间的执行次序。基本控制结构包括（）。

答案:顺序结构;选择结构;循环结构算法由（）要素组成。

答案:操作;控制结构;数据结构算法设计应满足以的目标包括（）。

答案:正确性;可使用性;健壮性算法的主要特征包括（）。

答案:有限性;确定性;可行性T(n)=T(n/3)+T(2n/3)+n

答案:O(log3/2n)/ananas/latex/p/576

答案:O()/ananas/latex/p/576

答案:O()给出算法的时间复杂性Loop(n):

p←0

fori←0to2ndo

p←p*i

答案:O(n)设S是一组n条直线，其中没有两条是平行的，也没有三条在同一点相交。可以用数学归纳法证明S中的直线确定了（）个交点。

答案:Θ()/ananas/latex/p/1542

答案:-1计算T(n)T(n)=1,

n=1T(n)=T(n-1)+n,

其它

答案:n(n+1)/2计算T(n)T(n)=4,当n=1T(n)=T(n-1)+4,其它

答案:4n算法分析包括最好情况下的时间复杂度(时间复杂度下界)、最坏情况下的时间复杂度(时间复杂度上界)和平均情况下的时间复杂度（时间复杂度均值）。实践表明可操作性最好的，且最有实际价值的，是（）。

答案:时间复杂度上界算法要对异常情况进行适当的处理，就是算法的（）。

答案:健壮性一切合法的输入数据都能得出满足要求的结果，包括典型的、苛刻的输入数据也能够得出满足要求的结果。这个含义对应算法的（）。

答案:正确性从klnk=Θ(n)能得出k=Θ(n/ln)吗？

答案:对O(1)=O(8)，O(1)和O(8)表示同一个函数时，差别仅在于其中的常数因子。

答案:对/ananas/latex/p/3207191

答案:对/ananas/latex/p/1086418

答案:对算法执行时间相关的因素包括（）。

答案:问题中数据存储的数据结构;算法设计的策略;问题的规模;实现算法的程序设计语言;算法采用的数学模型设n为算法中的问题规模，通常用（）渐进符号表示算法的执行时间与n之间的一种增长关系。

答案:Ο;Θ;Ω对算法与数据结构关系的描述，正确包括（）。

答案:数据结构是算法设计的基础。;算法是编程思想，数据结构则是这些思想的逻辑基础;算法设计就是在选定的存储结构上设计一个满足要求的好算法。半数集问题：给定一个自然数n，右n开始可以依次产生半数集set(n)中的数如下：1）n加入set(n)；2）在n的左边加一个自然数，但该自然数不能超过最近添加的数的一半；3）按此规则处理，直到不能添加自然数为止。元素允许重复。计算半数集set(n)中元素个数。设f(n)是半数集set(n)中元素个数，它的递推公式是（）。

答案:f(n)=f(n/2)+...+f(1)+1计算T(n)T(n)=4,当n=1T(n)=T(n-1)+4,其它

答案:4n假设有一台高性能计算机，其中CPU包含专用k>2个优化寄存器。假设已经存储在寄存器中的数不超过k个，那么这些寄存器支持在O(1)时间插入键值对（x,y）的操作。此外，这些寄存器支持在O(1)时间删除和返回具有最小关键字x的键值对（x,y）。证明：可使用这台高性能计算机用（）时间对n个数排序。

答案:O(nlogn/logk)/ananas/latex/p/550836

答案:Θ(㏒n)给定A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1，霍夫曼编码是什么？

答案:A->11,B->10,C->00,D->011,E->010计算T(n)T(n)=1,

n=1T(n)=T(n-1)+n,

其它

答案:n(n+1)/2给出算法的时间复杂性Loop(n):

p←0

fori←0to2ndo

p←p*i

答案:O(n)贪心算法则通常以（）的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

答案:自顶向下函数MinMax用来查找数组a[0:n-1]中的最大元素和最小元素，问：在各个程序中，a中元素之间的比较次数在最好、最坏和平均情况下各

1

,

2

,

3

。templateboolMinMax(Ta[],intn,int&Min,int&Max){//寻找a[0:n-1]中的最小元素与最大元素

//如果数组中的元素数目小于1，则还回false

if(n<1)returnfalse;

Min=Max=0;//初始化

for(inti=1;ia[i])Min=i;

elseif(a[Max]答案:A.n-1;C.2(n-1);D.(n-1)/ananas/latex/p/31709

答案:B.2n;A.n/ananas/latex/p/507324

答案:C.Q;A.O;B.W;B.W;C.Q;B.W;B.W;A.O下面算法的时间复杂度T（n）为O（）。输入：n=2k

,k为正整数输出：kk

←0Whilen

≥1do

forj

←1tondo

k

←k+1

n

←n/2returnk

答案:n假设某算法在输入规模为n时的计算时间为T(n)=

n2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新计算机上用同一算法在t秒内能解输入规模为

的问题。

答案:8n/ananas/latex/p/4320178

答案:A.n;C.

Θ;B.2;C.nlogn/star3/origin/a04005488eb2979f4558fbb68f823d77.png

答案:C.;A.θ()流水线作业问题。有8个作业{1，2，…，8}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。M110281269414M2571151631113作业12345678（1）给出一个最优调度方案

1

，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少；（2）计算所需的最少时间为

2

。

答案:A.{2，7，5，4，8，1，6，3};B.73/star3/origin/1f064ac14632579f99e5671f39f912d6.png

答案:C.112344;C.AADB/star3/origin/dca1b6dcaedaf4f73371de71a2f1e3c4.png

答案:B.35;C.27;B.45;B.37;C.1，2，4，3，5当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树为

1

，遍历时间为O（

2

）的计算时间。

答案:B.子集树;A.回溯法中遍历排列树的时间复杂度为O（

）。

答案:n!常用剪枝函数中，用