信息学奥赛:算法基础综合测试.docx

上传人:d**** 文档编号:69317661 上传时间:2023-01-01 格式:DOCX 页数:18 大小:294.74KB
返回 下载 相关 举报
信息学奥赛:算法基础综合测试.docx_第1页
第1页 / 共18页
信息学奥赛:算法基础综合测试.docx_第2页
第2页 / 共18页
点击查看更多>>
资源描述

《信息学奥赛:算法基础综合测试.docx》由会员分享,可在线阅读,更多相关《信息学奥赛:算法基础综合测试.docx(18页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息学奥赛:算法基础综合测试一、单选题(共13分,前6题每题1.5分,后2题每题2分)1、下列关于算法的描述正确的是()。 A. 算法中有待执行的运算和操作必须是相当基本的(正确答案)B. 一个算法至少有一个输入和一个输出C. 算法并不需要每一个步骤都确切地定义D. 一个算法可以没有结束2、下列关于算法的描述正确的是() A. 算法只能用自然语言来描述B. 算法只能用流程图或伪代码来表示C. 同一问题可以有不同的算法(正确答案)D. 同一问题的算法不同,结果必然不同3、下列排序算法中,()不是基于比较的排序。 A. 冒泡排序B.桶排序(正确答案)C. 快速排序D. 选择排序4、“你打开面前这扇

2、门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。”这一表述主要体现了( )的思想。 A. 枚举B. 分治C. 递归(正确答案)D. 贪心5、关于递归算法,下列说法不正确的是( )。 A. 一个过程或函数在其定义中有直接或间接调用自身,称为递归B. 递归算法的程序结构往往更简洁C. 递归可能会消耗大量的内存空间,程序执行慢,甚至出现栈溢出等问题D. 若递归算法执行效果慢,可

3、以采用“时间换空间”的思路,使用递推算法改进(正确答案)6、下列关于高精度算法的说法中,错误的是( )。 A. 高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算的算法,即高精度算法就是能处理高精度数各种运算的算法。B. 高精度算法中,参与运算的数(加数,被减数,减数,因数)范围大大超出了标准数据类型(整型,实型)能表示范围的运算。C. 高精度数一般采用使用一个数组来表示,一般采用字符串形式读入并采用正序的方式进行存储。(正确答案)D. 高精度算法的内在实质是模拟算法,用计算机来模拟人用笔的计算过程。7、(汉诺塔移动次数)在圣庙里,一块黄铜板上插着三根宝石柱。神在

4、创造世界的时候,在其中一根柱上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从神穿好的那根柱上移到另外一根柱上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。不管传说是否可信,我们现在要解决的是,假设初始柱A上从下到上地穿好了由大到小的n片金片,一次只能移动一片,且必须满足小片在大片之上。问最少移动( )次后所有的金片都从初始穿好的那根柱上移到另外一根柱C上。A. 2n-1 B. 2n-1 C. 2n+1 D. 2n+1 A. 2的n

5、次方-1(正确答案)B. 2的n-1次方C. 2的n+1次方D. 2的n次方+18、下面这段高精度加法程序计算a+b的值并存储在a中,其中缺了3个空,依次填入选项( )可以补全程序。甲:ai=(ai+bi)%10 乙:ai+1=ai+1+(ai+bi)/10 丙:a0=k+1void plus(int a,int b) int i,k; if(a0b0) k=a0; else k=b0; for(i=1;i0) ; else a0=k; A. 甲乙丙B. 乙甲丙(正确答案)C. 丙乙甲D. 丙甲乙二、阅读程序,完成各题(共75分,30小题每题2.5分)1、(1)这段程序是一个( )算法。 A.

6、 快速排序B. 归并排序C. 冒泡排序(正确答案)D. 选择排序(2)若输入n=5,再输入1 3 5 2 4,则程序第9行将会执行( )次比较。 A. 10(正确答案)B. 5C. 3D. 7(3)若输入n=4,以下输入( )会使得程序第10行执行的次数最多。 A. 1 2 3 4B. 4 3 2 1(正确答案)C. 4 2 3 1D. 1 4 3 2(4)若输入n=3,再输入3 1 3,则程序第10行会执行( )次。 A. 1(正确答案)B. 2C. 3D. 4(5)若将第7行in修改为iaj+1修改为aj=aj+1。若输入仍为n=3,再输入3 1 3,则程序第10行会执行( )次。 A.

7、1B. 2(正确答案)C. 3D. 4(8)将第7行in修改为in-1。若输入n=4,再输入4 3 2 1,则程序将输出( )。 A. 4 3 2 1B. 2 1 3 4(正确答案)C. 3 2 1 4D. 1 2 3 4(9)将第7行in修改为in-1。若输入n=4,再输入1 3 2 4,则程序将输出( )。 A. 4 3 2 1B. 2 1 3 4C. 3 2 1 4D. 1 2 3 4(正确答案)(10)在最好情况下,第10行将执行( )次。 A. 0(正确答案)B. 1C. nD. n(n-1)/22、(11)这段程序是一个( )算法。 A. 快速排序(正确答案)B. 归并排序C. 冒

8、泡排序D. 选择排序(12)该排序算法同时也体现了( )思想。 A. 枚举算法B. 查找算法C. 分治算法(正确答案)D. 贪心算法(13)若输入n=5,再输入1 3 5 2 4,则程序将会输出( )。 A. 1 2 3 4 5B. 5 4 3 2 1(正确答案)C. 1 5 4 3 2D. 5 1 2 3 4(14)若将第7行i=j修改为ij,程序( )。 A. i的取值范围少1B. 不能正确运行排序C. 出现编译错误D. 能够正确运行排序(正确答案)(15)将第10行i=j修改为ij,程序( )。 A. 将从小到大进行排序B. 不能正确运行排序(正确答案)C. 出现编译错误D. 能够正确运

9、行排序(16)将第11行t=ai;ai=aj;aj=t;修改为ai=t;t=aj;aj=ai;,程序( )。 A. 不能够正确执行交换(正确答案)B. 仍能够正确执行交换C. 出现编译错误D. 将从小到大进行排序(17)将第17行return删除,程序( )。 A. 将从小到大进行排序B. 不能正确运行排序C. 出现编译错误D. 能够正确运行排序(正确答案)(18)在最好情况下,该排序算法将执行( )次交换。 A. 0(正确答案)B. 1C. nD. n(n-1)/2(19)在最坏情况下,该排序算法将执行( )次交换。 A. 0B. 1C. nD. n(n-1)/2(正确答案)(20)在编程实

10、现该排序算法时,该思想与以下表述( )有异曲同工之妙。 A. 道生一,一生二,二生三,三生万物B. 吃自助餐,每次都挑最贵的一种食物吃C. 小明在思考,思考的内容是:“小明在思考,思考的内容是:小明在思考,思考的内容是:”(正确答案)D. 逐一排查,查到即止3、(21)这段程序是一个( )算法。 A. 顺序查找B. 二分查找(正确答案)C. 散列查找D. 枚举(22)若输入8 2后,再输入2 3 5 7 11 13 17 19,则程序将会输出( )。 A. -1B. 0C. 1(正确答案)D. 2(23)若输入6 3后,再输入1 3 3 3 3 5,则程序将会输出( )。 A. 2B. 3(正

11、确答案)C. 4D. 5(24)若输入6 3后,再输入1 3 5 6 4 2,则程序将会输出( )。 A. -1B. 0C. 1D. 2(正确答案)(25)若输入9 3后,再输入1 4 7 2 5 8 3 6 9,则程序将会输出( )。 A. -1(正确答案)B. 1C. 4D. 7(26)若将第8行l=r修改为lr,程序( )。 A. r的取值范围少1B. 不能正确运行查找(正确答案)C. 出现编译错误D. 能够正确运行查找(27)删去第12行break。输入6 3后,再输入1 2 3 4 5 6,则程序将( )。 A. 输出3B. 不能正确运行查找(正确答案)C. 出现编译错误D. 输出-

12、1(28)在执行该算法前,对数组a的要求主要是( )。 A. 数组a需要从小到大有序(正确答案)B. 数组a需要从大到小有序C. 对数组a没有任何要求D. 不需要完全有序,但需要数组a的前半部分小于中间值,后半部分大于中间值(29)该算法还可以利用( )的思想来编写程序。 A. 排序算法B. 递归算法(正确答案)C. 枚举算法D. 贪心算法(30)与该算法思想相似的问题有( )。 A. 求所有的“水仙花数”(“水仙花数”即每位数字的立方和等于该数的三位数,如153=13+53+33。)B. 青蛙跳台阶(青蛙一次可跳1或2级台阶,求青蛙跳上一个n级的台阶的跳法总数。)C. 猜数字游戏(在自然数1

13、到n中取一个数猜,每猜一次知道猜大了或猜小了。怎么猜数最快?)(正确答案)D. 钱币支付问题(假设不同面值纸币的各有若干张,现在不考虑找零钱的支付K元,求最少纸币张数。)三、阅读程序写结果(共22分,第一题6分,第二,三题每题8分)1、#include using namespace std;int main() int n,x,sum=0; cinn; for(int i=1;ix; sum=sum-x; coutsum; return 0;输入:6 180 30 110 50 40 60输出: _(答案:730)2、#includeusing namespace std;int main(

14、) const int N=6; int cN=; int vN=1,5,10,20,50,100; int i,k,m=0,cc=0; cink; for(i=0;ici; for(i=N-1;i=0;i-) cc=min(k/vi,ci); k=k-ccvi; m+=cc; if(k0) m=-1; if(m!=-1) coutmendl; else coutNOendl; return 0;输入:34 6 5 2 0 0 0输出: _(答案:8)3、#include using namespace std;long long f(int n) if(n=1) return 0; if(n=2) return 1; return 3f(n-1)-2f(n-2);int main() int m; cinm; coutf(m)endl;输入:8输出: _(答案:127)

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 考试试题 > 习题库

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁