算法分析与设计综合试卷.pdf

算法与分析综合试卷

一、选择题

1．算法分析是（）。

A．将算法用某种程序设计语言恰当地表示出来

B．在抽象数据集合上执行程序，以确定是否会产生错误的结果

C．对算法需要多少计算时间和存储空间作定量分析

D．证明算法对所有可能的合法输入都能算出正确的答案

2．算法确认是（）。

A．将算法用某种程序设计语言恰当地表示出来

B．证明算法对所有可能的合法输入都能算出正确的答案

C．对算法需要多少计算时间和存储空间作定量分析

D．在抽象数据集合上执行程序，以确定是否会产生错误的结果

3．算法与程序的区别在于算法具有（）。

A．能行性B．确定性C．有穷性D．输入和输出

4．设A[1..60]={11,12,…,70}。算法BINARYSEARCH在A上搜索x=33、7、70、

77时执行

的元素比较次数分别为a、b、c、d，则（）。

A．abcdB．ab=c=dC．ab=c=dD．acb=d

5．算法INSERTIONSORT在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的

元素比较次

数为（）。

A．14B．28C．7D．22

6．当A[1..n]中元素取值在范围（）时，算法RADIXSORT的时间复杂度为

T(nlogn)。

2n

A．A．[1..n]B．[n..2n]C．[1..n]D．[1..2]

7．设待排序的序列A[1..n]中元素取值于[1..n!]，则下列哪一个算法最坏情况下

排序更慢?

A．SELECTIONSORTB．INSERTIONSORT

C．RADIXSORTD．BUBBLESORT

8．一个排序算法如果能够使得序列中相同元素的位置次序在排序前后保持一致，

则称之为

稳定的排序算法。下列几种排序算法中哪一种不是稳定的？

A．SELECTIONSORTB．RADIXSORT

C．BUBBLEBSORTD．BOTTOMUPSORT

9．使用算法EXP来计算下列哪一个整数次幂所花费的乘法次数最多？

A．35B．36C．37D．38

10．算法MAJORITY在下列哪一个输入上执行时最后j=n，count=1，且c是主

元素？

A．{5,7,5,4,5}B．{5,7,5,4,8}C．{2,4,1,4,4,4,6,4}D．{1,2,3,4,5}

11．用贪心法设计算法的关键是（）。

A．将问题分解为多个子问题来分别处理B．选好贪心准则

C．获取各阶段间的递推关系式D．满足最优性原理

12．考虑带限期的作业调度问题：n=7，P(1:7)=(35,30,25,20,15,10,5)，

D(1:7)=(3,4,2,6,4,8,3)。

假设处理每个作业需1个单位时间，则最优调度的效益值为（）。

A．135B．110C．140D．120

13．在一棵树上进行宽度优先搜索的结点访问次序，相当于树的（）的结

点访问次序。

A．先根遍历B．中根遍历C．后根遍历D．层次遍历

14．用（）方法对树进行搜索时，