还剩7页未读,继续阅读
文本内容:
一、选择题1.一个.java文件中可以有()个public类A.一个B.两个C.多个D.零个2.一个算法应该是( )A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C3.用计算机无法解决“打印所有素数”的问题,其原因是解决该问题的算法违背了算法特征中的()A.唯一性B.有穷性C.有0个或多个输入D.有输出4.某校有6位学生参加学生会主席竞选,得票数依次为130,20,98,15,67,3若采用冒泡排序算法对其进行排序,则完成第二遍时的结果是()A.3,15,130,20,98,67B.3,15,20,130,98,67C.3,15,20,67,130,98D.3,15,20,67,98,1305.下列关于算法的描述,正确的是()A.一个算法的执行步骤可以是无限的B.一个完整的算法必须有输出C.算法只能用流程图表示D.一个完整的算法至少有一个输入6.JavaApplication源程序的主类是指包含有()方法的类A、main方法B、toString方法C、init方法D、actionPerfromed方法7.找出满足各位数字之和等于5的所有三位数可采用的算法思路是()A.分治法B.减治法C.蛮力法D.变治法8.在编写JavaApplication程序时,若需要使用到标准输入输出语句,必须在程序的开头写上语句9.计算某球队平均年龄的部分算法流程图如图所示,其中c用来记录已输入球员的人数,sum用来计算有效数据之和,d用来存储从键盘输入的球员年龄值,输入0时表示输入结束图中空白处理框
①和
②处应填入的是()A.
①sum←sum+dB.
①sum←sum+c
②c←c+1
②c←c+1C.
①sum←sum+dD.
①sum←sum+c
②d←d+1
②d←d+110.报名参加冬季越野赛跑的某班5位学生的学号是5,8,11,33,45利用折半查找,查找学号为33号学生的过程中,依次被访问到的学号是()A.5,11,33B.8,33C.11,45,33D.11,3311.表达式(short)8/
9.2*5的值的类型为A.shortB.intC.doubleD.float12.设x为int型变量,则执行一下语句段后,x的值为x=10;x+=x-=x-x;A.10B.20C.40D.3013.下列代码的执行结果是publicclassStringTest{publicstaticvoidmainStringargs[]{inta=4b=6c=8;Strings=”abc”;}A.ababccB.464688C.46abc8D.10abc814.下列程序段执行后t3的结果是intt1=2t2=3t3;t3=t1t2t1:t2+t1A.2B.4C.5D.615.要计算当0〈x〈10时,y=x,应当使用的语句是A.if0x10y=x;B.if0x|x10y=x;C.if0xx10y=x;D.if0x^x10y=x;16.对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下,第一趟2,12,16,88,5,10第二趟2,5,16,88,12,10第三趟2,5,10,88,12,16则采用的排序方法是()A.冒泡排序B.合并排序C.快速排序D.选择排序17.类与对象的关系是()A.建筑图纸和建筑物的关系B.汽车与发动机的关系C.人与黑人的关系D.没有关系18.JAVA语言二维数组定义中,第二维的长度A.可以不相等B.必须相等C.高维数组长度与低维数组长度相同D.固定长度19.算法必须具备()这三个特性A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性20.如下图所示,该流程图所表示的算法违背了算法的有穷性特征,下列修改方法中,可以改正该错误的是()A.将
①处改为i←0B.将
②处改为s≥0C.将
③处改为i←i-2D.将
④处改为s←s-i
二、填空题1.一个显而易见的事实是大部分算法的执行时间随着输入量的增加而增大2.算法是求解某一问题所使用的一系列清晰的指令3.算法分析时间效率模型的基本数学公式是Tn≈CopCn4.算法设计技术是用算法解题的一般性方法,用于解决不同计算领域的多种问题5.三个渐进符号O、Ω和Ө6.效率分析框架主要关心一个算法的基本操作次数的增长次数,并把它作为算法效率的主要指标7.Java源程序的文件名和程序中定义的主类名应保持一致,包括字母大小写的匹配8.算法中常见的问题类型包括排序、查找、字符串处理和组合问题等9.类中的构造方法是一个特殊的方法,其名称与类名相同10.面向对象程序设计语言中的3个重要特性分别是封装、继承和多态11.Java源程序文件的扩展名为java,编译生成的字节码文件的扩展名为class12.大多数算法的效率可以分为常数、对数、线性、平方、立方和指数等
三、简答题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.请简述减治法的基本思路?答减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系一旦建立了这种关系,既可以从顶至底(递归地),也可以从底至顶(非递归地)来运用该关系减治法有三种主要的变种减常数如1:每此迭代规模减小n→n-1减因子如1/2每此迭代规模减半n→n/2减可变规模每此迭代减小的规模不同6.请简述递归算法设计的基本思路?答递归的执行过程由分解过程和求值过程两部分构成实际上递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决此时分解到递归出口但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似并且有一个分解的终点从而使问题可解7.请简述变治法的基本思路?答变治法的技术基于变换思想变治法分为两个阶段的工作首先在“变”的阶段,出于这样或那样的原因,将问题的实例变得更容易求解;然后是“治”的阶段,对问题的实例进行求解根据对问题实例的变换方式不同,变治法有三种主要的类型
(1)实例化简——变换为同样问题的一个更简单或者更方便的实例;
(2)改变表现——变换为同样实力的不同表现;
(3)问题化简——变换为另一个问题的实例,这种问题的算法是已知的8.请简述时空权衡法的基本思路?答时空权衡法的基本思路是对问题的部分或全部输入做预处理,然后对得到的额外信息使用额外的存储空间来存储通过实现更快或更方便的数据存取,以加速后面问题的求解来提高算法的效率
四、算法实现题1.对于任意非负整数n,计算阶乘函数Fn=n!的值因为当n≥1时,n!=1×2×3×……×(n-1)×n=n-1!×n并且根据定义,0!=1,所以可以使用下面的递归算法计算n!Fn=Fn-1×n请编写Java应用程序,由键盘输入n的值,在屏幕上输出计算的n!的结果publicclassFN{staticlongfintn{longr=1;ifn!=0r=n*fn-1;returnr;}publicstaticvoidmainStringargs[]throwsIOException{//输入N的值byte[]buf=newbyte
[10];Stringstr=newStringbuf;intn=Integer.parseIntstr.trim;//计算N!的值longresult=fn;//输出结果}}2.斐波那契数列0,1,1,2,3,5,8,13,21,34,……这个数列可以用一个简单的递推式和两个初始条件来定义当n1时,Fn=Fn-1+Fn-2F0=0,F1=1请编写Java应用程序,由键盘输入n的值代表要生成斐波那契数列的项数,在屏幕上输出n项斐波那契数列publicclassFb{/*斐波那契数列算法*/intfintn{intr;ifn=1r=n;elser=fn-1+fn-2;returnr;}publicstaticvoidmainStringargs[]throwsIOException{请输入所求斐波那契数列的项数;bytebuf[]=newbyte
[20];Stringt1=newStringbuf;intn=Integer.parseIntt
1.trim;Fbf1=newFb;intb;输出包含+n+项的斐波那契数列;forinti=0;i=n;i++{b=f
1.fi;}}}3.编写基于Java语言的选择排序算法/****功能该算法用选择排序对给定的数组排序*输入一个乱序的整数数组a[]*输出升序排列的整数数组a[]***/publicvoidselectionSortinta[]{inttempmin;forinti=0;ia.length-1;i++{min=i;forintj=i+1;ja.length;j++ifa[min]a[j]min=j;temp=a[i];a[i]=a[min];a[min]=temp;}}4.编写基于Java语言的冒泡排序算法/****功能该算法用冒泡排序对给定的数组排序*输入一个乱序的整数数组a[]*输出升序排列的整数数组a[]***/publicvoidbubbleSortinta[]{inttemp;forinti=0;ia.length-1;i++forintj=0;ja.length-1-i;j++ifa[j]a[j+1]{temp=a[j+1];a[j+1]=a[j];a[j]=temp;}}5.编写基于Java语言的顺序查找算法/****功能该算法实现顺序查找功能*输入一个整数数组a[]和一个要查找的键值k*输出如果在数组中找到k,则返回对应数组元素的下标;如果在数组中找不到k,则返回-1***/publicintseqSearchinta[]intk{inti=0;whileia.lengtha[i]!=ki=i+1;ifia.lengthreturni;elsereturn-1;}6.编写基于Java语言的折半查找算法/****功能该算法实现折半查找功能*输入一个已经按照升序排列好的整数数组a[]和一个要查找的键值k*输出如果在数组中找到k,则返回对应数组元素的下标;如果在数组中找不到k,则返回-1***/publicintbinarySearchinta[]intk{intlow=0;intupper=a.length-1;whilelow=upper{intmid=low+upper/2;ifk==a[mid]returnmid;elseifdesa[mid]upper=mid-1;elselow=mid+1;}return-1;}7.编写基于Java语言的字符串匹配算法/****功能该算法实现字符串匹配功能*输入一个n个字符的字符串str代表一段文本一个m个字符的字符串key代表一个模式*输出如果查找成功的话,返回文本的第一个匹配字符串中第一个字符的位置,否则返回-1***/publicintstringMatchStringstrStringkey{intj;intn=str.length;intm=key.length;forinti=0;i=n-m;i++{j=0;whilejmkey.charAtj==str.charAti+j{j=j+1;ifj==mreturni;}}return-1;}8.编写基于Java语言的直接插入排序算法/****功能该算法用直接插入排序对给定的数组排序*输入一个乱序的整数数组a[]*输出升序排列的整数数组a[]***/publicvoidinsertSortinta[]{inttempij;fori=1;ia.length;i++{temp=a[i];j=i-1;whilej=0a[j]=temp{a[j+1]=a[j];j--;}a[j+1]=temp;}}。