算法分析与设计期末复习题(DOC 11页).doc

1、百度文库 - 让每个人平等地提升自我一、选择题1一个.java文件中可以有（ ）个public类。A一个 B两个 C多个 D零个2一个算法应该是（ ）A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C3用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ ）A唯一性 B有穷性 C有0个或多个输入 D有输出4某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（ ）A3，15，130，20，98，67 B3，15，20，130，98，67C3，15，20，67，130，9

2、8 D3，15，20，67，98，1305下列关于算法的描述，正确的是（ ）A一个算法的执行步骤可以是无限的B一个完整的算法必须有输出C算法只能用流程图表示 D一个完整的算法至少有一个输入6Java Application源程序的主类是指包含有（ ）方法的类。A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法7找出满足各位数字之和等于5的所有三位数可采用的算法思路是（ ）A分治法B减治法C蛮力法D变治法8在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。A、import java.awt

3、.* ; 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 c c + 1C sum sum + d D sum sum + c d d + 1 d d + 110报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，3

4、3，45。利用折半查找，查找学号为33号学生的过程中，依次被访问到的学号是（ ）A5，11，33 B8，33 C11，45，33 D11，3311表达式（short）8/9.2*5的值的类型为Ashort B int Cdouble Dfloat12 设x为int型变量，则执行一下语句段后，x的值为 x=10;x+=x-=x-x;A10 B20 C40 D3013下列代码的执行结果是public class StringTest public static void main(String args) int a=4,b=6,c=8; String s=”abc”;System.out.pri

5、ntln(a+b+s+c); System.out.printin(); Aababcc B464688 C46abc8 D10abc814 下列程序段执行后t3的结果是int t1 = 2, t2 = 3, t3;t3=t1t2? t1:t2+t1A2 B4 C5 D615要计算当0x10时，y=x，应当使用的语句是Aif(0x10)y=x; Bif(0x|x10)y=x;Cif(0x&x10)y=x; Dif(0xx 1时，F(n) = F(n-1) + F(n-2) F(0) = 0，F(1) = 1请编写Java应用程序，由键盘输入n的值代表要生成斐波那契数列的项数，在屏幕上输出n项斐

6、波那契数列。import java.io.*;public class Fb/*斐波那契数列算法*/int f(int n)int r;if(n = 1)r = n;elser = f(n-1) + f(n-2);return r;public static void main(String args) throws IOExceptionSystem.out.println(请输入所求斐波那契数列的项数：);byte buf = new byte20;System.in.read(buf);String t1 = new String(buf);int n = Integer.parseIn

7、t(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;ia.leng

8、th-1;i+) min = i; for(int j=i+1;j aj) min = j; temp = ai; ai = amin; amin = temp; 4编写基于Java语言的冒泡排序算法。/* 功能：该算法用冒泡排序对给定的数组排序* 输入：一个乱序的整数数组a * 输出：升序排列的整数数组a */public void bubbleSort(int a )int temp;for(int i=0;ia.length-1;i+)for(int j=0;jaj+1)temp = aj+1;aj+1 = aj;aj = temp;5编写基于Java语言的顺序查找算法。/* 功能：该算

9、法实现顺序查找功能* 输入：一个整数数组a 和一个要查找的键值k* 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1*/public int seqSearch(int a ,int k)int i = 0;while(i a.length ) & ( ai != k )i = i + 1;if( i a.length)百度文库 - 让每个人平等地提升自我return i;else百度文库 - 让每个人平等地提升自我return -1;6编写基于Java语言的折半查找算法。/* 功能：该算法实现折半查找功能* 输入：一个已经按照升序排列好的整数数组a 和一个

10、要查找的键值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 = amid)return mid;else if(des amid) upper = mid - 1; else low = mid + 1; return -1;7编写基于Java语言的字符串匹配算法。/* 功能：该算法实现字符串匹配功

11、能* 输入：一个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 & aj=temp)aj+1=aj;j-;aj+1=temp;11