(算法分析与设计期末复习题1.docVIP

一、选择题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．表达式（short）8/9.2*5的值的类型为 A．short B． int C．double D．float ． 设x为int型变量，则执行一下语句段后，x的值为 x=10; x+=x-=x-x; A．10 B．20 C．40 D．30 ．下列代码的执行结果是 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． 下列程序段执行后t3的结果是 int t1 = 2, t2 = 3, t3; t3=t1t2? t1:t2+t1A．2 B．4 C．5 D．6 ．要计算当0〈x〈10时，y=x，应当使用的语句是 A．if(0x10)y=x; B．if(0x|x10)y=x;C．if(0xx10)y=x; D．if(0x^x10)y=x; ．．．．．．．、Java源程序的文件名和程序中定义的 主类名 应保持一致，包括字母大小写的匹配。 8．算法中常见的问题类型包括： 排序 、 查找 、字符串处理和组合问题等。 9．类中的 构造 方法是一个特殊的方法，其名称与类名相同。 10．面向对象程序设计语言中的3个重要特性分别是 封装 、 继承 和 多态 。 11．Java源程序文件的扩展名为 java ，编译生成的字节码文件的扩展名为 class 。 12．大多数算法的效率可以分为常数、 对数 、线性、平方、 立方 和指数等。 三、简答题N的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。 在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。 5．请简述减治法的基本思路？ 答： 减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。一旦建立了这种关系，既可以从顶至底（递归地），也可以从底至顶（非递归地）来运用该关系。 减治法有三种主要的变种： 减常数(如1)：:每此迭代规模减小n→n-1 减因子(如1/2)：每此迭代规模减半n→ n/2 减可变规模：每此迭代减小的规模不同 6．请简述递归算法设计的基本思路？ 答： 递归的执行过程由分解过程和求值过程两部分构成。 实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。 但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。 7．请简述变治法的基本思路？ 答： 变治法的技术基于变换思想。变治法分为两个阶段的工作：首先在“变”的阶段，出于这样或那样的原因，将问题的实例变得更容易求解；然后是“治”的阶段，对问题的实例进行求解。 根据对问题实例的变换方式不同，变治法有三种主要的类型： （1）实例化简——变换为同样问题的一个更简单或者更方便的实例； （2）改变表现——变换为同样实力的不同表现； （3）问题化简——变换为另一个问题的实例，这种问题的算法是已知的。 8．请简述时空权衡法的基本思路？ 答： 时空权衡法的基本思路是对问题的部分或全部输入做预处理，然后对得到的额外信息使用额外的存储空间来存储。通过实现更快或更方便的数据存取，以加速后面问题的求解来提高算法的效率。 四、import java.io.*; public class FN { static long f(int n) { long r = 1; if(n != 0) r = n * f(n-1); return r; } public static void main(String args[]) throws IOException { //输入N的值 byte[] buf = new byte[1