试卷下载 浙江J组入围线66分，入围人数共946名，有效参加共5890人。

一、单项选择题

1. 答案：D

解析：C语言是面向过程的，在C语言中没有对象(class)这种概念，C++有STL，就是模版类，当然class也有的。Java、Python也都有class。OI更像c with stl，其实我们做的事情就是面向解决问题的过程，又叫算法。

2. 答案：B

解析：图灵是人工智能之父，有个很著名的人工智能测试叫做图灵测试。

3. 答案：A

解析：送分题，计算机只认0和1。

4. 答案：C

解析：继续送，先选第一个作为最大值，然后比较N-1次。1个数比较0次，特判出来也可以。

5. 答案：D

解析：b不可能比a先出栈，选D

6. 答案：D

解析：树有n-1边，m-(n-1)=m-n+1

7. 答案：C

解析：\(4+1+1* 1/2+1/4=5.75\)

8. 答案：A

解析：完全二叉树种数就是高度为5要填几个，是\(2^{5-1}=16\)个

9. 答案：B

解析：后缀表达即把运算符放在后面，如果不会转换，可以带答案，为B

10. 答案：B

解析：先6个里面选2个，再4个里选2个，最后两个2个里选两个。利用乘法原理，但是过程中包含了顺序，需要再除去。
\(C(6,2)*C(4,2)*C(2,2)/A(3,3)=15\)

11. 答案：B

解析：贪心，哈夫曼编码 出现次数多的编码短，这样总长度就短了。

12. 答案：A

解析：分类，第1位放3or第一位放1或2，\(2*2+(6+1)*2=18种\)

13. 答案：C

解析：\(7*5*3*2*1=210\)

14. 答案：B

解析：有abdce、acdbe、acedb三种顺序，有2种可能。

15. 答案：B

解析：1，2过河，1返回。
4，8过河，2返回。
1，2过河。
2+1+8+2+2=15，更一般的情况，挺难的贪心 POJ1700Crossing River

二、阅读程序

1.f(x)实际上是popcount，返回x二进制表示中1的个数，g(x)为lowbit操作，树状数组一个非常经典的操作。取出非负整数n在二进制表示下最低位的1，以及它后面的0构成的数值，也就是最低位的1所对应的2的幂。典中点之 基本数据类型在内存中的存储

1) 答案：F

解析：n=1001，a下标可使用范围[0,999]，越界了

2) 答案：F

解析：f(x)使用的是&(x-1)，1一定会被去完

3) 答案：F

解析：\(a[4]=10=(1010)_{2}\)，有f(x)=2, g(x)=2

4) 答案：T

解析：f(x)=16，g(x)=2，如果没看懂程序，这个不好做。

5) 答案：F

解析：g函数未定义

6) 答案：B

解析：这两个数非常特殊，65536时2的16次方，2147483647是int最大值，全是1。f(-65536)=16，g(65536)=65536，f(2147483647)=31，g(214748367)=1。这个不好做

2.仅包含解密字符串部分，应该我中午发了你们都看到了？当然硬着分析也问题不大。TZOJ7214: Base64编码

1) 答案：F

解析：解密得到的是任意的，没有限定

2) 答案：T

解析：仅包含了大小写字母、数字和"+"和"/"这64种字符和“=”，输入些垃圾字符，就会被忽略掉。

3) 答案：？T

解析：有争议，如果char类型有符号是-1，否则是255。C语言标准没定义，是ub(undefined behavior)。

4) 答案：B

解析：decode只有一个n的循环，string只有添加字符操作

5) 答案：B

解析：手算，不难，去年有彩蛋，今年没有。

6) 答案：C

解析：这个题目会稍微复杂些，你首先要推出输出字符串长度为8，然后再算再分析，这样的题目建议题目全写完后有非常多的时间再做。

3.和素数筛选有关，很像我们上课学的埃斯特尼筛法，他进行了一下优化。上课也提到过，这是欧拉筛(线性筛)。

1) 答案：T

解析：如果x不等于1，f[1],g[1]也用不到

2) 答案：F

解析：c[i]为i的最小质因子的次数+1，即f[i]的一个因子，这个筛法很巧妙的，有兴趣可以了解下，

3) 答案：F

解析：g求因子和，因子和的话

4) 答案：A

解析：这个算法很nb，O(n)的，因为第二重循环循环到要重复的数时就break掉了，也就是不会重复标记多次。

5) 答案：C

解析：数一下100以内的质数个数，2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97共25个

6) 答案：C

解析：看懂了很简单，f求因子个数，g求因子和。\(1000=2^{3}*5^{3}\)，因子个数为\((3+1)*(3+1)=16\)；因子和的公式比较复杂，自己就手算一下吧。

三、完善程序

1.本题很简单，有做错的出去挨打。我们约瑟夫环写的比这个难。

1) 答案：D

解析：c记录离开的人数，c=n-1作为结束条件

2) 答案：C

解析：p记录当前报的数，报1离开。

3) 答案：C

解析：离开的人数+1

4) 答案：D

解析：交替0和1

5) 答案：B

解析：i表示当前报数的人，需要从0~(n-1)依次

2.二分+枚举，不算难，相对阅读程序来说，这次完善程序很简单。

1) 答案：B

解析：按照横纵坐标排序。

2) 答案：D

解析： unique函数是要删去多余的点，第一个点保留，之后和前一个比，相等就舍去，其实就是离散化的思想，线段求交也能用。

3) 答案：C

解析：这不就是二分嘛，右移就是/2

4) 答案：B

解析：点是按升序排的，也是一样的比较方法，满足则p点在mid右侧

5) 答案：D

解析：前两层循在枚举左下顶点和右上顶点，需要判断i点是不是在j点的左下方。