NOIP初赛复习-普和组市公开课金奖市赛课一等奖课件

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

2、定发展，文字图象处理功效加强； 第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多关键部件可集成在一个或多个芯片上，从而出现了微型计算机。 一、 计算机产生与发展第3页计算机发展历史划分依据元器件电子管 晶体管 集成电路 超大规模集成电路第4页John von Neumann冯诺依曼计算机工作原理到当前为止，几乎全部计算机结构都按冯诺依曼提出方案组成，所以都可称为冯诺依曼机。冯诺依曼思想：二进制数、存放程序和程序控制、硬件由五大部件组成。计算机工作原理就是“存放程序和程序控制”，也称冯诺依曼工作原理。第5页计算机硬件系统 计算机硬件系统均由运算器、控制器、存放器、输入设备和

3、输出设备五大部分组成。他们之间逻辑关系以下列图所表示:第6页设备分类：区分图中设备第7页内存放器分类ROM：只读存放器，只能读出信息，保留厂家写入系统信息RAM：随机存放器，可读写，存放运行中程序和数据（普通机器内存18G）第8页惯用外部设备外 存：磁带，磁盘(软、硬)，移动闪存，光盘，.输入设备：键盘，鼠标，话筒，扫描仪，数码相机、摄像机，光笔，.输出设备：显示器，打印机（针式、喷墨、激光），绘图仪，音箱，.输入/输出设备：磁盘驱动器,光刻机,触摸屏, .第9页以下哪一个设备属于输出设备（） 。A. 扫描仪 B. 键盘 C. 鼠标 D. 打印机CPU、存放器、 I/O 设备是经过（）连接起来

4、。A. 接口 B. 总线 C. 控制线 D. 系统文件断电后会丢失数据存放器是（） 。A. RAM B. ROM C. 硬盘 D. 光盘以下对操作系统功效描述最为完整是（） 。A. 负责外设与主机之间信息交换B. 负责诊疗机器故障C. 控制和管理计算机系统各种硬件和软件资源使用D. 将源程序编译成目标程序以下选项中不属于图像格式是（） 。A. JPEG 格式 B. TXT 格式 C. GIF 格式 D. PNG 格式在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制” 操作选项，它意思是（）。A.用剪切板中文件替换该文件B.在该文件所在文件夹中，将该文件克隆一份C

5、.将该文件复制到剪切板，并保留原文件D.将该文件复制到剪切板，并删除原文件计算机假如缺乏（），将无法正常开启。A内存 B鼠标 C U 盘 D 摄像头（）不属于操作系统。AWindows BDOS CPhotoshop DNOI LinuxdbacbCAC第10页当前计算机芯片（集成电路）制造主要原料是（），它是一个能够在沙子中提炼出物质。A硅 B铜 C锗 D铝当前个人电脑（）市场拥有率最靠前厂商包含 Intel、AMD 等企业。A显示器 BCPU C内存 D鼠标1946 年诞生于美国宾夕法尼亚大学 ENIAC 属于（）计算机。A电子管 B晶体管 C集成电路 D超大规模集成电路矢量图（Vecto

6、r Image）图形文件所占贮存空间比较小，而且不论怎样放大、缩小或旋转等都不会失真，是因为它（）。A统计了大量像素块色彩值来表示图像B用点、直线或者多边形等基于数学方程几何图元来表示图像C每个像素点颜色信息均用矢量表示D把文件保留在互联网，采取在线浏览方式查看图像地址总线位数决定了 CPU 可直接寻址内存空间大小，比如地址总线为 16 位，其最大可寻址空间为 64KB。假如地址总线是 32 位，则理论上最大可寻址内存空间为（ ）。A128KB B1MB C1GB D4GB蓝牙和 Wi-Fi 都是（）设备。A无线广域网 B无线城域网 C无线局域网 D无线路由器ABABDC第11页一片容量为 8

7、GB SD 卡能存放大约（）张大小为 2MB 数码照片。A. 1600B. C. 4000D. 1 6000摩尔定律（Moores law）是由英特尔创始人之一戈登摩尔（Gordon Moore）提出来。依据摩尔定律，在过去几十年以及在可预测未来几年，单块集成电路集成度大约每（ ）个月翻一番。A. 1B. 6C. 18 D. 36存放器是（ ）主要组成部分。A. 硬盘 B. 高速缓存C.内存D.中央处理器有些人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（ ）。A. 正确，将文件放入回收站意味着彻底删除、无法恢复B. 不正确，只有将回收站清空后，才意味着彻底删除、无

8、法恢复C. 不正确，即使将回收站清空，文件只是被标识为删除，仍可能经过恢复软件找回D. 不正确，只要在硬盘上出现过文件，永远不可能被彻底删除从 ENIAC 到 当 前最先进 计算机 ，冯诺依曼体系结构一直占有 主要 地位。冯 诺依曼体系结 构关键内容是 （ ） 。A. 采取开关电路B. 采取半导体器件C. 采取存放程序和程序控制原理D. 采取键盘输入Linux下可执行文件默认扩展名为（ ）。A. exe B. com C. dll D. 以上都不是提出“存放程序”计算机工作原理是（ ）。A. 克劳德香农 B. 戈登摩尔 C. 查尔斯巴比奇 D. 冯诺依曼CCDCCDD第12页主存放器存取速度比

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

10、 D由研究电鱼，创造伏特电池在使用高级语言编写程序时，普通提到“空间复杂度”中“空间”是指（ ）。A. 程序运行时理论上所占内存空间B. 程序运行时理论上所占数组空间C. 程序运行时理论上所占硬盘空间D. 程序源文件理论上所占硬盘空间以下哪个是面向对象高级语言（） 。A. 汇编语言 B. C+ C. Fortran D. BasicBABAx第13页 用要求符号和规则来表示数方法十 进 制 数:基数为10，有十个数码 0 9，运算规则逢十进一二 进 制 数:基数为2，有两个数码 0 和 1，运算规则逢二进一十六进制数: 数码 0 9, AF八 进 制 数: 数码 0 7信息在计算机中存放 数制

11、第14页位权处于不一样位上数字所代表值不一样，一个数字在某个固定位置上所代表值是固定，这个固定位上值称为位权或权值。 位权与基数关系是：各进位制中位权值恰巧是基数若干次幂。所以，任何一个数制表示数都能够写成按位权展开多项式之和。比如，以下数制位权展开式：(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表示）从小数点以左，每一位对应权值分别为 R0、R1 、R2、R3、R4、；以小数点以右，每一位对应权值分别为 R1

12、、R2 、R3、。 第15页十进制转换成非十进制将十进制数转换为其它进制数时，整数部分和小数部分需分别转换，然后合并。 整数转换：用“除R取余”法。注：R表示转换结果为R进制数（如将十进制数转换为二进制数R就为2，转换为八进制数R就为8，转换为十六进制数R就为16）。 小数转换：用“乘R取整”法。注意：这种方法可能产生取不完情况，也就是说一个十进制数可能无法准确地转换成R进制数，这就是“存放误差”，可依据要求保留若干位。 第16页【例】 将(91.453)10转换成二进制数（取4位小数）。得 (91.453)10 = (1011011.0111)2 第17页字节(Byte)：8位(bit)二进

13、制数 1KB（千字节）=1024 Byte 1MB（兆）=1024 KB 1GB=1024 MB 1TB =1024 GB 信息量单位第18页数值（经过运算转换） (109)10 (1101101)2ASCII码 （American Standard Code for Information Interchange） A （65）10 B（66）10 a （97） 10 c （99）10UNICODE编码 敏 (25935) 10 (654F) 16 其它信息 专用程序转换例：第19页补码正数补码与原码相同，负数补码就是它反码在末位加“1”。（+64）10补码 01000000 （-64）10

14、补码 11000000 总之，正数原码、反码、补码都相同，就是它原码；负数原码符号位取1，其余不变；负数反码符号位取1，其余部分求反；负数补码就是它反码在末位加“1”。【例】 二进制数 原码 反码 补码+1011010 01011010 01011010 01011010-1011010 11011010 10100101 10100110第20页二进制数 00100100 和 00010101 和是（）。A. 00101000 B. 001010100 C. 01000101 D. 00111001二进制数 11.01 在十进制下是（）。A.3.25B.4.125C.6.25D.11.125

15、在十六进制表示法中，字母 A 相当于十进制中（）。A.9B.10C.15D.16在二进制下，1100100 + （ ） = 1110001。A. 1011B. 1101C. 1010D. 1111字符“0” ASCII 码为 48，则字符“9” ASCII 码为（ ）。A. 39 B. 57C. 120D. 视详细计算机而定一个正整数在二进制下有 100 位，则它在十六进制下有（ ）位。A. 7B. 13C. 25D. 不能确定2E+03表示（ ）。A. 2.03 B. 5 C. 8 D. 一个字节（byte）由（ ）个二进制位组成。A. 8 B. 16 C. 32 D. 以上都有可能DABA

16、B CDA第21页设X、Y、Z分别代表三进制下一位数字，若等式XY + ZX = XYX在三进制下成立，那么一样在三进制下，等式XY * ZX = （ ）也成立。A. YXZ B. ZXY C. XYZ D. XZY一个字长为8位整数补码是11111001，则它原码是（ ）。A. 00000111 B. 01111001 C. 11111001 D. 100001111TB 代表字节数量是（）。A. 2 10 次方 B. 2 20 次方C. 2 30 次方 D. 2 40 次方以下各无符号十进制整数中，能用八位二进制表示数中最大是（） 。A. 296 B. 133 C. 256 D. 199一

17、个 32 位整型变量占用（）个字节。A.4B.8C.32D.128十六进制数 9A 在（）进制下是 232。A四 B八 C十D十二BDDdaB第22页二、计算机网络第23页10月10日计算机网络拓扑结构总线型拓扑结构前一页后一页第24页10月10日计算机网络拓扑结构环型拓扑结构前一页后一页第25页10月10日计算机网络拓扑结构星型拓扑结构前一页后一页第26页10月10日计算机网络拓扑结构树型拓扑结构前一页后一页第27页10月10日计算机网络拓扑结构网状型拓扑结构网状型拓扑结构主要用于互联网前一页后一页第28页10月10日计算机网络拓扑结构无线型拓扑结构网状型拓扑结构主要用于互联网前一页后一页第

18、29页IP 地 址 组 成IP地址是32位二进制数，分成4组，每组8位二进制数，每组之间用圆点隔开，通惯用十进制来表示；000000000000000000000000000000001111111111111111111111111111111155IP地址范围是：55；宽带上网不是固定IP，而是连网时由ISP(Internet服务提供商 )随机给；每个网络上计算机IP不会相同。第30页Internet域名系统域名由几个英文单词组成，中间用点（.）连接，中间不能有空格。域名地址与IP地址实际上是同一个东西。域名系统是为了方便解释机器IP地址而设置。 如校IP是：8 域名是：第31页域名组成域

19、名系统采取层次结构，按地理域或机构域进行分层。域名中，从右到左依次为最高域名段、次高域名段等，最左一个字段为主机名 机构域：com 商业机构edu 教育机构gov 政府机构 net 网络组织地理域：cn 中国 jp 日本hk 香港M第32页OSI开放系统互联参考模型应用层Application表示层Presentation会话层session传输层transport物理层Physical数据链路层Data Link网络层Network7654321处理网络应用数据表示主机间通信进程间连接寻址和最短路径介质访问（接入）二进制传输第33页常见网络协议TCP（Transmission Control

20、 Protocol 传输控制协议）远程登录协议Telnet、文件传输协议FTP、超文本传输协议HTTP、域名服务DNS、简单邮件传输协议SMTP、邮局协议POP3等第34页以下哪一个是属于电子邮件收发协议（）。A. SMTP B. UDP C. P2P D. FTP以下几个 32 位 IP 地址中，书写错误是（） 。A. 7 B. C. 256.256.129.1 D. IPv4 协议使用 32 位地址，伴随其不停被分配，地址资源日趋枯竭。所以，它正逐步被 使用（）位地址 IPv6 协议所取代。A.40B.48C.64D.128通常在搜索引擎中，对某个关键词加上双引号表示（）。A.排除关键词，

21、不显示任何包含该关键词结果B.将关键词分解，在搜索结果中必须包含其中一部分C.准确搜索，只显示包含整个关键词结果D.站内搜索，只显示关键词所指向网站内容中国国家顶级域名是（）。A.cnB.chC.chnD.china（）是主要用于显示网页服务器或者文件系统 HTML 文件内容，并让用户与这些文件交互一个软件。A资源管理器 B浏览器 C电子邮件 D编译器acDCAB第35页（）是当前互联网上惯用 E-mail 服务协议。AHTTP BFTP CPOP3 DTelnet在以下HTML语句中，能够正确产生一个指向NOI官方网站超链接是（ ）。A. 欢迎访问NOI网站B. 欢迎访问NOI网站C. D.

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

23、Q(PQ)(PQ)假如树根算第1层，那么一棵n层二叉树最多有（ ）个结点。A. 2n-1 B. 2n C. 2n+1 D. 2n+1假如根结点深度记为 1，则一棵恰有 个叶结点二叉树深度最少是（ ）。 A. 10B. 11C. 12D. 13体育课铃声响了，同学们都陆续地奔向操场，按老师要求从高到矮站成一排。每个同学按次序来到操场时，都从排尾走向排头，找到第一个比自己高同学，并站在他后面。这种站队方法类似于（ ）算法 。A. 快速排序B. 插入排序C. 冒泡排序D. 归并排序CDAACB第38页无向完全图是图中每对顶点之间都恰有一条边简单图。已知无向完全图 G 有 7 个顶点，则它共有（ ）条

24、边。A. 7B. 21C. 42D. 49原字符串中任意一段连续字符所组成新字符串称为子串。则字符“AAABBBCCC”共有（）个不一样非空子串。A3 B12 C36 D45（）就是把一个复杂问题分成两个或更多相同类似子问题，再把子问题分解成更小子问题直到最终子问题能够简单地直接求解。而原问题解就是子问题解并。A动态规划 B贪心 C分治 D搜索使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会降低 1 个逆序对，所以序列 5，4，3，2，1 需要执行（）次操作，才能完成冒泡排序。A0 B5 C10 D15（）是一个先进先出线性表。A栈 B队列 C哈希表（散列表） D二叉树BCCCB第3

25、9页把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（）。A.大于原数B.小于原数C.等于原数D.与原数符号相反CCF NOIP 复赛全国统一评测时使用系统软件是（）。A.NOI WindowsB.NOI LinuxC.NOI Mac OSD.NOI DOS在一个无向图中，假如任意两点之间都存在路径相连，则称其为连通图。下列图是一个有4 个顶点、6 条边连通图。若要使它不再是连通图，最少要删去其中（）条边。A.1B.2C.3D.4下列图中所使用数据结构是（）。 A.哈希表B.栈C.队列D.二叉树逻辑表示式（）值与变量 A 真假无关。A.(A B) AB.(A B) BC.(A B)

26、(A B)D.(A B) A BDBCBC第40页下面故事与（）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山 里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个 老和尚给小和尚讲故事.A.枚举B.递归C.贪心D.分治链表不含有特点是（） 。A. 无须事先预计存放空间 B. 可随机访问任一元素C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比bb第41页四、问题求解把 M 个一样球放到 N 个一样袋子里，允许有袋子空着不放，问共有多少种不一样放置方法？ （用 K 表示） 。比如： M = 7， N = 3 时， K = 8；在这里认为（ 5,1,1）和（ 1,5,1）是同一个放置方法。问： M = 8， N = 5 时， K = _。如图所表示，图中每条边上数字表示该边长度，则从 A到 E最短距离是_。1811第42页7 个同学围坐一圈，要选 2 个不相邻作为代表，有_种不一样选法。某系统自称使