信息学奥赛：算法基础综合测试

信息学奥赛：算法基础综合测试一、单选题（共13分，前6题每题1.5分，后2题每题2分）1、下列关于算法的描述正确的是（）。算法中有待执行的运算和操作必须是相当基本的（正确答案）一个算法至少有一个输入和一个输出算法并不需要每一个步骤都确切地定义一个算法可以没有结束2、下列关于算法的描述正确的是（）算法只能用自然语言来描述算法只能用流程图或伪代码来表示同一问题可以有不同的算法（正确答案）同一问题的算法不同，结果必然不同3、下列排序算法中，（）不是基于比较的排序。冒泡排序计数排序（正确答案）快速排序选择排序4、“你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。”这一表述主要体现了（）的思想。枚举分治递归（正确答案）贪心5、关于递归算法，下列说法不正确的是（）。一个过程或函数在其定义中有直接或间接调用自身，称为递归递归算法的程序结构往往更简洁递归可能会消耗大量的内存空间，程序执行慢，甚至出现栈溢出等问题若递归算法执行效果慢，可以采用“时间换空间”的思路，使用递推算法改进（正确答案）6、下列关于高精度算法的说法中，错误的是（）。高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算的算法，即高精度算法就是能处理高精度数各种运算的算法。高精度算法中，参与运算的数（加数，被减数，减数，因数）范围大大超出了标准数据类型（整型，实型）能表示范围的运算。高精度数一般采用使用一个数组来表示，一般采用字符串形式读入并采用正序的方式进行存储。（正确答案）高精度算法的内在实质是模拟算法，用计算机来模拟人用笔的计算过程。7、（汉诺塔移动次数）在圣庙里，一块黄铜板上插着三根宝石柱。神在创造世界的时候，在其中一根柱上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从神穿好的那根柱上移到另外一根柱上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。不管传说是否可信，我们现在要解决的是，假设初始柱A上从下到上地穿好了由大到小的n片金片，一次只能移动一片，且必须满足小片在大片之上。问最少移动（）次后所有的金片都从初始穿好的那根柱上移到另外一根柱C上。2n-1TOC\o"1-5"\h\z2n-12n+12n+12的n次方-1(正确答案)2的n-1次方2的n+1次方2的n次方+18、下面这段高精度加法程序计算a+b的值并存储在a中，其中缺了3个空，依次填入选项()可以补全程序。甲：a[i]=(a[i]+b[i])%10乙：a[i+1]=a[i+1]+(a[i]+b[i])/10丙：a[0]=k+1voidplus(inta[],intb[]){inti,k;if(a[0]>b[0])k=a[0];elsek=b[0];for(i=1；i<=k；i++){■;;}if（a[k+1]>0）^^^^^;elsea[0]=k;}甲乙丙乙甲丙（正确答案）丙乙甲丙甲乙二、阅读程序，完成各题（共75分，30小题每题2.5分）1、3456789101112131434567891011121314int[10091];cin>>n;for(inti=l;i<=nji++)cin>>a[i];for(inti=l;i<n;i++)for(intj=l;j++)if(a[j]>a[j+l]){t=a[j];a[j]=a[j+l];a[j+l]=t;}for(inti=l;i<=nji++)cout<<a[i]|<<,,"return0;}（1）这段程序是一个（）算法。快速排序归并排序冒泡排序（正确答案）选择排序（2）若输入n=5，再输入13524,则程序第9行将会执行（）次比较。10（正确答案）537（3）若输入n=4，以下输入（）会使得程序第10行执行的次数最多。12344321（正确答案）42311432⑷若输入n=3，再输入313,则程序第10行会执行（）次。1（正确答案）TOC\o"1-5"\h\z234（5）若将第7行"i<n"修改为"i<=n-1"，程序（）。i的取值范围少1不能正确运行排序出现编译错误能够正确运行排序（正确答案）（6）将第10行"t=a[j];a[j]=a[j+1];a[j+1]=t;"修改为"t=a[j+1];a[j+1]=a[j];a[j]=t;"。程序（）。不能够正确执行交换仍能够正确执行交换（正确答案）出现编译错误将从大到小进行排序（7）将第9行"a[j]>a[j+1]"修改为"a[j]>=a[j+1]"。若输入仍为n=3,再输入313,则程序第10行会执行（）次。TOC\o"1-5"\h\z12（正确答案）34⑻将第7行"i<n"修改为"i<n-1"。若输入n=4,再输入4321,则程序将输出（）。43212134（正确答案）32141234（9）将第7行"i<n"修改为"i<n-1"。若输入n=4,再输入1324,则程序将输出（）。TOC\o"1-5"\h\z4321213432141234（正确答案）（10）在最好情况下，第10行将执行（）次。0（正确答案）1nn（n-1）/22、5689568910?1112131415161718■}qsort(l,j);if(i<r)qsort(i》p);return;■}20212223242526L}#include<iostream>usingnamespacestd;inta[100001];voidqsort(intl,intr)(inti=l,j=r.,m=a[(l+r)/2]t;if(l>=r)return;while(i<=j){while(a[j]>m)j・・;while(a[i]<m)i++;It=a[i];a[i]=a[j];a[j]=t;Ii++；j・・；)199intmain(){intn;cin>>n;for(inti=l;i<=n;i++)cin>>a[i];qsort(l,n);for(inti=n;i>=l;i--)cout<<a[i]«nreturn0;（11）这段程序是一个（）算法。快速排序（正确答案）归并排序冒泡排序选择排序（12）该排序算法同时也体现了（）思想。枚举算法查找算法分治算法（正确答案）贪心算法（13）若输入n=5，再输入13524,则程序将会输出（）。1234554321（正确答案）1543251234（14）若将第7行"i<=j"修改为"i<j",程序（）。i的取值范围少1不能正确运行排序出现编译错误能够正确运行排序（正确答案）（15）将第10行"i<=j"修改为"i<j",程序（）。将从小到大进行排序不能正确运行排序（正确答案）出现编译错误能够正确运行排序（16）将第11行"=a[i];a[i]=a[j];a[j]=t;"修改为a[i]=t;t=a[j];a[j]=a[i];",程序（）。A.不能够正确执行交换（正确答案）仍能够正确执行交换出现编译错误将从小到大进行排序（17）将第17行"return"删除，程序（）。将从小到大进行排序不能正确运行排序出现编译错误能够正确运行排序（正确答案）（18）在最好情况下，该排序算法将执行（）次交换。0（正确答案）TOC\o"1-5"\h\z1nn（n-1）/2（19）在最坏情况下，该排序算法将执行（）次交换。01nn（n-1）/2（正确答案）（20）在编程实现该排序算法时，该思想与以下表述（）有异曲同工之妙。道生一，一生二，二生三，三生万物吃自助餐，每次都挑最贵的一种食物吃小明在思考，思考的内容是：“小明在思考，思考的内容是：‘小明在思考，思考的内容是：……’”（正确答案）逐一排查，查到即止3、1245678Em1245678Em910111213141516171819Linta[101],njkjp=-l;cin>>n>>k;for(inti=l;i<=n;i++)cin>>a[i]jintl=ljr=n,m;while(l<=r)(m=(l+r)/2;if(a[m]==k){IIP=m；|break;}if(a[m]>k)r=m-l;if(a[m]<k)l=m+l;}cout<<p;return0*（21）这段程序是一个（）算法。顺序查找二分查找（正确答案）散列查找枚举（22）若输入82后，再输入235711131719,则程序将会输出（）。TOC\o"1-5"\h\z-101（正确答案）2（23）若输入63后，再输入133335,则程序将会输出（）。23（正确答案）45（24）若输入63后，再输入135642,则程序将会输出（）。-1012（正确答案）（25）若输入93后，再输入147258369,则程序将会输出（）。-1（正确答案）147（26）若将第8行"l<=r"修改为"l<r",程序（）。r的取值范围少1不能正确运行查找（正确答案）出现编译错误能够正确运行查找（27）删去第12行"break"。输入63后，再输入123456,则程序将（）。输出3不能正确运行查找（正确答案）出现编译错误输出-1（28）在执行该算法前，对数组a的要求主要是（）。数组a需要从小到大有序（正确答案）数组a需要从大到小有序对数组a没有任何要求不需要完全有序，但需要数组a的前半部分小于中间值，后半部分大于中间值（29）该算法还可以利用（）的思想来编写程序。排序算法递归算法（正确答案）枚举算法贪心算法（30）与该算法思想相似的问题有（）。求所有的“水仙花数”（“水仙花数”即每位数字的立方和等于该数的三位数，如153=13+53+33。）青蛙跳台阶（青蛙一次可跳1或2级台阶，求青蛙跳上一个n级的台阶的跳法总数。）猜数字游戏（在自然数1到n中取一个数猜，每猜一次知道猜大了或猜小了。怎么猜数最快？）（正确答案）钱币支付问题（假设不同面值纸币的各有若干张，现在不考虑找零钱的支付K元，求最少纸币张数。）三、阅读程序写结果（共12分，3题每题4分)1、#include<iostream>usingnamespacestd;intmain(){intn,x,sum=0;cin>>n;for(inti=1;i<=n;i++){sum=sum+200;cin>>x;sum二sum-x;}cout<<sum;return0;}输入：618030110504060输出：(答案：730)2、#include<iostream>usingnamespacestd;intmain(){constintN=6;intc[N]={};intv[N]={1,5,10,20,50,100};inti,k,m=0,cc=0;cin>>k；for(i=0；i<N；i++)cin>>c[i];for(i=N-1；i>=0；i--){cc二min(k/v[i],c[i]);k=k-ccv[i];m+