A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性20．如下图所示，该流程图所表示的算法违背了算法的有穷性特征，下列修改方法中，可以改正该错误的是（ ）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．请简述分治法的基本思路？答：将规模为N的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。
如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止在分治法中,子问题的解法通常与原问题相同,自然导致递归过程5．请简述减治法的基本思路？答：减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系一旦建立了这种关系，既可以从顶至底（递归地），也可以从底至顶（非递归地）来运用该关系减治法有三种主要的变种：n 减常数(如1)：:每此迭代规模减小n→n-1n 减因子(如1/2)：每此迭代规模减半n→ n/2n 减可变规模：每此迭代减小的规模不同6．请简述递归算法设计的基本思路？答：递归的执行过程由分解过程和求值过程两部分构成实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口) 但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似并且有一个分解的终点从而使问题可解 7．请简述变治法的基本思路？答：变治法的技术基于变换思想变治法分为两个阶段的工作：首先在“变”的阶段，出于这样或那样的原因，将问题的实例变得更容易求解；然后是“治”的阶段，对问题的实例进行求解。
根据对问题实例的变换方式不同，变治法有三种主要的类型： （1）实例化简——变换为同样问题的一个更简单或者更方便的实例； （2）改变表现——变换为同样实力的不同表现； （3）问题化简——变换为另一个问题的实例，这种问题的算法是已知的8．请简述时空权衡法的基本思路？答：时空权衡法的基本思路是对问题的部分或全部输入做预处理，然后对得到的额外信息使用额外的存储空间来存储通过实现更快或更方便的数据存取，以加速后面问题的求解来提高算法的效率四、算法实现题1．对于任意非负整数n，计算阶乘函数F(n) = n！的值因为当n ≥ 1时，n！= 1×2×3×……×（n-1）×n = (n-1)！×n并且根据定义，0！= 1，所以可以使用下面的递归算法计算n！：F(n) = F(n-1) × n请编写Java应用程序，由键盘输入n的值，在屏幕上输出计算的n！的结果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[10]; System.out.println("请输入一个整数："); System.in.read(buf); String str=new String(buf); int n=Integer.parseInt(str.trim()); //计算N！的值 long result = f(n); //输出结果 System.out.println(n + "!=" + result); }}2．斐波那契数列：0，1，1，2，3，5，8，13，21，34，……这个数列可以用一个简单的递推式和两个初始条件来定义：当n > 1时，F(n) = F(n-1) + F(n-2) F(0) = 0，F(1) = 1请编写Java应用程序，由键盘输入n的值代表要生成斐波那契数列的项数，在屏幕上输出n项斐波那契数列。
import java.io.*;public class Fb{ /*斐波那契数列算法*/ int f(int n){ int r; if(n <= 1) r = n; else r = f(n-1) + f(n-2); return r; } public static void main(String args[]) throws IOException{ System.out.println("请输入所求斐波那契数列的项数："); byte buf[] = new byte[20]; System.in.read(buf); String t1 = new String(buf); int n = Integer.parseInt(t1.trim()); Fb f1 = new Fb(); int b; System.out.println("输出包含" + n + "项的斐波那契数列："); for(int i = 0; i <= n; i++) { b = f1.f(i); System.out.print(b + " "); } System.out.println(); }}3．编写基于Java语言的选择排序算法。
/**** 功能：该算法用选择排序对给定的数组排序* 输入：一个乱序的整数数组a[ ]* 输出：升序排列的整数数组a[ ]***/public void selectionSort (int a[ ]){ int temp,min; for(int i=0;i a[j]) min = j; temp = a[i]; a[i] = a[min]; a[min] = temp; }}4．编写基于Java语言的冒泡排序算法/**** 功能：该算法用冒泡排序对给定的数组排序* 输入：一个乱序的整数数组a[ ]* 输出：升序排列的整数数组a[ ]***/public void bubbleSort(int a[ ]){ int temp; for(int i=0;ia[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; }}5．编写基于Java语言的顺序查找算法。
/**** 功能：该算法实现顺序查找功能* 输入：一个整数数组a[ ]和一个要查找的键值k* 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1***/public int seqSearch(int a[ ],int k){ int i = 0; while((i < a.length ) && ( a[i] != k )) i = i + 1; if( i < a.length) return i; else return -1;}6．编写基于Java语言的折半查找算法/**** 功能：该算法实现折半查找功能* 输入：一个已经按照升序排列好的整数数组a[ ]和一个要查找的键值k* 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1***/public int binarySearch(int a[ ], int k){ int low = 0; int upper = a.length - 1; while(low <= upper) { int mid = (low+upper) / 2; if(k == a[mid]) return mid; else if(des < a[mid]) upper = mid - 1; else low = mid + 1; } return -1;}7．编写基于Java语言的字符串匹配算法。
/**** 功能：该算法实现字符串匹配功能* 输入：一个n个字符的字符串str代表一段文本 一个m个字符的字符串key代表一个模式* 输出：如果查找成功的话，返回文本的第一个匹配字符串中第一个字符的位置，否则返回-1***/public int stringMatch(String str,String key){ int j; int n = str.length(); int m = key.length(); for(int i = 0; i <= (n - m); i++) { j = 0; while((j < m) && (key.charAt(j) == str.charAt(i+j))) { j = j + 1; System.out.println(i + "," + j); if(j == m) return i; } } return -1;}8．编写基于Java语言的直接插入排序算法/**** 功能：该算法用直接插入排序对给定的数组排序* 输入：一个乱序的整数数组a[ ]* 输出：升序排列的整数数组a[ ]***/public void insertSort (int a[ ]){ int temp,i,j; for(i=1;i=0 && a[j]>=temp) { a[j+1]=a[j]; j--; } a[j+1]=temp; }}9 / 9。