一、单选题
1、一个32 位整型变量占用（ ）个字节。
A 4
B 8
C 32
D 128
2、二进制数11.01在十进制下是（ ）。
A 3.25
B 4.125
C 6.25
D 11.125
3、下面的故事与（ ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’?
A、
枚举
B、 递归
C、
贪心
D、
分治
4、1948年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A 冯·诺伊曼（John von Neumann）
B 图灵（Alan Turing）
C 欧拉（Leonhard Euler）
D 克劳德·香农（Claude Shannon）
5、已知一棵二叉树有2013个节点，则其中至多有（ ）个节点有2个子节点。
A 1006
B 1007
C 1023
D 1024
6、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。
A、
2
B、 3
C、
4
D、
5
7、斐波那契数列的定义如下：F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐波那契数列的第 n 项，则其时间复杂度为（ ）。
int F(int n)
{
if(n<=2)
return 1;
else
return F(n-1)+F(n-2);
}
A O(1)
B O(n)
C O(n2)
D O(Fn)
8、二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（ ）是一个有序序列。
A 先序遍历
B 中序遍历
C 后序遍历
D 宽度优先遍历
9、将（2,6,10,17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数 h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。
A、 x mod 11
B、
x2mod 11
C、
2x mod 11
D 
10、IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ ）位地址的 IPv6 协议所取代。
A 40
B 48
C 64
D 128
11、二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（ ）条边。
A 18
B 24
C 36
D 66
12、（ ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
A ASCII
B Unicode
C GBK 2312
D BIG5
13、把64位非零浮点数强制转换成32位浮点数后，不可能（ ）。
A 大于原数
B 小于原数
C 等于原数
D 与原数符号相反
14、对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
A O(mn+n3)
B O(n2)
C O((m+n)log n)
D O((m+n2)log n)
15、T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数，且有递归式T(n)=2*T(n/2)+2n，那么 T(n)=（ ）。
A Θ(n)
B Θ(n log n)
C Θ(n2)
D Θ(n2log n)
二、多选题
16、下列程序中，正确计算1,2,…,100 这100个自然数之和sum（初始值为 0）的是（ ）。
A for(i=1;i<=100;i++)
sum+=i;
B、
i=1;
while(i>100){
sum+=i;
i++;
}
C、 i=1; do{ sum+=i; i++; }while(i<=100);
D、
i=1;
do{
sum+=i;
i++;
}while(i>100);
17、（ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。
A 快速排序
B 插入排序
C 冒泡排序
D 归并排序
18、以 A0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ ）。
A A1
B A2
C A3
D A4
19、（ ）属于 NP 类问题。
A 存在一个 P 类问题
B 任何一个 P 类问题
C 任何一个不属于 P 类的问题
D 任何一个在（输入规模的）指数时间内能够解决的问题
20、CCF NOIP 复赛考试结束后，因（ ）提出的申诉将不会被受理。
A 源程序文件名大小写错误
B 源程序保存在指定文件夹以外的位置
C 输出文件的文件名错误
D 只提交了可执行文件，未提交源程序
三、简答题
21、某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn，均为0或1。该系统每次随机生成 n 个数 a1,a2,…,an，均为 0 或 1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。例如，当 n=4 时，有人窃听了以下 5 次问答：
就破解出了密码 s1=_________，s2=_________，s3=_________，s4=_________。
参考答案：s1=0，s2=1，s3=0，s4=1
22、现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率随机跳到1,2,…,k 号荷叶之一上，直至跳到1号荷叶为止。当n=2 时，平均一共跳2次；当 n=3 时，平均一共跳 2.5 次。则当 n=5 时，平均一共跳_________次。
参考答案：当 n=5 时，平均一共跳 3 次。
23、
#include<iostream>
#include<string >
using namespace std;
int main( )
{ string
Str;
cin>>str;
int n = str.size( );
bool isPlalindrome = true;
for (int i =0; i<n/2;i++){
if (str[i] !=str[n-i-1]) isPlalindrome = false;
}
if(isPlalindrome)
cout << ”Yes” << endl;
else cout << ”No” << endl;
}
输入：abceecba
输出：_________
参考答案：Yes
24、
#include<iostream>
using namespace std;
int main( )
{
int a,b,u,v,i, num;
cin >>a>>b>>u>>v;
num =0;
for ( i= a; I <=b; i++)
if (((i%u) ==0)||((i%v)==0))
num ++;
count <<num<<endl;
return 0;
}
输入：1 1000 10 15
输出：_________
参考答案：输出为 68
25、
#include<iostream>
using namespace std;
int main( )
{
const int SIZE = 100;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for (int i=0; i<n; i++) {
cin >>height[i];
num[i]= 1;
for (int j=0; j<i; j++) {
if ((height[j]<height[i])&&(num[j]>= num[i]))
num[i] =num[j]+1;
}
}
ans =0;
for(int I = 1; i<n; i++){
if(num[i] >ans) ans =num[j];
}
Cout <<ans<<endl;
}
输入：
8
3 2 5 11 12 7 4 10
6
输出：_________
参考答案：输出：4
26、
#include<iostream>
#include<string >
using namespace std;
const int SIZE = 100;
int n, m, p, a[SIZE] [SIZE], count;
void colour (int x, int y)
{
Count++;
a[x][y] = 1;
if ((x > 1)&& (a[x-1][y] == 0))
colour( x - 1, y);
if ((y> 1)&& (a[x][y-1] == 0))
colour( x, y- 1);
if ((x < n)&& (a[x+1][y] == 0))
colour( x +1, y);
if ((y < m)&& (a[x][y+1] == 0))
colour( x, y+1);
}
int main( )
{
int i, j, x, y, ans;
memset(a, 0, sizeof(a));
cin >>n>>m>>p;
for(i =1 ; I <=p; i++) {
cin>>x>>y;
a[x][y] = 1;
}
ans = 0;
for (i =1; i <=n; i++)
for (j =1; j <=m;j++)
if (a[i][j] == 0)
{count = 0;
colour (i , j);
if (ans <count)
ans <count;
}
count<<ans<<endl;
return 0;
}
输入：
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
输出：_________
参考答案：输出为"3"
四、实操题
27、（序列重排）全局数组变量 a 定义如下：
Const int SIZE = 100;
int a[SIZE],n;
它记录着一个长度为 n 的序列a[1],a[2],…,a[n]。
现在需要一个函数，以整数 p(1≤p≤n)为参数，实现如下功能：将序列 a 的前 p 个数与后 n–p 个数对调，且不改变这 p 个数（或 n–p 个数）之间的相对位置。例如，长度为 5 的序列 1,2,3,4,5，当 p=2 时重排结果为 3,4,5,1,2。
有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n)、空间复杂度为 O(n)：
void swap1(int p)
{
int i, j, b[SIZE];
for (i = 1; i <= p; i++)
b[ ( 1) ] = a[i]; //（2 分）
for (i = p + 1; i <= n; i++)
b[i - p] = a[i];
for (i = 1; i <= n; i++)
a[i] = b[i];
}
我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法：
void swap2(int p)
{
int i, j, temp;
for (i = p + 1; i <= n; i++) {
temp = a[i];
for (j = i; j >= (2) ; j--) //（2 分）
a[j] = a[j - 1];
(3) = temp; //（2 分）
}
}
事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：
void swap3(int p)
{
int start1, end1, start2, end2, i, j, temp;
start1 = 1;
end1 = p;
start2 = p + 1;
end2 = n;
while (true) {
i = start1;
j = start2;
while ((i <= end1) && (j <= end2)) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
if (i <= end1)
start1 = i;
else if ( (4) ) { //（3 分）
start1 = (5) //（3 分）
endl = (6) //（3 分）
start2 = j;
}
else
break;
}
}
参考答案：1. (1)处应填入：i2. (2)处应填入：p+13. (3)处应填入：a[j - 1]4. (4)处应填入：j > end25. (5)处应填入：i6. (6)处应填入：endl = n;
28、（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长，输出任意一个即可。例如，序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, i, j, a[SIZE], cur1, cur2, count1, count2,
ans_length, ans_start, ans_end;
//cur1, cur2 分别表示当前子序列中的两个不同整数
//count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i];
i = 1;
j = 1;
//i, j 分别表示当前子序列的首尾，并保证其中至多有两个不同整数
while ((j <= n) && (a[j] == a[i]))
j++;
cur1 = a[i];
cur2 = a[j];
count1 = (1) //（3 分）
count2 = 1;
ans_length = j - i + 1;
while (j < n) {
j++;
if (a[j] == cur1)
count1++;
else if (a[j] == cur2)
count2++;
else {
if (a[j - 1] == (2) ) { //（3 分）
while (count2 > 0) {
if (a[i] == cur1)
count1--;
else
ount2--;
i++;
}
cur2 = a[j];
count2 = 1;
}
else {
while (count1 > 0) {
if (a[i] == cur1)
(3) //（2 分）
else
(4) //（2 分）
i++;
}
(5) //（3 分）
count1 = 1;
}
}
if (ans_length < j - i + 1) {
ans_length = j - i + 1;
ans_start = i;
ans_end = j;
}
}
for (i = ans_start; i <= ans_end; i++)
cout<<a[i]<<' ';
return 0;
}
参考答案：1. 在代码中的位置（1）处，`count1`应该初始化为0，表示`cur1`在当前子序列中出现的次数。2. 在代码中的位置（2）处，应判断`a[j-1]`是否等于`cur2`，因为当前位置`j`的元素与`cur1`和`cur2`都不同，所以需要判断前一个元素是否等于`cur2`。3. 在代码中的位置（3）处，如果`a[i]`等于`cur1`，则`count1`减1，否则`count2`减1，表示将`cur1`或`cur2`从子序列中移除。4. 在代码中的位置（4）处，如果`a[i]`等于`cur1`，则`count1`减1，否则`count2`减1，表示将`cur1`或`cur2`从子序列中移除。5. 在代码中的位置（5）处，将`cur1`更新为`a[j]`，并将`count1`重置为1，表示将`a[j]`作为新的`cur1`，并重新开始计数。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
