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

1. 补码（10011001）2的原码是（）。

{{ select(1) }}

• 10011001
• 01100110
• 11100110
• 11100111

2. 计算机中，决定计算机寻址大小的是（）。

{{ select(2) }}

• 内存
• 寄存器
• 数据总线
• 地址总线

3. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

{{ select(3) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

4.从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要的地位。冯·诺依曼体系结构的核心内容是（ ）。

{{ select(4) }}

• 采用开关电路
• 采用半导体器件
• 采用存储程序和程序控制原理
• 采用键盘输入

5.在 C++程序中,表达式 23|2^5 的值是( ) {{ select(5) }}

• 23
• 1
• 32
• 18

6.已知7个结点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号,以下同),中根遍历 是4 2 6 5 1 7 3,则该二叉树的后根遍历是( ) 。 {{ select(6) }}

• 4 6 5 2 7 3 1
• 4 6 5 2 1 3 7
• 4 2 3 1 5 4 7
• 4 6 5 3 1 7 2

7.一颗完全二叉树可以使用数组表示，现在标记根为0（即数组第0个元素为二叉树的根），已知一个节点的下标为i，则该节点的父节点下标为（）。

{{ select(7) }}

• （i＋1）／2
• i－2
• （i－1）／2
• i／2

8.已知一个栈的空间大小为3，元素 a b c d e 顺序入栈，那么下面不能的出栈顺序是（）。 {{ select(8) }}

• a b c d e
• b c d e a
• d c b a e
• c d e b a

9.（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 {{ select(9) }}

• 动态规划
• 贪心
• 分治
• 搜索

10.与十进制数28.5625相等的四进制数是（ ）。

{{ select(10) }}

• 130.5625
• 13.21
• 130.21
• 130.5

11.已知x=（0.1011010）2 ，则[X/2]补=（ ）2。

{{ select(11) }}

• 0.1011101
• 11110110
• 0.0101101
• 0.100110

12.地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（ ）。

{{ select(12) }}

• 2 4 3 6 5 7
• 2 4 1 2 5 7
• 2 4 3 1 7 6
• 2 4 3 6 7 5

13.完全二叉树的节点个数为11，则它的最后一层叶结点个数为（ ）。

{{ select(13) }}

• 4
• 3
• 5
• 2

14.对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。

{{ select(14) }}

• a
• b
• c
• d

15.现在有5个字母 A、B、C、D、E出现的频率分别为10，2，3，5，8，问由这些字母构成的哈夫曼树最长的编码长度为（ ）。

{{ select(15) }}

• 1
• 2
• 3
• 4

二.阅读程序写结果（共4题，每题8分，共计32分）

判断题

1).第10行str[i] |=32换成str[i]+=32效果相同（）

{{ select(16) }}

• √
• ×

2).函数my_strip参数在64位系统下占8个字节（）

{{ select(17) }}

• √
• ×

3)若没有6 7两行，程序也能正常运行（）

{{ select(18) }}

• √
• ×

4).16行gets输入可能会读入超过64个字符（）

{{ select(19) }}

• √
• ×

选择题

5).输入数据 Are you ok，那么输出的结果为（）

{{ select(20) }}

• Are you ok
• Are You Ok
• are:you:ok
• ARE:YOU:OK

6).若输入5个连续空格，那么输出结果为（）

{{ select(21) }}

• 无输出
• ：
• 5:
• :::::

判断题

1).COUNT是一个变量（） {{ select(22) }}

• √
• ×

2).如果将数组a放在全局，那么cocktail_sort可以不传参数（） {{ select(23) }}

• √
• ×

3).若将第14 15行注释掉，程序效果相同（） {{ select(24) }}

• √
• ×

4).若输入数据全部相同，最后将输出1（） {{ select(25) }}

• √
• ×

选择题

5).若输入数据 10 1 2 3 4 5，那么输出的结果为（）。 {{ select(26) }}

• 1
• 2
• 3
• 4

6)若输入数据 10 5 3 2 4 1，那么输出结果为（）。 {{ select(27) }}

• 1
• 2
• 3
• 4

判断题

1).第四行为递归的终止条件（） {{ select(28) }}

• √
• ×

2).foo函数没有返回值（） {{ select(29) }}

• √
• ×

选择题

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

{{ select(30) }}

• 7,6,5
• 5,7,6
• 5,6,7
• 7,5,6

4).若输入数据3 1 2，则结果为（）。

{{ select(31) }}

• 3,1,2
• 1,2,3
• 2,3,1
• 2,1,3

5).如果第4行修改为if (a>b && c > b),那么第三题的结果为（）。

{{ select(32) }}

• 7,6,5
• 5,7,6
• 5,6,7
• 7,5,6

6).(4分)在最坏的情况下，foo将会被调用几次（）。

{{ select(33) }}

• 1
• 2
• 3
• 4

三、完善程序(每小题3分，总共30分)

（1）快速排序为常用的排序，请完善下面程序。

1).①处应填（ ）。

{{ select(34) }}

• i <= j
• i < j
• i == j
• i >= j

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

• j++
• j--
• i++
• i--

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

• swap(a[i-1],a[j])
• swap(a[i],a[j])
• swap(a[i],a[j-1])
• swap(a[i+1],a[j+1])

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

• quick_sort(a,right,j)
• quick_sort(a,left,i)
• quick_sort(a,left,i+1)
• quick_sort(a,left,i-1)

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

• quick_sort(a,0,n)
• quick_sort(a,1,n)
• quick_sort(a,0,n-1)
• quick_sort(a,0,n)

2.（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

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

• 1
• n
• i+1
• 0

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

• y[j]>y[i]
• y[j]<y[i]
• y[j]>=y[i]
• y[j]<=y[i]

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

• f[i]+1
• f[j]+1
• f[i]++
• f[j]++

4).④处应填（ ）。

{{ select(42) }}

• f[i]>max_f
• f[i]>=max_f
• f[j]>=max_f
• f[j]>max_f

5).⑤处应填（ ）。

{{ select(43) }}

• ans = i
• ans = i++
• ans = j
• ans = f[i]