《NOIP初赛知识点(大全).ppt》由会员分享，可在线阅读，更多相关《NOIP初赛知识点(大全).ppt（108页珍藏版）》请在三一办公上搜索。
1、初赛知识复习,2009/10/11,初赛试题形式 初赛：初赛全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题(即每题有且只有一个正确答案，选对得分)，后10题为不定项选择题(即每题有1至5个正确答案，只有全部选对才得分)。2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序(不一定有关于程序功能的说明)，考生通过
2、阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。,知识范围内容与要求 1、计算机的基本常识 计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化)信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输出方式)信息的表示与处理(信息编码、微处理部件MPU、内存储结构、指令，程序，和存储
3、程序原理、程序的三种基本控制结构)信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理)信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCPIP协议、HTTP协议、WEB应用的主要方式和特点)人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文本及交互操作)信息技术的新发展、新特点、新应用等。,2、计算机的基本操作 WINDOWS和LINUX的基本操作知识 联网的基本使用常识(网上浏览、搜索和查询等)常用的工具软件使用(文字编辑、电子邮件收发等)3、程序设计的基本知识 数据结构 程序语言中基本数据类型(字符、
4、整数、长整数、浮点)浮点运算中的精度和数值比较 一维数组(串)与线性表 记录类型(PASCAL)结构类型(C)程序设计 结构化程序设计的基本概念 阅读理解程序的基本能力 具有将简单问题抽象成适合计算机解决的模型的基本能力 具有针对模型设计简单算法的基本能力 程序流程描述(自然语言伪码NS图其他)程序设计语言(PASCALCC+，)基本算法处理 初等算法(计数、统计、数学运算等)排序算法(冒泡法、插入排序、合并排序、快速排序)查找(顺序查找、二分法)回溯算法,计算机结构与组成原理 基本的数学知识（集合的运算、排列与组合）,计算机结构与组成原理,一、计算机发展及应用1、第一台电子计算机的诞生：EN
5、IAC 1946年，世界上第一台数字式电于计算机是由美固宾夕法尼亚大学的物理学家约翰莫克利（John Mauchly）和工程师普雷斯伯埃克特（）领导研制的取名为ENIAC（Elecotmnic Nurnerical Integrator And Calculator）的计算杌。2、第一台具有存储程序功能的计算机：EDVAC。冯诺依曼依据存储程序的工作原理设计.运算器、控制器、存储器、输人设备和输出设备这五部分组成，同ENIAC相比，EDVAC方案有两个重大改进：（1）：采用了二进制；（2）：提出了“存储程序”，,1903年，冯诺伊曼（Neumann，John von）出生于匈牙利的布达佩斯,考
6、题:NOIP101、美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献包括（）。A)提出理想计算机的数学模型，成为计算机科学的理论基础。B)提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C)设计出第一台具有存储程序功能的计算机EDVAC。D)采用集成电路作为计算机的主要功能部件。E)指出计算机性能将以每两年翻一番的速度向前发展。,图灵(Alan Turing)是（）。(NOIP9)A）美国人 B）英国人 C）德国人 D）匈牙利人,艾伦麦席森图灵（Alan Mathison Turing，1912年6月23日-1954年6月7日），英国数学家图灵机由三部分组成，包括一条 带子、一个
7、读写头和一个控制装置。图灵对于人工智能的发展有诸多贡献，例如：图灵曾写过一篇名为机器会思考吗？（Can Machine Think?）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。图灵奖是美国计算机协会于1966年设立的，又叫A.M.图灵奖，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦图灵，这个奖设立目的之一是纪念这位科学家。,B,3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）。noip12A.沃尔夫奖 B.诺贝尔奖 C.菲尔兹奖 D.图灵奖 E.南丁格尔奖11.在下列关于图灵奖的说法中
8、，正确的有（）。noip14A.图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B.图灵奖有“计算机界诺贝尔奖”之称C.迄今为止，还没有华裔计算机科学家获此殊荣D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵,2000 Andrew Chi-Chih Yao-PhD,UIUC;Prof,Princeton(now at 清华)因对计算理论做出了诸多根本性的重大贡献.(图灵奖自创立以来获得该奖项的首位华裔学者,全球华人的骄傲),第一个给计算机写程序的人是（）。(NOIP9)A）Alan Mathison Turing B）Ada Lovelace C）
9、John von Neumann D）John Mc-Carthy E）Edsger Wybe Dijkstr,1、英国著名诗人拜伦的女儿Ada Lovelace(爱达).由于她在程序设计上的开创性工作，Ada Lovelace被称为世界上”第一位程序员”。“世界上第一位软件工程师”。2、董铁宝是“中国第一个程序员”。董铁宝1945年赴美国学习，在伊利诺伊大学学习、研究时，他参与了第一代电子计算机伊利亚克机的设计、编程和使用。董铁宝于1956年回到中国并任教于北京大学，成为王选（计算数学专业院士）的老师。董铁宝在1968年文化大革命期间自杀身亡。,B,3、计算机发展的几个阶段,微型计算机的问世
10、是由于（）的出现。(NOIP8)A）中小规模集成电路 B）晶体管电路 C）（超）大规模集成电路 D）电子管电路,C,4、计算机应用科学计算（数值计算）。数据处理（信息处理）。人工智能。自动控制。计算机辅助设计和制造：CAI（计算机辅助教学）CAM（计算机辅助制造）CAT（计算机辅助测试）CAD（计算机辅助设计）CAE(计算机辅助教育)CIMS（计算机集成制造系统）,二、保护知识产权：计算机软件保护条例最早是1991年6月4日国务院发布的，现已废止。现公布计算机软件保护条例，自2002年1月1日起实施。第二章 软件著作权 第八条 软件著作权人享有下列各项权利：（一）发表权（二）署名权（三）修改权
11、（四）复制权；（五）发行权（六）出租权（七）信息网络传播权（八）翻译权（九）应当由软件著作权人享有的其他权利。,计算机软件保护法是用来保护软件()的（NOIP7）A)编写权 B)复制权 C)使用权 D)著作权,D,三、计算机病毒,计算机病毒是一种功能较特殊的计算机程序，计算机病毒的特征可以归纳为下面两点：能够将自身复制到其他程序中。不独立以文件形式存在，仅附加在别的程序上。失去这两个特征中的任何一个，都不成其为病毒。,计算机病毒是()(NOIP7)A)通过计算机传播的危害人体健康的一种病毒B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C)一种由于计算机元器件老化而产生的对生
12、态环境有害的物质D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒计算机病毒的特点是（）(NOIP6)A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性 C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性 计算机病毒传染的必要条件是：（）。(NOIP8)A）在内存中运行病毒程序 B）对磁盘进行读写操作 C）在内存中运行含有病毒的可执行的程序 D）复制文件,B,C,B,四、计算机系统的组成：,1、硬件系统2、软件系统,只有硬件没有安装软件的计算机称为“裸机”,1、硬件系统的组成：,五个基本部分组成：（1）运算器（2）控制器（3）存储器（4）输人
13、设备（5）输出设备,1）运算器+控制器=CPU:中央处理器（Center Process Unit）,计算机的核心部件(指挥系统)直接决定计算机的运行速度。如：计算机的配置：“Intel奔腾IV2.8GHz/512M/80GB/50X”每秒运算次数是：2.8*210*210*210,2）存储器,外存储器：硬盘、光盘、软盘、优盘等。内存储器：ROM 和 RAM ROM:Read Only Memory：只读存储器 RAM:Random Access Memory：随机存取存储器 平时说的内存：RAM：256MB,512MB,1GMB 高速缓存器：cache 高速缓存器内存速度 外存速度,主机的概
14、念：包括：CPU和内存储器,CPU访问内存的速度比访问下列哪个（些）存储设备要慢（）。（NOIP9）A）寄存器B）硬盘C）软盘D）高速缓存 E）光盘微型计算机中，（）的存取速度最快。(NOIP8)A）高速缓存 B）外存储器 C）寄存器 D）内存储器在计算机硬件系统中，cache是()存储器(NOIP7)A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲,AD,A,D,4、下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。NOIP10A.CPU B.图形卡（显卡）C.光驱 D.主板 E.内存、用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（）。NOIP10 A.针式打印机
15、B.喷墨打印机 C.激光打印机 D.笔式绘图仪 E.喷墨绘图仪、下列哪个（些）不是计算机的存储设备（）。NOIP10 A.文件管理器 B.内存 C.显卡 D.硬盘 E.U盘、下列说法中正确的有（）。NOIP10A.CPU的基本功能就是执行指令。B.CPU的主频是指CPU在1秒内完成的指令周期数，主频越快的CPU速度一定越快。C.内部构造不同的CPU运行相同的机器语言程序，一定会产生不同的结果。D.在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。E.数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。、彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（）。NOI
16、P10 A.红 B.白 C.蓝 D.绿 E.橙、下列哪个（些）是64位处理器（）。NOIP10 A.Intel Itanium B.Intel Pentium III C.AMD Athlon64 D.AMD Opteron E.IBM Power 5,C,C,C,ADE,ACD,ACDE,NOIP116.下列设备中没有计算功能的是（）。A.笔记本电脑B.掌上电脑C.智能手机 D.电子计算器 E.液晶显示器7.Intel的首颗64 位处理器是（）。A.8088 B.8086 C.80386 D.80486 E.Pentium15.下列外设接口中可以通过无线连接的方式连接设备的是（）。A.USB
17、 2.0 高速版 B.红外 C.蓝牙 D.串口 E.IEEE 802.11g 无线网卡17.以下哪个（些）不是计算机的输出设备（）。A.鼠标 B.显示器 C.键盘 D.扫描仪 E.绘图仪18.以下断电之后将不能保存数据的有（）。A.硬盘 B.寄存器 C.显存 D.内存 E.高速缓存,E,E,BCE,ACD,BCDE,17.以下断电之后将不能保存数据的有（）。noip12A.硬盘 B.ROM C.显存 D.RAM 17.以下断电之后仍能保存数据的有（）。noip13A.硬盘 B.ROM C.显存 D.RAM12计算机在工作过程中，若突然停电，（）中的信息不会丢失。noip14A.硬盘 B.CPU
18、 C.ROM D.RAM,2微型计算机中，控制器的基本功能是（）。noip14A.控制机器各个部件协调工作 B.实现算术运算和逻辑运算 C.存储各种控制信息 D.获取外部信息E.存放程序和数据1.在以下各项中，（）不是CPU 的组成部分。noip13A.控制器 B.运算器 C.寄存器 D.主板 E.算术逻辑单元(ALU)1.在以下各项中。（）不是CPU的组成部分。noip12A.控制器 B.运算器 C.寄存器 D.ALU E.RAM,2、BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM芯片上的程序。noip12A.控制器 B.CPU C.主板 D.内存条 E.硬盘,2、计算机的
19、三总线结构：,总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的,地址总线(AB)是单向总线，用以传送CPU向外设或存储器发出的地址信息。数据总线(DB)是双向总线，用以CPU与内存或接口之间传输数据信息。控制总线(CB)是双向总线，有的作为输出，有的作为输入，用以CPU与内存或I/O接口之间传送控制信息。分别传送地址信号、数据信号和控制信号。,中央处理器（CPU）能访问的最大存储器容量取决于（）。(NOIP8 NOIP7)A）地址总线 B）数据总线 C）控制总线 D）实际内存容量计算机系统总线上传送的信号有（）(NOI6)A.地址信号与控制信号B.数据信号
20、、控制信号与地址信号C.控制信号与数据信号D.数据信号与地址信号,A,B,二）软件系统,包括：、系统软件：（）操作系统软件：dos,OS/2，windows95,windows98,windows 2000,windowsxp windows Server,windows NT,unix,linux，Netware，Windows Vista（）计算机语言:机器语言汇编语言 高级语言：basic,pascal,c,c+,viscal basic、应用软件：office(word,powerpoin,excel),3dmax,flash,photoshop等.,什么是面向对象程序设计（模块化）：
21、,面向对象程序设计（英语：Object Oriented Programming，缩写：OOP），指一种程序设计范型，同时也是一种程序开发的方法论。它将对象作为程序的基本单元，将程序和数据封装其中，以提高软件的重用性、灵活性和扩展性。20世纪70年代的SmallTalk语言在面向对象方面堪称经典-以至于30年后的今天依然将这一语言视为面向对象语言的基础。传统的面向过程程序设计,面向对象语言(Object-Oriented Language)是一类以对象作为基本程序结构单位的程序设计语言,一种是纯面向对象语言，如Smalltalk、EIFFEL等。混合型面向对象语言，即在过程式语言及其它语言中加
22、入类、继承等成分，如C+、Objective-C等。Visual BC,Java,1、下列哪个（些）不是数据库软件的名称（）。NIOP10 A.MySQL B.SQL Server C.Oracle D.Outlook E.Foxpro2、下列哪个（些）软件属于操作系统软件（）。NIOP10 A.Microsoft Word B.Windows XP C.Foxmail D.金山影霸 E.Red Hat Linux3、下列哪个（些）程序设计语言支持面向对象程序设计方法（）。NIOP10 A.C+B.Object Pascal C.C D.Smalltalk E.Java4、下列哪个（些）软件不
23、是操作系统软件的名字（）。NOIP9 A）WindowsXP B)DOS C)Linux D)OS/2 E)Arch/Info 5、在以下各项中，（）不是操作系统软件。noip14A.Solaris B.Linux C.Sybase D.Windows Vista E.Symbian,18.在下列关于计算机语言的说法中，正确的有（）。noip13A.高级语言比汇编语言更高级，是因为它的程序的运行效率更高B.随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台C.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上D.C是一种面向过程的高级计算机语言18.在下列
24、关于计算机语言的说法中，正确的有（）。noip12A.Pascal和C都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上C.C+是历史上的第一个支持面向对象的计算机语言D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高,五、计算机指令系统计算机能直接识别和执行的命令称为指令。指令本身是二进制代码。是要计算机执行某种操作的命令。用机器指令编写的程序称之为机器语言程序。一条指令通常由操作码和地址码两部分组成。,六、计算机的数字系统数值信息在计算机内的表示方法就是用二进制数来表示。一般说来，如果数制只采用R个基本符号，则称为基R数值，R称为数制的基数，
25、而数制中每一固定位置对应的单位值称为权。,进位计数制的编码符合“逢R进位”的规则，各位的权是以R为底的幂，一个数可按权展开成为多项式。例如，一个十进制数256.47可按权展开为 256.47=21025101610十410-1710-2,1、R进制转换为十进制 基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就是十进制数例:3506.28=68+081+582+383+28-1=1862.25 例:0.2A16=216-1+1016-2=0.1640625,2、十进制转换为R进制 进制整数转换成R进制的整数:除R取余法。十进制小数转换成R进制时:乘R取整.例：将0.312510转换成
26、二进制数 0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以0.312510=0.01012,3、二、八、十六进制的相互转换 每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的0不能省略，两头不够时可以补0。尤其是小数后末尾的0例如：将1011010.12转换成八进制和十六进制数 001 011 010.100 1011010.12132.481 3 2.40101 1010.1000 1011010.12=5A.816 5 A.8 将十六进制数F7.28变为二进制数F 7.2 8 F7
27、.2816=11110111.0010121111 0111.0010 1000,十进制数2003等值于二进制数（）。(NOIP9)A）0100000111 B）10000011 C）110000111 D）1111010011十进制书11/128可用二进制数码序列表示为:()。(NOIP8)A）1011/1000000 B）1011/100000000 C）0.001011 D）0.0001011算式（2047）10（3FF）16（2000）8的结果是（）。(NOIP8 NOIP7)A）（2048）10 B）（2049）10 C）（3746）8 D）（1AF7）1664KB的存储器用十六进制
28、表示，它的最大的地址码是()(NOIP7)A)10000 B)FFFF C)1FFFF D)EFFFF,D,D,A,B,十进制算术表达式 3*512+7*64+4*8+5的运算结果，用二进制表示为().(NOIP5)下列无符号数中，最小的数是（）(NOIP6)A.（11011001）2B.(75)10C.(37)8D.(2A)16运算式(2008)10-(3723)8 的结果是（）。NOIP9 A）(-1715)10 B)(5)10 C)(5)16 D)(101)2 E)(3263)8,B,C,B CD,8、十进制数100.625等值于二进制数（）（NOIP10）。A.1001100.101
29、B.1100100.101 C.1100100.011 D.1001100.11 E.1001100.0113、(2004)10+(32)16的结果是（）。（NOIP10）A.(2036)16 B.(2054)10 C.(4006)8 3、以下二进制数的值与十进制数23.456 的值最接近的是（）（NOIP11）。A.10111.0101 B.11011.1111 C.11011.0111 D.10111.0111 E.10111.111112.(3725)8+(B)16的运算结果是（）。（NOIP11）D.(3006)10 E.(7E0)1612.(2010)16+(32)8的结果是（）。n
30、oip12A.(8234)10 B.(202A)16,7、与十进制数28.5625相等的四进制数是（）。noip14A.123.21 B.131.22 C.130.22 D.130.21 E.130.2015.(2008)10+(5B)16的结果是（）。noip148、与十进制数17.5625 对应的8 进制数是（）。noip13A.21.5625 B.21.44 C.21.73D.21.731 E.前4 个答案都不对13.(2070)16+(34)8 的结果是（）。noip13A.(8332)10 B.(208C)169.与十进制数1770.625 对应的八进制数是（）。noip12A.33
31、52.5 B.3350.5 C.3352.1161 D.3350.1151 E.前4个答案都不对,12.(2010)16+(32)8的结果是（）。noip12A.(8234)10 B.(202A)16,七、在计算机中带符号数的表示法原码：在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。如：10000010，00000010反码：反码的定义如下:对于正数，它的反码表示与原码相同。即x反=x原对于负数，则除符号位仍为“1”外，其余各位“1”换成”0”，”0”换成1”，即得到反码X反。例如-1101001 反=10010110。对于0，它的反码有两种表示:+0
32、 反=000-0 反=111,补码：正数的补码就是该正数本身。01100100补 01000100 对于负数:两头的1不变，中间取反。10100100补 11011100+0补-0补000。BCD码（8421码）BCD码就是用二进制代码表示的十进制数，也称BCD数。它是用4位二进制代码00001001来表示十进制数0-9。如：39的BCD码为00111001。,已知x=（0.1011010）2，则 x/2 补=（）2。(NOIP8)A）0.1011101 B）11110110 C）0.0101101 D）0.100110 x补码=10011000，其原码为()(NOIP7)A)01100111
33、1 B)11101000 C)11100110 D)01100101,C,B,八、信息存储单位位（bit，缩写为b）：度量数据的最小单位，表示一位二进制信息。字节(byte，缩写为B)：一个字节由八位二进制数字组成（l byte8bit）。字节是信息存储中最常用的基本单位。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：KB 1K=1024 MB 1M=1024KGB 1G=1024MTB 1t=1024G机器字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位
34、等。,九、计算机网络知识1、计算机网络的拓扑结构网络中各个站点相互连接的方法和形式称之为网络拓扑,总线拓扑,星型拓扑,环型拓扑,树型拓扑,2、计算机网络体系结构的核心是OSI模型国际标准化组织（ISO）提出的开放系统互联参考模型（OSI）已成为网络体系结构的标准,在这些层中，除了最高的第7层没有需要服务的上一层、最低的第1层没有可利用服务的下一层外，其它的每一层都建立在下一层的基础上，利用下一层来实现自己的功能，并向上一级提供服务。主机A与主机B进行通信时，通信协议是在对等层之间进行的。其中，物理层与物理层之间的通信协议是直接的，其他对等层之间的通信协议都是间接的。,7432,9、TCP/IP
35、是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。Noip14A.链路层 B网络层 C.传输层 D.应用层 E.会话层,TCP/IP（Transmission Control Protocol/Internet Protocol)的简写，中文译名为传输控制协议/因特网互联协议，又叫网络通讯协议。超文本传输协议（HTTP），文件传输协议（FTP），Telnet和简单邮件传输协议（SMTP：发送收电
36、子邮件，pop3：接收电子邮件）,3、Internet 网络地址(IP地址),A类网络为大型网络；B类网络为中型网络；C类网络为小型网络。这三类网络的地址特征为A类网络以0开头，网络号码是7位，主机号码是24位 B类网络以10开头，网络号码是14位，主机号码是16位C类网络以110开头，C类网络的网络号码是21位，主机号码是8位D类地址以1110开头，E类地址以11110开头。,8.常见的邮件传输服务器使用（）协议发送邮件。（NOIp11）A.HTTP B.SMTP C.TCP D.FTP E.POP39.不能在Linux 上使用的网页浏览器是（）。（NOIp11）A.Internet Exp
37、lore B.Netscape C.Opera D.Firefox E.Mozilla8、下列哪个网络上常用的名字缩写是错误的（）。（NOIP10）A、WWW（World Wide Web）B、URL（Uniform Resource Locator）C、HTTP（Hypertext Transfer Protocol）D、FTP（Fast Transfer Protocol）E、TCP（Transfer Control Protocol）。10、一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（）。A.调制解调器 B.路由器 C.网卡 D.网关
38、 E.网桥,十、逻辑运算：,运算：与:and 或:or+非:not 异或:xor运算的优先级：非与或,1、“与”运算（“”，“”，and）在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之“与”逻辑(并且)。“与”运算又称为逻辑乘，其运算符号为“”，有时也用“”表示。两变量“与”运算关系可表示为 F=AB 或者 F=AB,“与”运算的运算法则为：00=0 10=001=0 11=1结论：若A、B均为1，则F为1；否则，F为0推广：A0=0 A1=A,、“或”运算（“+”，“”,or）在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一
39、个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。“或”运算又称逻辑加，其运算符号为“+”，有时也用“”表示。两变量“或”运算的关系可表示为 F=A+B 或者 F=A B“或”运算的运算法则为：0+0=0 1+0=10+1=1 1+1=1结论：仅当A、B均为0时，F才为0 推广：A+0=A A+1=1,3.“非”运算 在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。“非”运算也叫求反运算或者逻辑否定。其运算符号为“-”，有时也用“”表示。“非”运算的逻辑关系可表示为 F=或者 F=A“非”运算的运算法则为=1=0,
40、(NOIP9)假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A/B/C/D的值是（）。A）true B）false C）0 D）1 E）NULL(NOIP8)已知A=35H，A/05H/A/30H 的结果是：（）。A）30H B）05H C）35H D）53H11.（NIOP11）设A=true，B=false，C=false，D=true，以下逻辑运算表达式值为真的有（）。A.(A B)(C D)B.(A B)C)D C.A(B C)D)D.(A(B C)D E.(A B)(C D),5已知A=11001010，B=00001111，C=01011100，ABC
41、=()。(A)11001110(B)01110110(C)11101110(D)0100110013下列逻辑运算正确的是（）。A)A（A+B）=AB)A+（AB）=AC)A（B+C）=AB+AC D)A+（BC）=（A+B）（A+C）E)A+1=A,5在Pascal语言中，表达式(21 xor 2)的值是（）noip12A.441 B.42 C.23 D.24 E.25 6在Pascal语言中，判断a不等于0且b不等于0的正确的条件表达式是（）noip12A.not a=0 or not b=0 B.not(a=0)and(b=0)C.not(a=0 and b=0)D.(a0)or(b0)E
42、.(a0)and(b0)11.设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（）。noip12A.(AB)(CD)E B.(AB)C)DE)C.A(BCDE)D.(A(BC)DE,竞赛环境的考察：,16.在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（）。noip12A.gcc/g+B.Turbo Pascal C.Turbo C D.free pascal 16.在下列各软件中，属于NOIP 竞赛（复赛）推荐使用的语言环境有（）。noip13A.gcc B.g+C.Turbo C D.free pascal19.NOIP竞赛推荐使用的语言环境有（）。n
43、oi14A.Dev-C+B.Visual C+C.free pascal D.Lazarus,信息学竞赛中的数学知识,集合的运算 排列与组合,集合及其运算,1、集合的运算：并、交、补、差 2、容斥原理,1、集合的运算：并、交、补、差并：交：补：或或差:-,A,B,A,B,A,A,B,A B,A B,A-B,8.（NOIP9）设全集E=1，2，3，4，5，集合A=1，4，B=1，2，5，C=2，4，则集合（A B）C 为（）。A）空集 B）1C）3，5D）1，5 E）1，3，51、（NOIP10）设全集I=a,b,c,d,e,f,g，集合A=a,b,c，B=b,d,e，C=e,f,g，那么集合为
44、（）。A.a,b,c,d B.a,b,d,e C.b,d,e D.b,c,d,e E.d,f,g2.（NOIP11）设全集I=a,b,c,d,e,f,g,h，集合BA=a,b,c,d,e,f，C A=c,d,e，AB=a,d，那么集合C B A 为（）。A.c,e B.d,e C.e D.c,d,e E.d,f,2、容斥原理,在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。,对有限集合S，用表示
45、S的元素个数,容斥原理的第一形式：设A，B是有限集合，则,容斥原理的第二形式：设A、B、C是有限集合，则,1、（NOIP10）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。2、某学校足球队有球衣30件，篮球队有球衣15件，排球队有球衣18件，三队队员总数为50人，其中有2人同时参加3个队，那么同时只参加两个队的队员有多少？、分母是1001的最简分数一共有多少个？,10，9,排列与组合,1.排列的定义:,从n个不同元素中,任取m个元
46、素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列.,排列数公式:,全排列问题：n个不同的元素排成一排，排列方法有：,=n*(n-1)*(n-2)*2*1=n!,2.组合的定义:,从n个不同元素中,任取m个元素,并成一组,叫做从n个不同元素中取出m个元素的一个组合.,组合数公式:,排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题.,加法原理和乘法原理从A到C共有多少中走法？,A,B,C,例1:学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？,解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7
47、个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种.,结论1 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.,例2:5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?,解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法.,结论2 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同
48、时要注意合并元素内部也可以作排列.,例3:袋中有不同年份生产的5分硬币23个,不同年份生产的1角硬币10个,如果从袋中取出2元钱,有多少种取法?,解 把所有的硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.,结论3 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.,分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.,例4
49、 学校安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序?,解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种.,结论4 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求.,分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性.,例5 某个班级共有43位同学,从中任抽5人,
50、正、副班长、团支部书记至少有一人在内的抽法有多少种?,解 43人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种.,结论5 排异法:有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除.,分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.,圆周排列：从n个不同的元素中取r个沿一圆周排列，排列的方案：,/r,N个元素的圆周排列：,/n,
