该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一、单项选择题(共 15 题，每题 2 分，共计 30 分:每题有且仅有一个正确选项)

1.1 TB 代表的字节数量是(） {{ select(1) }}

• 2 的 10 次方
• 2的 20 次方
• 2的 30 次方
• 2的 40 次方

2.下列几个 32 位 IP 地址中，书写错误的是() {{ select(2) }}

• 256.256.129.1
• 10.0.0.1
• 162.105.128.27
• 192.168.0.1

3.已知 x的值用 8 位二进制表示为 00110100，则 C++ 程序片段 x &(x-1)的结果可以用 8位二进制( )表示。 {{ select(3) }}

• 00000001
• 00110000
• 00110011
• 00110111

4.从 100 到 999 这 900 个整数中,不包含数字 9 的整数共有( )个。 {{ select(4) }}

• 632
• 640
• 648
• 800

5.下列表达式中和下图的表达式树实质上完全一致的是(）

{{ select(5) }}

• a+b*c-d*f
• a*c+b*c-d*f
• a+b-c*d*f
• (a+b)*c*(d-f)

6.已知队列(12，30，5，37，18，22，15)，第一个进队列的元素是12，则下列说法中错误的是(） {{ select(6) }}

• 第一个出队列的元素是 12
• 第二个进队列的元素是 30
• 第四个出队列的元素是5
• 第五个进队列的元素是 18

7.如下所示的有向无环图，若对该图进行深度优先遍历，可以得到的正确的顶点序列不包括(）

{{ select(7) }}

• 1、2、3、4、5
• 1、2、3、5、4
• 1、3、2、5、4
• 1、4、3、2、5

8、若逻辑变量 A、C 为真,B、D 为假,以下逻辑运算表达式为真的是() {{ select(8) }}

• A^(DV¬C)^B
• ((¬A^B)vC)^B
• (A^B)V(C^DV¬A)
• (BVCVD)VD^A

9、由四个相同结点所构成的二叉树共有(）种

{{ select(9) }}

• 14
• 15
• 16
• 18

10.有一个 5x5 的棋盘，棋盘左下格有一枚棋子，我们每次可以将棋子向右移动一格，也可以向上移动一格，但棋盘的某些方格不可以放置棋子(如下图所示,划x的方格表示不可以放置棋子),则左下格到右上格一共存在(）条路径。

{{ select(10) }}

• 10
• 11
• 12
• 13

11、有三根相邻的柱子，标号分别为A、B、C。初始时，柱子A从下到上按金字塔状叠放着n个不同大小的圆盘。现在，要把所有圆盘从柱子A移动到柱子B上，每次只能移动一个圆盘，要求移动过程中，同一根柱子上始终不能出现大盘子位于小盘子之上的情形。请问完成这一任务至少需要多少次，并输出具体的移动方案。解决这一问题，程序设计中通常采用() 算法。 {{ select(11) }}

• 穷举
• 贪心
• 广度优先搜索
• 递归

12.在 8 位二进制补码中，10100111 表示的是十进制下的(

{{ select(12) }}

• 39
• -88
• -39
• -89

13 .在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是() {{ select(13) }}

• 堆排序
• 希尔排序
• 冒泡排序
• 快速排序

14.要求以下程序的功能是计算 1+1/2 +1/3+…+1/20 的结果，并保留8 位小数输出。但程序运行后，输出结果错误。

 #include <iostream>
 #include <iomanip>
 using namespace std;
 int main(){
     int n= 20;
     double s=1.0;
     while(n>1){
         s=s+1/n;
         n--;
     }
     cout<< fixed<< setprecision(8)<< s<<endl;
     return 0;
 }

如要使程序正确，但只能修改一行程序，则应当修改的程序行是()

{{ select(14) }}

• double s=1.0;
• while(n>1){
• s=s+1/n;
• n--;

15.下列有关CSP或NOI的说法中，错误的是()。 {{ select(15) }}

• 1984年，邓小平同志提出“计算机的普及要从娃娃抓起"。为响应这一号召，中国计算机学会于当年自主创办了 NOI。
• CSP-J/S的中文意思是非专业级软件能力认证，分为csP-J(入门级)和CSP-S(提高级)。CSP-J/S 成绩优异者，可参加NOI省级选拔，省级选拔成绩优异者可参加 NOI。
• NOI的中文意思是全国青少年信息学奥林匹克竞赛，参与的青少年选手来自全国各省、直辖市、自治区，但不包括香港特别行政区、澳门特别行政区
• NOI机试中，文件或文件目录名不正确(包括大小写错误)、所提交的程序文件试图访问网络、打开或创建题目规定的输入/输出文件之外的其它文件，均会导致被判0分。

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√，错误填x;除特殊说明外，判断题1.5分，选择题3分，共计40分)

程序一：

16)删除第 25 行，对计算答案没有任何影响。( ) {{ select(16) }}

• 正确
• 错误

17)输入的字符串只能包含大写字母，不然可能出现运行时错误。( ) {{ select(17) }}

• 正确
• 错误

18)如果输入的所有字符串总长度超过 100000,程序一定会访问无效内存。( ) {{ select(18) }}

• 正确
• 错误

19)把 cnt 初值设为 1,把第 30 行的+1 删去,对最终答案无影响。 {{ select(19) }}

• 正确
• 错误

20)若输入的字符串为 AS ASP ASCII BASIC BASSAC ，则输出为(

{{ select(20) }}

• 14
• 15
• 18
• 22

21)若输入了 100个各不相同的字符串，每个串的长度为1000，则答案最小为()

{{ select(21) }}

• 1001
• 1103
• 1104
• 100001

程序二：

22)要使输出等于 n，输入必须满足 a1 < a2< .. < an。( ) {{ select(22) }}

• 正确
• 错误

23)若输入数字个数超过 101个，一定会发生数组下标溢出。( ) {{ select(23) }}

• 正确
• 错误

24)程序运行过程中，变量r的值一定不会等于 n。( ) {{ select(24) }}

• 正确
• 错误

25)输入为7 11 11 13 9 8 17 19则，输出为()

{{ select(25) }}

• 7
• 6
• 5
• 4

26)第 22 行 last[r]=a 最多会运行( )

{{ select(26) }}

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

27)若输入n = 100，且第 16 行的 while 循环运行了至少一次，那么输出结果不可能是()

{{ select(27) }}

• 2
• 3
• 49
• 98

程序三：

28)14行tmp =rand()%(right-left)+left换成tmp=(right+left)/2，程序运行结果不变。( ) {{ select(28) }}

• 正确
• 错误

29)第 29 行和第 30 行的递归调用，每次只能调用其中一个。( ) {{ select(29) }}

• 正确
• 错误

30)如果n的取值范围不是[1,m]，程序可能出现运行时错误。( ) {{ select(30) }}

• 正确
• 错误

31)输入的数据为: 5 4 3 2 5 1 4 则程序的运行结果是

{{ select(31) }}

• 2
• 3
• 4
• 5

32)若输入的数据为:10 80 90 40 50 20 30 10 60 70 100 4,则程序的运行结果是()

{{ select(32) }}

• 44
• 40
• 60
• 70

33)此程序的时间复杂度是( )

{{ select(33) }}

• O(logm)
• O($m^2$)
• O(mlogm)
• O(m)

三、完善程序(单选题，每题3分，共计30分)

程序一：

(蛇形方阵)给出一个不大于 9 的正整数 n，输出 nxn 的蛇形方阵。从左上角填上1开始，顺时针方向依次填入数字，如果到达边界或者已填过的方格，就顺时针转换方向，继续填写，直到整个方阵全部填满，下面是n=4 对应的蛇形矩阵：

34. ①处应填（ ） {{ select(34) }}

• ceil(1.0 *n /2)
• ceil(1*n/2)
• floor(1.0 *n /2)
• floor(1*n/2)

35. ②处应填（ ） {{ select(35) }}

• i
• i+1
• n-i-1
• i-1

36. ③处应填（ ） {{ select(36) }}

• n
• n-i
• n-i-1
• num

37. ④处应填（ ） {{ select(37) }}

• i
• j
• n-i-1
• n-j-1

38. ⑤处应填（ ） {{ select(38) }}

• a[i][j]
• a[j][i]
• a[n-i-1][j]
• a[j][n-i-1]

程序二：

(过河问题)在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一座独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同，两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 n(2<=n<20)和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。 例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为 7。具体方法是:甲、乙一起过桥到河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为 2+1+4=7。

39. ①处应填（ ） {{ select(39) }}

• num<=0
• num<=1
• num<=2
• num<=3

40. ②处应填（ ） {{ select(40) }}

• 1
• i
• i-1
• i+1

41. ③处应填（ ） {{ select(41) }}

• pos[i]==LEFT && pos [i+1]==LEET
• pos[i]==LEFT || pos [i+1]==LEET
• pos[i]==LEFT
• pos[i]!=LEFT

42. ④处应填（ ） {{ select(42) }}

• go(RIGHT_TO_LEFT)+ hour[i]
• go(LEET_TO_RIGHT)+ hour[i]
• min(hour[i],hour[i+1])+hour[i]
• hour[i]

43. ⑤处应填（ ） {{ select(43) }}

• pos[i]==LEFT
• pos[i]==RIGHT
• pos[i]==LEET_TO_RIGHT
• pos[i]==RIGHT_TO_LEFT