第十六届全国青少年信息学奥林匹克联赛初赛试题及解析

时间：2023-02-24 理论教育版权反馈

【摘要】：迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。另外，独木桥上最多能承受两个人同时经过，否则将会坍塌。摩尔定律是指IC上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。美籍匈牙利科学家冯·诺依曼最先提出程序存储的思想，并成功将其运用在计算机的设计之中，根据这一原理制造的计算机被称为冯·诺依曼结构计算机。

6.5.1　第十六届全国青少年信息学奥林匹克联赛初赛试题

一、单项选择题

1．2E＋03表示　　　　（　　）

A．2.03

B．5

C．8

D．2000

2．一个字节（Byte）由（　　）个二进制位组成。　　　　（　　）

A．8

B．16

C．32

D．以上都有可能

3．以下逻辑表达式的值恒为真的是　　　　（　　）

A．P∨（ alt P∧Q）∨（ alt P∧ alt Q）

B．Q∨（ alt P∧Q）∨（P∧ alt Q）

C．P∨Q∨（P∧ alt Q）∨（ alt P∧Q）

D．P∨ alt Q∨（P∧ alt Q）∨（ alt P∧ alt Q）

4．LINUX下可执行文件的默认扩张名为　　　　（　　）

A．.exe

B．.com

C．.dll

D．以上都不是

5．如果树根算是第一层，那么一棵n层的二叉树最多有（　　）个节点。　　　　（　　）

A．2ⁿ－1

B．2ⁿ

C．2ⁿ＋1

D．2^n＋1

6．提出“存储程序”的计算机工作原理的是　　　　（　　）

A．克劳德·香农

B．戈登·摩尔

C．查尔斯·巴比奇

D．冯·诺依曼

7．设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（　　）也成立。　　　　（　　）

A．YXZ

B．ZXY

C．XYZ

D．XZY

8．Pascal语言、C语言和C＋＋语言都属于　　　　（　　）

A．面向对象语言

B．脚本语言

C．解释性语言

D．编译性语言

9．前缀表达式“＋3*2＋512”的值是　　　　（　　）

A．23

B．25

C．37

D．65

10．主存储器的存取速度比中央处理器（CPU）的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了　　　　（　　）

A．寄存器

B．高速缓存

C．闪存

D．外存

11．一个字长为8位的整数的补码是11111001，则它的原码是　　　　（　　）

A．00000111

B．01111001

C．11111001

D．1000111

12．基于比较的排序时间复杂度的下限是（　　），其中n是待排的元素个数。　　　　（　　）

A．O（n）

B．O（n log n）

C．O（log n）

D．O（n²）

13．一个自然数在十进制下有n位，则它在二进制下的位数与（　　）最接近。　　　　（　　）

A．5n

B．nlog₂ 10

C．1×log₂ n

D．10ⁿlog₂ n

14．在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是　　　　（　　）

A．＜a url＝"http://www.noi.cn"欢迎访问NOI网站＜/a＞

B．＜a href＝ "http://www.noi.cn"＞欢迎访问NOI网站＜/a＞

C．＜a＞http://www.noi.cn＜/a＞

D．＜a name＝"http://www.noi.cn"＞欢迎访问NOT网站＜/a＞

15．元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第一个出栈的是R3，那么第5个出栈的不可能是　　　　（　　）

A．R1

B．R2

C．R4

D．R5

16．（Pascal）双向链表中有两个指针域llink和rlink，分别指向该节点的前驱及后继。

设p指向链表中的一个节点，它的左右节点均非空。现要求删除节点p，则下面语句序列中错误的是　　　　（　　）

A．p alt .rlink alt .llink＝p alt .rlink；P alt .llink alt .rlink＝p alt .llink；dispose（p）；

B．p alt .llink alt .rlink＝p alt .rlink；p alt .rlink alt .llink＝p alt .llink；dispose（p）；

C．p alt .rlink alt .llink＝p alt .llink；p alt .rlink alt .llink alt .rlink＝p alt .rlink；dispose（p）；

D．p alt .llink alt .rlink＝p alt .rlink；p alt .llink alt .rlink alt .llink＝p alt .llink；dispose（p）；

16．（C＋＋）双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点P，则下面语句序列中错误的是　　　　（　　）。

A．p—＞rlink—＞llink＝p—＞rlink；p—＞llink—＞rlink＝p—＞llink；free（p）；

B．p—＞llink—＞rlink＝p—＞rlink；p—＞rlink—＞llink＝p—＞llink；free（p）；

C．p—＞rlink—＞llink＝p—＞llink；p—＞rlink—＞llink—＞rlink＝p—＞rlink；free（p）；

D．p—＞llink—＞rlink＝p—＞rlink；p—＞llink—＞rlink—＞llink＝p—＞llink；free（p）；

17．一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根节点的左子树的节点个数可能是　　　　（　　）

A．2

B．3

C．4

D．5

18．关于拓扑排序，下面说法正确的是　　　　（　　）

A．所有连通的有向图都可以实现拓扑排序

B．对一个图而言，拓扑排序的结果是唯一的

C．拓扑排序中入度为0的节点总会排在入度大于0的节点的前面

D．拓扑排序结果序列中的第一个节点一定是入度为0的点

19．完全二叉树的顺序存储方案，是指将完全二叉树的节点从上至下，从左至右依次存放到一个顺序结构的数组中。假定根节点存放在数组的1号位置，则第k号节点的父节点如果存在的话，应当存放在数组的（　　）号位置。　　　　　（　　）

A．2k

B．2k＋1

C．k／2下取整

D．（k＋1）／2下取整

20．全国青少年信息学奥林匹克系列活动的主办单位是　　　　（　　）

A．教育部

B．科技部

C．共青团中央

D．中国计算机学会

二、问题求解（共2题，每题5分，共计10分）。

1．LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。

举例说明，考虑一个待编码的信息串：“xyx yy yy xyx”。初始词典只有3个条目，第一个为x，编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。现在已知初始词典的3个条目如上述，则信息串“yyxy xx yyxy xyx xx xyx”的编码是＿＿＿＿＿＿

2．队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是“2 3”。当元素2、3也出队后，队列快照是“”，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有＿＿种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，“5 1”、“4 2 2”、“”都是可能的队列快照：而“7”不是可能的队列快照，因为剩下的2个正整数的和不可能是1。

三、阅读程序写结果（共4题，每题8分，共计32分）。

1．（Pascal）

alt

1．（C＋＋）

alt

2．（Pascal）

alt

2．（C＋＋）

alt

3．（Pascal）

alt

提示：

alt

3．（C＋＋）

alt

提示：

alt

4．（Pascal）

alt

4．（C＋＋）

alt

四、完善程序（前4空，每空2.5分，后6空，每空3分，共计28分）。

1．（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可以写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。

程序（Pascal）：

alt

若输入n为2010，则输出 alt 时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。

程序（C＋＋）：

alt

若输入n为2010，则输出 alt 时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。

2．（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一座独木桥走到河的左岸。在伸手不见五指的黑夜里，过桥时必须借助灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多能承受两个人同时经过，否则将会坍塌。每个人单独过独木桥都需要一定的时间，不同的人要的时间可能不同。两个人一起过独木桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间。现在输入N（2≤N＜1000）和这N个人单独过桥需要的时间，请计算总共最少需要多少时间，他们才能全部到达河左岸。

例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲，丙在一起过桥到河的左岸，总时间为2＋1＋4＝7。

程序（Pascal）：

alt

2．程序（C＋＋）：

alt

6.5.2　十六届全国信息学奥林匹克联赛初赛普及试题解析

一、单项选择题

1．D。

2．A。

3．A　B、C中P＝Q＝false，D中p＝false、Q＝true时表达式为假。

4．D　动态链接库英文为DLL（Dynamic Link Library），DLL是一个包含可由多个程序同时使用的代码和数据的库，DLL不是可执行文件。

5．A　当该树为满二叉树时，这棵树拥有最多的节点，一颗n层二叉树有2ⁿ－1节点。

6．D　克劳德·艾尔伍德·香农是美国数学家，信息论的创始人。摩尔定律是指IC上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。摩尔定律是由英特尔名誉董事长戈登·摩尔经过长期观察发现得之。查尔斯·巴比奇是科学管理的先驱者，第一台可编程的机械计算机的设计者。美籍匈牙利科学家冯·诺依曼最先提出程序存储的思想，并成功将其运用在计算机的设计之中，根据这一原理制造的计算机被称为冯·诺依曼结构计算机。世界上第一台冯·诺依曼式计算机是1949年研制的EDVAC，由于他对现代计算机技术的突出贡献，因此冯·诺依曼又被称为“计算机之父”。

7．B　XY＋ZX＝XYX这个等式在3进制下成立，我们不妨把它化成10进制，3X＋Y＋3Z＋X＝9X＋3Y＋X即3Z＝6X＋2Y，由于X、Y、Z分别代表0、1、2，枚举后得出X＝1，Y＝0，Z＝2，这样代入XY×ZX＝（10）₃＋（21）₃＝（21）₁₀＝（210）₃＝（ZXY）₃。

8．D　计算机语言常识，编译是指在应用源程序执行之前，就将程序源代码“翻译”成目标代码（机器语言），因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。但应用程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件才能执行，只有目标文件而没有源代码，修改很不方便。

9．C　运算符号只能作为父节点，而数字是叶节点。中缀表达式是3＋2*（5＋12）＝37，见图1。

alt

图1　第9题图

10．B　高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片组成，容量比较小但速度比主存高得多，接近于CPU的速度。闪存卡是利用闪存技术达到存储电子信息的存储器，一般应用在数码相机、掌上电脑、MP3等小型数码产品中作为存储介质，所以样子小巧，像一张卡片，所以称之为闪存卡。

11．D　正数的补码与原码相同。负数的补码负号位为1，其余位为该数绝对值的原码按位取反后整个数加1。11111001的首位1，作为符号位代表该数是负数，所以保留该位，1111001减1然后取反，再加上符号位1，结果是10000111。

12．B。

13．B。

14．B。

15．B　R3出栈时，R2为栈顶，R1在R2之下，肯定晚于R2之后出栈，R2不可能最后一个出栈，自然不会是第5个出栈。

16．A　A中将p的后继的前驱改为指向p的后继，p的前驱的后继改为指向p的前驱，这样链表就中断了。

17．A　根的左右子树的各自先后序遍历中，所有的节点应该是紧靠在一起，若假设左子树有3个节点，根据前序遍历那3个节点必然是ABC，但根据后序遍历则应该是CBF，这样就矛盾了。

18．D　A中，当图中有环，必然无法拓扑排序；B中，同一时刻，入度为0的点不唯一，拓扑排序也就不唯一；C中，如下1—3—2也是正确的拓扑排序，但3却在2之前。

　　1→3

19．C　其实就是父节点的编号是多少，稍微寻找一下规律便知道，当k是偶数，父节点是k／2，当k是奇数，父节点是（k－1）／2，综合一下就是k／2取下整。

20．D。

二、问题求解

1．2-2-1-2-3-1-1-3-4-1-2-1-3-5-3-6　这等于是一道模拟题，yyxy、xx、xyx加入词典并分别对应4、5、6，但是它们首次出现时时用原有的词条（x、y）来表示。

2．49　3个元素可能是（1，1，6）（1，2，5）（1，3，4）（2，2，4）（2，3，3）。快照中元素个数可能是0，1，2，3，当元素个数为0时，有1种；当元素个数为1时，有6种（1 2 3 4 5 6）；当元素个数为2时，有3×3＋6×2＝21种；当元素个数为3时，有3×3＋6×2＝21种；一共有49种。

三、阅读程序写结果

1．2 20 77 91　在读入x之前，通过3次比较将a1，a2，a3从小到大排好序，然后将x插入适当位置，输出一个由a1，a2，a3，x组成的递增序列。

2．99 101 111　这道题的rsum我们可以代一两个数进行模拟，这个rsum其实就是对进行倒序，i＝rsum其实就是要寻找一些正向与逆向相同的数，这道题也就是要求n～m的回文数。

3．120 112　根据提示空格的ASCII码最小，这道题的循环也就是寻找字符串中ASCII码最大的两个字符。显然数字小于大写字母小于小写字母，所以答案一定在小写字母中，最大的两个小写字母是x，p，他们与a分别间隔23个与15个字母，ord（ml）＝120, ord（m2）＝112。

4．1

四、完善程序（Pascal）

1．①tmp:＝true

②p［i］

③p［r］:＝i

④p［j］＋p［k］

⑤1004

主程序的第一段是寻找所有不大于，n的素数，对于i，若所有小于i的素数均不能被它整除，则i是素数。③是将这些素数存储到p中。④i＋i是当前需要验证的偶数，j，k是枚举p中的项，若有“p［j］＋p［k］＝i＋i”则表示“i＋i”满足哥德巴赫猜想，并将ans加一。⑤是输出一共有多少需要验证，注意需要将2排除，则一共有1004个偶数。

2．①num＜＝2

②go（LEFT_TO_RIGHT）

③pos［i］＝LEFT

④time［i］＋go（RIGHT_TO_LEFT）

⑤pos［i］:＝LEFT

go函数分为两部分，一是从右往左走，一是从左往右走，最后状态肯定是2个人从右往左走。①上面的ans是寻找目前在右边的人的最长过桥时间，并统计在右边的人数，当num≤2时，右边人全部走到左边任务就结束了。②是一个普通的回溯，此次过桥时间＋未知的后续的过桥时间，由此将问题缩小规模。当我们需要从左往右走时，显然只需要1个人，这时除了人数以外，与从右往左走相同，判断人是否在左边，然后状态赋值为RIGHT，递归，再将状态改回来。

四、完善程序（C＋＋）

1．①tmp＝1

②p［j］

③p［r］＝i

④p［j］＋p［k］（或p［k］＋p［j］）

⑤1004

2．①num＜＝2（或num＜3或num＝＝2）

②go（LEFT_TO_RIGHT）

③pos［i］＝＝LEFT（或LEFT＝＝pos［i］）

④hour［i］＋go（RIGHT_TO_LEFT）（或go（RIGHT_TO_LEFT）＋hour［i］）

⑤pos［i］＝LEFT

本小题中，LEFT可用true代替，LEFT_TO_RIGHT可用true代替，RIGHT_TO_LEFT可用false代替。