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

总结
一、单项选择题
控制器的基本功能是协调机器各个部件的工作。
逻辑运算表达式的值为真。
图灵奖无华裔科学家获奖。
ROM中信息不丢失。
叶节点数为N-1。
Sybase不是操作系统软件。
栈容量至少为5。
四进制数为130.21。
非空子串数目为29。
Flickr是典型的Web2.0应用。
二、问题求解
输入：
4本不同的书A,B,C,D；红皮A,B；黑皮C,D； 所有黑皮书排在一起且红皮书排在一起； A比C靠左； 摆法数目： 满足条件的摆法数目为48种（红皮内部排列方式×黑皮内部排列方式×红黑整体排列方式）； 具体计算如下：
输入:
9 19 29 39
输出:
`
276
输入:3 1 2
输出:3,1,2
输入:5 -6 -11 -59 -6 -59 -6 -59
输出:-6,-59,-6,-59,-6,-59
输入:ABDCEGF BDAGECF
输出:B

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

1．微型计算机中， 控制器的基本功能是（ ）。

A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算

C. 获取外部信息 D. 存放程序和数据

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

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

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

3. 在下列关于图灵奖的说法中， 不正确的是（ ）。

A. 图灵奖是由美国计算机协会于1967年创立的,旨在奖励那些在计算机领域有显著贡献的专业人士.

B. 图灵奖有“计算机界诺贝尔奖”之称

C. 迄今为止， 还没有华裔计算机科学家获此殊荣

D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵

4．计算机在工作过程中， 若突然停电，（ ）中的信息不会丢失。

A. ROM和 RAM B. CPU C.ROM D. RAM

5．完全二叉树共有 2*N-1个结点， 则它的叶节点数是（ ）。

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

6. 在以下各项中，（ ）不是操作系统软件。

A. Solaris B. Linux C. Windows Vista D. Sybase

设空栈 S 按 a→b→c→d→e→f 的顺序依次将它们压入，则按 b→d→f→e→c→a 的顺序弹出时其最小容量为（ ）。

A. 6 B. 5 C. 4 D. 3

8. 与十进制数 28.5625相等的四进制数是（ ）。

A. 123.21 B. 131.22 C. 130.22 D. 130.21

9. 设字符串S=”Olympic”，S的非空子串的数目是（ ）。

A. 28 B. 29 C. 16 D. 17

Web2.0 已成为近十年来互联网发展的重要概念之一，在其基本理念中体现了互动交流与资源共享的特点。下列网站中，（ ）是典型

的 Web2.0 应用。

A. Sina B. Flickr C. Yahoo D. Google

在递归过程中或函数调用时，管理参数和返回地址通常会采用（栈）的数据结构。

A. 队列 B. 多维数组 C. 线性表 D. 栈

12. (2008)10 + (5B)16 的结果是（ ）。

A. (833)16 B. (2089)10 C. (4163)8 D. (100001100011)2

已知二叉树T的前序、中序序列分别为1\quad2\quad4\quad3\quad5\quad7\quad6（其中节点编号即为下标），现求其后序序列是什么？

A. 4 2 5 7 6 3 1

C. 7 4 2 5 6 3 1

B. 4 2 7 5 6 3 1

D. 4 2 7 6 5 3 1

对数组{8,23,4,16,77,-5,53,100}进行排序，请计算至少需要多少次交换才能使元素按从大到小排列。

A. 4 B. 5 C. 6 D. 7

15． 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}进行二分查找， 成功查找 元素 19 的查找长度（比较次数） 是（ ）。

A. 1 B. 2 C. 3 D. 4

16. 面向对象程序设计（Object-Oriented Programming）被视为一种程序设计的方法论。该方法将对象视为程序的基本单元，并将其数据和行为封装到对象中，从而增强了软件的重用性、灵活性和可扩展性。以下关于面向对象程序设计的说法中不正确的是（ ）。

A. 面向对象程序设计通常采用自顶向下设计方法进行设计。

B. 面向对象程序设计方法包含继承特性(inheritance)、封装特性(encapsulation)、多模态特性(polynomial)等关键点。

支持具有面向对象特性的语言被称为面向对象编程语言。目前广泛使用的编程语言包括C++、C#和JAVA等。

D. 面向对象程序设计领域的起源可追溯至Simula语言。该领域随后经历了逐步完善的SmallTalk语言阶段。

在程序运行过程中获得了更为丰富的拓展，并对先前概念进行了更为深入的重构与诠释。到目前为止, SmallTalk语言仍被普遍认为是面向对象语言的基本框架。

17. 在 32*32 点阵的“字库”中， 汉字“北”与“京”的字模占用字节数之和是（ ）。

A. 512 B. 256 C. 384 D. 128

18. 设 T 是一棵有 n 个顶点的树， 下列说法不正确的是（ ）。

A. T有 n 条边 B. T 是连通的

C. T 是无环的 D. T有 n-1 条边

19. 下列不属于NOIP竞赛推荐使用的语言环境的是（ ）。

A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus

20．在 C++程序中， 表达式 200|10 的值是（ ）

A. 20 B. 1 C. 220 D. 202

二． 问题求解（共 2 题， 每题 5 分，共计 10 分）

在书架上放置了四本不同的书籍,分别标记为A,B,C和D. 其中,A号和B号书籍为红色封面,《C》与《D》则为黑色封面. 将其摆放在书桌上.

架上符合要求的所有黑皮书籍排列在一起的方式共有多少种？其中A必须位于C左侧，并且所有红皮书籍应放置在指定区域中。

一起， 所有黑皮的书要摆放在一起， 共有 种摆法。

共有6个城市,任意两个城市之间都有一条道路相连,各城市间的距离数据列于下表中,请根据上述数据计算各城市的某些属性或证明某个定理.

市 1 到城市 6 的最短距离为 。

城市 1	城市 2	城市 3	城市 4	城市 5	城市 6
城市 1	0	2	3	1	12	15
城市 2	2	0	2	5	3	12
城市 3	3	2	0	3	6	5
城市 4	1	5	3	0	7	9
城市 5	12	3	6	7	0	2
城市 6	15	12	5	9	2	0

三． 阅读程序写结果（共 4 题，每题 8 分， 共计 32 分）

1. #include

using namespace std;

int main()

{

int i, a, b, c, d, f[4];

for(i = 0; i < 4; i++) cin >> f[i];

a = f[0] + f[1] + f[2] + f[3];

a = a / f[0];

b = f[0] + f[2] + f[3];

b = b / a;

c = (b * f[1] + a) / f[2];

d = f[(b / c ) % 4];

if(f[(a + b + c + d) % 4] > f[2])

cout << a + b<< endl;

else

cout << c + d << endl;

return 0;

}

输入： 9 19 29 39

输出：

2．#include using namespace std;

void foo(int a, int b, int c)

{

if(a > b)

foo(c, a, b);

else

cout<<a<<','<<b<<','<<c<<endl;

}

int main()

{

int a, b, c;

cin >> a >> b >> c;

foo(a, b, c);

return 0;

}

输入: 3 1 2

输出: __________

3．#include

using namespace std;

void func(int ary[], int n )

{

int i=0, j, x;

j=n-1;

while(i<j)

{

while (i<j&&ary[i]>0) i++;

while (i<j&&ary[j]<0) j--;

if (i<j){

x=ary[i];

ary[i++]=ary[j];

ary[j--]=x;

}

}

}

int main()

{

int a[20], i, m;

m=10;

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

{

cin>>a[i];

}

func(a, m);

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

cout<<a[i]<<" ";

cout<< endl;

return 0;

}

输入： 5 4 -6 -11 6 -59 22 -6 1 10

输出： ____________________________________

4. #include #include

using namespace std;

#define MAX 100

void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int

epos_m)

{

int i, root_m;

if(spos_f > epos_f)

return;

for(i = spos_m; i <= epos_m; i++)

if(first[spos_f] == mid[i])

{

root_m = i;

break;

}

solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);

solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);

cout << first[spos_f];

}

int main()

{

char first[MAX], mid[MAX];

int len;

cin >> len;

cin >> first >> mid;

solve(first, 0, len - 1, mid , 0, len - 1);

cout << endl;

return 0;

}

输入： 7

ABDCEGF

BDAGECF

输出： ____________________________________

四． 完善程序 ( 前 4 空， 每空 2.5 分，后 6 空， 每空 3 分，共 28 分****)****

给定一个仅由大小写字母组成的字符串S，请问您希望将其转换为什么样的形式？本程序会将输入字符串S中的每一个字符按预先设定规则进行转换，并输出转换后的结果。该程序接受两个参数：第一个参数是待转换字符集合中的原始数据串S；第二个参数是一个包含所有26个英文字母的一个排列组合（不考虑大小写的区分），其中第一个字符对应于大写字母A及其小写字母a的映射关系；其余字符则依次对应于后续各个位置上的字符映射关系；第三个参数是一个可选设置项，默认情况下执行全部映射操作；如果设置为"False"则只对大写字母进行映射操作而不处理小写字母

此小写字母被采用作替代符号。在S'中所取之第二个字符位置上，则是由大写字母B及其对应的小写字母b共同决定的。具体而言，在S中所存在的大写字母B将被替换成本符号的大写字母形式（即Γ），而S中小写的b则将被替换成本符号的小写字母形式（即γ）。其余字符亦依照此类方式处理。

#include

#include <string.h>

char change[26], str[5000];

using namespace std;

void CheckChangeRule()

{

int i;

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

{

if (__① __)

change[i] -= 'A' - 'a';

}

}

void ChangeString()

{

int i;

for (i = 0;i <strlen(str);i ++)

{

if (__② __)

str[i] = change[str[i] - 'A'] -'a' + 'A';

else

③

}

}

int main()

{

int i;

cin >> str ;

cin >> change;

CheckChangeRule();

④ __

cout << str << endl;

return 0;

}

(寻找序列中的第k个最大值) 给定一个包含一百万个无序正整数的序列，并指定另一个整数值n（满足条件：1 ≤ n ≤ 且该算法在处理规模为一百万的数据时表现优异），然后通过类似于快速排序算法的方式确定该序列的第n个最大元素。其中关于如何确定第k个最大元素的问题可以通过以下方法解决：例如，在上述示例中（如序列{1,2,3,4,5}），第三个最大的数字是3；而在更大规模的数据集中也可以应用同样的逻辑来找到所需的最大值或最小值的位置。

#include

using namespace std;

int a[1000001],n,ans = -1;

void swap(int &a,int &b)

{

int c;

c = a; a = b; b = c;

}

int FindKth(int left, int right, int n)

{

int tmp,value,i,j;

if (left == right) return left;

tmp = rand()% (right - left) + left;

swap(a[tmp],a[left]);

value =__① __

i = left; j = right; while (i < j) {

while (i < if (i < j) while (i < if (i < j)

}

j &&__② __) j --;

{a[i] = a[j]; i ++;} else break;

j &&__③ __) i ++;

{a[j] = a[i]; j - -;} else break;

④ __

if (i < n) return FindKth(__⑤ __);

if (i > n) return __⑥ __

return i;

}

int main()

{

int i;

int m = 1000000;

for (i = 1;i <= m;i ++)

cin >> a[i];

cin >> n;

ans = FindKth(1,m,n);

cout << a[ans];

return 0;

}