noip初赛试题1

NOIP普及组（初赛）试题精选一、计算机系统1.在以下各项中，（）不是CPU的组成部分。（NOIP2007）A．控制器B．运算器C．寄存器D．主板【答案】D。CPU由控制器、运算器和寄存器组成。2.在下列各项中，只有（）不是计算机存储容量的常用单位。（NOIP2007）A．ByteB．KBC．UBD．TB【答案】C。存储容量：Byte=8bit（位）、1KB=1024B、1MB=1024KB、1GB=1024MB、1TB=1024GB。3.与十进制数1770对应的八进制数是（）。（NOIP2007）A．3350B．3351C．3352D．3540【答案】C。考查进制转换，掌握十进制、二进制、八进制和十六进制互换，以及多个不同进制数的运算（转换为同一进制数进行计算）。4.与十进制数28.5625相等的四进制数是（）。（NOIP2008）A．123.21B．131.22C．130.22D．130.21【答案】D。熟练掌握进制转换的知识。5.计算机在工作过程中，若突然停电，（）中的信息不会丢失。（NOIP2008）A．ROM和RAMB．CPUC．ROMD．RAM【答案】C。ROM（只读存储器）断电后信息不丢失，RAM（随机存储器，内存）断电后信息全部丢失。6.在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（）。（NOIP2008）A．512B．256C．384D．128【答案】B。32*32点阵的字库，每个字占字节数为32*32/8=128字节（1个字节等于8个二进制位，1Byte=8bits，而1位对应点阵中的1个点）。所以2个汉字共要256个字节。7.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。（NOIP2006）A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖【答案】D。沃尔夫奖主要是奖励对推动人类科学与艺术文明做出杰出贡献的人士；诺贝尔奖有生理或医学奖、文学奖、物理学奖、化学奖、经济学奖和和平奖；菲尔兹奖－数学界的诺贝尔奖；图灵奖－计算机界的诺贝尔奖，2000年姚期智获得“图灵奖”，也是迄今为止获得此项殊荣的唯一华裔计算机科学家。二、网络和数据库1.在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。（NOIP2007）A．二叉树B．多叉树C．哈希表D．二维表【答案】D。关系数据库是用二维表表示逻辑结构，类似于Excel。2.LAN的含义是（）。（NOIP2007）A．因特网B．局域网C．广域网D．城域网【答案】B。Internet（因特网）、LAN（局域网）、WAN（广域网）、MAN（城域网）3.Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web2.0应用。（NOIP2008）A．SinaB．FlickerC．YahooD．Google【答案】B。Web2.0最大的特点就是任何人可以参与、发布网页信息，如博客、播客（土豆、优酷等）、维基百科等。4.常见的邮件传输服务器使用（）协议接收邮件。（NOIP2005）A.HTTPB.SMTPC.TCPD.FTPE.POP3【答案】E。SMTP-发送邮件协议；POP3-接收邮件协议；HTTP-超文本传输协议；FTP-文件传输协议；TCP/IP-传输控制协议/因特网互联协议，它是Internet最基本的协议。5.下列网络中常用的名字缩写对应的中文解释错误的是（）。（NOIP2004）A、(WorldWideWeb)：万维网B、URL（UinformResourceLocator）：统一资源定位器C、HTTP（HypertextTransferProtocol）：超文本传输协议D、FTP(FileTransferProtocol)：快速传输协议E、TCP（TransferControlProtocol）：传输控制协议【答案】D。FTP：文件传输协议。URL：统一资源定位器（网址）。6.下列哪个不是数据库软件的名称（）A、MYSQLB、SQLSeverC、OracleD、金山影霸【答案】D。数据库软件常用的有：MYSQL、SQLServer、Access、Foxpro、Oracle、Sybase等。三、编程语言1.一个无法靠自身的控制终止的循环成为“死循环”，例如，在C语言程序中，语句“while(1)printf(“*”);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。（NOIP2007）A．不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查B．有些编译系统可以检测出死循环C．死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环D．死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的【答案】A。2.在Pascal语言中，表达式（23or2xor5）的值是（）。（NOIP2007）A．18B．1C．23D．32【答案】A。本题考查进制转换和逻辑运算（and、or、not和xor）。对于本题首先将十进制整数转换二进制数，然后再按位进行逻辑运算。16842110111(=23)(or)00010(=2)10111(xor)00101(=5)10010(=18)7.(2070)16+(34)8的结果是（）。（NOIP2007）A．（8332）10B．（208A）16C．（100000000110）2D．(20212)8【答案】A。本题两个数分别是十六进制和八进制，故先将它们转换为二进制，然后再进行计算和转换。①(2070)16=(0010,0000,0111,0000)（每位展开为4位二进制数）②(34)8=(11,100)2（（每位展开为3位二进制数）③利用二进制数的运算法则，得到两者相加为（0010,0000,0001）2＝（8332）108.(2008)10+(5B)16的结果是（）。（NOIP2008）A．（833）16B．（2089）10C．（4163）8D．（100001100011）2【答案】A。9.设A=B=True，C=D=False，下面逻辑运算表达式值为假的有（）。（NOIP2007）A．(﹁A∧B)∨(C∧D∨A)B．﹁(((A∧B)∨C)∧D)C．A∧(B∨C∨D)∨DD．(A∧(D∨C))∧B【答案】D。“﹁”表示not，“∧”表示and（与，并且），“∨”表示or（或者）。10.在下列关于计算机语言的说法中，不正确的是（）。（NOIP2006）A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C++是历史上的第一个支持面向对象的计算机语言D.与汇编语言相比，高级语言程序更容易阅读【答案】C。第一个支持面向对象的计算机语言是Smalltalk。四、数据结构1.地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（）。（NOIP2007）A．243657B．241257C．243176D．243675【答案】D。栈，后进先出。2.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。（NOIP2006）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2【答案】C。栈操作。3.完全二叉树共有2*N-1个结点，则它的叶节点数是（）。（NOIP2008）A．N-1B．NC．2*ND．2N-1【答案】B。在二叉树中，结点的度数有0、1、2三种情况，其中度为0的结点就是叶子结点。设D0表示度为0的结点个数，D1表示度为1的结点个数，D2表示度为2的结点个数，则有二叉树结点=D0+D1+D2。在完全二叉树中，若除去最下面一层的结点，则此时的二叉树构成一个满二叉树，其结点个数为（奇数），而题目中的二叉树共有2*N-1（奇数）个结点，所以可以知道完全二叉树最下面一层的结点个数为偶数个，得知D1=0。这样我们只要求出D2，就可以得到D0的值了。接下来，我们来看二叉树边的个数，由于“边数=结点数-1”（除去根结点，因为只有它的上面没有边），D0结点（叶节点）无发出的边，D1结点个数为0，D2发出的边数为D2*2，所以得到：边数=结点数-1=D2*2→结点数=D2*2+1→D2=（结点数-1）÷2=(2*N-2)÷2=N-1∵D0+D2=2*N-1∴D0=2*N-1-(N-1)=N4.完全二叉树的结点个数为11，则它的叶结点个数为（）。（NOIP2005）A.4B.3C.5D.2E.6【答案】E。用上题的结论。5.高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10B.11C.12D.13【答案】B。满二叉树的结点个数为（根结点的深度为1），而这棵二叉树共有2381个结点，可以算出上面满二叉树的结点个数是=2048-1=2047，故这棵树有11+1（最下面1层）=12。由于题目中根结点的深度是从0（一般从1）开始的，所以该树高12-1=11。6.递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。（NOIP2008）A．队列B．多维数组C．线性表D．栈【答案】D。7.设T是一棵有n个顶点的树，下列说法不正确的是（）。（NOIP2008）A．T有n条边B．T是连通的C．T是无环的D．T有n-1条边【答案】A。n个顶点的树，除了根结点以外，其余每个结点上方都连接一条边，所以一共有n-1条边。8.已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（）。（NOIP2007）A．4652731B．4652137C．4231547D．4653172【答案】A。先根遍历=先序遍历（根→左→右），中根遍历=中序遍历（左→根→右），后根遍历=后序遍历（左→右→根）。中序遍历保证了左子树的所有结点在它左边，右子树的结点在它右边。过程如下：后用先序遍历结果，找到父结点，然后按照中序遍历结果将其左右子树分开；然后再从先序遍历结果中再找到左子树的根结点，再重复以上操作……直到所有结点归位。先序：1245637中序：4265173①先序第1个数字是1（二叉树根），将中序中1的左半段与右半段分开，即得到1的左子树是4265，右子树是73，表示为（4265）1（73）。图1②再看1的左子树4265，其对应的先序2456，此时先序第1个数字是2（左子树的根），将中序以2再次划分为左子树4，右子树65，表示为（4）2（65），如图2所示。图2图3图4③2的右子树中序为65，先序为56，则2的右子树的根是5，再看中序，得到（6）5，到这里完成结点1左子树的结构，如图3所示。④同样方法构建1右子树，得到（7）3，如图4所示。⑤依照后序遍历的特点（左→右→根），得到结果：4652731，故答案为A。【思考】（1）已知中序和后序，如何求先序？（2）已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列：_BC_EF__中序序列：BDE_AG_H后序序列：_DC_GH_A9.二叉树T，已知其先根遍历是1243576（数字为节点的编号，下同），中根遍历2415736，则该二叉树的后根遍历是（）。（NOIP2008）A．4257631B．4275631C．7425631D．42