最新NOIP普及组试题精选

1、NOIP 普及组(初赛)试题精选一、计算机系统1. 在以下各项中，()不是CPU的组成部分。(NOIP2007)A. 控制器B运算器C 寄存器D 主板【答案】Do CPU由控制器、运算器和寄存器组成。2. 在下列各项中，只有( )不是计算机存储容量的常用单位。(NOIP2007)A. Byte B . KB C . UB D . TB【答案】C。存储容量： Byte=8 bit (位)、1KB=1024B、1MB=1024KB 1GB=1024MB 1TB=1024G Bo3. 与十进制数 1770 对应的八进制数是( )。( NOIP2007)A . 3350 B . 3351 C . 33

2、52 D . 3540【答案】C。考查进制转换，掌握十进制、二进制、八进制和十六进制互换，以及多个不同进制 数的运算(转换为同一进制数进行计算)。4. 与十进制数 28.5625 相等的四进制数是()。( NOIP2008)A. 123.21B. 131.22 C . 130.22 D . 130.21【答案】D。熟练掌握进制转换的知识。5. 计算机在工作过程中，若突然停电，()中的信息不会丢失。(NOIP2008)A. ROM和 RAM B . CPU C . ROM D . RAM【答案】Co ROM(只读存储器)断电后信息不丢失，RAM(随机存储器，内存)断电后信息全部丢失。6. 在 3

3、2*32 点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是()。( NOIP2008)A512B256 C384D128【答案】Bo 32*32点阵的字库，每个字占字节数为32*32/8=128字节（1个字节等于8个二进制位， 1Byte=8bits ，而 1 位对应点阵中的 1 个点）。所以 2 个汉字共要 256 个字节。7. 在下面各世界顶级的奖项中， 为计算机科学与技术领域做出杰出贡献的科学家设立的奖项 是（）o（ NOIP2006）A. 沃尔夫奖B.诺贝尔奖C. 菲尔兹奖D. 图灵奖【答案】D。沃尔夫奖主要是奖励对推动人类科学与艺术文明做岀杰岀贡献的人士；诺贝尔奖有生理或医

4、学奖、 文学奖、 物理学奖、 化学奖、 经济学奖和和平奖； 菲尔兹奖数学界的诺贝尔奖； 图灵奖计算机界的诺贝尔奖， 2000 年姚期智获得“图灵奖”，也是迄今为止获得此项殊荣的 唯一华裔计算机科学家。二、网络和数据库1. 在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。（ NOIP2007）A.二叉树B.多叉树 C .哈希表D .二维表【答案】D。关系数据库是用二维表表示逻辑结构，类似于Excel o2. LAN的含义是（）。（NOIP2007）A.因特网B局域网C 广域网D 城域网【答案】Bo Internet （因特网）、LAN （局域网）、 WAN（广域网）、 MAN（城域网）

5、3. Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（ ）是典型的 Web 2.0 应用。（ NOIP2008）A. SinaB. Flicker C. Yahoo D . Google【答案】Bo Web2.0最大的特点就是任何人可以参与、发布网页信息，如博客、播客（土豆、优 酷等）、维基百科等。4. 常见的邮件传输服务器使用（ ）协议接收邮件。（ NOIP2005）A. HTTP B. SMTP C. TCP D. FTP E. POP3【答案】Eo SMTP-发送邮件协议；POP3-接收邮件协议；HTTP-超文本传输协议；FTP-文件传输协 议； TCP

6、/IP- 传输控制协议 /因特网互联协议，它是 Internet 最基本的协议。）。（ NOIP2004）5. 下列网络中常用的名字缩写对应的中文解释错误的是（A、WWW(World Wide Web):万维网B 、 URL(Uinform Resource Locator )：统一资源定位器）：超文本传输协议：快速传输协议）：传输控制协议C 、 HTTP(Hypertext Transfer ProtocolD 、 FTP (File Transfer Protocol)E 、 TCP ( T ransfe r Control Protocol【答案】Do FTP:文件传输协议。 URL统一

7、资源定位器（网址）6. 下列哪个不是数据库软件的名称（ ）A 、 MYSQLB 、 SQL SeverC 、 OracleD 、金山影霸【答案】D。数据库软件常用的有：MYSQL SQLServer、Access、Foxpro、Oracle、Sybase 等。三、编程语言1. 一个无法靠自身的控制终止的循环成为“死循环”，例如，在C语言程序中，语句“ while（1） printf（“ * ”）；"就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。（NOIP2007）A. 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会岀现死循环，

8、因而， 任何编译系统都不做死循环检查B. 有些编译系统可以检测岀死循环C. 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查岀死循环D. 死循环与多进程中岀现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的【答案】 Ao2. 在 Pascal 语言中，表达式 （23 or 2 xor 5 ）的值是（ ）o（ NOIP2007）学习-好资料A . 18B. 1C23D32【答案】A。本题考查进制转换和逻辑运算(and、or、not和xor )。对于本题首先将十进制整数转换二进制数，然后再按位进行逻辑运算。16842110111(=23)(or)00010(=2)

9、10111(xor)00101(=5)10010(=18)7. (2070) 16 + (34) 8 的结果是()。(NOIP2007)A.( 8332) ioB.( 208A) 16 C .( ) 2 D . (20212) 8【答案】A。本题两个数分别是十六进制和八进制，故先将它们转换为二进制，然后再进行计算和转换。 (2070) 16=(0010,0000,0111,0000) (每位展开为 4 位二进制数) (34) 8= (11,100) 2(每位展开为3位二进制数) 利用二进制数的运算法则，得到两者相加为(0010,0000,0001 ) 2=( 8332) 108. (2008)

10、10+(5B)16 的结果是()。(NOIP2008)A.( 833)16B.( 2089) 10C.( 4163)8 D .( ) 2)o( NOIP2007)【答案】Ao9. 设A=B=True, C=D=False，下面逻辑运算表达式值为假的有(A . (AA B) V (C A DV A)B. (A A B) V C) A D)C. AA (B V CV D) V DD. (A A (D V C) A B【答案】D。“”表示not，“A”表示and (与，并且)，“V”表示 or (或者)。10. 在下列关于计算机语言的说法中，不正确的是()。( NOIP2006)A. Pascal和

11、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

12、6 5 7B2 4 1 2 5 7 C2 4 3 1 7 6D2 4 36 7 5【答案】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。栈操作。)。( NOIP2008)3. 完全二叉树共有 2*N-1 个结点，则它的叶节点数是（A

13、N-1BNC2*N D2N-1答案】 B。在二叉树中，结点的度数有0、 1、 2 三种情况，其中度为0 的结点就是叶子结点。设D0 表示度为 0 的结点个数，D1表示度为1的结点个数，D2表示度为2的结点个数,则有二叉树结点 =D0+D1+D2。在完全二叉树中，若除去最下面一层的结点，则此时的二叉树构成一个满二叉树，其结点个数为 （奇数），而题目中的二叉树共有 2*N-1 （奇数）个结点，所以可以知道完全二叉树最下面一层的结点个数为偶数个，得知D仁0。这样我们只要求岀 D2,就可以得到 D0的值了。接下来，我们来看二叉树边的个数，由于“边数=结点数 -1 ”（除去根结点，因为只有它的上面没有边

14、），D0结点（叶节点）无发岀的边，D1结点个数为0 , D2发岀的边数为 D2*2，所以得到：边数=结点数-1=D2*2 f 结点数=D2*2+1 fD2=(结点数-1 ) -2=(2*N-2) - 2=N-14.D0+D2=2*N-1D0=2*N-1-(N-1)=N完全二叉树的结点个数为1 1 ，则它的叶结点个数为（NOIP2005)E. 6A. 4 B.3 C.5 D. 2 【答案】E。用上题的结论。5. 高度为 n 的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1 的满二叉树。 在这里，树高等于叶结点的最大深度，根结点的深度为0 ，如果某个均衡的二叉树共有 2381

15、个结点， 则该树的树高为（）。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)A. T有

16、n 条边B. T 是连通的C. T 是无环的D. T 有 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 7 C 4 2 3 1 5 4 7 D4 6 53 1 7 2【答案】A。先根遍历=先序遍历（根-左-右），中根遍历=中序遍历（左-根-右），后根遍历=后序遍历（左-右-根）。中

17、序遍历保证了左子树的所有结点在它左边，右子树的结点在它右边。过程如下：后用先序遍历结果，找到父结点， 然后按照中序遍历结果将其左右子树分开；然后再从先序遍历结果中再找到左子树的根结点，再重复以上操作直到所有结点归位。先序： 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再次划

18、分为左子树 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 所示。 依照后序遍历的特点（左t右t根），得到结果：4 6 5 2 7 3 1 ，故答案为Ao【思考】（ 1 ）已知中序和后序，如何求先序？（2）已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列：_BC_EF_中序序列： BDE_AG_H后序序列

19、： _DC_GH_A数字为节点的编号，下同），中根遍)o( NOIP2008)9. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6历 2 4 1 5 7 3 6 ，则该二叉树的后根遍历是（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 31【答案】 Bo10. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6数字为结点的编号，以下同），后根遍历是 3 2 5 6 4 1 ，则该二叉树的可能的中根遍历是（)o( NOIP2006)A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 1 3 5 4 6

20、 D. 2 3 1 4 6 5【答案】B。先序遍历和后序遍历不能确定唯一中序遍历，对于本题的结果可以是：2 3 1 5 46 或者 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

21、, c, e, d B. b, c, a, e, dC. 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、NB、2N C、2N-1 D、2N+1 E、2AN-1【答案】C。满二叉树的结点个数为（根结点的深度为1），其叶子节点的个数为，所以“结点个数” =“叶子节点” *2-1=2N-1 。五、算法1. 近 20年来，许多计算机专家都大力推崇递归算法，认为它

22、是解决较复杂问题的强有力的 工具。在下列关于递归算法的说法中，正确的是（）。（ NOIP2007）A. 在1977年前后形成标准的计算机高级语言“F0RTRAN7”禁止在程序使用递归，原因之 一是该方法可能会占用更多的内存空间B. 和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些C. 对于较复杂的问题，用递归方式编程一般比非递归方式更难一些D. 对于已经定义好的标准数学函数sin（x）,应用程序中的语句"y=sin（sin（x）;”就是-种递归调用。【答案】 A。2. 在下列各种排序算法中， 不是以“比较” 作为主要操作的算法是 （）（NOIP2006）A. 选择排序B.

23、 冒泡排序C. 插入排序D. 基数排序【答案】0基于“比较”的排序：冒泡、选择、插入、快速、归并、堆、希尔等；而“非比较” 的排序：计数排序、桶排序、基数排序等。3. 设字符串S="Olympic" ，S的非空子串的数目是（）。（NOIP2008）A. 28B. 29 C . 16 D . 17【答案】A。串长为1的子串有7个，串长为2的子串有6个，串长为 7的子串有1个, 共 7+6+5+2+1=28。4. 将数组 8， 23， 4， 16， 77， -5， 53， 100中的元素按从小到大的顺序排列，每次可以交 换任意两个元素，最少需要交换（）次。（ NOIP2008）

24、A. 4 B . 5 C . 6 D . 7【答案】B。选择排序，第1次是将第1个元素与右边7个元素中最小的一个交换，第 2次是将 第 2 个元素与右边 6 个元素中最小的一个交换， 。 若当前元素已是其余元素中最小的， 则不 需要交换。5. 对有序数组 5 ， 13， 19， 21， 37， 56，元素 19 的查找长度（比较次数）是（）。64， 75， 88， 92， 100 进行二分查找，成功查找NOIP2008）A. 1B【答案】B。首先与中间元素56 比较，比 56 小，则继续在56 左侧的 5 个元素中查找；与这个元素的中间元素 19 比较，相等，则找到，所以只需要比较 2次6.

25、由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靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有种摆法。（NOIP2OO8）【答案】12,4。

26、由于要求黑皮的书排在一起，所以把C和D做为一个排列的对象，故3个对象的全排列为，而C和D可以互换位置，所以第一空的解为：=12。 红皮书要摆在一起，黑皮书要摆在一起，所以我们将A和B作为一个排列对象， C和D作为一个排列对象，另外 A必须比C靠左，则必然是 AB空，由于A和B可以互换（=2），C和D 可以互换（=2），所以摆法有 2X 2=4种。2. 有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为 。（ NOIP2008）城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市415307

27、9城市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)=。(提示：先固定一个数，对于其余

28、的 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

29、(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 种。利用加法原理，得到这个递推式。由于它是二维的，所以我们可以用填表的方法来求解岀答案，每个单元格中的数等于它左下方数+下方数x r。r=1r=2r=3n=613190n=511525n=4176n=3131n=2110n=11004. NOIP2007 第

30、 2 题（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街,5条东西向的横街。现要从西南角的 A走到东北角的B,最短的走法共有多少种？ BA【答案】210。递推：设f（i,j）表示到达第i行（横街）、第j列（纵街）时的最短走法，故可以写岀递推式:(i,j)=f(i,j-1)+f(i-1,j)f(i,j-1)f(i,j)f(i-1,j)15153570126210141020355684136101521281234567A1111111组合:无论怎么走法，每种走法最终均是由向上走 4 步，向右走 6 步组成，一共 10 步，所以全部 走法是从 10 步里选出其中的 4

31、 步向上走（其余 6 步向右走），即 （种）。5. （寻找假币） 现有 80 枚硬币， 其中有一枚是假币， 其重量稍轻， 所有真币的重量都相同， 如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第 1 次的称重 方法。请写出你的结果： 。（ NOIP2006）【答案】 4，第一步：分成 3 组： 27， 27，26，将前 2 组放到天平上。若第 1 组与第 2组相等，则假币在第 3 组中；若第 1组比第 2组轻，则假币在第 1组中，否则就 在第 2 组中。以此类推，第 2 步： 9 9 927 枚）或 9 9 8 （26 枚）；第 3 步： 3 3 39 枚）或 3 3

32、2 （ 8 枚）第 4 步： 1 1 13 枚）或 1 1 （2 枚）6. （取石子游戏） 现有 5 堆石子，石子数依次为 3 ， 5， 7， 19，50，甲乙两人轮流从任一 堆中任取（每次只能取自一堆，不能不取） , 取最后一颗石子的一方获胜。甲先取，问甲有没有 获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取 多少？请写出你的结果： 。（ NOIP2006）【答案】从 50 中取走 32 粒剩余 18 粒是正确的。算法： 从其中一堆中取 n 个，使得剩余的所有数目正好是“必负局（此时先取必输的局面）”。 所谓“必负局”是指把剩余的每一堆的数目都转化成二进制的数， 然后把它们相加，规定做不进位的加法（也就是异或运算），即 0+0 = 0, 1+0 = 0, 0+1 = 1,1+1 = 0 （不进位），如果所 得和是 0（多个 0）