noip初赛试题1.docx

NOIP普及组（初赛）试题精选一、计算机系统1.在以下各项中，（）不是CPU的组成部分。（NOIP2007）A控制器B运算器C寄存器D主板【答案】D。CPU由控制器、运算器和寄存器组成。2.在下列各项中，只有（）不是计算机存储容量的常用单位。（NOIP2007）AByteBKBCUBDTB【答案】C。存储容量：Byte=8 bit（位）、1KB=1024B、1MB=1024KB、1GB=1024MB、1TB=1024GB。3.与十进制数1770对应的八进制数是（）。（NOIP2007）A3350B3351C3352D3540【答案】C。考查进制转换，掌握十进制、二进制、八进制和十六进制互换，以及多个不同进制数的运算（转换为同一进制数进行计算）。4.与十进制数28.5625相等的四进制数是（）。（NOIP2008）A123.21B131.22C130.22D130.21【答案】D。熟练掌握进制转换的知识。5.计算机在工作过程中，若突然停电，（）中的信息不会丢失。（NOIP2008）AROM和RAMBCPUCROMDRAM【答案】C。ROM（只读存储器）断电后信息不丢失，RAM（随机存储器，内存）断电后信息全部丢失。6.在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（）。（NOIP2008）A512B256C384D128【答案】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是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web 2.0应用。（NOIP2008）ASinaBFlickerCYahooDGoogle【答案】B。Web2.0最大的特点就是任何人可以参与、发布网页信息，如博客、播客（土豆、优酷等）、维基百科等。4.常见的邮件传输服务器使用（）协议接收邮件。（NOIP2005）A. HTTPB. SMTPC. TCPD. FTPE. POP3【答案】E。SMTP-发送邮件协议；POP3-接收邮件协议；HTTP-超文本传输协议；FTP-文件传输协议；TCP/IP-传输控制协议/因特网互联协议，它是Internet最基本的协议。5.下列网络中常用的名字缩写对应的中文解释错误的是（）。（NOIP2004）A、WWW(World Wide Web)：万维网B、URL（Uinform Resource Locator）：统一资源定位器C、HTTP（Hypertext Transfer Protocol）：超文本传输协议D、FTP(File Transfer Protocol)：快速传输协议E、TCP（Transfer Control Protocol）：传输控制协议【答案】D。FTP：文件传输协议。URL：统一资源定位器（网址）。6.下列哪个不是数据库软件的名称（）A、MYSQLB、SQL SeverC、OracleD、金山影霸【答案】D。数据库软件常用的有：MYSQL、SQLServer、Access、Foxpro、Oracle、Sybase等。三、编程语言1.一个无法靠自身的控制终止的循环成为“死循环”，例如，在C语言程序中，语句“while(1) printf(“*”);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。（NOIP2007）A不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查B有些编译系统可以检测出死循环C死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环D死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的【答案】A。2.在Pascal语言中，表达式（23 or 2 xor 5）的值是（）。（NOIP2007）A18B1C23D32【答案】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(AB)(CDA)B(AB)C)D)CA(BCD)DD(A(DC)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）A2 4 3 6 5 7B2 4 1 2 5 7C2 4 3 1 7 6D2 4 3 6 7 5【答案】D。栈，后进先出。2.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（）。（NOIP2006）A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2【答案】C。栈操作。3.完全二叉树共有2*N-1个结点，则它的叶节点数是（）。（NOIP2008）AN-1BNC2*ND2N-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+1D2=（结点数-1）2= (2*N-2)2=N-1D0+D2=2*N-1D0=2*N-1-(N-1)=N4.完全二叉树的结点个数为11，则它的叶结点个数为（）。（NOIP2005）A. 4B.3C.5D. 2E. 6【答案】E。用上题的结论。5.高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A. 10B. 11 C. 12 D. 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）AT有n条边BT是连通的CT是无环的DT有n-1条边【答案】A。n个顶点的树，除了根结点以外，其余每个结点上方都连接一条边，所以一共有n-1条边。8.已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（）。（NOIP2007）A4 6 5 2 7 3 1B4 6 5 2 1 3 7C4 2 3 1 5 4 7D4 6 5 3 1 7 2【答案】A。先根遍历=先序遍历（根左右），中根遍历=中序遍历（左根右），后根遍历=后序遍历（左右根）。中序遍历保证了左子树的所有结点在它左边，右子树的结点在它右边。过程如下：后用先序遍历结果，找到父结点，然后按照中序遍历结果将其左右子树分开；然后再从先序遍历结果中再找到左子树的根结点，再重复以上操作直到所有结点归位。先序：1 2 4 5 6 3 7中序：4 2 6 5 1 7 3先序第1个数字是1（二叉树根），将中序中1的左半段与右半段分开，即得到1的左子树是4 2 6 5，右子树是7 3，表示为（4 2 6 5）1（7 3）。图1再看1的左子树4 2 6 5，其对应的先序2 4 5 6，此时先序第1个数字是2（左子树的根），将中序以2再次划分为左子树4，右子树6 5，表示为（4）2（6 5），如图2所示。图2图3图42的右子树中序为6 5，先序为5 6，则2的右子树的根是5，再看中序，得到（6）5，到这里完成结点1左子树的结构，如图3所示。同样方法构建1右子树，得到（7）3，如图4所示。依照后序遍历的特点（左右根），得到结果：4 6 5 2 7 3 1，故答案为A。【思考】（1）已知中序和后序，如何求先序？（2）已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列：_BC_EF_中序序列：BDE_AG_H后序序列：_DC_GH_A9.二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为节点的编号，下同），中根遍历2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。（NOIP2008）A4 2 5 7 6 3 1B427563 1C7 4 2 5 6 3 1D4 2 7 6 5 3 1【答案】B。10.已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）。（NOIP2006）A. 3 2 1 4 6 5B. 3 2 1 5 4 6C. 2 1 3 5 4 6D. 2 3 1 4 6 5【答案】B。先序遍历和后序遍历不能确定唯一中序遍历，对于本题的结果可以是：2 3 1 5 4 6或者3 2 1 5 4 6。11.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（）。（NOIP2005）A.无法确定B. BC. CD. DE. E【答案】C。12.设栈S的初始状态为空，元素a, b, c, d, e依次入栈，以下出栈序列不可能出现的有（）。（NOIP2006）A. a, b, c, e, dB. b, c, a, e, dC. a, e, c, b, dD. d, c, e, b, a【答案】C。选项C中的出栈序列：a,e,c,b,d，a,e出栈，则栈中必是b,c,d（从下往上），出栈序列只能是d,c,b，而不是c,b,d。13.满二叉树的叶节点为N，则它的节点总数为（）（NOIP2004）A、NB、2NC、2N-1D、2N+1E、2N-1【答案】C。满二叉树的结点个数为（根结点的深度为1），其叶子节点的个数为，所以“结点个数”=“叶子节点”*2-1=2N-1。五、算法1.近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（）。（NOIP2007）A在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间B和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些C对于较复杂的问题，用递归方式编程一般比非递归方式更难一些D对于已经定义好的标准数学函数sin(x)，应用程序中的语句“y=sin(sin(x);”就是一种递归调用。【答案】A。2.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。（NOIP2006）A.选择排序B.冒泡排序C.插入排序D.基数排序【答案】D。基于“比较”的排序：冒泡、选择、插入、快速、归并、堆、希尔等；而“非比较”的排序：计数排序、桶排序、基数排序等。3.设字符串S=Olympic，S的非空子串的数目是（）。（NOIP2008）A28B29C16D17【答案】A。串长为1的子串有7个，串长为2的子串有6个，串长为7的子串有1个，共7+6+5+2+1=28。4.将数组8，23，4，16，77，-5，53，100中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。（NOIP2008）A4B5C6D7【答案】B。选择排序，第1次是将第1个元素与右边7个元素中最小的一个交换，第2次是将第2个元素与右边6个元素中最小的一个交换，。若当前元素已是其余元素中最小的，则不需要交换。5.对有序数组 5，13，19，21，37，56，64，75，88，92，100进行二分查找，成功查找元素19的查找长度（比较次数）是（）。（NOIP2008）A1B2C3D4【答案】B。首先与中间元素56比较，比56小，则继续在56左侧的5个元素中查找；与这5个元素的中间元素19比较，相等，则找到，所以只需要比较2次。6.由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。（NOIP2004）A、20B、8C、16D、12E、24【答案】D。把“abc”看成一个整体，记为d。本题转换为2个a、1个c、1个d进行全排列，由于有2个a，所以要除以a的全排列个数，即。六、问题求解1.书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_种摆法。（NOIP2008）【答案】12,4。由于要求黑皮的书排在一起，所以把C和D做为一个排列的对象，故3个对象的全排列为，而C和D可以互换位置，所以第一空的解为：=12。红皮书要摆在一起，黑皮书要摆在一起，所以我们将A和B作为一个排列对象，C和D作为一个排列对象，另外A必须比C靠左，则必然是ABCD，由于A和B可以互换（=2），C和D可以互换（=2），所以摆法有22=4种。2.有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_。（NOIP2008）城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920【答案】7(1-2-5-6)。参考图的单源最短路径（Dijkstra算法）。3.NOIP2007第1题：子集划分将n个数（1，2，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为(1),(234)，(2),(134)，(3),(124)，(4),(123)，(12),(34)，(13),(24)，(14),(23)。当n=6，r=3时，S(6,3)=_。（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）【答案】90。组合：将6分成3个集合，只有3种分法：4个、1个、1个；3个、2个、1个；2个、2个、2个，所以利用组合数学知识，可以得到。说明：最后一种可能性是分成2个、2个、2个，从6个数取出2个的组合数为，再从余下的4个数中取出2个的组合数为，最后余下的2个数作为一个集合，但这种方法会出现重复的情况，如(12),(34),(56)、(12),(56),(34)、(34),(12),(56)、(34),(56),(12)、(56),(12),(34)、(56),(34),(12)，即=6种。递推：s(n,r)=s(n-1,r)*r+s(n-1,r-1)，其中s(n,r)表示n个数分为r个集合的方法种数。先可以固定一个数，如k，则接下来有两种方法：一种是将余下的n-1个数分成r-1个集合，即数k独占一个集合；另一种是将余下的n-1个数分成r个集合，再将前面固定的那个数，任意放在r个集合的任一个中，则方法有s(n-1,r-1)*r种。利用加法原理，得到这个递推式。由于它是二维的，所以我们可以用填表的方法来求解出答案，每个单元格中的数等于它左下方数+下方数r。r=1r=2r=3n=613190n=511525n=4176n=3131n=2110n=11004.NOIP2007第2题（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？_BA【答案】210。递推：设f(i,j)表示到达第i行（横街）、第j列（纵街）时的最短走法，故可以写出递推式：f(i,j)=f(i,j-1)+f(i-1,j)。f(i,j-1)f(i,j)f(i-1,j)B15153570126210141020355684136101521281234567A1111111组合：无论怎么走法，每种走法最终均是由向上走4步，向右走6步组成，一共10步，所以全部走法是从10步里选出其中的4步向上走（其余6步向右走），即（种）。5.（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_。（NOIP2006）【答案】4，第一步：分成3组：27，27，26，将前2组放到天平上。若第1组与第2组相等，则假币在第3组中；若第1组比第2组轻，则假币在第1组中，否则就在第2组中。以此类推，第2步：9 9 9（27枚）或9 9 8（26枚）；第3步：3 3 3（9枚）或3 3 2（8枚）第4步：1 1 1（3枚）或1 1（2枚）6.（取石子游戏）现有5堆石子，石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：_。（NOIP2006）【答案】从50中取走32粒剩余18粒是正确的。算法：从其中一堆中取n个，使得剩余的所有数目正好是“必负局（此时先取必输的局面）”。所谓“必负局”是指把剩余的每一堆的数目都转化成二进制的数，然后把它们相加，规定做不进位的加法（也就是异或运算），即0+00，1+00，0+11，1+10（不进位），如果所得和是0（多个0），那么此种局势称为“必负局”。“必负局”原理：一个“必负局”，