发布时间 : 星期五 文章《算法分析与设计》期末复习题更新完毕开始阅读81608668f424ccbff121dd36a32d7375a517c616
.
一、选择题
1．一个.java文件中可以有（ ）个public类。 A．一个 B．两个 C．多个 D．零个 2．一个算法应该是（ ）
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C
3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ ） A．唯一性 B．有穷性 C．有0个或多个输入 D．有输出
4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（ ）
A．3，15，130，20，98，67 C．3，15，20，67，130，98
B．3，15，20，130，98，67 D．3，15，20，67，98，130
B．一个完整的算法必须有输出
5．下列关于算法的描述，正确的是（ ） A．一个算法的执行步骤可以是无限的 C．算法只能用流程图表示
D．一个完整的算法至少有一个输入
6．Java Application源程序的主类是指包含有（ ）方法的类。
A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（ ） A．分治法
B．减治法
C．蛮力法
D．变治法
8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ;
9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。
.
.
图中空白处理框①和②处应填入的是（ ）
A．① sum ← sum + d B．① sum ← sum + c ② c ← c + 1 ② d ← d + 1
② c ← c + 1 ② d ← d + 1
C．① sum ← sum + d D．① sum ← sum + c
10．报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。利用折半查找，查找学号为33号学生的过程中，依次被访问到的学号是（ ）
A．5，11，33 B．8，33 C．11，45，33 D．11，33 11．表达式（short）8/9.2*5的值的类型为 A．short x=10;
x+=x-=x-x;
A．10 B．20 C．40 13．下列代码的执行结果是 public class StringTest{
public static void main(String args[]){ int a=4,b=6,c=8; String s=”abc”;
System.out.println(a+b+s+c);
System.out.printin(); } }
A．ababcc
B．464688 C．46abc8
D．10abc8
14． 下列程序段执行后t3的结果是 int t1 = 2, t2 = 3, t3; t3=t1 A．2 B．4 C．5 D．6 15．要计算当0〈x〈10时，y=x，应当使用的语句是 . D．30 B． int C．double D．float 12． 设x为int型变量，则执行一下语句段后，x的值为 . A．if(0 A．冒泡排序 B．合并排序 C．快速排序 D．选择排序 17．类与对象的关系是（ ） A． 建筑图纸和建筑物的关系 B． 汽车与发动机的关系 C． 人与黑人的关系 D． 没有关系 18．JAVA语言二维数组定义中，第二维的长度 ( ) A．可以不相等 B．必须相等 C．高维数组长度与低维数组长度相同 19．算法必须具备（ ）这三个特性。 A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性 20．如下图所示，该流程图所表示的算法违背了算法的有穷性特征，下列修改方法中，可以改正该错误的是（ ） D．固定长度 A．将①处改为 i ← 0 B．将②处改为 s ≥ 0 ? C．将③处改为 i ← i-2 D．将④处改为 s ← s-i 二、填空题 1．一个显而易见的事实是：大部分算法的执行时间随着 输入量的增加 而增大。 2．算法是 求解某一问题所使用的一系列清晰的指令 。 3．算法分析时间效率模型的基本数学公式是： T(n) ≈ CopC(n) 。 . . 4．算法设计技术是 用算法解题的一般性方法 ，用于解决不同计算领域的多种问题。 5．三个渐进符号： O 、 ? 和 ? 。 6．效率分析框架主要关心一个算法的 基本操作次数的增长次数 ，并把它作为算法效率的主要指标。 7．Java源程序的文件名和程序中定义的 主类名 应保持一致，包括字母大小写的匹配。 8．算法中常见的问题类型包括： 排序 、 查找 、字符串处理和组合问题等。 9．类中的 构造 方法是一个特殊的方法，其名称与类名相同。 10．面向对象程序设计语言中的3个重要特性分别是 封装 、 继承 和 多态 。 11．Java源程序文件的扩展名为 java ，编译生成的字节码文件的扩展名为 class 。 12．大多数算法的效率可以分为常数、 对数 、线性、平方、 立方 和指数等。 三、简答题 1．什么是算法？算法的五个重要特征是什么？ 答：算法是求解某一问题所使用的一系列清晰的指令。 答： （1）输入：有零个或多个由外部提供的量作为算法的输入. （2）输出：算法产生至少一个量作为输出. （3）确定性：组成算法的每条指令是清晰的,无歧义的. （4）有限性：在执行了有穷步骤后运算终止. （5）可行性：运算都是基本运算，原理上能在有限时间内完成. 2．请简述蛮力算法的优点？ 答： 蛮力算法是一种简单直接地解决问题的方法。蛮力法具有如下优点：(1)应用范围广；(2)不受实例规模的限制；(3)当要解决的问题实例不多,设计更高效算法的代价太大时可选用；(4)对解决一些小规模的问题实例仍然有效；(5)可作为衡量其他算法的参照物。 3．算法设计与分析过程的典型步骤都包括哪些？ 答： （1）了解问题的内容 （2）了解计算设备的性能 （3）在精确解法和近似解法之间选择 （4）确定适当的数据结构 （5）算法设计技术 （6）详细表述算法的方法 （7）证明算法的正确性 （8）分析算法 （9）为算法写代码 4．请简述分治法的基本思路？ .