第 14 题
$Description$
在整数的补码表示法中,以下说法正确的是( )。
A. 只有负整数的编码最高位为1
B. 在编码的位数确定后,所能表示的最小整数和最大整数的绝对值相同
C. 整数0只有一个唯一的编码
D. 两个用补码表示的数相加时,如果在最高位产生进位,则表示运算溢出
$Answer:AC$
不,不是你想的那个意思
$Explanation:$
补码和反码存在的意义一度令我十分困惑。
实际上,反码和补码是为了解决计算机内的加减法问题。
用原码做减法结果显然不正确。
反码表示又会出现一个问题:0和-0在计算机内的表示并不相同。
比 如 说
~
1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0
- 而补码的横空出世解决了以上的所有问题。
1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原
- 这样0用[0000 0000]表示, 而以前出现问题的-0则不存在了.而且可以用[1000 0000]表示-128:
(-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补
- 所以八位补码能够表示的范围是$[-128,127]$
第 22 题
$Description$
无向图G有7个顶点,若不存在由奇数条边构成的简单回路,则它至多有__条边。
$Answer:12$
$Explanation:$
这是一道经验题。
因此,
由经验可得,将图划分为二分图能使边数最大。通过计算得两边分别有3,4个点时最优。
$ps.$附《西江月 证明》一首。
即得易见平凡,仿照上例显然。
留作习题答案略,读者自证不难。
反之亦然同理,推论自然成立。
略去过程QED,由上可知证毕。
第 23 题
$Description$
记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列。
如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是_。
$Answer:18$
$Explanation:$
此题可用抽屉原理解决。
设正整数的前缀和为$sum_i$
现将$[1,32]$划分为17个集合,满足:
集合中有一个或两个元素。
- 若有两个元素,较大元素与较小元素的差为9.
也就是{1,10}, {2,11}, …, {8,17}, {18,27}, {19,28},…,{23,32} ,{24},{25},{26}
$sum_i$不能含有一个集合中的两个元素,则$n=18$时恰不能满足。