Noip2010提高组初赛试题及详细解析(C语言)

第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。）1.与16进制数A1.2等值的10进制数是（C）A.101.2B.111.4C.161.125D.177.25解析1:看进制转换的表原式等于10（A）×161＋1×160＋2×16-1=161.1252.一个字节（byte）由（）个二进制位组成。A.8B.16C.32D.以上都有可能解析2:一个字节（byte）由（8）个二进制位组成，即一个字节等于八比特3.一下逻辑表达式的值恒为真的是（）A.P∨（┐P∧Q)∨（┐P∧┐Q)B.Q∨（┐P∧Q)∨(P∨┐Q)C.P∨Q∨(P∧┐Q)∨(┐P∧Q)D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)解析3：各个逻辑符号的问题，可以进行一定的假设。设P,Q都为假∨表示或相当于生活中的“或者”，∧表示与.相当于生活中说的“并且”┐表示非.真或真为真：真或假为真：假或假为假：假与假为假，假与真为假，真与真为真。真为真，非真为假，假为假，非假为真。4.Linux下可执行文件的默认扩展名为（）A.exeB.comC.dllD.都不是解析4：Linux下常见的文件名后缀、文件类型1、系统文件*.conf配置文件*.rpmrpm包*.a一种存档文件*.lock一种琐文件*.~备份文件*.隐藏文件2:程序或脚本*.cc语言源程序文件*.cppc++语言源程序*.hc或c++头文件*.o程序对象文件*.plperl语言源程序*.phpphp语言源程序*.tcltcl脚本程序*.so/.lib库文件*.sqlsql语言文件3:格式文件*.txt无格式的ascii码文件*.html/.htm静态web页*.pspostScipt文件*.au一种声音文件*.wav一种声音文件*.xpm一种图像文件*.png一种图形,图像文件4:存档与压缩文件*.tartar归档文件*.Z/.gz/.bz2压缩文件*.tar.gz/.tgz/.tar.bz2/.tbz为压缩后的tar包linux本身是没有扩展名这个概念的。只有文件属性里可以定义可执行权限5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。A.100B.144C.164D.196解析5：设进制为z得到:12=1×z1+2×z012*12=（1×z1+2）*（1×z1+2）=z2+4z+4=1×z2+4×z1+4×z0=1446.提出“存储程序”的计算机工作原理的是（）。A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼解析6：克劳德·香农：克劳德·艾尔伍德·香农（ClaudeElwoodShannon，1916年4月30日—2001年2月26日）美国数学家，信息学的创始人。冯.诺依曼，计算机之父，第一台计算机设计出来之后，没有内存，冯.诺依曼提出了存储程序的概念和思路阿兰·麦席森·图灵AlanMathisonTuring，6月23日生于英国伦敦。是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。7.前缀表达式“+3*2+512”的值是（）A.23B.25C.37D.65解析7：前缀表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，为纪念其发明者波兰数学家JanLukasiewicz也称为“波兰式”。例如，-1+23，它等价于1-(2+3)。对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例如，“+3*2+512”前缀表达式求值，扫描到12时，记录下这个数字串，扫描到5时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为12+5，结果为17，记录下这个新数字串，并继续向左扫描，扫描到2时，记录下这个数字串，扫描到*时，将*右移做相邻两数字串的运算符，记为2*17，结果为34，记录下这个新字符，然后继续扫描，扫描到3记录下来，再继续扫描到“+”，把运算符右移，记为3+34=37.8.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（）A.寄存器B.高速缓存C.闪存D.外存解析8：寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。闪存（FlashMemory）是一种长寿命的非易失性（在断电情况下仍能保持所存储的数据信息）的存储器由于其断电时仍能保存数据，闪存通常被用来保存设置信息，如在电脑的BIOS外储存器是指除计算机内存及CPU缓存以外的储存器，此类储存器一般断电后仍然能保存数据。常见的外储存器有硬盘、软盘、光盘、U盘等。“高速缓存”的目的是为了让数据访问的速度适应CPU的处理速度，其基于的原理是内存中“程序执行与数据访问的局域性行为”，即一定程序执行时间和空间内，被访问的代码集中于一部分。9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整解析9：关于二叉树的性质(1)在二叉树中，第i层的结点总数不超过2^(i-1)；(2)深度为h的二叉树最多有2^h-1个结点(h=1)，最少有h个结点；(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4)具有n个结点的完全二叉树的深度为int（log2n）+1(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则如果I1，则其父结点的编号为I/2；如果2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；如果2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i10.一下竞赛活动中历史最悠久的是（）A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）解析10：全国青少年信息学奥林匹克联赛（NOIP）全国青少年信息学奥林匹克联赛（NationalOlympiadinInformaticsinProvinces，简称NOIP）自1995年至今已举办17次。每年由中国计算机学会（CCF）统一组织。全国青少年信息学奥林匹克（NOI）是国内包括港澳在内的省级代表队最高水平的大赛，自1984年至今，在国内包括香港、澳门，已组织了24次竞赛活动。国际信息学奥林匹克竞赛（IOI）首届竞赛于1989年在保加利亚的布拉维茨举行，有13个国家的46名选手参赛。此后IOI每年举办一届，亚太地区信息学奥林匹克竞赛（APIO）亚洲与太平洋地区信息学奥林匹克（Asia-PacificInformaticsOlympiad,APIO），是一个面向亚太地区在校中学生的信息学科竞赛。旨在给青少年提供更多的赛事机会，推动亚太地区的信息学奥林匹克的发展。该竞赛性质为区域性的网上准同步赛，每年五月的第一或第二个星期六举办，2007年举办第一届，主办方为澳大利亚，中国区的承办方是北京，中国人民大学，2008年是沈阳，东北大学，2009年是天津，天津大学，2010年是北京，北航大学，2011年是北京，中国人民大学，2012年是北京，北京大学二.不定项选择题（共10题，每题1.5分，共计15分。每题有一个或多个正确选项。多选或少选均不得分。）1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第一个出栈的是R3，那么第五个出栈的可能是（）。A.R1B.R2C.R4D.R5解析1：入栈依次进入，那么当R3入栈时，堆栈应该是R1，R2，R3此时R3出栈。就是R1，R2然后不论R4，R5如何出入栈，R1必然会在R2之后出栈，所以第五个出栈的不会是R2，R2最多只能在第四个出栈。2.Pascal语言、C语言、和C++语言都属于（）A.高级语言B.自然语言C.解释型语言D.编译性语言3.原地排序是指在排序过程中（除了存储待排序元素以外的）付诸空间的大小与数据规模无关的排序算法。一下属于原地排序的有（）A.冒泡排序B.插入排序C.基数排序D.选择排序4.在整数的补码表示法中，以下说法正确的是（）A.只有负整数的编码最高为1B.在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C.整数0只有唯一的一个编码D.两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出5.一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（）A.0B.2C.4D.66.在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（）A.aurl=网站/aB.aherf=网站/aC.a=网站/a解析6：HTML语言html/html创建一个HTML文档head/head设置文档标题和其它在网页中不显示的信息title/title设置文档的标题h1/h1最大的标题fontcolor=00ff00.../font；字体颜色fontsize=1.../font；最小字体br/定义新行ahref=URL/a创建超文本链接/a创建自动发送电子邮件的链接aname=name/a创建位于文档内部的书签ahref=#name/a创建指向位于文档内部书签的链接7.关于拓扑排序，下面说法正确的是（）A.所有连通的有向图都可以实现拓扑排序B.对同一个图而言，拓扑排序的结果是唯一的C.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面D.拓扑排序结果序列中的第一个结点一定是入度为0的结点8.一个平面的法线是指与该平面垂直的直线。过点（1,1,1）、（0,3,0）、（2,0,0）的平面的法线是（）A.过点（1,1,1）、（2,3,3）的直线B.过点（1,1,1）、（3,2,1）的直线C.过点（0,3,0）、（-3,1,1）的直线D.过点（2,0,0）、（5,2,1）的直线解析8：立体几何问题。9.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点P,则下面语句序列中正确的是（）A.p-rlink-llink=p-rlink;p-llink-rlink=p-llink;free(p);B.P-llink-rlink=p-rlink;p-rlink-llnik=p-llink;free(p);C.p-rlink-llink=p-llink;p-rlink-llink-r