NOIP2008初赛普及组C题目及答案.docx

《NOIP2008初赛普及组C题目及答案.docx》由会员分享，可在线阅读，更多相关《NOIP2008初赛普及组C题目及答案.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十四届全国青少年信息学奥林匹克联赛初赛试题2021 普及组 语言 二小时完成 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、 单项选择题 共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年设立的，特地嘉奖那些对

2、计算机事业作出重要奉献的个人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

3、相等的四进制数是 。9. 设字符串，S的非空子串的数目是 。A. 28 B. 29 C. 16 D. 17102.0是近年来互联网的热门概念之一，其核心思想是互动及共享。以下网站中， 是典型的2.0应用。 A. B. C. D. 11 递归过程或函数调用时，处理参数和返回地址，通常运用一种称为 的数据构造。A. 队列 B. 多维数组 C. 线性表 D. 栈12. (2021)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

4、 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. 面对对象程序设计 是一种程序设计的方法论，它将对

5、象作为程序的根本单元，将数据和程序封装在对象中，以进步软件的重用性、灵敏性和扩展性。下面关于面对对象程序设计的说法中，不正确的选项是 。A. 面对对象程序设计通常承受自顶向下设计方法进展设计。B. 面对对象程序设计方法具有继承性、封装性、多态性等几大特点。C. 支持面对对象特性的语言称为面对对象的编程语言，目前较为流行的有、等。D. 面对对象的程序设计的雏形来自于语言，后来在语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，语言照旧被视为面对对象语言的根底。17. 在32*32点阵的“字库中，汉字“北及“京的字模占用字节数之和是 。 A. 512 B. 256 C. 384

6、 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个城市，任何两个城市之间都有

7、一条道路连接，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 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) %

8、 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); 0;输入: 3 1 2输出: 3 ; ( , n ) 0, j, x;1;(ij) (i0) ; (ij0) ; (ij)i;j; () a20, i, m;10;(0; iai;(a, m); (0; im; )ai ; ; 0;输入：5 4 -6 -11 6 -59 22 -6 1 10输出：4. ; 100 ( , , , , , ) i, ;( );(i = ; i = ; )( i) = i;(,

9、 + 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用该字母的小写交换

10、；S中的第二个字母是字母B和b的交换字母，即S中的B用该字母的大写交换，S中的b用该字母的小写交换； 以此类推。 26, 5000; ; () i; (i = 0 26 ) ( ) i A - a; () i; (i = 0 ; ; (); ; 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; () i; m = 1000000; (i = 1 ai; n; = (1); =Ai=Z(只写i=Ai=Z只写i=Z也对3i=i-a;4();2.1a;2aj4ai=;5i+16(,i1,n);