阅读程序部分难度比较高,其他的难度还可以,整体来说必之前难一点。
一、单项选择1.D
2.B
3.A
4.C
N个数字找最大值,一般做法就是把第一个数字作为最大值直接存下来,然后和后面的每个数字比较,这种方法的比较次数是N-1,同时也是答案中的最小值了,故选 C。
5.D
模拟入栈出栈操作就可以。
6.D
图有m条表,树的边数是n-1,即m - ( ) = n-1. 需要删除 m-n+1条边。
7.C
8.A
高度为5的完全二叉树最后最后一层的节点数取值范围为1 - 16 故选 A
9.B
10.B
C62 * C42 * C22 / A33 先给每一组选人,因为不区分编号,消除因为组号带来的不同,故需要除以 A33
11.B
12.A
分情况讨论:
无重复数字:只能选123,然后A33
有重复数字:先从1,2选出重复数字具体是谁,然后再选出唯一的数字,这样的三个数字有三种排列方法。
C21 * C21 * 3
所以共有 A33 + C21 * C21 * 3 = 18种情况
13.C
7 * 5 * 3 * 2 * 1
14.B
15.B
这里过河有两种策略:
策略1:让快的人送慢的人过河 然后快的人划船回来 可以节省回来的时间
策略2:让两个慢的人一起过河 这样整体来说可能会节省一些时间
过河过程:
1 2 → 过河 ←1 回来
4 8 → 过河 ←2 回来
1 2 → 过河
总的过河时间: 2 + 1 + 8 + 2 + 2 = 15
二、阅读程序(1)
题目重点是要知道 f(x) 和 g(x)的作用。
首先看f(x):
假设 x 是 5,转换成补码进行运算
x: 0000 0000 0000 0101
x-1: 0000 0000 0000 0100
x&x-1: 0000 0000 0000 0100
x变成4:,继续运算
x: 0000 0000 0000 0100
x-1: 0000 0000 0000 0011
x&x-1: 0000 0000 0000 0000
那么,不难看出,x&x-1的作用相当于去掉了二进制x中最低位的1,
f(x)这个算法叫做pop_count(),作用是统计一个数字的二进制形式中有含有的 1 的数量。
然后看g(x):
假设 x 是 5,转换成补码进行运算
x: 0000 0000 0000 0101
-x: 1111 1111 1111 1011
x&-x: 0000 0000 0000 0101
假设 x 是 4,转换成补码进行运算
x: 0000 0000 0000 0100
-x: 1111 1111 1111 1100
x&-x: 0000 0000 0000 0100
那么,不难看出,x&-x的作用相当于取到了二进制x中最低位的1的权重。
g(x)其实就是树状数组中常用的 lowbit()操作。
错误
错误
错误
根据代码分析进行计算
2:2+1 = 3 正确
11:3+1 = 4 正确
9: 2+1 = 3 正确
16: 1+16 = 17正确
10: 2+2 = 4 错误
正确 直接计算: 511998 = 0111 1100 1111 1111 1110 16 + 2 = 18
20: 错误 需要有函数