2019 CSP-S / NOIP提高组初赛试题解析
（一）
一、单项选择题
1. 若有定义：int a=7； float x=2.5，y=4.7；则表达式x+a%3*(int)(x+y)%2的值是:( )
A.0.000000 B.2.750000
C.2.500000 D.3.500000
解析:D。基础，考察数据类型和算术优先级。
2. 下列属于图像文件格式的有（ ）
A.WMV B.MPEG
C.JPEG D.AVI
解析:C。计算机基础知识，其他三个是视频格式。
3. 二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（ ）。
A.11 1111 1111 1101
B.11 1111 1111 1101
C.10 1111 1111 1111
D.11 1111 1111 1111
解析:D。位运算基本知识，两位上有一位为1的时候结果就为1。0|0=0；1|0=1；0|1=1；1|1=1。
4. 编译器的功能是（ ）
A.将源程序重新组合
B.将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
C.将低级语言翻译成高级语言
D.将一种编程语言翻译成自然语言
解析:B。编译器是将高级语言（如C++）编译成计算机能够理解的二进制0和1（机器语言、低级语言）
5. 设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（ ）
A.X=(x*100+0.5)/100.0;
B.x=(int)(x*100+0.5)/100.0;
C.x=(x/100+0.5)*100.0;
D.x=x*100+0.5/100.0;
解析:B。主要考察强制类型转换，加0.5再转成int是四舍五入常用操作。
6. 由数字1，1，2，4，8，8所组成的不同的4位数的个数是（ ）
A.104 B.102
C.98 D.100
解析:B。排列组合问题，也可以用穷举算。
若由4种不同数字即1、2、4、8有A（4,4）=24种；
若有且只有2个数一样，共有1124；1128；1148；1288；1488；2488六类，共6*A(4,4)/A(2,2)=72种；
若1、1、8、8组合有A(4,4)/(A(2,2)*2)=6种；
7. 排序的算法很多，若按排序的稳定性和不稳定性分类，则( )是不稳定排序。
A.冒泡排序
B.直接插入排序
C.快速排序
D.归并排序
解析:C。排序的稳定性特点是排序完成后，之前相同的元素排序不会改变。快速排序在排序时在交换中间元素时可能会打乱顺序。如3、1、1、2、1、6、7、8、9，在一开始3与中间1交换后，稳定性已被打破。
8. G是一个非连通无向图(没有重边和自环)，共有28条边，则该图至少有( )个顶点。
A.10 B.9
C.11 D.8
解析:B。要求最小的点就是要尽可能占用边， n 个点的完全无向图最多占用n*(n+1)/2 条边，n=8的时候是8*7/2=28，意味着8个顶点最多有28条边。由于题目是求非连通图，则再加上单独第9个点。
9. 一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？( )
A.40 B.25
C.30 D.20
解析:B。第1、2位有（0、1、8、6、9）五个数字，第3位有（0、1、8）三个数字，第4、5位由第1、2位决定。由于0,1,8模3正好余0,1,2，所以其他位确定则第3位自然确定，共5*5=25种。
10. 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？( )
A.23 B.21
C.20 D.22
解析:A。容斥原理，至少一门满分人数=数学满分+语文满分-语文数学满分=15+12-4=23。
11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？( )
A.n² B.n㏒n
C.2n D.2n-1
解析:D。两个数组从小到大依次比较，哪边小哪边入数组，当某一数组全部计入结果数组后，剩下的也依次进入。最好的情况是数组A所有数都比数组B第一个数小，只要比较n次。最坏情况是全部比较完，最后AB只剩最后一个数比较，总比较次数就是2n-1。
12. 以下哪个结构可以用来存储图？（ ）
A.栈 B.二叉树
C.队列 D.邻接矩阵
解析:D。数据结构基础。
13. 以下哪些算法不属于贪心算法（ ）。
A.Di.jkstra算法
B.Floyd算法
C.Prim算法
D.Kruskal算法
解析:B。Floyd算法枚举了全部情况自然不是贪心，其他算法均有取最小值。
14. 有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问一下哪个数是可能的公比？（ ）。
A.5 B.3
C.4 D.2
解析:B。直接代入看是否整除可以快速求得答案。可令公比为q，2*q^(2n-2)=118098,得q^(n-1)=248,四个选项中只有3是248的约数。
14. 有正实数构成的数字三角形排列形式如图所示。第一行的数为a(1,1)，第二行a(2,1)，a(2,2)，第n行的数为a(n,1)，a(n,2)，…，a(n,n)。从a(1,1)开始，每一行的数a(i,j)只有两条边可以分别通向下一行的两个数a(i+1,j)和a(i+1,j+1)。用动态规划算法找出一条从a(1,1)向下通道a(n,1)，a(n,2)，…，a(n,n)中某个数的路径，使得该路径上的数之和最大。
令C[i][j]是从a(1,1)到a(i,j)的路径上的数的最大和，并且C[i][0]= C[0][j]=0，则C[i][j]=( )
A.max{C[i-1][j-1],C[i-1][j]}+ a(i,j)
B.C[i-1][j-1]+C[i-1][j]
C.max{C[i-1][j-1],c[i-1][j]}+1
D.max{C[i][j-1],C[i-1][j]}+ a(i,j)
解析:A。每个点只能从上方两个点过来，自然取最大的加a(i,j)。
