NOIP2008初赛普与组C++题目与答案.doc
优质文本第十四届全国青少年信息学奥林匹克联赛初赛试题2016 普及组 语言 二小时完成 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、 单项选择题 共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.。1微型计算机中，控制器的根本功能是 。A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 获取外部信息 D. 存放程序和数据2. 设，以下逻辑运算表达式值为真的是 。A. (AB)(CDA) B. (AB)C)D C. (BCD)DA D. A(DC)B 3. 在以下关于图灵奖的说法中，不正确的选项是 。A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要奉献的个人B. 图灵奖有“计算机界诺贝尔奖之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵4计算机在工作过程中，假设突然停电， 中的信息不会丧失。A. 和 B. D. 5完全二叉树共有2*1个结点，那么它的叶节点数是 。A. 1 B. N C. 2*N D. 216. 在以下各项中， 不是操作系统软件。A. B. C. D. 7设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，那么栈S的容量至少应该是 。A. 6 B. 5 C. 4 D. 38. 与十进制数28.5625相等的四进制数是 。A. 123.21 B. 131.22 C. 130.22 D. 130.219. 设字符串，S的非空子串的数目是 。A. 28 B. 29 C. 16 D. 17102.0是近年来互联网的热门概念之一，其核心思想是互动与分享。以下网站中， 是典型的2.0应用。 A. B. C. D. 11 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为 的数据结构。A. 队列 B. 多维数组 C. 线性表 D. 栈12. (2016)10 + (5B)16的结果是 。A. (833)16 B. (2089)10 C. (4163)8 D. (1)213. 二叉树T，其先根遍历是1 2 4 3 5 7 6数字为结点的编号，以下同，中根遍历是2 4 1 5 7 3 6，那么该二叉树的后根遍历是 。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 114将数组8, 23, 4, 16, 77, -5, 53, 100中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换 次。A. 4 B. 5 C. 6 D. 715 对有序数组5, 13, 19, 21, 37, 56, 64, 75, 88，92，100进行二分查找，成功查找元素19的查找长度比较次数是 。A. 1 B. 2 C. 3 D. 416. 面向对象程序设计 是一种程序设计的方法论，它将对象作为程序的根本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的选项是 。A. 面向对象程序设计通常采用自顶向下设计方法进行设计。B. 面向对象程序设计方法具有继承性、封装性、多态性等几大特点。C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有、等。D. 面向对象的程序设计的雏形来自于语言，后来在语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，语言仍然被视为面向对象语言的根底。17. 在32*32点阵的“字库中，汉字“北与“京的字模占用字节数之和是 。 A. 512 B. 256 C. 384 D. 12818. 设T是一棵有n个顶点的树，以下说法不正确的选项是 。A. T有n条边 B. T是连通的C. T是无环的 D. T有1条边19. 以下不属于竞赛推荐使用的语言环境的是 。A. B. C. D. 20在程序中，表达式200|10的值是 A. 20 B. 1 C. 220 D. 202 二问题求解共2题，每题5分，共计10分1. 书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有种。满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有种摆法。2有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，那么城市1到城市6的最短距离为。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920三阅读程序写结果共4题，每题8分，共计32分1. <> ; () i, a, b, c, d, f4;(i = 0; i < 4; ) >> 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;(f(a + b + c + d) % 4 > f2) << a + b<< ; << c + d << ; 0;输入：9 19 29 39 输出：2<> ; ( a, b, c)(a > b) (c, a, b);<<a<<','<<b<<','<<c<< () a, b, c; >> a >> b >> c;(a, b, c); 0;输入: 3 1 2输出: 3 <> ; ( , n ) 0, j, x;1;(i<j) (i<i>0) ; (i<j<0) ; (i<j)i;j; () a20, i, m;10;(0; i<m; )>>ai;(a, m); (0; i<m; )<<ai<<" "<< ; 0;输入：5 4 -6 -11 6 -59 22 -6 1 10输出：4. <><> ; 100 ( , , , , , ) i, ;( > );(i = ; i <= ; )( i) = i;(, + 1, + ( - ), , , - 1);(, + ( - ) + 1, , , + 1, ); << ; () , ; ; >> ; >> >> ;(, 0, - 1, , 0, - 1); << ; 0;输入：7输出：四完善程序 (前4空，每空2.5分，后6空，每空3分，共28分)1字符串替换给定一个字符串SS仅包含大小写字母，下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S由26个字母组成，它是的任一排列，大小写不定，S规定了每个字母对应的替换字母：S中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换； 以此类推。 <> <> 26, 5000; ; () i; (i = 0 < 26 ) ( ) i 'A' - 'a' () i; (i = 0 <() ) ( ) i = i - 'A' -'a' + 'A' () i; >> ; >> ; (); << << ; 0;2. (找第k大的数) 给定一个长度为1,000,000的无序正整数序列, 以及另一个数n (1<<=1000000), 然后以类似快速排序的方法找到序列中第n大的数关于第n大的数：例如序列1，2，3，4，5，6中第3大的数是4。 <> ; a1000001 = -1; ( ) c;c = a; a = b;b = c; ( , , n) ; ( ) ; = ()% ( - ) + ;(a); = i = ;j = ; (i < j) (i < j ) j ; (i < j) ai = aj; i ; ; (i < j ) i ; (i < j) aj = ai; j - -; ; (i < n) ( ); (i > n) i; () i; m = 1000000; (i = 1 <= ) >> ai; >> n; = (1); << a; 0;参考答案一 选择题 二 问题解答1. 12 42. 7三 阅读程序1. 232. 2.,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. 四完善程序1.1i >= 'A' i <= 'Z'(只写i <= 'Z'也对) 2i >= 'A' i <= 'Z'只写i <= 'Z'也对3i = i - 'a'4();2.1a;2aj < 3ai > 4ai = 5i + 16(, i 1, n);
