争取每天更新两篇

2013 提高组

(前面是原题) 分析在后面

1、A，一个字节有8个bit，32位整型变量占用4个字节，故选A。

2、A，二进制11.01转为十进制，（11.01）2 = 12+1+00.5+1*0.25 = （3.25）10 。所以选A

3、B,老和尚给小和尚讲的故事里边有故事本身，递归是函数内部调用函数本身，故选B，递归。(自己调用自己)

4、D，1948香农信息论鼻祖。冯诺依曼在1944年提出冯诺依曼理论 如今的计算机仍属于冯诺依曼架构 其理论简要概括为 计算机硬件设备由存储器 运算器 控制器 输入设备

输出设备5部分构成,思想为把计算过程描述为由许多命令安一定顺序组成的程序,程序和数据输入电脑,计算机对已存入的程序和数据处理后,输出结果.

说到图灵 应该想到他1936年提出了一种理想计算机的数学模型(图灵机)

成为计算机科学理论基础的第一人.欧拉是跑过七桥的hh

5、A，一定是满二叉树时拥有2个字节点的节点数最多，最下一层会有2013-1023=990个节点，于是倒数第二层会有990/2=495个节点有2个字节点，从第1层到倒数第三层共有1023-2^9=511个节点，且这些节点都是用2个子节点的节点，所以共有495+511=1006个，选A。

还有一种解法就是 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； 则 2*N2+N1=2012 要使 N2最大 则使N1为0 解的 1006

6、B，无向图中，不是连通图意味着一个节点的度为0,所有顶点度最少是3，最多是4,所以最少需要删除3条边，选B。

7、D，这个题有点小坑…我第一次做无脑选了O(n)，其实选O(Fn))至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).

8、B，先序遍历 根左右 中序遍历 左根右 后序遍历 左右根就ok了

9、D，由计算可得,A,B,C都有冲突 D项分别为1，2，3，4，不冲突。

10、D，IPV6地址是128位的。

11、C，6*6=36条边。
12、B，Unicode（统一码、万国码、单一码）是计算机科学领域里的一项业界标准,包括字符集、编码方案等。Unicode 是为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。1990年开始研发，1994年正式公布。

13、D，64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位。

14、B，Dijkstra算法计算单源最短路时间复杂度如果不借助堆或优先队列优化，是O（n^2）.y总讲过

15、B，看到 n/2显然是log级别的 这里又没出现n²

二、不定项选择题（5*1.5）
1、AC，很显然
2、AD，只有快速排序和归并排序是nlgn的，冒泡和插入都是n²的时间复杂度。
3、CD，学过的应该都没问题
4、AB，NP问题是指还未被证明是否存在多项式算法能够解决的问题

首先需要介绍P(Polynomial,多项式)问题.P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题.NP(Non-Deterministic Polynomial, 非确定多项式)问题,是指可以在多项式时间内被非确定机(他可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题

5、ABCD

三、问题求解（2*5）
1、0 1 1 1；简单题
2、37/12，递归

四、阅读程序写结果（4*8）
1、Yes，回文串
2、133，容斥原理或者集合求并很容易可以得到1000/10+1000/15-1000/30=133.
3、4，最长上升子序列
4、7，求最大连通块

五、完善程序(15+13)
1、n-p+i i-p+1 a[i-p] i>end1 i j-1;

2、j-i cur1 count1–; count2–; cur1=a[j],手动模拟吧