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

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

【摘要】：　　　　（　　）19．全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是　　　　（　　）1．小陈现有2个任务A、B要完成，每个任务分别有若干步骤如下：A＝a1→a2→a3，B＝b1→b2→b3→b4→b5。试计算小陈饭前已做的可能的任务步骤序列共有＿＿＿种。它由我国国际互联网络信息中心正式注册并运行。

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

一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案）。

1．关于图灵机下面的说法哪个是正确的　　　　（　　）

A．图灵机是世界上最早的电子计算机

B．由于大量使用磁带操作，图灵机运行速度很慢

C．图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用

D．图灵机只是一个理论上的计算模型

2．关于计算机内存下面的说法哪个是正确的　　　　（　　）

A．随机存储器的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的

B．1MB内存通常是指1024×1024字节大小的内存

C．计算机内存严格说来包括主存、高速缓存和寄存器三个部分

D．一般内存中的数据即使在断电的情况下也能保留2个小时以上

3．关于BIOS下面说法哪个是正确的　　　　（　　）

A．BIOS是计算机基本输入输出系统软件的简称

B．BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序

C．BIOS一般由操作系统厂商来开发完成

D．BIOS能供提各种文件拷贝、复制、删除以及目录维护等文件管理功能

4．关于CPU下面哪个说法是正确的　　　　（　　）

A．CPU全称为中央处理器（或中央处理单元）

B．CPU可以直接运行汇编语言

C．同样主频下，32位的CPU比16位的CPU运行速度快一倍

D．CPU最早是由Intel公司发明的

5．关于ASCII，下面哪个说法是正确的　　　　（　　）

A．ASCII码就是键盘上所有键的唯一编码

B一个ASCII码使用一个字节的内存空间就能够存放

C．最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码

D．ASCII码是英国人主持制定并推广使用的

6．下列软件中不是计算机操作系统的是　　　　（　　）

A．Windows

B．LINUX

C．OS/2

D．WPS

7．关于互联网，下面的说法哪一个是正确的　　　　（　　）

A．新一代互联网使用的IPv6标准是IPv5标准的升级与补充

B．互联网的入网主机如果有了域名就不再需要IP地址

C．互联网的基础协议为TCP/IP协议

D．互联网上所有可下载的软件及数据资源都是可以合法免费使用的

8．关于HTML下面哪种说法是正确的　　　　（　　）

A．HTML实现了文本、图形、声音乃至视频信息的统一编码

B．HTML全称为超文本标记语言

C．网上广泛使用的Flash动画都是由HTML编写的

D．HTML也是一种高级程序设计语言

9．关于程序设计语言，下面哪个说法是正确的　　　　（　　）

A．加了注释的程序一般会比同样的没有加注释的程序运行速度慢

B．高级语言开发的程序不能使用在低层次的硬件系统（如自控机床）或低端手机上

C．高级语言相对于低级语言更容易实现跨平台的移植

D．以上说法都不对

10．已知大写字母A的ASCII编码为65（十进制），则大写字母J的十进制ASCII编码为　　　　（　　）

A．71

B．72

C．73

D．以上都不是

11．十进制小数125.125对应的八进制数是　　　　（　　）

A．100.1

B．175.175

C．175.1

D．100.175

12．有六个元素FEDCBA从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？　　　　（　　）

A．EDCFAB

B．DECABF

C．CDFEBA

D．BCDAEF

13．表达式a*（b＋c）－d的后缀表达式是　　　　（　　）

A．abe*d＋－

B．abc＋*d－

C．abc*＋d－

D．一＋*abcd

14．一个包含n个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为　　（　　）

A．2n＋1

B．2n－1

C．n－1

D．n＋1

15．快速排序最坏情况下的算法复杂度为　　　　（　　）

A．O（log₂ n）

B．O（n）

C．O（nlog₂n）

D．O（n²）

16．有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素　　　　（　　）

A．11次

B．12次

C．13次

D．14次

17．排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的　　　　（　　）

A．冒泡排序

B．插入排序

C．归并排序

D．快速排序

18．已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？　　　　（　　）

A．n

B．n＋1

C．n－1

D．n（n－1）

19．全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是　　　　（　　）

A．http://www.noi.com/

B．http://www.noi.org/

C．http://www.noi.cn/

D．http://www.xinxixue.com/

20．在参加NOI系列竞赛过程中，下面哪一种行为是不被严格禁止的　　　　（　　）

A．携带书写工具，手表和不具有通讯功能的电子词典进入赛场

B．在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数

C．通过互联网搜索取得解题思路

D．在提交的程序中启动多个进程以提高程序的执行效率

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

1．小陈现有2个任务A、B要完成，每个任务分别有若干步骤如下：A＝a1→a2→a3，B＝b1→b2→b3→b4→b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如…a2→b2→a3→b3……是合法的，而…a2→b3→a3→b2…是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有＿＿＿种。

2．有如下的一段程序：

1．a:＝1；

2．b:＝a；

3．d:＝－a；

4．e:＝a＋d；

5．c:＝2*d；

6．f:＝b＋e－d；

7．g:＝a*f＋c；

现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通信，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通信花费的时间不计。则这段程序最快可以在＿＿单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。如，若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

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

1．（Pascal）

alt

1．（C＋＋）

alt

2．（Pascal）

alt

2．（C＋＋）

alt

3．（Pascal）

alt

3．（C＋＋）

alt

4．（Pascal）

alt

4．（C＋＋）

alt

四、完善程序（前8空，每空3分，后2空，每空2分，共28分）

1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如当数列为4，-5，3，2，4时，输出9和3；数列为1，2，3，-5，0，7，8时，输出16和7。

程序（Pascal）：

alt

2．（国王放置）在n×m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法？假设国王放置在第（x，y）格，国王的攻击的区域是：（x－1，y－1），（x－1，y），（x－1，y＋1），（x，y－1），（x，y＋1），（x＋1，y－1），（x＋1，y），（x＋1，y＋1）。读入三个数n，m，k，输出答案。题目利用回溯法求解。棋盘行标号为0－n－1，列标号为0－m－1。

程序（Pascal）：

alt

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

一、单项选择题

1．D　最早的电子计算机是ENIAC；图灵机是计算机模型，没有运行速度，更谈不上磁带操作；图灵本人在二战中破译德军密码系统中发挥了重要作用，而不是图灵机发挥作用；图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，构造出一台假想的机器。

2．B　RAM不是位置随机，而是随时访问；1MB＝1024KB＝1024×1024B；高速缓存和寄存器的物理实现是集成在CPU中，这两部分不属于冯·诺依曼体系中的五大部分的任意一个部分；显然内存中数据断电后会消失。

3．A　BIOS是英文“Basic Input Output System”的缩略语，直译过来后中文名称就是“基本输入输出系统”。BIOS只存一些系统启动的基本信息，这些设备的驱动程序是不存在的；BIOS一般由单独的芯片厂家生产。

4．A　CPU只能运行二进制代码也就是机器语言；C中位数只能说明处理的字长，所在的系统硬件指令不同，速度难以比较；Intel公司推出了世界上第一台微处理器，但是之前CPU已经由电子管与晶体管实现。

5．B　ASCII是美国标准信息交换码，用一个字节保存，扩展的ASCII用两个字节保存，汉字编码不是ASCII的内容。

6．D　WPS文本编辑软件，OS/2是苹果公司的操作系统。

7．C　IPv6与IPv5一点关系也没有，IPv6是IPv4的替代版本；IP是必须的，域名是为了方便记忆；D中注意盗版非法。

8．B　文本、图形甚至声音和视频的编码没有统一；Flash是由Adobe公司的Flash软件制作；HTML只不过是组合成一个文本文件的一系列标签，不是高级语言。

9．C　注释是被电脑忽略的；高级语言开发的程序可以使用低层硬件，编译后生成目标代码。

10．D　65＋9＝74。

11．C。

12．C　C中当C出栈，此时F是被压在E下，不可能先于E出栈。

13．B　该树见图1。

alt

图1　第13题图

14．D　假设一棵树的边数为v，叶节点个数为x，则所有边分为两类：两端是分支节点（n－1条）或有一端时叶子节点（x条），x＋n－1＝v，v≤2n，所以叶节点数量最多为n＋1。

15．D　当输入数据是有序的，快速排序也就退化成了冒泡排序。

16．B　2¹¹－1＝2047，2¹²－1＝4095，排序二叉树高度为12，则只需要12次就可以定位到所需元素。

17．D　快速排序会使数据左右位置调换。

18．A　n个点首尾相接，构成环。

19．C　com一般用于商业性的机构或公司；org是顶级域名的一种类型，通常表示此域名独立于其他种类。通常，非营利组织（Other Organizations）以及工业标准组织会采用此域名后缀；cn，Internet网络域名，国家顶级域名，表示中国网站。它由我国国际互联网络信息中心（Inter NIC）正式注册并运行。

20．B。

二、问题求解

1．70　解析：完成任务可能情况有

｛a1，a2，a3，b1｝，｛a1，a2，a3，b1，b2｝

｛a1，a2，a3，b1，b2，b3｝，｛a1，a2，a3，b1，b2，b3，b4｝

alt