第十三届全国青少年信息学奥林匹克联赛初赛.ppt

《第十三届全国青少年信息学奥林匹克联赛初赛.ppt》由会员分享，可在线阅读，更多相关《第十三届全国青少年信息学奥林匹克联赛初赛.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第十三届全国青少年信息学奥林匹克联赛初赛试题n1.在以下各项中。（在以下各项中。（D）不是）不是CPU的组成部分。的组成部分。nA.控制器控制器B.运算器运算器C.寄存器寄存器D.主板主板E.算术算术逻辑单元逻辑单元(ALU)2.在关系数据库中在关系数据库中,存放在数据库中的数据的逻辑结构以存放在数据库中的数据的逻辑结构以(E)为主。为主。A.二叉树二叉树B.多叉树多叉树C.哈希表哈希表D.B+树树E.二维表二维表n点评：数据库管理系统点评：数据库管理系统(DBMS)。最典型的。最典型的DBMS是关系数据库管理是关系数据库管理系统系统(RDBMS)。RDBMS将信息存储在由行和列组成的表中。如

2、果您将信息存储在由行和列组成的表中。如果您使用过电子表格，那么可能比较熟悉如何将数据存储在表中。数据库使用过电子表格，那么可能比较熟悉如何将数据存储在表中。数据库表中的每一列都包含一个不同类型的属性，而每一行则对应于单个记表中的每一列都包含一个不同类型的属性，而每一行则对应于单个记录。例如，在客户表中，列可能包含姓名、地址、电话号码和帐户信录。例如，在客户表中，列可能包含姓名、地址、电话号码和帐户信息；而每一行则是一个单独的客户。息；而每一行则是一个单独的客户。3.在下列各项中，只有（在下列各项中，只有（D）不是计算机存储容量的常）不是计算机存储容量的常用单位。用单位。A.ByteB.KBC.

3、MBD.UBE.TBn点评：点评：1kB=1024B(kB-kilobajt)千千n1MB=1024kB(MB-megabajt)兆兆1GB=1024MB(GB-gigabajt)吉吉n1TB=1024GB(TB-terabajt)太太1PB=1024TB(PB-petabajt)拍拍n1EB=1024PB(EB-eksabajt)艾艾1ZB=1024EB(ZB-zettabajt)皆皆n1YB=1024ZB(YB-jottabajt)佑佑1BB=1024JB(BB-brontobajt)n4ASCII码的含义是（B）。nA.二十进制转换码B.美国信息交换标准代码C.数字的二进制数码5在在Pa

4、scal语言中，表达式语言中，表达式(23or2xor5)的值是（的值是（）A.18B.1C.23D.32E.24n点评：点评：a a b b Not a Not a a and b a and b a or b a or b a a xorxor b b false false false false true true false false false false false false false false true true true true false false true true true true true true false false false false fal

5、se false true true true true true true true true false false true true true true false false 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，说穿了，就是直接对整数在内存中的二进制位进行操作。比如，6and11。6的二进制是的二进制是110，11的二进制是的二进制是1011，那么，那么6and11的结果就是的结果就是2，它是二进制对应位进行逻辑运算的结果（它是二进制对应位进行逻

6、辑运算的结果（0表示表示False，1表示表示True，空位都当空位都当0处理）。处理）。23or2xor5运算的优先顺序为：运算的优先顺序为：括号括号函数函数NOT*、/、div、mod、and+、or、xor关系运算（关系运算（、=、=、）6在在Pascal语言中，判断整数语言中，判断整数a等于等于0或或b等于等于0或或c等等于于0的正确的条件表达式是（的正确的条件表达式是（B）nA.not(a0)or(b0)or(c0)nB.not(a0)and(b0)and(c0)nC.not(a=0)and(b=0)or(c=0)nD.(a=0)and(b=0)and(c=0)nE.not(a=0)

7、or(b=0)or(c=0)7.地面上有标号为地面上有标号为A、B、C的的3根细柱根细柱,在在A柱上放有柱上放有10个直径相同中间有孔的圆盘个直径相同中间有孔的圆盘,从上到下次依次编号为从上到下次依次编号为1,2,3,，将，将A柱上的部分盘子经过柱上的部分盘子经过B柱移入柱移入C柱柱,也可以在也可以在B柱上暂存。如果柱上暂存。如果B柱上的操作记录为：柱上的操作记录为：“进，进，出，进，进，出，进，进，出，出，进，进，出，进，出，出进，进，出，出，进，进，出，进，出，出”。那么。那么,在在C柱上柱上,从下到上的盘子的编号为（从下到上的盘子的编号为（D）。）。A.243657B.241257C.2

8、43176D.243675E.2143758.与十进制数与十进制数17.5625相对应的相对应的8进制数是（进制数是（B）。）。A.21.5625B.21.44C.21.73D.21.731E.前前4个答案都不对个答案都不对点评：（点评：（10001.1001）29.欧拉图欧拉图G是指可以构成一个闭回路的图，且图是指可以构成一个闭回路的图，且图G的每一条边恰好在的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中这个闭回路上出现一次（即一笔画成）。在以下各个描述中,不一定不一定是欧拉图的是：（是欧拉图的是：（D）。）。A.图图G中没有度为奇数的顶点中没有度为奇数的顶点B.包括欧

9、拉环游的图包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径欧拉环游是指通过图中每边恰好一次的闭路径)C.包括欧拉闭迹的图包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径欧拉迹是指通过途中每边恰好一次的路径)D.存在一条回路存在一条回路,通过每个顶点恰好一次通过每个顶点恰好一次E.本身为闭迹的图本身为闭迹的图一、一、问题问题的提出的提出图论图论起源于起源于18世世纪纪，1736年瑞士数学家欧拉年瑞士数学家欧拉发发表表了了图论图论的第一篇的第一篇论论文文“哥尼斯堡七哥尼斯堡七桥问题桥问题”。在当。在当时时的哥的哥尼斯堡城有一条横尼斯堡城有一条横贯贯全市的普雷格全市的普雷格尔尔河，河

10、中的两个河，河中的两个岛岛与两岸用七座与两岸用七座桥联结桥联结起来，起来，见图见图(1)。当。当时时那里的居民那里的居民热热衷于一个衷于一个难题难题：游人怎：游人怎样样不重复地走遍七不重复地走遍七桥桥，最后回到，最后回到出出发发点。点。为了解决这个问题，欧拉用个字母代替陆地，作为个顶点，将联结两块陆地的桥用相应的线段表示，如图(2)，于是哥尼斯堡七桥问题就变成了图(2)中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。二、定义二、定义欧拉通路欧拉通路(欧拉迹欧拉迹)通过图中每条边一次且仅一次，通过图中每条边一次且仅一次，并且过每一顶点的通路

11、。并且过每一顶点的通路。欧拉回路欧拉回路(欧拉闭迹欧拉闭迹)通过图中每条边一次且仅一通过图中每条边一次且仅一次，并且过每一顶点的回路。次，并且过每一顶点的回路。欧拉图欧拉图存在欧拉回路的图。存在欧拉回路的图。欧拉图或通路的判定欧拉图或通路的判定(1)无向连通图无向连通图G是欧拉图是欧拉图;G不含奇数度结点不含奇数度结点(G的所有结点度数为偶数的所有结点度数为偶数):(定理定理1)(2)非平凡连通图非平凡连通图G含有欧拉通路含有欧拉通路;G最多有两个奇数度的结点；最多有两个奇数度的结点；(定理定理1的推论的推论)(3)连通有向图连通有向图D含有有向欧拉回路含有有向欧拉回路(即欧拉图即欧拉图);D

12、中每个结点的入度出中每个结点的入度出度度三、无向三、无向图图是否具有欧拉通路或回路的判定是否具有欧拉通路或回路的判定有欧拉通路有欧拉通路连连通，通，图图中只有两个奇度中只有两个奇度顶顶点点(它它们们分分别别是是欧拉通路的两个端点欧拉通路的两个端点)。有欧拉回路有欧拉回路(为为欧拉欧拉图图)连连通，通，图图中均中均为为偶度偶度顶顶点。点。例例1、以下、以下图图形能否一笔画成？形能否一笔画成？解：解：(1)有有4个奇度顶点，无欧拉回路或通路，不能一笔画成。个奇度顶点，无欧拉回路或通路，不能一笔画成。(2)与与(3)都是都是2个奇度顶点，其余均为偶度顶点，具有欧拉通路，可一笔画成。个奇度顶点，其余均

13、为偶度顶点，具有欧拉通路，可一笔画成。(4)图中均为偶度顶点，具有欧拉回路，可一笔画成。图中均为偶度顶点，具有欧拉回路，可一笔画成。10.一个无法靠自身的控制终止的循环称为一个无法靠自身的控制终止的循环称为“死循环死循环”，例如在，例如在C语言语言程序中，语句程序中，语句“while(1)printf(*)；”就是一个死循环，运行它将无就是一个死循环，运行它将无休止地打印休止地打印*号。下面关于死循环的说法中号。下面关于死循环的说法中,只有（只有（A）是正确的。）是正确的。A.不存在一种算法不存在一种算法,对任何一个程序及相应的输入数据对任何一个程序及相应的输入数据,都可以判断是都可以判断是否

14、会出现死循环否会出现死循环,因而因而,任何编译系统都不做死循环检查任何编译系统都不做死循环检查B.有些编译系统可以检测出死循环有些编译系统可以检测出死循环C.死循环属于语法错误，死循环属于语法错误，既然编译系统能检查各种语法错误，既然编译系统能检查各种语法错误，当然也当然也能检查出死循环能检查出死循环D.死循环与多进程中出现的死循环与多进程中出现的“死锁死锁”差不多，而死锁是可以检测的，因差不多，而死锁是可以检测的，因而，死循环也是可以检测的而，死循环也是可以检测的E.对于死循环，只能等到发生时做现场处理对于死循环，只能等到发生时做现场处理,没有什么更积极的手段没有什么更积极的手段二、二、不定

15、项选择题不定项选择题（共（共10题，每题题，每题1.5分，共计分，共计15分。每题正确答案的个数大于或等于分。每题正确答案的个数大于或等于1。多选或少选均。多选或少选均不得分）。不得分）。11.设设A=B=true，C=D=false，以下逻辑运算表达式值为真，以下逻辑运算表达式值为真的有（的有（ABC）。）。A.(AB)(CDA)B.(AB)C)D)C.A(BCD)DD.(A(DC)B12.命题命题“PQ”可读做可读做P蕴含蕴含Q，其中其中P、Q是两个独立的是两个独立的命题命题.只有当命题只有当命题P成立而命题成立而命题Q不成立时，不成立时，命题命题PQ的的值为值为false，其它情况均为其

16、它情况均为true.与命题与命题PQ等价的逻辑等价的逻辑关系式是（关系式是（AD）。）。A.PQB.PQC.(PQ)D.(QP)点评：假设点评：假设PQ为假，为假，A选项为假，则选项为假，则P和和Q只能均为假，只能均为假，因此只有当命题因此只有当命题P成立而命题成立而命题Q不成立时，不成立时，命题命题PQ的的值为值为false。13.(2070)16+(34)8的结果是（的结果是（ABD）。）。A.(8332)10B.(208C)16C.(100000000110)2D.(20214)8点评：（点评：（10000010001100）214.已知已知7个节点的二叉树的先根遍历是个节点的二叉树的先

17、根遍历是1245637(数字数字为结点的编号，以下同为结点的编号，以下同)，后根遍历是后根遍历是4652731，则该则该二叉树的可能的中根遍历是（二叉树的可能的中根遍历是（ABD）A.4265173B.4256137C.4231547D.4256173ABCDFE前序遍历：前序遍历：当在节点左面时可以处理该当在节点左面时可以处理该节点，用节点左边的黑色方框表示。节点，用节点左边的黑色方框表示。中序遍历：中序遍历：当在节点下面时可以当在节点下面时可以处理该节点，用节点下边的黑色方框处理该节点，用节点下边的黑色方框表示。表示。ABCDFE前序遍历为：前序遍历为：ABCDEF中序遍历：中序遍历：CB

18、DAEF后序遍历：后序遍历：当在节点右面时可以处理该节点，用当在节点右面时可以处理该节点，用节点右边的黑色方框表示。节点右边的黑色方框表示。ABCDFE后遍历：后遍历：CDBFEA15.冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文、和英语的三科成绩，如果还存放三科成绩的总分，了学生的数学、语文、和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看做冗余数据。冗余数据往往会造成数据的不一致，例如则总分就可以看做冗余数据。冗余数据往往会造成数据的不一致，例如上面上面4个数据如果都是输入的，由于操作错误使

19、总分不等于三科成绩之和，个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，就会产生矛盾。下面关于冗余数据的说法中，正确的是（正确的是（BC）。）。A.应该在数据库中消除一切冗余数据应该在数据库中消除一切冗余数据B.与用高级语言编写的数据处理系统相比，与用高级语言编写的数据处理系统相比，用关系数据库编写的系统更用关系数据库编写的系统更容易消除冗余数据容易消除冗余数据C.为了提高查询效率，为了提高查询效率，在数据库中可以适当保留一些冗余数据，在数据库中可以适当保留一些冗余数据，但更新但更新时要做相容性检验时要做相容性检验D.做相容性检验会降低效率，

20、做相容性检验会降低效率，可以不理睬数据库中的冗余数据可以不理睬数据库中的冗余数据16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（ABD）。A.gccB.g+C.TurboCD.freepascal17.以下断电之后将仍能保存数据的有（AB）。A.硬盘B.ROMC.显存D.RAM18.在下列关于计算机语言的说法中，正确的有（在下列关于计算机语言的说法中，正确的有（CD）。）。A.高级语言比汇编语言更高级，高级语言比汇编语言更高级，是因为它的程序的运行效率更高是因为它的程序的运行效率更高B.随着随着Pascal、C等高级语言的出现，等高级语言的出现，机器语言和汇编语言已经退出机

21、器语言和汇编语言已经退出了历史舞台了历史舞台C.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上算机上D.C是一种面向过程的高级计算机语言是一种面向过程的高级计算机语言点评：点评：高级语言具有可移植性高级语言具有可移植性，就是说在一种型号，就是说在一种型号CPU的机器上的机器上编写了程序到另外编写了程序到另外CPU的机器上一样能够运行；而汇编语言不具有可的机器上一样能够运行；而汇编语言不具有可移植性。这是最主要的区别。移植性。这是最主要的区别。高级语言易学易懂易上手，而且容易维护；汇编语言正好相反。高级语言易学易懂易上手

22、，而且容易维护；汇编语言正好相反。高级语言基本上不能对硬件直接编程，而汇编语言可以。所以一般单高级语言基本上不能对硬件直接编程，而汇编语言可以。所以一般单片机开发或者嵌入式系统的开发一般就选择汇编语言和片机开发或者嵌入式系统的开发一般就选择汇编语言和C语言编程语言编程19.在下列关于算法复杂性的说法中，在下列关于算法复杂性的说法中，正确的有（正确的有（BC）。）。A.算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间B.算法的时间复杂度，是指对于该算法的一种或几种主要的运算，算法的时间复杂度，是指对于该算法的一种或几种主要的运算

23、，运运算的次数与问题的规模之间的函数关系算的次数与问题的规模之间的函数关系C.一个问题如果是一个问题如果是NPC类的，类的，就意味着在解决该问题时，就意味着在解决该问题时，不存在一不存在一个具有多项式时间复杂度的算法个具有多项式时间复杂度的算法.但这一点还没有得到理论上证实，但这一点还没有得到理论上证实，也没有被否定也没有被否定D.一个问题如果是一个问题如果是NP类的，与类的，与C有相同的结论有相同的结论时间复杂度时间复杂度并不是表示一个程序解决问题需要花多少并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多时间，而是当问题规模扩大后，程序需要的时间长

24、度增长得有多快。也就是说，应该看当这个数据的规模变大到数百倍后，程序快。也就是说，应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。万倍。像冒泡排序、插入排序等，数据扩大像冒泡排序、插入排序等，数据扩大2倍，时间变慢倍，时间变慢4倍的，属倍的，属于于O(n2)的复杂度。的复杂度。20.近近20年来，年来，许多计算机专家都大力推崇递归算法，认为它是解决较许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具复杂问题的强有力的工具.在下列关于递归的说法中，在下列关于递归的说

25、法中，正确的是（正确的是（AC）。）。A.在在1977年前后形成标准的计算机高级语言年前后形成标准的计算机高级语言FORTRAN77禁止在程序使用禁止在程序使用递归，递归，原因之一是该方法可能会占用更多的内存空间原因之一是该方法可能会占用更多的内存空间.B.和非递归算法相比，和非递归算法相比，解决同一个问题，解决同一个问题，递归算法一般运行得更快一些递归算法一般运行得更快一些C.对于较复杂的问题，对于较复杂的问题，用递归方式编程往往比非递归方式更容易一些用递归方式编程往往比非递归方式更容易一些D.对于已定义好的标准数学函数对于已定义好的标准数学函数sin(x)，应用程序中的语句应用程序中的语句

26、“y=sin(sin(x);”就是一种递归调用就是一种递归调用三问题求解（共三问题求解（共2题，每题题，每题5分，共计分，共计10分）分）1给定给定n个有标号的球，标号依次为个有标号的球，标号依次为1，2，n。将这。将这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=7，

27、r=4时，时，S(7,4)=350。2N个人在操场里围成一圈，将这个人在操场里围成一圈，将这N个人按顺时针方向从个人按顺时针方向从1到到N编号，然后从第一个人起，每隔一个人让下一个人离开编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，例如，J(5)=3，J(10)=5，等等。，等等。则则J(400)=289。（提示：对。（提示：对N=2m+r进行分析，其进行分析，其中中0r2m）。）。