noip普及组初赛试题及讲解.pdf

NOIP普及组（初赛）试题精选 一、计算机系统 1. 在以下各项中，（ ）不是CPU的组成部分。（NOIP2007） A控制器 B运算器 C寄存器 D主板 【答案】D。CPU由控制器、运算器和寄存器组成。 2. 在下列各项中，只有（ ）不是计算机存储容量的常用单位。 （NOIP2007） AByte BKB CUB DTB 【答案】C。存储容量：Byte=8 bit（位）、1KB=1024B、1MB=1024KB、1GB=1024MB、1TB=1024GB。 3. 与十进制数1770对应的八进制数是（ ）。（NOIP2007） A3350 B3351 C3352 D3540 【答案】C。考查进制转换，掌握十进制、二进制、八进制和十六进制 互换，以及多个不同进制数的运算（转换为同一进制数进行计算）。 4. 与十进制数28.5625相等的四进制数是（ ）。（NOIP2008） A123.21 B131.22 C130.22 D130.21 【答案】D。熟练掌握进制转换的知识。 5. 计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。 （NOIP2008） AROM 和 RAM BCPU CROM DRAM 【答案】C。ROM（只读存储器）断电后信息不丢失，RAM（随机存储 器，内存）断电后信息全部丢失。 6. 在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和 是（ ）。（NOIP2008） A512 B256 C384 D128 【答案】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） ASina BFlicker CYahoo DGoogle 【答案】B。Web2.0最大的特点就是任何人可以参与、发布网页信息， 如博客、播客（土豆、优酷等）、维基百科等。 4. 常见的邮件传输服务器使用（ ）协议接收邮件。（NOIP2005） A. HTTP B. SMTP C. TCP D. FTP E. 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、MYSQL B、SQL Sever C、Oracle D、金山影霸 【答案】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） A18 B1 C23 D32 【答案】A。本题考查进制转换和逻辑运算（and、or、not和xor）。对 于本题首先将十进制整数转换二进制数，然后再按位进行逻辑运算。 168421 10111(=23) (or)00010(=2) 10111 (xor)00101(=5) 10010(=18) 7. (2070)16 + (34)8 的结果是（ ）。（NOIP2007） A（8332）10 B（208A）16 C （100000000110）2 D(20212)8 【答案】A。本题两个数分别是十六进制和八进制，故先将它们转换为 二进制，然后再进行计算和转换。 (2070)16=(0010,0000,0111,0000)（每位展开为4位二进制数） (34)8= (11,100)2 （每位展开为3位二进制数） 利用二进制数的运算法则，得到两者相加为（0010,0000,0001）2 （8332）10 8. (2008)10+(5B)16的结果是（ ）。（NOIP2008） A（833）16 B（2089）10 C（4163）8 D（100001100011）2 【答案】A。 9. 设A=B=True，C=D=False，下面逻辑运算表达式值为假的有（ ）。（NOIP2007） A(AB)(CDA) B (AB)C)D) CA(BCD)D D(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 7 B2 4 1 2 5 7 C2 4 3 1 7 6 D2 4 3 6 7 5 【答案】D。栈，后进先出。 2. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入 口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录 为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆 入站的 顺序为 1，2，3，则车辆出站的顺序为（ ）。 （NOIP2006） A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 【答案】C。栈操作。 3. 完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。 （NOIP2008） AN-1 BN C2*N D2N-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)=N 4. 完全二叉树的结点个数为11，则它的叶结点个数为（ ）。 （NOIP2005） A. 4 B.3 C.5 D. 2 E. 6 【答案】E。用上题的结论。 5. 高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝， 它应该是高度为 n-1 的满二叉树。 在这里，树高等于叶结点的最大深 度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点， 则该树的树高为（ ）。 A. 10 B. 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 1 B4 6 5 2 1 3 7 C4 2 3 1 5 4 7 D4 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图4 2的右子树中序为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_A 9. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为节点的编 号，下同），中根遍历2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。（NOIP2008） A4 2 5 7 6 3 1 B4 2 7 5 6 3 1 C7 4 2 5 6 3 1 D4 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 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 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. B C. C D. D E. E 【答案】C。 12. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈 序列不可能出现的有（ ）。（NOIP2006） A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. 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、N B、2N C、2N-1 D、2N+1 E、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） A28 B29 C16 D17 【答案】A。串长为1的子串有7个，串长为2的子串有6个，串长 为7的子串有1个，共7+6+5+2+1=28。 4. 将数组8，23，4，16，77，-5，53，100中的元素按从小到大的 顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。 （NOIP2008） A4 B5 C6 D7 【答案】B。选择排序，第1次是将第1个元素与右边7个元素中最小的一 个交换，第2次是将第2个元素与右边6个元素中最小的一个交换， 。若当前元素已是其余元素中最小的，则不需要交换。 5. 对有序数组 5，13，19，21，37，56，64，75，88，92，100进 行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。 （NOIP2008） A1 B2 C3 D4 【答案】B。首先与中间元素56比较，比56小，则继续在56左侧的5个元 素中查找；与这5个元素的中间元素19比较，相等，则找到，所以只需 要比较2次。 6. 由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有 （ ）个。（NOIP2004） A、20 B、8 C、16 D、12 E、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靠左，则必然是AB CD，由于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=3 n=613190 n=511525 n=4176 n=3131 n=2110 n=1100 4. NOIP2007第2题 （最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7 条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的 B，最短的走法共有多少种？_ B A 【答案】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) B 15153570126210 1410203556841234567 A 1 111111 组合： 无论怎么走法，每种走法最终均是由向上走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），那么此种局势称为“必负局”。 “必负局”原理：一个“必负局