一、
单项选择题（共
15
题，每题
1.5
分，共计
22.5
分；每题有且仅有一个正确 选项）
1.
一个
32
位整型变量占用（ ）个字节。
A. 4 B. 8 C. 32 D. 128
A
1
字节
=8
位（
1byte=8bit
）
2.
二进制数
11.01
在十进制下是（ ）。
A. 3.25 B. 4.125 C. 6.25 D. 11.125
A
送分题
3.
下面的故事与（ ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：
‚从前有座山，山 里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个 老和尚给小和尚讲故事
….
’‛
A.
枚举
B.
递归
C.
贪心
D.
分治
B
学过的都知道
=w=
4. 1948
年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A.
冯·诺伊曼（
John von Neumann
）
B.
图灵（
Alan Turing
）
C.
欧拉（
Leonhard Euler
）
D.
克劳德·香农（
Claude Shannon
）
D
个人感觉蒙也能蒙对吧，记住就好，。香农用信息熵的概念来描述信源的不确定度。
5.
已知一棵二叉树有
2013
个节点，则其中至多有（ ）个节点有
2
个子节点。
A. 1006 B. 1007 C. 1023 D. 1024
A
学过二叉树的应该都知道至少也了解，最后一个非叶子节点为
n div 2
6.
在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通
图。右图是一个有
5
个顶点、
8
条边的连通图。若要使它不再是连通 图，至少要删去其中的（ ）条边。
A. 2 B. 3 C. 4 D. 5
B
无向图中，不是连通图意味着一个节点的度为
0
，最小为
3
7.
斐波那契数列的定义如下：
F1 = 1, F2 = 1, Fn = Fn
–
1 + Fn
–
2 (n
≥
3)
。如果用下面的函数计 算斐波那契数列的第
n
项，则其时间复杂度为（ ）。
funtion F(n : longint) : longint;
begin
if n <= 2 then F := 1 else F := F(n – 1) + F(n – 2);
end;
A. O(1) B. O(n) C. O(n2) D. O(Fn)
D
ABC
显然不对
=w=
，其实实际上确实是
D
8.
二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子
树上所有节点的值。那么，二叉查找树的（
）是一个有序序列。
A.
先序遍历
B.
中序遍历
C.
后序遍历
D.
宽度优先遍历
B
显然
9.
将（
2, 6, 10, 17
）分别存储到某个地址区间为
0~10
的哈希表中，如果哈希函数
h(x) =
（ ），将不会产生冲突，其中
a mod b
表示
a
除以
b
的余数。
A. x mod 11 B. X^2 mod 11 C. 2x mod 11 D.
⌊√ ⌋
mod 11
，其中⌊√ ⌋表示√ 下取整
D
试试就知道
10. IPv4
协议使用
32
位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用（ ）位地址的
IPv6
协议所取代。
A. 40 B. 48 C. 64 D. 128
D
姿势题，记住吧
11.
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。
那么，
12
个顶点的二分图至多有（ ）条边。
A. 18 B. 24 C. 36 D. 66
C
一边
6
个点，以左边来看，一个点最多和对面连
6
条边
12.
（
）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进
制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
A. ASCII B. Unicode C. GBK 2312 D. BIG5
B
又到了一年一度拼人品的时候了
=w=
，不过显然
A
是不选的
Unicode
（统一码、万国码、单一码）是计算机科学领域里的一项业界标准
,
包括字符集、编码方案等。
Unicode
是为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的二进制编码，
以满足跨语言、跨平台进行文本转换、处理的要求。
1990
年开始研发，
1994
年正式公布。
13.
把
64
位非零浮点数强制转换成
32
位浮点数后，不可能（ ）。
A.
大于原数
B.
小于原数
C.
等于原数
D.
与原数符号相反
D
这个显然吧
14.
对一个
n
个顶点、
m
条边的带权有向简单图用
Dijkstra
算法计算单源最短路时，如果不 使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
A. O(mn + n3) B. O(n2) C. O((m + n) log n) D. O((m + n2) log n)
B
15. T(n)
表示某个算法输入规模为
n
时的运算次数。如果
T(1)
为常数，且有递归式
T(n) = 2*T(n / 2) + 2n
，那么
T(n) =
（ ）。
A.
Θ
(n) B.
Θ
(n log n) C.
Θ
(n2) D.
Θ
(n2 log n)
B
T
（
n/2)
显然运算次数是
logn
的，求
T(n)
所以
B
二、不定项选择题（共
5
题，每题
1.5
分，共计
7.5
分；每题有一个或多个正确 选项，多选或少选均不得分）
1.
下列程序中，正确计算
1, 2,
…
, 100
这
100
个自然数之和
sum
（初始值为
0
）的是（ ）。
A. for i := 1 to 100 do sum := sum + i;
B. i := 1; while i > 100 do begin sum := sum + i; inc(i); end;
C. i := 1; repeat sum := sum + i; inc(i); until i > 100;
D. i := 1; repeat sum := sum + i; inc(i); until i <= 100;
AC
入门的都知道
=
。
=
2.
（
）的平均时间复杂度为
O(n log n)
，其中
n
是待排序的元素个数。
A.
快速排序
B.
插入排序
C.
冒泡排序
D.
归并排序
AD
堆排、快排、归并排序都是
O
（
nlogn
）
3.
以
A0
作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标 无关），最后一个遍历到的顶点可能是（ ）。
A. A1 B. A2 C. A3 D. A4
CD
学过的应该都没问题
=w=
4.
（ ）属于
NP
类问题。
A.
存在一个
P
类问题
B.
任何一个
P
类问题
C.
任何一个不属于
P
类的问题
D.
任何一个在（输入规模的）指数时间内能够解决的问题
AB
貌似
NP
问题年年倍受青睐啊
NP
问题是指还未被证明是否存在多项式算法能够解决的问题
首先需要介绍
P(Polynomial,
多项式
)
问题
.
P
问题是可以在多项式时间内被确定机
(
通常意义的计算机
)
解决的问题
.NP(Non-Deterministic Polynomial,
非确定多项式
)
问题
,
是指可以在多项式时间内被非确定机
(
他可以猜
,
他总是能猜到最能满足你需要的那种选择
,
如果你让他解决
n
皇后问题
,
他只要猜
n
次就能完成
—-
每次都是那么幸运
)
解决的问题
5. CCF NOIP
复赛考试结束后，因（ ）提出的申诉将不会被受理。
A.
源程序文件名大小写错误
B.
源程序保存在指定文件夹以外的位置
C.
输出文件的文件名错误
D.
只提交了可执行文件，未提交源程序
ABCD
三
1
、
0 1 1 1
由第五组可知
s1=0;
然后根据第一组得
s2=1;
带入第三组得
s3=1;
最后由第二组带入可知
s4=1;
2
、
37/12
http://www.zybang.com/question/bc7d28939ad71012b5e18ddf591f261d.html
很清楚详细了
四
1、
Yes (
这是一个判断输入字符串是否是回文串的程序
=w=)
2、
133 (
求
1~1000
之间
5
和
10
的倍数，注意去重）
3、
4
（求最长上升子序列长度）
4、
7
（
flood fill
的最大面积
五
【pascal答案】
1、
（
1)n-p+i
(2)i-p+1
(3)a[i-p]
(4)j<=end2
（
5
）
i(
个人感觉
end1+1
也可以）
(6)j-1
（保证两段的连续性）
2、
(1)j-i
（
2
）
cur1
（3）
dec(count1)
（4）
Dec(count2)
（5）
Cur1:=a[j]
——by Eirlys
转载请注明出处=w=