B采用最小值堆的优先队列式分支限界法 C采用最大值堆的优先队列式分支限界法
D以上都常用针对具体问题可以选择采用其中某种更为合适的方式
97. 对布线问题以下（ C ）是不正确描述。 A布线问题的解空间是一个图
B可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定
C采用广度优先的标号法找到从起点到终点的布线方案这个方案如果存在的话不一定是最短的
D采用先入先出的队列作为活结点表以，终点b为扩展结点或活结点队列为空作为算法结束条件
98. 下述表达不正确的是（ D ）。
nA. n/2?2的渐进表达式上界函数是O(2) nB．n/2?2的渐进表达式下界函数是?(2)
32n2nC．logn的渐进表达式上界函数是O(logn) D．logn的渐进表达式下界函数是?(n)
99．当输入规模为n时，算法增长率最大的是（ A ）。 A．5 B．20log2n C．2n D．3nlog3n
100. T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（ C ）。 A．T(n)=T(n-1)+1，T(1)=1 B．T(n)=2n2
C. T(n)=T(n/2)+1，T(1)=1 D. T(n)=3nlog2n
101. 有9个村庄，其坐标位置如下表所示：
2n33i x(i) y(i) 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在（ C ）才能使邮局到9个村庄的距离和最短。 A. （4.5，0） B. （4.5，4.5） C. （5，5） D. （5，0）
102. n个人拎着水桶在一个水龙头前面排队打水水桶有大有小水桶必须打满水水流恒定。如下（ A ） 说法不正确
A．让水桶大的人先打水可以使得每个人排队时间之和最小 B．让水桶小的人先打水可以使得每个人排队时间之和最小
C．让水桶小的人先打水在某个确定的时间t内可以让尽可能多的人打上水 D．若要在尽可能短的时间内n个人都打完水按照什么顺序其实都一样
103. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ B ）。 A. n!
nB. 2
n?1C. 2?1
D.
?n!/i!
i?1n104．以下关于判定问题难易处理的叙述中正确的是（ C ） A.可以由多项式时间算法求解的问题是难处理的 B.需要超过多项式时间算法求解的问题是易处理的 C.可以由多项式时间算法求解的问题是易处理的
D.需要超过多项式时间算法求解的问题是不能处理的
105. 回溯法在解空间树T上的搜索方式是（ A ） A. 深度优先 B. 广度优先 C. 最小耗费优先 D. 活结点优先
106. 设f(N)，g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当 N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时有上界g(N)，记作f(N)=O(g(N)),即f(N)的 阶（ A ）g(N)的阶。
A. 不高于 B. 不低于 C. 等价于 D. 逼近
107. 以下（ C ）不能在线性时间完成排序 A.计数排序 B.基数排序 C.堆排序 D.桶排序
108. 以下（ A ）不一定得到问题的最优解 A.贪心算法 B.回溯算法 C.分支限界法 D.动态规划法
109.下列不属于一个好的算法应具有的特性的是（ C ）。 A. 正确性 B. 简明性 C. 无限性 D. 最优性
110. 算法分析是（ C ）。
A. 将算法用某种程序设计语言恰当地表示出来
B．在抽象数据集合上执行程序，以确定是否会产生错误的结果 C. 对算法需要多少计算时间和存储空间作定量分析
D. 证明算法对所有可能的合法输入都能算出正确的答案
111. 学校要举行运动会，请你设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是（ C ）。 A. 分析问题，编写程序，设计算法，调试程序 B. 设计算法，编写程序，提出问题，调试程序 C. 提出问题，设计算法，编写程序，调试程序 D. 设计算法，提出问题，编写程序，调试程序
112. 考虑背包问题：n=6，M=10，V（1:6）=（15，59，21，30，60，5），W（1:6）=（1，5，2，3，6，1）。该问题的最大效益值为（ C ）。 A. 101 B. 110
C. 115 D.120
113. 考虑背包问题：n=6，M=10，V（1:6）=（15，59，21，30，60，5），W（1:6）=（1，5，2，3，6，1）。若把它看作是0/1背包问题，则该问题的最大效益值为（ B ）。 A. 101 B. 110 C. 115 D.120
114. 找最小生成树的算法Kruskal的时间复杂度为（ D ）。 A. O(n2) B. O(mlogn) C. O(nlogm) D. O(mlogm)
115. 算法与程序的区别在于算法具有（ C ）。 A. 能行性 B. 确定性 C. 有穷性
D. 输入和输出
116. 设A[1..60]={11,12,…,70}。算法折半查找在A上搜索x=33、7、70、77时执行的元素比较次数分别为a、b、c、d, 则（ C ）。 A. a 117. 算法直接插入排序在A[1..8]={45,33,24,45,12,12,24,12}上运行时执行的元素比较次数为（ D ）。 A. 14 B. 28 C. 7 D. 22 118. void hanoi(int n, int a, int b, int c) { if (n>0) { hanoi( n-1, a, c, b); move(a, b); hanoi( n-1, c, b, a); } } 上述算法的时间复杂度为（ A ）。 A. O(2n) B. O(nlogn) C. D. 119. 当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以使用（ B ）来消除或减少问题的好坏实例间的这种差别。 A. 数值概率算法 B. 舍伍德算法 C. 拉斯维加斯算法 D. 蒙特卡罗算法 120. 当输入规模为n时，算法增长率最快的是( C )。 A. 12n B.100log2n C. 2n2 D. 3nlog3n 121. 关于0-1背包问题，以下描述正确的是（ D ）。 A. 可以使用贪心算法找到最优解 B. 能找到多项式时间的有效算法 C. 使用教材介绍的动态规划方法可求解任意0-1背包问题 D. 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0-1背包问题。 122. 设有n项独立的作业{1,2,?, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完 （n>m）。对于多级调度问题，使用哪种贪心策略比较合适（ B ）。 A. 作业从小到大依次分配给空闲的机器 B. 作业从大到小依次分配给空闲的机器 C. 每个机器分配一样的作业数 D. 使用以上几种贪心策略都能找到最优解，所以都合适 ?(n!) ?(nn)