第十一届全国青少年信息学奥林匹克联赛初赛试题

第十一届全国青少年信息学奥林匹克联赛初赛试题

（ 提高组 C 语言 二小时完成）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。

1. 字符串“ababacbab”和字符串“abcba”的最长公共子串是（B ）。

A. abcba . Bcba C. abc D. ab E. bcba

2. 设全集I = {a, b, c, d, e, f, g, h}，集合 = {a, b, c, d, e, f}， = {c, d, e}， = {a, d}，那么集合 为（ A）。

A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}

3. 以下二进制数的值与十进制数23.456的值最接近的是（D ）。

A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111

4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ E）。

A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2

将这五个坐标为A(5, 3)、B(3, 5)、C(2, 1)、D(3, 3)以及E(5, 1)的点设为完全图G的所有顶点。任意两点间的欧几里得距离即为该完全图相应边上的权重。计算该完全图最小生成树各边权重之和所得结果为选项D

A. 8 B. 7+ C. 9 D. 6+ E. 4+2 +

6. 下列设备中没有计算功能的是（ E。

A. 笔记本电脑 B. 掌上电脑 C. 智能手机

D. 电子计算器 E. 液晶显示器

7. Intel的首颗64位处理器是（E ）。

A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium

8. 常见的邮件传输服务器使用（B ）协议发送邮件。

A. HTTP B. SMTP C. TCP D. FTP E. POP3

9. 不能在Linux上使用的网页浏览器是（A ）。

A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla

一位艺术史学家拥有20,000张尺寸为1024 × 768的真彩色图片，并将其以位图格式存储于单张CD光盘上（假设每张CD容量为600MB），大约需要多少张CD光盘？

A. 1 B. 10 C. 100 D. 1000 E. 10000

二、 不定项选择题 （共10题，每题1.5分，共计15分。多选或少选均不得分）。

11. 设A = true，B = false，C = false，D = true，以下逻辑运算表达式值为真的有（CDE ）。

A. (A∧B)∨(C∧D) B. ((A∧B)∨C)∧D C. A∧((B∨C)∨D)

D. (A∧(B∨C))∨D E. (A∨B)∧(C∨D)

12. (3725)8 + (B)16的运算结果是（BCE ）。

A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16

1. 二叉树T进行广度优先搜索得到序列A B C D E F G H I。已知A为C的父亲节点；D为其子节点G的父亲；F为其子节点I的父亲。该树的高度不超过3层（根节点位于第0层）。则E父亲 node 可能是B和C

A. A B. B C. C D. D E. F

14. 设栈S最初为空，则元素a至g依次推入栈S中，在这种情况下不可能出现的出站顺序是选项CE.

A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g

D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a

15. 下列外设接口中可以通过无线连接的方式连接设备的是（BCE ）。

A. USB 2.0 高速版 B. 红外 C. 蓝牙 D. 串口 E. IEEE 802.11g 无线网卡

16. 处理器A每秒处理指令的速度是处理器B的两倍。同一特定程序P分别经编译生成了.processor A和.processor B的操作指令序列；经编译后,生成的操作指令数量显示为:在生成后的情况中,由_processor A生成的操作指令数量与由_processor B生成的数量之比达到了4:1的比例。已知软件.P program P的时间复杂度函数表示为O(n²),当用_processor A运行该软件.P时可以在一个小时内处理的最大输入规模等于n个数据项,那么采用_processor B运行该软件.P时,在一小时计算时间内可处理的最大输入规模是多少?(D)

A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4

17. 以下哪个（些）不是计算机的输出设备（ACD ）。

A. 鼠标 B. 显示器 C. 键盘 D. 扫描仪 E. 绘图仪

18. 以下断电之后将不能保存数据的有（BCDE ）。

A. 硬盘 B. 寄存器 C. 显存 D. 内存 E. 高速缓存

19. 下列活动中属于信息学奥赛系列活动的是（ABCDE ）。

A. NOIP B. NOI C. IOI D. 冬令营 E. 国家队选拔赛

20. 下列关于高级语言的说法正确的有（BDE ）。

A. Ada是历史上的第一个高级语言

B. Pascal和C都是编译执行的高级语言

C. C++是历史上的第一个支持面向对象的语言

D. 编译器将高级语言程序转变为目标代码

E. 高级别语言程序比底层语言程序更加容易从一种计算机移植到另一种计算机上

三．问题求解（请在空格处填上答案，每空5分，共计10分）

将该数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按照从小到大的顺序重新排列，并允许每次交换任何两个元素的位置，则最少需要进行5次这样的交换操作才能完成排序任务

2. 游戏规则如下所述：一共有N根火柴棒呈放于桌面上。两名玩家轮流进行操作，在每一轮中每位玩家必须从桌面上选取至少一根且至多两根火柴棒。无法继续选取的一方被判定失败而另一方获胜。若存在一种策略使得先手玩家能够确保胜利，则在结果记录中对应位置标记₁；反之，则标记₀。（结果序列当N分别等于 ¹⁰⁰、²⁰⁰、³⁰⁰、⁴⁰⁰与5^{\circ}₀时依次对应 ¹¹₀₁₁ 的二进制表示）

四．阅读程序（共4题，每题8分，共计32分）

1． #include <stdio.h>

int main() {

int a, b, c, p, q, r[3];

scanf(“%d%d%d”, &a, &b, &c);

p = a / b / c;

q = b – c + a + p;

r[0] = a * p / q * q;

r[1] = r[0] * (r[0] – 300);

if (3 * q – p % 3 <= r[0] && r[2] == r[2])

r[1] = r[r[0] / p % 2];

else

r[1] = q % p;

printf(“%d\n”, r[0] – r[1]);

return 0;

}

输入：100 7 3

输出： -7452

2． #include <stdio.h>

#include <math.h>

int a[50];

void work(int p, int r) {

if (p < r) {

int i = p - 1, j, temp;

for (j = p; j < r; j++) {

if (a[j] >= a[r]) {

i++;

temp = a[i]; a[i] = a[j]; a[j] = temp;

}

}

temp = a[i + 1]; a[i + 1] = a[r]; a[r] = temp;

work(p, i);

work(i + 2, r);

}

}

int main() {

int n, i, sum = 0;

scanf("%d", &n);

for (i = 0; i < n; i++) scanf("%d", &(a[i]));

work(0, n - 1);

for (i = 0; i < n - 1; i++) sum += abs(a[i + 1] - a[i]);

printf("%d\n", sum);

return 0;

}

输入：10 23 435 12 345 3123 43 456 12 32 -100

输出： 3223

3． #include<stdio.h>

#include<string.h>

int main(){

char str[60];

int len, i, j, chr[26];

char mmin = 'z';

scanf("%s", str);

len = strlen(str);

for (i = len - 1; i >= 1; i--)

if (str[i - 1] < str[i]) break;

if (i == 0) {

printf("No result!\n");

return 0;

}

for (j = 0; j < i - 1; j++) putchar(str[j]);

memset(chr, 0, sizeof(chr));

for (j = i; j < len; j++) {

if (str[j] > str[i - 1] && str[j] < mmin)

mmin = str[j];

chr[str[j] - 'a']++;

}

chr[mmin - 'a']--;

chr[str[i - 1] - 'a']++;

putchar(mmin);

for(i = 0; i < 26; i++)

for(j = 0; j < chr[i]; j++)

putchar(i + 'a');

putchar('\n');

return 0;

}

输入：zzyzcccbbbaaa

输出： zzzaaabbbcccy

4. #include <stdio.h>

long g(long k) {

if (k <= 1) return k;

return (2002 * g(k - 1) + 2003 * g(k - 2)) % 2005;

}

int main() {

long n;

scanf("%ld", &n);

printf("%ld\n", g(n));

return 0;

}

输入：2005

输出： 31

五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)

1．木材加工

题目描述:

木材厂拥有一批原木，在进行加工时现计划将这些木材分割成若干等长的小段，在切割过程中可能会存在未被利用的木材，在所需小段的数量已经确定下来的情况下，请确定在满足条件情况下追求尽可能长的小段，并找出能够实现的最大长度

木材长度采用厘米作为计量单位。原木的长度均为正整数，在进行切割时要求得到的小段木材长度也必须为正整数。

输入:

第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。

接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。

输出:

该系统将可分割所得的部分的最大尺寸作为输出结果。若无法分割出至少1厘米长的部分，则返回值为0。

输入样例:

3 7

232

124

456

输出样例:

114

程序：

#include <stdio.h>

int n, k, len[10000];

int isok(int t) {

int num = 0, i;

for (i = 0; i < n; i++) {

if (num >= k) break;

num = ①num+len[i]/t ;

}

if ( ②num>=k ) return 1;

else return 0;

}

int main() {

int i, left, right, mid;

scanf("%d%d", &n, &k);

right = 0;

for (i = 0; i < n; i++) {

scanf("%d", &(len[i]));

if (right < len[i]) right = len[i];

}

right++;

③left=0 ;

while ( ④left+1 < right) {

mid = (left + right) / 2;

if ( ⑤!isol(mid) (或者isol(mid)==0) ) right = mid;

else left = mid;

}

printf ("%d\n", left);

return 0;

}

2．N叉树

题目描述:

我们对二叉树的先根遍历、中根遍历以及后根遍历非常熟悉。掌握了先根序列和中根序列之后，我们能够唯一确定一棵二叉树；类似地，在已知后序序列和中序序列的情况下，二叉树同样能够被唯一确定。然而仅凭先序序列和后序序列，并不能唯一确定一棵二叉树；但是我们可以统计满足特定条件的不同情况来得出结论。这个问题不算太复杂，并不涉及编程或算法细节；随后我们将这一问题扩展到N-ary树的情形。

我们采用小写字母来标记N叉树的各个节点，并规定每个节点必须使用独特的字母进行区分。例如，在4叉树的情形下，若先序遍历所得序列为abdefgc，则后序遍历的结果为defgbca；基于此关系式我们可以推导出共有六种可能的4叉树结构（如图所示）。

输入:

输入数据包括3行。

第一行是一个正整数N(1 ≤ N ≤ 20)，表示我们要考虑N叉树。

下一行和再下一行分别表示两组字符串序列的结果：其中一组为先序遍历的结果集；另一组为后序遍历的结果集

输出:

输出不同的N叉树的数目。题目中给的数据保证得到的结果小于231。

输入样例:

4

abdefgc

defgbca

输出样例:

6

程序：

#include <stdio.h>

#include <string.h>

char str1[100], str2[100];

int N;

long com[100][100];

long getcom(int x, int y) {

if (y == 0 || x == y) ①return 1 (或者 return 1L,或者 return 1l) ;

else if (com[x][y] != 0) return com[x][y];

else {

com[x][y] = getcom(x - 1, y)+ ②getcom(x-1,y-1) ;

return com[x][y];

}

}

long count(int a, int b, int c){

long sum = 1;

int k = 0;

int s = a + 1, t = c, p;

if (a == b) return 1;

while(s <= b){

p = t;

while(str1[s] != str2[t]) t++;

sum = sum * count(s, s + t - p, p);

s = ③s+t-p+1 ;

④t++ (或者++t/t=t+1/t+=1) ;

k++;

}

return ⑤ sum * getcom(N, k);

}

int main(){

int len;

scanf("%d", &N);

scanf("%s%s", str1, str2);

len = strlen(str1);

printf("%ld\n", count( ⑥0,len-1,0 ));

return 0;

}

赛区 市 学校 姓名

========================== 密 封 线 ==========================

第十一届全国青少年信息学奥林匹克联赛初赛试题

提高组答卷纸

阅 卷 记 录
总阅卷人 总 得 分
第 一 大 题	得 分	第三大题得分
题号	1	2	3	4	5	6	7	8	9	10	第四大题得分
得分	1)	2)	3)	4)
第 二 大 题	得 分	第五大题得分
题号	11	12	13	14	15	16	17	18	19	20	(1)	(2)
得分

============================ 以下由考生填写 ============================

答卷部分

一. 单项选择题 （共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。

题号	1	2	３	4	5	6	7	8	9	10
选择

二．不定项选择题 （共10题，每题1.5分，共计15分。多选或少选均不得分）。

题号	11	12	13	14	15	16	17	18	19	20
选择

三．问题解答 （每题5分，共10分）

1. 答：

2. 答：

四. 阅读程序，并写出程序的正确运行结果：（每题8分，共32分）

(1) 程序的运行结果是:

(2) 程序的运行结果是:

赛区 市 学校 姓名

========================== 密 封 线 ==========================

(3) 程序的运行结果是:

(4) 程序的运行结果是:

五. 完善程序 (前5空，每空2分，后6空，每空3分，共28分)

C 语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

（1） ________________________________

（2） ________________________________

（3） ________________________________

（4） ________________________________

（5） ________________________________

（1） ________________________________

（2） ________________________________

（3） ________________________________

（4）________________________________

（5）________________________________

（6） ________________________________