NOIP2008初赛普及组C++题目及答案

1、2第十四届全国青少年信息学奥林匹克联赛初赛试题2008普及组 C+ 语言 二小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效单项选择题 （共 20 题,每题 1.5分，共计 30 分。每题有且仅有一个正确答案 . ）。1微型计算机中，控制器的基本功能是（A. 控制机器各个部件协调工作B.）。实现算术运算和逻辑运算C. 获取外部信息D.存放程序和数据2. 设 A=true ， B=false ，C=true ， D=false以下逻辑运算表达式值为真的是（）。A. (A A B) V (C A DVA)B. (AA B)V C)ADC. （B V CV D）A DA A3. 在

2、下列关于图灵奖的说法中,不正确的是（A. 图灵奖是美国计算机协会于1966年设立的,专门奖励那些对计算机事业作出重要贡献的个人D. AA (DV C)A B）。B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵4计算机在工作过程中,若突然停电, （A. ROM和 RAM B. CPU C.ROM D. RAM5完全二叉树共有 2*N-1 个结点,则它的叶节点数是（）中的信息不会丢失。A. N-1 B. NC. 2*N D. 2）。N-16. 在以下各项中,（ ）不是操作系统软件。A. Solaris B

3、. LinuxC. Windows Vista7设栈 S 的初始状态为空，元素 a， b， c， d，f，e, c，a,则栈S的容量至少应该是（d，D. Sybasee，f依次入栈S,出栈的序列为b，）。A. 6B. 5C. 4D. 38. 与十进制数 28.5625 相等的四进制数是（）。A. 123.21 B. 131.22 C. 130.22 D. 130.219. 设字符串S=” Olympic ”，S的非空子串的数目是（）。A. 28 B. 29 C. 16D. 1710 . Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站 中，（）是典型的 Web2.0应

4、用。通常使用一种称为（）的数A. 队列B.多维数组C.线性表D.10 + (5B) 16的结果是(16 B. (2089)）。12. （2008）A. （833）13.二叉树T,已知其先根遍历是根遍历是 2 4 1 5 7 3 6 ，则该二叉树的后根遍历是（10C. (4163)D. （1） 数字为结点的编号，以下同），中）。A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 114 将数组 8, 23, 4, 16, 77, -5, 53, 100 可以交换任意两个元素，最少需要交换（中的元素按从大到小的顺序排列，）次

5、。每次A. 4B. 5C. 6D. 715 对有序数组 5, 13, 19, 21, 37, 56, 64, 75, 88 功查找元素 19的查找长度（比较次数）是（）。， 92， 100 进行二分查找，成A. 1B. 2C. 3D. 411 递归过程或函数调用时，处理参数和返回地址， 据结构。）。16. 面向对象程序设计（ Object-Oriented Programming ）是一种程序设计的方法论， 它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、 灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（A. 面向对象程序设计通常采用自顶向下设计方法进行

6、设计。B. 面向对象程序设计方法具有继承性（ inheritance ）、封装性（ encapsulation ）、多态性（ polymorphism ）等几大特点。C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有 JAVA、C#等。D. 面向对象的程序设计的雏形来自于C+、Simula 语言，后来在 SmallTalk 和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今， 仍然被视为面向对象语言的基础。语言的完善SmallTalk 语言17. 在 32*32 点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是）。A. 512 B. 256 C. 384 D

7、. 12818. 设 T 是一棵有 n 个顶点的树，下列说法不正确的是（A. T 有 n 条边B. T是连通的B. T）。C. T 是无环的D. T有 n-1 条边19.下列不属于NOIP竞赛推荐使用的语言环境的是（）。A. Dev-C+B. Visual C+C. free p ascalD.Lazarus20 .在C+程序中,表达式200|10的值是（）A. 20 B.1C.220 D. 2022题，每题5分，共计10 分）二问题求解（共1.书架上有4本不同的书 A B、C、Db其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有 种。满足A必须比C

8、靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有种摆法。6个城市两两之间的距离如下2.有6个城市，任何两个城市之间都有一条道路连接,城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920O表所示，则城市1到城市6的最短距离为三阅读程序写结果（共 4题，每题8分，共计32分） 1. #in clude<iostream> using n ames pace std;int mai n()int i, a, b, c, d, f4;for(i = 0; i < 4;

9、 i+) cin >> fi;a = f0 + f1 + f2 + f3;a = a / f0;b = f0 + f2 + f3;b = b / a;c = (b * f1 + a) / f2;d = f(b / c ) % 4;if(f(a + b + c + d) % 4 > f2)cout << a + b<< en dl;elsecout << c + d << endl;return 0;输入： 9 19 29 39输出：2#include<iostream> using namespace std;voi

10、d foo(int a, int b, int c)if(a > b)foo(c, a, b);elsecout<<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 <iostream> using namespace std;void func(int ary,

11、int n )int i=0, j, x;j=n-1;while(i<j)while (i<j&&aryi>0) i+;while (i<j&&aryj<0) j-;if (i<j)x=aryi;aryi+=aryj;aryj-=x;int main()int a20, i, m;m=10;for(i=0; i<m; i+)cin>>ai;func(a, m);for (i=0; i<m; i+)cout<<ai<<" " cout<< endl;

12、return 0;输入： 5 4 -6 -11 6 -59 22 -6 1 10输出：4. #include<iostream>#include<cstring> 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(firstspos

13、_f = midi)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 << firstspos_f;int main()char firstMAX, midMAX;int len;cin >> len;cin >> first >> mid;so

14、lve(first, 0, len - 1, mid , 0, len - 1);cout << endl;return 0;输入： 7ABDCEGFBDAGECF输出：分，后6空，每空3分，共28分）S （S仅包含大小写字母），下面的程序将S中的S经过替换后的结果。程序的输入是两个字符四.完善程序（前4空，每空2.5S,第二个字符串S'由26个字母组成，它是 a-zS'中的第一个字母1.（字符串替换）给定一个字符串 每个字母用规定的字母替换，并输出 串，第一个字符串是给定的字符串的任一排列，大小写不定，S'规定了每个字母对应的替换字母：是字母A和a的替换字

15、母，即 S中的A用该字母的大写替换， S中的a用该字母的小 写替换；S'中的第二个字母是字母 B和b的替换字母，即S中的B用该字母的大写替 换，S中的b用该字母的小写替换；以此类推。#in elude <iostream> #in elude <stri ng.h> char chan ge26, str5000;using n ames pace std;void CheckCha ngeRule()int i;for (i = 0;i < 26;i +)if (cha ngei -= 'A' - 'a'void Chan

16、 geStri ng()int i;for (i = 0;i <strle n( str);i +)if (stri = chan gestri - 'A' -'a' + 'A'elseint mai n()int i;cin >> str ;cin >> cha nge;CheckCha ngeRule();cout << str << en dl;return 0;2.（找第k大的数）给定一个长度为1,000,000的无序正整数序列，以及另一个数n （1<=n<=1000000

17、）,然后以类似快速排序的方法找到序列中第 n大的数（关于第 n大的 数：例如序列1，2，3，4，5，6中第3大的数是4）。#in clude <iostream> using n ames pace std;int a1000001 ,n,ans = -1;void s & a,i nt &b)int c;c = a; a = b;b = c;int Fin dKth(i nt left, i nt right, i nt n)int tmp, value,i,j;if (left = right) retur n left;tmp = ran d()% (righ

18、t - left) + left;swa p(at mp ,aleft);value =i = left;j = right;while (i < j)while (i < j &&)j -；if (i < j) ai = aj; i +; else break;)i +;while (i < j &&if (i < j) aj = ai; j - -; else break;if (i < n) return Fin dKth(）：if (i > n) retur nreturn i;int mai n()int i;int m = 1000000;for (i = 1;i <= m;i +)cin >> ai;cin >> n;ans = Fin dKth(1, m,n); cout << aa ns;return 0;参考答案（6）ABCCB1.2.127选择题DCDAB DABBB ABABD 问题解答4阅读程序1.2.3.4. 四完善程序232.,3,15 4 10 1 6 22 -59 -6 -11 -6DBGEFCA1.（1）（2）（3）（4）2.（1）（2）（3）（4）（5）changei >