一、单选题（共 15 题，每题 2 分，共计 30 分）

1. 关于图灵机下面的说法哪个是正确的：（）

{{ select(1) }}

• 图灵机是世界上最早的电子计算机。
• 由于大量使用磁带操作，图灵机运行速度很慢。
• 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
• 图灵机只是一个理论上的计算模型。

2. 关于CPU下面哪个说法是正确的：（）

{{ select(2) }}

• CPU全称为中央处理器（或中央处理单元）。
• CPU可以直接运行汇编语言。
• 同样主频下，32位的CPU比16位的CPU运行速度快一倍。
• CPU最早是由Intel公司发明的。

3. 关于ASCII，下面哪个说法是正确的：（）

{{ select(3) }}

• ASCII码就是键盘上所有键的唯一编码。
• 一个ASCII码使用一个字节的内存空间就能够存放。
• 最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
• ASCII码是英国人主持制定并推广使用的。

4.关于程序设计语言，下面哪个说法是正确的：（）

{{ select(4) }}

• 加了注释的程序一般会比同样的没有加注释的程序运行速度慢。
• 高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。
• 高级语言相对于低级语言更容易实现跨平台的移植。
• 以上说法都不对。

5.已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：（） {{ select(5) }}

• 71
• 72
• 73
• 以上都不是

6.十进制小数125.125对应的8进制数是（） {{ select(6) }}

• 100.1
• 175.175
• 175.1
• 100.175

7.有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ （）

{{ select(7) }}

• EDCFAB
• DECABF
• CDFEBA
• BCDAEF

8.表达式a*(b+c)-d的后缀表达式是： （） {{ select(8) }}

• abcd*±
• abc+*d-
• abc*+d-
• -+*abcd

9.一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：（） {{ select(9) }}

• 2n + 1
• 2n-1
• n-1
• n+1

10.快速排序最坏情况下的算法时间复杂度为： （）

{{ select(10) }}

• O($log_2n$)
• O($n$)
• O($nlog_2n$)
• O($n^2$)

11.有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素： （）

{{ select(11) }}

• 11次
• 12次
• 13次
• 14次

12.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：（）

{{ select(12) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

13.已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？（）

{{ select(13) }}

• n
• n+1
• n-1
• n*(n-1)

14.全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：（）

{{ select(14) }}

• http://www.noi.com/
• http://www.noi.org/
• http://www.noi.cn/
• http://www.xinxixue.com/

15.在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：（）

{{ select(15) }}

• 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
• 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
• 通过互联网搜索取得解题思路。
• 在提交的程序中启动多个进程以提高程序的执行效率。

二.阅读程序

阅读程序第一题

判断题

1).这个程序读⼊了⼀个整数 n 和⼀个整数数组，并且将整数数组存在数组 a 中（）

{{ select(16) }}

• √
• ×

2).1. 若将第 13 ⾏中的改为 a[1] ，则程序运⾏结果可能会发⽣改变（）

{{ select(17) }}

• √
• ×

3).若将第 8 ⾏改为 memset(a, 1, sizeof a); ，则执⾏完此语句后， a[0] 的值为 1（）

{{ select(18) }}

• √
• ×

4).若将第 8 ⾏改为 memset(a, 0, 4); ，则程序运⾏结果⼀定不变（）

{{ select(19) }}

• √
• ×

单选题

5).若输⼊的 n 为 5，输⼊的五个数字分别是 1 2 -1 -2 0 ，则程序的输出结果为（）

{{ select(20) }}

• 5
• 3
• 4
• 2

6).若输⼊了 50 个数字，则输出的结果最多为（）

{{ select(21) }}

• 2500
• 1250
• 2450
• 1225

2. 阅读程序第二题

判断题

1).1. 若输⼊的 x 均不为 0，则 a 数组的 [1...n] 元素⼀定均不为 0（） {{ select(22) }}

• √
• ×

2).1. 若输⼊的 x 均不为 0，则 b 数组的 [1...n] 元素⼀定均不为 0（） {{ select(23) }}

• √
• ×

3).1. 若输⼊的数字均为正整数且程序正常运⾏，则程序输出的结果⼀定⼤于 0（） {{ select(24) }}

• √
• ×

4).若输⼊的 n 为 5，且其余输⼊的数字均为 int 范围内的数字，则该程序⼀定能正常运⾏并输出结果（） {{ select(25) }}

• √
• ×

单选题

5).若输⼊为 5 2 2 3 3 5，则该程序的输出为（） {{ select(26) }}

• 36
• 38
• 39
• 21

6)要想让 b 数组的 [1...n] 元素均不为 0 并且 ans ⼤于 100，那么 n 最⼩应该为（） {{ select(27) }}

• 6
• 7
• 8
• 9

3. 阅读程序第三题

注意：输⼊的字符串仅包含 这六种字符中的⼀种。

判断题

1).若将第 9 ⾏的 char a[] 改为 char a[6] ，程序运⾏结果⼀定不变。 {{ select(28) }}

• √
• ×

2).若将第 9 ⾏改为 char a[] = {"{[(}])"}; ，程序运⾏结果⼀定不变。 {{ select(29) }}

• √
• ×

3).若在第 20 ⾏之后加上⼀句 break; ，程序运⾏结果⼀定不变。 {{ select(30) }}

• √
• ×

4).如果输⼊的字符串⻓度为奇数，则程序运⾏结果⼀定为 NO。 {{ select(31) }}

• √
• ×

5).若将第 23 ⾏中的 第flag && sta.empty() 改为flag，程序的运行结果一定不变。

{{ select(32) }}

• √
• ×

6).第 7 ⾏刚定义 sta 时，sta 内容为随机值。 {{ select(33) }}

• √
• ×

7).若将第 6 ⾏改为 getline(cin, s); ，程序运⾏结果⼀定不变。 {{ select(34 }}

• √
• ×

8).如果输⼊的字符串⻓度⼤于 6，则程序可能会运⾏崩溃。 {{ select(35 }}

• √
• ×

单选题

9).如果输⼊的字符串⻓度为 100，则 sta 中元素的数量最多为（）。 {{ select(36) }}

• 50
• 100
• 6
• 3

10).若程序的输出结果为 YES ，则输⼊的字符串可能为（）

{{ select(37) }}

• {[(())(])}
• {}[]((([)]))
• {[]}[{}]()
• {()}([)]()

三、完善程序

（1）（选择数对）有 $n$ 个⼩朋友分别拿着⼀个数字，现在要求你将⼩朋友两两配对，要求每对⼩朋友⼿上的数字之差⼤于给定值 $k$。问最多可以从数组中选出多少对符合条件⼩朋友。（每个⼩朋友最多只能和另外⼀个⼩朋友配对）

输⼊格式：第⼀⾏给出$n, k$分别表示⼩朋友的个数，以及参数 $k (1 \le n , k \le 10^5)$，接下来给出 $n$ 个数字，表示每个⼩朋友⼿上的数字。

提示：⼆分最终的结果，对于⼆分的结果$mid$，在check函数中$O(n)$判断能能否选出$mid$对小朋友符合要求，最终保留二分的结果。

试补全程序。

1).①处应填（ ）。

{{ select(38) }}

• j = 1
• j = n - mid
• j = n - mid + 1
• j = mid

2).②处应填（ ）。 {{ select(39) }}

• a[i] - a[j] > k
• a[i] - a[j] <= k
• a[j] - a[i] > k
• a[j] - a[i] <= k

3).③处应填（ ）。 {{ select(40) }}

• 1
• 0
• n/2
• a[1]

4).④处应填（ ）。 {{ select(41) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

5).⑤处应填（ ）。 {{ select(42) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

2. (栅栏涂⾊)现在有$n$个宽度为$1$的栅栏（可以看作⻓⽅形）在平⾯上并列，其中第 个栅栏的⾼度为 ，现在要每次可以选择⼀块⻓⽅形的区域涂⾊，不能涂到⽆栅栏的地⽅。问⾄少涂⾊⼏次，可以把所有栅栏全部涂⾊（⼀个位置可以被涂⾊多次） 输入第一行包含一个正整数$n$，接下来$n$个数字分别表示每个长方体的高度$a_i$。 解题思路：用递归来求解，假设现在需要涂色a[l]到a[r]的栅栏，我们可以横着涂一个minn * (r - l + 1)的区域，其中minn 为这些栅栏的最低高度。此时会将栅栏中未涂色的区域分成多段（因为可能有多个地方可能有minn），再分别进行递归即可。

1).①处应填（ ）。 {{ select(43) }}

• return
• return 0
• return 1
• 什么也不⽤填

2).②处应填（ ）。 {{ select(44) }}

• get_st(i, minn)
• i
• i + 1
• res

3).③处应填（ ）。 {{ select(45) }}

• dfs(st, r-1)
• dfs(st+1, r)
• dfs(st, r)
• dfs(st+1, r-1)

4).④处应填（ ）。

{{ select(46) }}

• res+1
• res
• res + dfs(l, st) + dfs(st, r)
• res + dfs(l, st - 1) + dfs(st + 1, r)

5).⑤处应填（ ）。

{{ select(47) }}

• res
• dfs(1, n)
• dfs(l, r)
• dfs(1, n) - 1