NOIP初赛复习-普及组幻灯片

1、NOIP初赛复习,普及组,1,2,全国青少年信息学奥林匹克联赛初赛 1、单项选择 2、问题求解 3、阅读程序写结果 4、完善程序,2,6/23/2020,计算机的产生是20世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： 第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； 第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； 第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器

2、为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。,一、 计算机的产生与发展,3,6/23/2020,计算机发展历史的划分依据元器件,电子管 晶体管 集成电路 超大规模集成电路,4,6/23/2020,John von Neumann 冯诺依曼,计算机的工作原理,到目前为止，几乎所有的计算机的结构都按冯诺依曼提出的方案组成，因此都可称为冯诺依曼机。 冯诺依曼思想：二进制数、存储程序和程序控制、硬件由五大部件构成。 计算机的工作原理就是“存储程序和

3、程序控制”，也称冯诺依曼工作原理。,5,6/23/2020,计算机硬件系统,计算机硬件系统均由运算器、控制器、存储器、输入设备和输出设备五大部分构成。他们之间的逻辑关系如下图所示:,6,6/23/2020,设备分类：区分图中设备,7,6/23/2020,内存储器的分类,ROM：只读存储器，只能读出信息，保存厂家写入的系统信息 RAM：随机存储器，可读写，存放运行中的程序和数据（一般机器内存18G）,8,6/23/2020,常用外部设备,外 存：磁带，磁盘(软、硬)，移动闪存，光盘，. 输入设备：键盘，鼠标，话筒，扫描仪，数码相机、摄像机，光笔，. 输出设备：显示器，打印机（针式、喷墨、激光），

4、绘图仪，音箱，. 输入/输出设备：磁盘驱动器,光刻机,触摸屏, .,9,6/23/2020,以下哪一种设备属于输出设备（） 。 A. 扫描仪 B. 键盘 C. 鼠标 D. 打印机 CPU、存储器、 I/O 设备是通过（）连接起来的。 A. 接口 B. 总线 C. 控制线 D. 系统文件 断电后会丢失数据的存储器是（） 。 A. RAM B. ROM C. 硬盘 D. 光盘 下列对操作系统功能的描述最为完整的是（） 。 A. 负责外设与主机之间的信息交换 B. 负责诊断机器的故障 C. 控制和管理计算机系统的各种硬件和软件资源的使用 D. 将源程序编译成目标程序 下列选项中不属于图像格式的是（）

5、 。 A. JPEG 格式 B. TXT 格式 C. GIF 格式 D. PNG 格式 在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的 操作选项，它的意思是（）。 A. 用剪切板中的文件替换该文件 B. 在该文件所在文件夹中，将该文件克隆一份 C. 将该文件复制到剪切板，并保留原文件 D. 将该文件复制到剪切板，并删除原文件 计算机如果缺少（），将无法正常启动。 A内存 B鼠标 C U 盘 D 摄像头 （）不属于操作系统。 AWindows BDOS CPhotoshop DNOI Linux,d,b,a,c,b,C,A,C,10,6/23/2020,目前

6、计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。 A硅 B铜 C锗 D铝 目前个人电脑的（）市场占有率最靠前的厂商包括 Intel、AMD 等公司。 A显示器 BCPU C内存 D鼠标 1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（）计算机。 A电子管 B晶体管 C集成电路 D超大规模集成电路 矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。 A记录了大量像素块的色彩值来表示图像 B用点、直线或者多边形等基于数学方程的几何图元来表示图像 C每个像素点的颜色信息均用矢量表示 D把文件

7、保存在互联网，采用在线浏览的方式查看图像 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ ）。 A128KB B1MB C1GB D4GB 蓝牙和 Wi-Fi 都是（）设备。 A无线广域网 B无线城域网 C无线局域网 D无线路由器,A,B,A,B,D,C,11,6/23/2020,一片容量为 8GB 的 SD 卡能存储大约（）张大小为 2MB 的数码照片。 A. 1600 B. 2000 C. 4000 D. 1 6000 摩尔定律（Moores law）是由英特尔创始

8、人之一戈登摩尔（Gordon Moore）提出来的。根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（ ）个月翻一番。 A. 1 B. 6 C. 18 D. 36 寄存器是（ ）的重要组成部分。 A. 硬盘 B. 高速缓存 C.内存 D.中央处理器 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ ）。 A. 正确的，将文件放入回收站意味着彻底删除、无法恢复 B. 不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C. 不正确的，即使将回收站清空，文件只是被标记为删除，仍可能通过恢复软件找回 D. 不正确的，只要在硬盘上出现过的

9、文件，永远不可能被彻底删除 从 ENIAC 到 当 前最先进 的计算机 ，冯诺依曼体系结构始终占有 重要 的地位。冯 诺依曼体系结 构的核心内容是 （ ） 。 A. 采用开关电路 B. 采用半导体器件 C. 采用存储程序和程序控制原理 D. 采用键盘输入 Linux下可执行文件的默认扩展名为（ ）。 A. exe B. com C. dll D. 以上都不是 提出“存储程序”的计算机工作原理的是（ ）。 A. 克劳德香农 B. 戈登摩尔 C. 查尔斯巴比奇 D. 冯诺依曼,C,C,D,C,C,D,D,12,6/23/2020,主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后

10、者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（ ）。 A. 寄存器 B. 高速缓存 C. 闪存 D. 外存 在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。 A系统分配的栈空间溢出 B系统分配的堆空间溢出 C系统分配的队列空间溢出 D系统分配的链表空间溢出 仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（） A由研究蝙蝠，发明雷达 B由研究蜘蛛网，发明因特网 C由研究海豚，发明声纳

11、 D由研究电鱼，发明伏特电池 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。 A. 程序运行时理论上所占的内存空间 B. 程序运行时理论上所占的数组空间 C. 程序运行时理论上所占的硬盘空间 D. 程序源文件理论上所占的硬盘空间 以下哪个是面向对象的高级语言（） 。 A. 汇编语言 B. C+ C. Fortran D. Basic,B,A,B,A,x,13,6/23/2020,用规定的符号和规则来表示数的方法,十 进 制 数:,基数为10，有十个数码 0 9，运算规则逢十进一,二 进 制 数:,基数为2，有两个数码 0 和 1，运算规则逢二进一,十六进制数: 数码

12、 0 9, AF,八 进 制 数: 数码 0 7,信息在计算机中的存储,数制,14,2,位权,处在不同位上的数字所代表的值不同，一个数字在某个固定位置上所代表的值是固定的，这个固定位上的值称为位权或权值。 位权与基数的关系是：各进位制中位权的值恰巧是基数的若干次幂。因此，任何一种数制表示的数都可以写成按位权展开的多项式之和。 例如，下列数制的位权展开式： (56789)10 =5104+6103+7102+8101+9100 (1011.11)2 =123+022+121+120+12-1+12-2 (FDE.5)16 =15162+13161+14160+516-1 任意进制数（用R表示）从

13、小数点以左，每一位对应的权值分别为 R0、R1 、R2、R3、R4、；以小数点以右，每一位对应的权值分别为 R1、R2 、R3、。,15,6/23/2020,十进制转换成非十进制,将十进制数转换为其他进制数时，整数部分和小数部分需分别转换，然后合并。 整数转换：用“除R取余”法。 注：R表示转换结果为R进制的数（如将十进制数转换为二进制数R就为2，转换为八进制数R就为8，转换为十六进制数R就为16）。 小数转换：用“乘R取整”法。 注意：这种方法可能产生取不完的情况，也就是说一个十进制数可能无法精确地转换成R进制数，这就是“存储误差”，可根据要求保留若干位。,16,6/23/2020,【例】

14、将(91.453)10转换成二进制数（取4位小数）。,得 (91.453)10 = (1011011.0111)2,17,6/23/2020,字节(Byte)：8位(bit)二进制数 1KB（千字节）=1024 Byte 1MB（兆）=1024 KB 1GB=1024 MB 1TB =1024 GB,信息量的单位,18,6/23/2020,数值（通过运算转换） (109)10 (1101101)2 ASCII码 （American Standard Code for Information Interchange） A （65）10 B（66）10 a （97） 10 c （99）10 UNI

15、CODE编码 敏 (25935) 10 (654F) 16 其它信息 专用程序转换,例：,19,6/23/2020,补码,正数的补码与原码相同，负数的补码就是它的反码在末位加“1”。 （+64）10的补码 01000000 （-64）10的补码 11000000 总之，正数的原码、反码、补码都相同，就是它的原码；负数的原码符号位取1，其余不变；负数的反码符号位取1，其余部分求反；负数的补码就是它的反码在末位加“1”。 【例】 二进制数 原码 反码 补码 +1011010 01011010 01011010 01011010 -1011010 11011010 10100101 10100110

16、,20,6/23/2020,二进制数 00100100 和 00010101 的和是（）。 A. 00101000 B. 001010100 C. 01000101 D. 00111001 二进制数 11.01 在十进制下是（）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 在十六进制表示法中，字母 A 相当于十进制中的（）。 A. 9 B. 10 C. 15 D. 16 在二进制下，1100100 + （ ） = 1110001。 A. 1011 B. 1101 C. 1010 D. 1111 字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（

17、 ）。 A. 39 B. 57 C. 120 D. 视具体的计算机而定 一个正整数在二进制下有 100 位，则它在十六进制下有（ ）位。 A. 7 B. 13 C. 25 D. 不能确定 2E+03表示（ ）。 A. 2.03 B. 5 C. 8 D. 2000 一个字节（byte）由（ ）个二进制位组成。 A. 8 B. 16 C. 32 D. 以上都有可能,D,A,B,A,B,C,D,A,21,6/23/2020,设X、Y、Z分别代表三进制下的一位数字，若等式XY + ZX = XYX在三进制下成立，那么同样在三进制下，等式XY * ZX = （ ）也成立。 A. YXZ B. ZXY C

18、. XYZ D. XZY 一个字长为8位的整数的补码是11111001，则它的原码是（ ）。 A. 00000111 B. 01111001 C. 11111001 D. 10000111 1TB 代表的字节数量是（）。 A. 2 的 10 次方 B. 2 的 20 次方 C. 2 的 30 次方 D. 2 的 40 次方 下列各无符号十进制整数中，能用八位二进制表示的数中最大的是（） 。 A. 296 B. 133 C. 256 D. 199 一个 32 位整型变量占用（）个字节。 A. 4 B. 8 C. 32 D. 128 十六进制数 9A 在（）进制下是 232。 A四 B八 C十 D

19、十二,B,D,D,d,a,B,22,6/23/2020,二、计算机网络,23,6/23/2020,2,计算机网络拓扑结构,总线型拓扑结构,前一页,后一页,24,2,计算机网络拓扑结构,环型拓扑结构,前一页,后一页,25,2,计算机网络拓扑结构,星型拓扑结构,前一页,后一页,26,2,计算机网络拓扑结构,树型拓扑结构,前一页,后一页,27,2,计算机网络拓扑结构,网状型拓扑结构,网状型拓扑结构主要用于互联网,前一页,后一页,28,2,计算机网络拓扑结构,无线型拓扑结构,网状型拓扑结构主要用于互联网,前一页,后一页,29,IP 地 址 的 组 成,IP地址的是32位二进制数，分成4组，每组8位二进

20、制数，每组之间用圆点隔开，通常用十进制来表示；,,55,IP地址范围是：55； 宽带上网不是固定IP，而是连网时由ISP(Internet服务提供商 )随机给的； 每个网络上的计算机的IP不会相同。,30,6/23/2020,Internet的域名系统,域名由几个英文单词组成，中间用点（.）连接，中间不能有空格。 域名地址与IP地址实际上是同一个东西。域名系统是为了方便解释机器的IP地址而设立的。 如校的IP是：8 域名是：,31,6/23/2020,域名的构成,域名系统采用层次结构，按地

21、理域或机构域进行分层。域名中，从右到左依次为最高域名段、次高域名段等，最左的一个字段为主机名,机构域： com 商业机构 edu 教育机构 gov 政府机构 net 网络组织,地理域： cn 中国 jp 日本 hk 香港,M,32,6/23/2020,OSI开放系统互联参考模型,33,6/23/2020,常见网络协议,TCP（Transmission Control Protocol 传输控制协议） 远程登录协议Telnet、文件传输协议FTP、 超文本传输协议HTTP、域名服务DNS、 简单邮件传输协议SMTP、邮局协议POP3等,34,6/23/2020,以下哪一种是属于电子邮件收发的协议

22、（）。 A. SMTP B. UDP C. P2P D. FTP 下列几个 32 位 IP 地址中，书写错误的是（） 。 A. 7 B. C. 256.256.129.1 D. IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用（）位地址的 IPv6 协议所取代。 A. 40 B. 48 C. 64 D. 128 通常在搜索引擎中，对某个关键词加上双引号表示（）。 A. 排除关键词，不显示任何包含该关键词的结果 B. 将关键词分解，在搜索结果中必须包含其中的一部分 C. 精确搜索，只显

23、示包含整个关键词的结果 D. 站内搜索，只显示关键词所指向网站的内容 中国的国家顶级域名是（）。 A. .cn B. .ch C. .chn D. .china （）是主要用于显示网页服务器或者文件系统的 HTML 文件的内容，并让用户与这些文件交互的一种软件。 A资源管理器 B浏览器 C电子邮件 D编译器,a,c,D,C,A,B,35,6/23/2020,（）是目前互联网上常用的 E-mail 服务协议。 AHTTP BFTP CPOP3 DTelnet 在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（ ）。 A. 欢迎访问NOI网站 B. 欢迎访问NOI网站 C. D

24、. 欢迎访问NOI网站 关于HTML下面哪种说法是正确的： A.HTML实现了文本、图形、声音乃至视频信息的统一编码。 B.HTML全称为超文本标记语言。 C.网上广泛使用的 Flash动画都是由HTML编写的。 D.HTML也是一种高级程序设计语言。,C,B,B,36,6/23/2020,三、算法基础,37,6/23/2020,前缀表达式“+ 3 * 2 + 5 12”的值是（ ）。 A. 23 B. 25 C. 37 D. 65 全国青少年信息学奥林匹克系列活动的主办单位是（ ）。 A. 教育部 B. 科技部 C. 共青团中央 D. 中国计算机学会 以下逻辑表达式的值恒为真的是（ ）。 A

25、. P(PQ)(PQ) B. Q(PQ)(PQ) C. PQ(PQ)(PQ) D. PQ(PQ)(PQ) 如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点。 A. 2n-1 B. 2n C. 2n+1 D. 2n+1 如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ ）。 A. 10 B. 11 C. 12 D. 13 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法 。 A. 快速排序 B. 插入排序 C. 冒泡排序

26、 D. 归并排序,C,D,A,A,C,B,38,6/23/2020,无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它共有（ ）条边。 A. 7 B. 21 C. 42 D. 49 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（）个不同的非空子串。 A3 B12 C36 D45 （）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。 A动态规划 B贪心 C分治 D搜索 使用冒泡排序对序列进行升序排列，每执行一次交换操

27、作系统将会减少 1 个逆序对，因此序列 5，4，3，2，1 需要执行（）次操作，才能完成冒泡排序。 A0 B5 C10 D15 （）是一种先进先出的线性表。 A栈 B队列 C哈希表（散列表） D二叉树,B,C,C,C,B,39,6/23/2020,把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（）。 A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反 CCF NOIP 复赛全国统一评测时使用的系统软件是（）。 A. NOI Windows B. NOI Linux C. NOI Mac OS D. NOI DOS 在一个无向图中，如果任意两点之间都存在路径相连，则

28、称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。 A. 1 B. 2 C. 3 D. 4 下图中所使用的数据结构是（）。 A. 哈希表 B. 栈 C. 队列 D. 二叉树 逻辑表达式（）的值与变量 A 的真假无关。 A. (A B) A B. (A B) B C. (A B) (A B) D. (A B) A B,D,B,C,B,C,40,6/23/2020,下面的故事与（）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山 里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个 老和尚给小和尚讲故事. A. 枚举 B. 递归 C. 贪心 D. 分治 链表不具有的特点是（） 。 A. 不必事先估计存储空间 B. 可随机访问任一元素 C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比,b,b,41,6/23/