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

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

1. 以下哪一种设备属于输出设备（ ）

{{ select(1) }}

• 扫描仪
• 键盘
• 鼠标
• 打印机

2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。

{{ select(2) }}

• (269)16
• (617)10
• (1151)8
• (1001101011)2

3. 1MB 等于（ ）

{{ select(3) }}

• 1000 字节
• 1024 字节
• 1000 X 1000 字节
• 1024 X 1024 字节

4.广域网的英文缩写是（ ）。

{{ select(4) }}

• LAN
• WAN (Wide Area Network)
• MAN
• LNA

5.中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。 {{ select(5) }}

• 1983
• 1984
• 1985
• 1986

6.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第 81个字符是字母 ( )。 {{ select(6) }}

• A
• S
• D
• a

7.根节点深度为 0，一棵深度为 h 的满 k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有( )个结点。

{{ select(7) }}

• (k^(h+1) -1)/(k-1)
• k^(h-1)
• k^h
• (k^(h-1) ) / (k - 1)

8.以下排序算法中，不需要进行关键字比较操作的算法是( )。

{{ select(8) }}

• 基数排序
• 冒泡排序
• 堆排序
• 直接插入排序

9.给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 N - 1 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整，⌊ ⌋表示向下取整) {{ select(9) }}

• ⌈3N / 2⌉ - 2
• ⌊3N / 2⌋ - 2
• 2N - 2
• 2N - 4

10.下面的故事与( )算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事:‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事......’”

{{ select(10) }}

• 枚举
• 递归
• 贪心
• 分治

11.由四个没有区别的点构成的简单无向连通图的个数是( )

{{ select(11) }}

• 6
• 7
• 8
• 9

12.设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为( )。

{{ select(12) }}

• 5 / 32
• 15 / 128
• 1 / 8
• 21 / 128

13.10000 以内，与 10000 互质的正整数有( )个。

{{ select(13) }}

• 2000
• 4000
• 6000
• 8000

14.为了统计一个非负整数的二进制形式中 1 的个数，代码如下:

则空格内要填入的语句是( )。

{{ select(14) }}

• x >>= 1
• x &= x - 1
• x |= x >> 1
• x <<= 1

15.下图中所使用的数据结构是( )。

{{ select(15) }}

• 哈希表
• 栈
• 队列
• 二叉树

二.阅读程序

判断题

1).（2分）输入浮点数，程序也能正常执行（）

{{ select(16) }}

• √
• ×

2).（2分）若将第 5 行的 s[i]改成 i<strlen(st)，效果相同（）

{{ select(17) }}

• √
• ×

3).（2分）st[i]+=1 的结果为整数（）

{{ select(18) }}

• √
• ×

4).（2分）若输入全为小写字母，则输出为原字符串（）

{{ select(19) }}

• √
• ×

单选题

5).若输入数据 AbCdEf，那么输出的结果为（）

{{ select(20) }}

• AbCdEf
• BbDdFf
• BcDeFg
• BCDEFG

6).若输入的字符串长度为 n，第 5 行的 s[i]改成 i<strlen(st)，那么程序的时间复杂度为（）

{{ select(21) }}

• O（n）
• O（n 2）
• O(nlogn)
• O(2n)

判断题

1).res 有可能等于 0（） {{ select(22) }}

• √
• ×

2).乘法的优先级高于取余（） {{ select(23) }}

• √
• ×

3).若将第 4 行&x 改为 x，程序有可能异常结束（） {{ select(24) }}

• √
• ×

4).若将第 6 行的 i < x 改为 i<=x 结果不会改变（） {{ select(25) }}

• √
• ×

单选题

5).若输⼊10，那么输出的结果为（） {{ select(26) }}

• 0
• 1
• 2
• 3

6)若将第 7 行改为 i*i%x==0,输入数据 6，那么输出结果为（） {{ select(27) }}

• 0
• 1
• 2
• 3

判断题

1).第 5 行为递归的唯一结束条件（）。 {{ select(28) }}

• √
• ×

2).如果 findans 为 void 类型，那么程序将会报错（） {{ select(29) }}

• √
• ×

3).如果输入的数值过大，那么栈有可能会溢出（） {{ select(30) }}

• √
• ×

4).m 和 n 中较小的值决定了递归的层数（） {{ select(31) }}

• √
• ×

单选题

5).若输入 6 3，那么结果为（）

{{ select(32) }}

• 18
• 3
• 5
• 6

6).若输⼊7 4，那么输出结果（）

{{ select(33) }}

• 18
• 3
• 5
• 6

三、完善程序

（1）（最大公约数之和）下列程序想要求解整数 举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约 数为 2；1 和 4 的最大公约数为 1。于是答案为 1 + 2 + 1 = 4。 要求 getDivisor 函数的复杂度为 0(√n)，gcd 函数的复杂度为 O(log max(a,b))。

1).①处应填（ ）。

{{ select(34) }}

• i
• i*i
• i+i
• a[i]

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

• n
• sqrt(n)
• n/i
• n%i

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

• return a
• return b
• return 0
• return 1

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

• a%b
• b%a
• a
• b

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

• gcd(a[i],a[j])+i
• gcd(a[i], a[j])
• ans
• ans + gcd(a[i], a[j])

2.对于一个 1 到 n 的排列 p(即 1 到 n 中每一个数在 p 中出现了恰好一次)，令qi 为第 i 个位置之后第一个比 pi 值更大的位置，如果不存在这样的位置，则qi =n+1。举例来说，如果 n=5 且 p 为 1 5 4 2 3，则 q 为 2 6 6 5 6。 下列程序读入了排列 p，使用双向链表求解了答案。试补全程序。（第二空 2 分，其余 3 分）数据范围 1 ≤ n ≤ 10^5。

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

• a[x] = i
• a[i] = x
• a[x] = x
• a[x] = i++

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

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

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

• R[a[i]]
• a[R[i]]
• R[i]
• R[x]

4).④处应填（ ）。

{{ select(42) }}

• a[x]
• a[i]
• L[a[i]]
• L[i]

5).⑤处应填（ ）。

{{ select(43) }}

• a[i]
• L[i]
• R[i]
• R[a[i]]