当前位置：文档之家 › 18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)

18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)

  • 格式：doc
  • 大小：277.50 KB
  • 文档页数：16

第十八届全国青少年信息学奥林匹克联赛初赛（普及组Pascal语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意·试题纸共有10页，答题纸共有2页，满分100分。

请在答题纸上作答，写在试题纸上一律无效。

·不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1. 计算机如果缺少（A），将无法正常启动。

A. 内存B. 鼠标C. U盘D. 摄像头2. （B ）是一种先进先出的线性表。

A. 栈B. 队列C. 哈希表（散列表）D. 二叉树解析：1.栈的定义(可参考：_ware/data_structure/web/zhanhuoduilie/栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

(2)当表中没有元素时称为空栈。

(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。

每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

2.队列：定义：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

（1）允许删除的一端称为队头（Front）。

（2）允许插入的一端称为队尾（Rear）。

（3）当队列中没有元素时称为空队列。

（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

队列的修改是依先进先出的原则进行的。

新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。

退出队列的次序只能是a1，a2，…，an。

3.哈希表(散列表)散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。

这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。

从而达到在O(1)时间内就可完成查找。

哈希表存在散列表的冲突现象：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。

该现象称为冲突(Collision)或碰撞。

发生冲突的两个关键字称为该散列函数的同义词(Synonym)。

【例】上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。

----------------------------------------4.在计算机科学中，二叉树是每个结点最多有两个子树的有序树。

通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）,次序不能颠倒。

·二叉树的5种形态：·二叉树的遍历：3. 目前计算机芯片（集成电路）制造的主要原料是（A），它是一种可以在沙子中提炼出的物质。

A. 硅B. 铜C. 锗D. 铝4. 十六进制数9A在（B ）进制下是232.A. 四B. 八C. 十D. 十二解析：9A 十六, 先转化成十进制＝9*162-1 +10*161-1十进制＝154十进制, 再转化成二进制=二进制＝10 011 010 (从最右边起三个一组,分别转换成十进制数字, 就得到八进制表示的数) =2 3 2八进制注：十进制,八进制和十六进制互化应以二进制作为桥梁，将二进制转化成16或8进制：以小数点为界分别向左右每4（或3）个数字为一组进行分组，每组分别转化成二进制数，最后合并在一起，并把首0去掉（尾0不可以去）。

如：( 001 101 001)2=(151)8(0001 0110.0101 1011)2=(16.5B)165.（C）不属于操作系统。

A. WindowsB. DOSC. PhotoshopD. NOI Linux6. 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（C）。

解析：从题目“中序遍历是BAC”得知:还原此二叉树可能是以下几种情况:A. ABC +中序遍历是BAC，还原得到：B. CBA +中序遍历是BAC，还原得到：C. ACB 还原得到：这两个树的中序遍历都不是BAC。

D. BAC 中序遍历是BAC，还原得到：前序：先根节点，然后遍历左子树,最后遍历右子树，根-左-右。

中序：先遍历左子树，再是根节点，最后遍历右子树，左-根-右后序：先遍历左子树，再遍历右子树，最后是根节点，左-右-根在每个左右子树也遵守以上各自规则！A. 显示器：三星，LG，戴尔，宏碁，HP……B. CPU ：INTEL ，AMD，台湾VIA 威盛... ...C. 内存：金士顿Kingston，威刚，海盗船等D. 鼠标：双飞燕雷柏(Rapoo)罗技(Logitech) 大水牛... ...8. 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列：5,4,3,2,1 需要执行（C）次操作，才能完成冒泡排序。

A. 0B. 5C. 10D. 15冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。

即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。

然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。

至此第一趟结束，将最大的数放到了最后。

在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

如此下去，重复以上过程，直至最终完成排序。

此题答案：冒泡排序最多要排n*(n-1)/2次（本题这样的原本序列是逆序列），最少要n-1次冒泡次数（由小到大的正序列）。

9. 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（A ）计算机。

A. 电子管：电子管元件在运行时产生的热量太多，可靠性较差，运算速度不快，价格昂贵，体积庞大，这些都使计算机发展受到限制B. 晶体管：1954年，美国贝尔实验室研制成功第一台使用晶体管线路的计算机，取名“催迪克”（TRADIC），装有800个晶体管。

晶体管不仅能实现电子管的功能，又具有尺寸小、重量轻、寿命长、效率高、发热少、功耗低等优点C. 集成电路：1958年，美国德州仪器的工程师Jack Kilby发明了集成电路（IC），将三种电子元件结合到一片小小的硅片上。

更多的元件集成到单一的半导体芯片上，计算机变得更小，功耗更低，速度更快D. 超大规模集成电路：60年代初期，美国的基尔比和诺伊斯发明了集成电路，引发了电路设计革命。

随后，集成电路的集成度以每3-4年提高一个数量级的速度增长。

大规模集成电路(LSI) 可以在一个芯片上容纳几百个元件。

到了80 年代，超大规模集成电路(VLSI) 在芯片上容纳了几十万个元件，后来的甚大规模集成电路(ULSI) 上将数量扩充到百万级。

使得计算机的体积和价格不断下降，而功能和可靠性不断增强。

10. 无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。

如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（A）。

分层思想是：对等层之间执行相同的操作，较低的层为它的上一层提供服务。

下面左边是OSI模型，右边是OSI与TCP/IP模型对比：A. 中国公司的经理与波兰公司的经理交互商业文件:B. 军队发布命令:C. 国际会议中，每个人都与他国地位对等的人直接进行会谈:D. 体育比赛中，每一级比赛的优胜者晋级上一级比赛:11.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（B ）。

A. 记录了大量像素块的色彩值来表示图像B. 用点、直线或者多边形等基于数学方程的几何图元来表示图像C. 每个像素点的颜色信息均用矢量表示D. 把文件保存在互联网，采用在线浏览的方式查看图像位图使用我们称为像素的一格一格的小点来描述图像，放大易失真矢量图用点、直线或者多边形等基于数学方程的几何图元来表示图像，放大不易失真12. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（ D）。

A. a, d, c, bB. b, a, c, dC. a, c, b, dD. d, a, b, c 解析：不管d在哪个位置，abc的顺序肯定是先a 后 b , 最后 c入栈的。

13. （B ）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。

A. 资源管理器B. 浏览器C. 电子邮件D. 编译器14. （C ）是目前互联网上常用的E-mail服务协议。

A. HTTPB. FTPC. POP3D. Telnet解析：HTTP：超文本传输协议；FTP：文件传输协议POP3是Post Office Protocol 3的简称，即邮局协议的第3个版本,它规定怎样将个人计算机连接到Internet的邮件服务器和下载电子邮件的电子协议。

它是因特网电子邮件的第一个离线协议标准,POP3允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上,同时删除保存在邮件服务器上的邮件，而POP3服务器则是遵循POP3协议的接收邮件服务器，用来接收电子邮件的。

SMTPSMTP的全称是“Simple Mail Transfer Protocol”，即简单邮件传输协议。

它是一组用于从源地址到目的地址传输邮件的规范，通过它来控制邮件的中转方式。

SMTP 协议属于TCP/IP 协议簇，它帮助每台计算机在发送或中转信件时找到下一个目的地。

SMTP 服务器就是遵循SMTP 协议的发送邮件服务器。

15. （C ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。

而原问题的解就是子问题解的合并。

A. 动态规划B. 贪心C. 分治D. 搜索当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。

对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。

合集下载

noip2018普及组初赛试题+答案

noip2018普及组初赛试题+答案

第24届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2 0 18 年10月13日14： 30-1 6:30选手注意：1、试题纸共有7页，答题纸共有2页，满分100分。

请在答题纸上作答，写在试题纸上得一律无效。

2、不得使用任何电子设备（如计算器、手机、电子词典等）或査阅任何书籍资料。

一、单项选择题（共1 5题，每题2分，共计3 0分;每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A、扫描仪B、键盘C、鼠标D、打印机2、下列四个不同进制得数中，与其它三项数值上不相等得就是（）。

A、（269）16 （注解：2 * l 6 入2 + 6 * 16^ 1 +9 * 1 6八0 = 617）B、（617）10C、（1 15 1）8 （注解：1 * 8入3 + 1 ± 8 ^2 +5 ^8^1+1 * 8^0 = 617）D、（1001101011） 23、1 MB 等于（）。

A、100 0字节B、 1 024字节C、 1 000 X 1000 字节D、1024 X 1024 字节4、广域网得英文缩写就是（）。

A、LANB、WAN （Wide Area Network）C、MAND、LNA5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A、 1 983B、19 8 4C、198 5D、19 8 66、如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 得顺序循环按键，即Ca psLock. A、S、I）、F、CapsLock. A、S、D、F ................. ，屏幕上输岀得第8 1个字符就是字母（）。

A、AB、SC、 DD、a7、根节点深度为0,—棵深度为h得满k（ k > 1 ）叉树，即除最后一层无任何子节点外, 每一层上得所有结点都有k个子结点得树，共有（）个结点。

NOIP2018普及组初赛题详细解析

NOIP2018普及组初赛题详细解析

NOIP2018初赛普及组C++题目+解析二十四届全国青少年信息学奥林匹克联赛初赛——普及组一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机答案:D解析:扫描仪是输出设备显而易见2. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)2答案: D解析：都转成二进制，然后前3个都是1001101001，跟D不同3. 1MB 等于（）。

A. 1000 字节B. 1024 字节C. 1000 X 1000 字节D. 1024 X 1024 字节答案:D解析:1 M B = 1024 K B = 1024 ∗ 1024 B1MB=1024KB=1024*1024B1MB=1024KB=1024∗1024B4. 广域网的英文缩写是（）。

A. LANB. WANC. MAND. LNA答案:B A是局域网C是城域网5. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 1986答案:B6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母（）。

A. AB. SC. DD. a答案:A解析:取模7. 根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。

A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1) / (k - 1)答案:A解析:1）假设h=2，k=2，画出完美二叉树，共7个节点。

学科竞赛-2018NOIP普及组初赛试题_1

学科竞赛-2018NOIP普及组初赛试题_1

2018NOIP普及组初赛试题第二十四届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018 年10 月13 日14:30~16:30选手注意：试题纸共有7 页，答题纸共有2 页，满分100 分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机2、下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A.(269)16B.(617)10C.(1151)8D.(1001101011)23、1MB 等于（）。

A.1000 字节B.B. 1024 字节C.1000 X 1000 字节D.D. 1024 X 1024 字节4、广域网的英文缩写是（）。

A. LANB. WANC. MAND. LNA5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983C. 1985D. 19866、如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母A. AB. SC. DD. a7、根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。

A.(k h+1 - 1) / (k - 1)B.k h-1C.k hD.(k h-1) / (k - 1)8、以下排序算法中，不需要进行关键字比较操作的算法是（）。

A. 基数排序B. 冒泡排序C. 堆排序D. 直接插入排序9、给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要N - 1 次比较操作。

第十八届全国青少年信息学奥林匹克竞赛初赛普及组参考答案

第十八届全国青少年信息学奥林匹克竞赛初赛普及组参考答案

第十八届全国青少年信息学奥林匹克竞赛初赛普及组参考答案第十八届全国青少年信息学奥林匹克竞赛初赛普及组试题和参考答案一、单项选择题（共20题，每题1.5分，共计30分，每题有且仅有一个正确答案）1、计算机如果缺少（），将无法正常启动。

A、内存B、鼠标C、U盘D、摄像头2、（）是一种先进先出的线性表。

A、栈B、队列C、哈希表D、二叉树3、目前计算机芯片（集成电路）制造的主要原料是（），它是一种能从沙子中提炼出来的物质。

A、硅B、铜C、锗D、铝4、十六进制数9A在（）进制下是232。

A、四B、八C、十D、十二5、（）不属于操作系统。

A、WindowsB、DOSC、PhotoshopD、NOI Linux6、如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。

A、ABCB、CBAC、ACBD、BAC7、目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。

A、显示器B、CPUC、内存D、鼠标8、使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5、4、3、2、1需要进行（）次交换，才能完成冒泡排序。

A、0B、5C、10D、159、1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。

A、电子管B、晶体管C、集成电路D、超大规模集成电路10、无论是TCP/IP模型，还是OSI模型，都可视为网络的分层模型，每个网络协议都可以被归为某一层中，如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。

11、矢量图图形文件所占的存储空间较小，并且不论如何放大、缩小或旋转等都不会失真，是因为它（）A、记录了大量像素块的色彩值来表示图像B、用点、直线或多边形等基于数学方程的几何图元来表示图像C、每个像素点的颜色信息均用矢量表示D、把文件保存在互联网，采用在线浏览的方式查看图像12、如果一个栈初识时为空，且当前栈中的元素从栈底到栈顶依次为a、b、c，另有元素d已经出栈，则可能的入栈顺序是（）。