2017noip-错题本

1. 在8位二进制补码中，10101011表示的数是十进制下的（ ）。

   A. 43 B. -85 C. -43 D.84

   最初选择：A，因为只是去掉了符号位，并没有理解补码、反码、原码的概念。

   正确答案：B

   解题：由于是补码，转换为10进制的方法如下：补码-1得到反码，反码取反得到原码，经过进制转换成为10进制，加符号。

   10101011（补码）->10101010（反码）->01010101（原码）->-(64+16+4+1)=-85????

   关于补码、反码、原码不再赘述。

2. 甲乙丙3位同学选修课程，从4门课程中选。甲选修2门，乙丙各选修3门，则不同的选修方案共有（ ）。

   A. 36种 B. 48种 C.96种 D.192种

   解题：考验排列组合的组合，甲对应两门课，两门课颠倒顺序不算所以是组合。乙和丙对应三门课，颠倒无效，所以如下图（鼠标手抖????）。结果96种。故选择C。

3. 设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边， 才能使得 G 变成一棵树。

   A. m - n + 1

   B. m - n

   C. m + n + 1

   D. n - m + 1

   定理：树的边数=点数-1=n-1，所以要删掉m-(n-1)=m-n+1条边。

   故选择A。

4. 表达式 a * (b + c) * d的后缀形式是（ ）

   A. abcd*+*

   B. abc+*d*

   C. a*bc+*d

   D. b+c*a*d

   解题：做这种题最好的方法是画一棵树，将表达式套进去，即可使用前序遍历，后序遍历找到前缀表达式（波兰表达式）和后缀表达式（逆波兰表达式），我们平时使用的是中缀表达式，最常用，但是计算机为了处理括号，制造出了后缀表达式，也就是后缀形式，不需要括号。

   这个表达式的树如下：
   
   后缀表达式，就是表达式树的后序遍历，即为abc+*d*，故选择B。

   树的遍历形式不明白也不再赘述。可以再评论区询问，能看见一定回答。

一名Oier的努力，正在更新……