初赛知识复习初赛知识复习2009/10/111初赛试题形式初赛试题形式 初赛：初赛全部为笔试，满分初赛：初赛全部为笔试，满分100分。试题由四部分组成：分。试题由四部分组成： 1、选择题：共、选择题：共20题，每题题，每题1.5分，共计分，共计30分。每题有分。每题有5个备选答案，前个备选答案，前10个题为单选题个题为单选题(即每题有且只有一个正确答案，选对得分即每题有且只有一个正确答案，选对得分)，后，后10题为不定项选题为不定项选择题择题(即每题有即每题有1至至5个正确答案，只有全部选对才得分个正确答案，只有全部选对才得分)。 2、问题求解题：共、问题求解题：共2题，每题题，每题5分，共计分，共计10分。试题给出一个叙述较为简分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。考生给出的答案与标准答案相同，则得分：否则不得分。 3、程序阅读理解题：共、程序阅读理解题：共4题，每题题，每题8分，共计分，共计32分。题目给出一段程序分。题目给出一段程序(不不一定有关于程序功能的说明一定有关于程序功能的说明)，考生通过阅读理解该段程序给出程序的输出。输出，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。与标准答案一致，则得分；否则不得分。 4、程序完善题：共、程序完善题：共2题，每题题，每题14分，共计分，共计28分。题目给出一段关于程序功分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。出被略去的语句。填对则得分；否则不得分。 2知识范围知识范围内容与要求内容与要求 1、计算机的基本常识、计算机的基本常识 计算机和信息社会计算机和信息社会(信息社会的主要特征、计算机的主要特征、数信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化字通信网络的主要特征、数字化) 信息输入输出基本原理信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输信息交换环境、文字图形多媒体信息的输入输出方式入输出方式) 信息的表示与处理信息的表示与处理(信息编码、微处理部件信息编码、微处理部件MPU、内存储结构、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构指令，程序，和存储程序原理、程序的三种基本控制结构) 信息的存储、组织与管理信息的存储、组织与管理(存储介质、存储器结构、文件管理、数存储介质、存储器结构、文件管理、数据库管理据库管理) 信息系统组成及互连网的基本知识信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、部件间可扩展互连方式、层次式的互连结构、互联网络、TCPIP协议、协议、HTTP协议、协议、WEB应用的主要方式和特点应用的主要方式和特点) 人机交互界面的基本概念人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径窗口系统、人和计算机交流信息的途径(文本及交互操作文本及交互操作) 信息技术的新发展、新特点、新应用等。信息技术的新发展、新特点、新应用等。32、计算机的基本操作、计算机的基本操作 WINDOWS和和LINUX的基本操作知识的基本操作知识 联网的基本使用常识联网的基本使用常识 (网上浏览、搜索和查询等网上浏览、搜索和查询等) 常用的工具软件使用常用的工具软件使用(文字编辑、电子邮件收发等文字编辑、电子邮件收发等)3、程序设计的基本知识、程序设计的基本知识 数据结构数据结构 程序语言中基本数据类型程序语言中基本数据类型(字符、整数、长整数、浮点字符、整数、长整数、浮点) 浮点运算中的精度和数值比较浮点运算中的精度和数值比较 一维数组一维数组(串串)与线性表与线性表 记录类型记录类型(PASCAL)结构类型结构类型(C) 程序设计程序设计 结构化程序设计的基本概念结构化程序设计的基本概念 阅读理解程序的基本能力阅读理解程序的基本能力 具有将简单问题抽象成适合计算机解决的模型的基本能力具有将简单问题抽象成适合计算机解决的模型的基本能力 具有针对模型设计简单算法的基本能力具有针对模型设计简单算法的基本能力 程序流程描述程序流程描述(自然语言伪码自然语言伪码NS图其他图其他) 程序设计语言程序设计语言(PASCALCC+，) 基本算法处理基本算法处理 初等算法初等算法(计数、统计、数学运算等计数、统计、数学运算等) 排序算法排序算法(冒泡法、插入排序、合并排序、快速排序冒泡法、插入排序、合并排序、快速排序) 查找查找(顺序查找、二分法顺序查找、二分法) 回溯算法回溯算法4 计算机结构与组成原理计算机结构与组成原理 基本的数学知识基本的数学知识 （集合的运算、排列与组合）（集合的运算、排列与组合）5 计算机结构与组成原理计算机结构与组成原理6 一、计算机发展及应用一、计算机发展及应用1 1、第一台电子计算机的诞生：、第一台电子计算机的诞生： ENIACENIAC 19461946年年，世世界界上上第第一一台台数数字字式式电电于于计计算算机机是是由由美美固固宾宾夕夕法法尼尼亚亚大大学学的的物物理理学学家家 约约 翰翰 莫莫 克克 利利 （ John John MauchlyMauchly） 和和 工工 程程 师师 普普 雷雷 斯斯 伯伯 埃埃 克克 特特（ J.hesper.EckertJ.hesper.Eckert） 领领 导导 研研 制制 的的 取取 名名 为为 ENIACENIAC（ Elecotmnic Elecotmnic Nurnerical Nurnerical Integrator And CalculatorIntegrator And Calculator）的计算杌。）的计算杌。2 2、第一台具有存储程序功能的计算机：、第一台具有存储程序功能的计算机：EDVACEDVAC。冯冯诺依曼依据存储程序的工作原理设计诺依曼依据存储程序的工作原理设计. .运算器、控制器、存储器、输人设备和输出设备这五部分组成，运算器、控制器、存储器、输人设备和输出设备这五部分组成，同同ENIACENIAC相比，相比，EDVACEDVAC方案有两个重大改进：方案有两个重大改进： （1 1）：）：采用了二进制；采用了二进制； （2 2）：）：提出了提出了“存储程序存储程序”， 719031903年，冯年，冯诺伊曼（诺伊曼（NeumannNeumann，John vonJohn von）出生于匈牙利的布达佩斯）出生于匈牙利的布达佩斯 8考题考题: NOIP10: NOIP101 1、美籍匈牙利数学家冯、美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献包括（诺依曼对计算机科学发展所做出的贡献包括（ ）。）。A) A) 提出理想计算机的数学模型，成为计算机科学的理论基础。提出理想计算机的数学模型，成为计算机科学的理论基础。B)B) 提出存储程序工作原理，对现代电子计算机的发展产生深远影响。提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C)C) 设计出第一台具有存储程序功能的计算机设计出第一台具有存储程序功能的计算机EDVACEDVAC。D) D) 采用集成电路作为计算机的主要功能部件。采用集成电路作为计算机的主要功能部件。E) E) 指出计算机性能将以每两年翻一番的速度向前发展。指出计算机性能将以每两年翻一番的速度向前发展。9图灵(AlanTuring)是（）。(NOIP9)A）美国人B）英国人C）德国人D）匈牙利人艾伦艾伦麦席森麦席森图灵（图灵（AlanMathisonTuring，1912年年6月月23日日-1954年年6月月7日），日），英国英国数学家数学家图灵机由三部分组成，包括一条图灵机由三部分组成，包括一条 带子、一个读写头和一个控制装置。带子、一个读写头和一个控制装置。 图灵对于人工智能的发展有诸多贡献，例如：图灵曾写过一篇名为图灵对于人工智能的发展有诸多贡献，例如：图灵曾写过一篇名为机器会思考吗？（机器会思考吗？（Can Machine Think?）的论文，其中提出了一）的论文，其中提出了一种用于判定机器是否具有智能的种用于判定机器是否具有智能的试验试验方法，即图灵试验。方法，即图灵试验。图灵奖是图灵奖是美国美国计算机协会于计算机协会于1966年设立的，又叫年设立的，又叫A.M.图灵奖图灵奖，专，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦学的先驱、英国科学家艾伦图灵，这个奖设立目的之一是纪念这位图灵，这个奖设立目的之一是纪念这位科学家。科学家。B103.在下面各世界顶级的奖项中，为计算机科学与技术领域在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（作出杰出贡献的科学家设立的奖项是（）。）。noip12A.沃尔夫奖沃尔夫奖B.诺贝尔奖诺贝尔奖C.菲尔兹奖菲尔兹奖D.图灵奖图灵奖E.南丁格尔奖南丁格尔奖11.在下列关于图灵奖的说法中，正确的有（在下列关于图灵奖的说法中，正确的有（）。）。noip14A.图灵奖是美国计算机协会于图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作年设立的，专门奖励那些对计算机事业作出重要贡献的个人出重要贡献的个人B.图灵奖有图灵奖有“计算机界诺贝尔奖计算机界诺贝尔奖”之称之称C.迄今为止，还没有华裔计算机科学家获此殊荣迄今为止，还没有华裔计算机科学家获此殊荣D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵图灵2000AndrewChi-ChihYao-PhD,UIUC;Prof,Princeton(nowat清清华华)因对计算理论做出了诸多根本性的重大贡献因对计算理论做出了诸多根本性的重大贡献.(图灵奖自创立以来获得该图灵奖自创立以来获得该奖项的首位华裔学者奖项的首位华裔学者,全球华人的骄傲全球华人的骄傲)11第一个给计算机写程序的人是（）。(NOIP9)A）AlanMathisonTuringB）AdaLovelaceC）JohnvonNeumannD）JohnMc-CarthyE）EdsgerWybeDijkstr1、英国著名诗人拜伦的女儿AdaLovelace(爱达).由于她在程序设计上的开创性工作，AdaLovelace被称为世界上”第一位程序员”。“世界上第一位软件工程师”。 2、董董铁铁宝宝是“中国第一个程序员”。董铁宝1945年赴美国学习，在伊利诺伊大学学习、研究时，他参与了第一代电子计算机伊利亚克机的设计、编程和使用。董铁宝于1956年回到中国并任教于北京大学，成为王王选选（计计算算数数学学专专业业院院士士）的老师。董铁宝在1968年文化大革命期间自杀身亡。B123、计算机发展的几个阶段计算机发展的几个阶段第一代第一代（19461958）第二代第二代（19581964）第三代第三代（19641975）第四代第四代（1975至今）至今）主要电主要电子器件子器件电子管电子管晶体管晶体管中小规模中小规模集成电路集成电路大规模超大规大规模超大规模集成电路模集成电路微型计算机的问世是由于（）的出现。(NOIP8)A）中小规模集成电路B）晶体管电路C）（超）大规模集成电路D）电子管电路C134、计算机应用计算机应用科学计算（数值计算）科学计算（数值计算）。数据处理（信息处理）数据处理（信息处理）。人工智能人工智能。自动控制自动控制。计算机辅助设计和制造：计算机辅助设计和制造：CAI（计算机辅助教学）（计算机辅助教学）CAM（计算机辅助制造）（计算机辅助制造）CAT（计算机辅助测试）（计算机辅助测试）CAD（计算机辅助设计）（计算机辅助设计）CAE(计算机辅助教育计算机辅助教育)CIMS（计算机集成制造系统）（计算机集成制造系统）14二、保护知识产权：保护知识产权：计算机软件保护条例计算机软件保护条例最早是1991年年6月月4日日国务院发布的，现已废止。现公布计算机软件保护条例，自2002年年1月月1日日起实施。第二章软件著作权软件著作权第八条软件著作权著作权人享有下列各项权利：（一）发表权（二）署名权（三）修改权（四）复制权；（五）发行权（六）出租权（七）信息网络传播权（八）翻译权（九）应当由软件著作权人享有的其他权利。15计算机软件保护法是用来保护软件()的（NOIP7）A)编写权B)复制权C)使用权D)著作权D16三、计算机病毒计算机病毒计算机病毒是一种功能较特殊的计算机程序，计算机病毒的特征可以归纳为下面两点：能够将自身复制到其他程序中。不独立以文件形式存在，仅附加在别的程序上。失去这两个特征中的任何一个，都不成其为病毒。17计算机病毒是()(NOIP7)A)通过计算机传播的危害人体健康的一种病毒B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C)一种由于计算机元器件老化而产生的对生态环境有害的物质D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒计算机病毒的特点是（）(NOIP6)A.传播性、潜伏性、易读性与隐蔽性B.破坏性、传播性、潜伏性与安全性C.传播性、潜伏性、破坏性与隐蔽性D.传播性、潜伏性、破坏性与易读性计算机病毒传染的必要条件是：（）。(NOIP8)A）在内存中运行病毒程序B）对磁盘进行读写操作C）在内存中运行含有病毒的可执行的程序D）复制文件BCB18四、计算机系统的组成：四、计算机系统的组成：1、硬件系统2、软件系统只有硬件没有安装软件的计算机称为只有硬件没有安装软件的计算机称为“裸机裸机”191、硬件系统的组成：五个基本部分组成：五个基本部分组成：（1）运算器）运算器（2）控制器）控制器（3）存储器）存储器（4）输人设备）输人设备（5）输出设备）输出设备20输输入入设设备备运算器运算器存储器存储器控制器控制器输输出出设设备备输入输入输出输出211）运算器）运算器+控制器控制器=CPU:中央处理器中央处理器（CenterProcessUnit）计算机的核心部件(指挥系统)直接决定计算机的运行速度。如：计算机的配置：“Intel奔腾IV2.8GHz/512M/80GB/50X”每秒运算次数是：2.8*210*210*210222）存储器）存储器外存储器：硬盘、光盘、软盘、优盘等。外存储器：硬盘、光盘、软盘、优盘等。内存储器：内存储器：ROM ROM 和和 RAM RAM ROM: Read Only Memory ROM: Read Only Memory ：只读存储器：只读存储器 RAM: Random Access Memory RAM: Random Access Memory ：随机存取存储器：随机存取存储器 平时说的内存：平时说的内存：RAMRAM：256MB,512MB,1GMB256MB,512MB,1GMB 高速缓存器：高速缓存器：cachecache 高速缓存器高速缓存器内存速度内存速度 外存速度外存速度23主机的概念：主机的概念：包括：包括：CPUCPU和和内存储器内存储器24CPU访问内存的速度比访问下列哪个（些）存储设备要慢（）。（NOIP9）A）寄存器B）硬盘C）软盘D）高速缓存E）光盘微型计算机中，（）的存取速度最快。(NOIP8)A）高速缓存B）外存储器C）寄存器D）内存储器在计算机硬件系统中，cache是()存储器(NOIP7)A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲ADAD25 4 4、下面哪个部件对于个人桌面电脑的正常运行不是必需的（、下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。）。NOIP10NOIP10A.CPU B. A.CPU B. 图形卡（显卡）图形卡（显卡） C. C. 光驱光驱 D. D. 主板主板 E. E. 内存内存、用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（、用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ ）。）。NOIP10NOIP10 A.A.针式打印机针式打印机 B. B. 喷墨打印机喷墨打印机 C. C. 激光打印机激光打印机 D. D. 笔式绘图仪笔式绘图仪 E. E. 喷墨绘图喷墨绘图仪仪、下列哪个（些）不是计算机的存储设备（、下列哪个（些）不是计算机的存储设备（ ）。）。NOIP10NOIP10 A. A.文件管理器文件管理器 B. B. 内存内存 C. C. 显卡显卡 D. D. 硬盘硬盘 E. U E. U盘盘 、下列说法中正确的有（、下列说法中正确的有（ ）。）。NOIP10NOIP10A.CPUA.CPU的基本功能就是执行指令。的基本功能就是执行指令。 B.CPU B.CPU的主频是指的主频是指CPUCPU在在1 1秒内完成的指令周期数，主频越快的秒内完成的指令周期数，主频越快的CPUCPU速度一定越快。速度一定越快。 C. C.内部构造不同的内部构造不同的CPUCPU运行相同的机器语言程序，一定会产生不同的结果。运行相同的机器语言程序，一定会产生不同的结果。 D. D.在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。 E. E.数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。、彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（、彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ）。）。NOIP10NOIP10 A. A.红红 B. B. 白白 C. C. 蓝蓝 D. D. 绿绿 E. E. 橙橙、下列哪个（些）是、下列哪个（些）是6464位处理器（位处理器（ ）。）。NOIP10NOIP10 A. Intel Itanium B. Intel Pentium III C. AMD Athlon64 A. Intel Itanium B. Intel Pentium III C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 D. AMD Opteron E. IBM Power 5C,C,C,ADE,ACD,ACDE26NOIP11NOIP116. 6. 下列设备中没有计算功能的是（下列设备中没有计算功能的是（ ）。）。A. A. 笔记本电脑笔记本电脑B. B. 掌上电脑掌上电脑C. C. 智能手机智能手机 D. D. 电子计算器电子计算器 E. E. 液晶显示器液晶显示器7. Intel7. Intel的首颗的首颗64 64 位处理器是（位处理器是（ ）。）。A. 8088 B. 8086 C. 80386 D. 80486 E. PentiumA. 8088 B. 8086 C. 80386 D. 80486 E. Pentium15. 15. 下列外设接口中可以通过无线连接的方式连接设备的是（下列外设接口中可以通过无线连接的方式连接设备的是（ ）。）。A. USB 2.0 A. USB 2.0 高速版高速版 B. B. 红外红外 C. C. 蓝牙蓝牙 D. D. 串口串口 E. IEEE 802.11g E. IEEE 802.11g 无线网卡无线网卡17. 17. 以下哪个（些）不是计算机的输出设备（以下哪个（些）不是计算机的输出设备（ ）。）。A. A. 鼠标鼠标 B. B. 显示器显示器 C. C. 键盘键盘 D. D. 扫描仪扫描仪 E. E. 绘图仪绘图仪18. 18. 以下断电之后将不能保存数据的有（以下断电之后将不能保存数据的有（ ）。）。A. A. 硬盘硬盘 B. B. 寄存器寄存器 C. C. 显存显存 D. D. 内存内存 E. E. 高速缓存高速缓存E,E,BCE,ACD,BCDE2717.以下断电之后将不能保存数据的有（以下断电之后将不能保存数据的有（）。）。noip12A.硬盘硬盘B.ROMC.显存显存D.RAM17.以下断电之后仍能保存数据的有（以下断电之后仍能保存数据的有（）。）。noip13A.硬盘硬盘B.ROMC.显存显存D.RAM12计算机在工作过程中，若突然停电，（计算机在工作过程中，若突然停电，（）中的信）中的信息不会丢失。息不会丢失。noip14A.硬盘硬盘B.CPUC.ROMD.RAM282 2微型计算机中，控制器的基本功能是（微型计算机中，控制器的基本功能是（ ）。）。noip14noip14A. A. 控制机器各个部件协调工作控制机器各个部件协调工作 B. B. 实现算术运算和逻辑实现算术运算和逻辑运算运算 C. C. 存储各种控制信息存储各种控制信息 D. D. 获取获取外部信息外部信息E. E. 存放程序和数据存放程序和数据1. 1. 在以下各项中，（在以下各项中，（ ）不是）不是CPU CPU 的组成部分。的组成部分。noip13noip13A. A. 控制器控制器 B. B. 运算器运算器 C. C. 寄存器寄存器 D. D. 主板主板 E. E. 算术逻辑单元算术逻辑单元(ALU)(ALU)1.在以下各项中。（在以下各项中。（）不是）不是CPU的组成部分。的组成部分。noip12A.控制器控制器B.运算器运算器C.寄存器寄存器D.ALUE.RAM292、BIOS（基本输入输出系统）是一组固化在计算机内（基本输入输出系统）是一组固化在计算机内（）上一个上一个ROM芯片上的程序。芯片上的程序。noip12A.控制器控制器B.CPUC.主板主板D.内存条内存条E.硬盘硬盘302、计算机的三总线结构：、计算机的三总线结构：总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的息传输都是通过它们来实现的地址总线地址总线(AB)是单向总线，用以传送是单向总线，用以传送CPU向外设或存储器发出的地址信息。向外设或存储器发出的地址信息。数据总线数据总线(DB)是双向总线，用以是双向总线，用以CPU与内存或接口之间传输数据信息。与内存或接口之间传输数据信息。控制总线控制总线(CB)是双向总线，有的作为输出，有的作为输入，用以是双向总线，有的作为输出，有的作为输入，用以CPU与内存或与内存或I/O接口之间传送控制信息。接口之间传送控制信息。分别传送分别传送地址信号地址信号、数据信号数据信号和和控制信号控制信号。31中央处理器（CPU）能访问的最大存储器容量取决于（ ）。(NOIP8NOIP7)A）地址总线B）数据总线C）控制总线D）实际内存容量计算机系统总线上传送的信号有（）(NOI6)A.地址信号与控制信号B.数据信号、控制信号与地址信号C.控制信号与数据信号D.数据信号与地址信号AB32二）软件系统二）软件系统包括：包括：、系统软件：、系统软件：（）操作系统软件：（）操作系统软件： dos, OS/2 dos, OS/2 ，windows95,windows98,windows 2000,windowsxpwindows95,windows98,windows 2000,windowsxp windows Server,windows NT ,unix,linux windows Server,windows NT ,unix,linux，NetwareNetware ， WindowsVista （）计算机语言（）计算机语言: :机器语言机器语言汇编语言汇编语言 高级语言：高级语言：basic,pascal,c,c+,viscal basicbasic,pascal,c,c+,viscal basic、应用软件：、应用软件：office (word,powerpoin,excel),3dmax,flash,photoshopoffice (word,powerpoin,excel),3dmax,flash,photoshop等等. .33什么是面向对象程序设计（什么是面向对象程序设计（模块化模块化 ）：）：面向对象程序设计（英语：面向对象程序设计（英语：Object Oriented Object Oriented ProgrammingProgramming，缩写：，缩写：OOPOOP），指一种程序设计范型，同），指一种程序设计范型，同时也是一种程序开发的方法论。它将对象作为程序的基时也是一种程序开发的方法论。它将对象作为程序的基本单元，将程序和数据封装其中，以提高软件的重用性、本单元，将程序和数据封装其中，以提高软件的重用性、灵活性和扩展性。灵活性和扩展性。 2020世纪世纪7070年代的年代的SmallTalkSmallTalk语言在面向对象方面堪称经语言在面向对象方面堪称经典典-以至于以至于3030年后的今天依然将这一语言视为面向对象年后的今天依然将这一语言视为面向对象语言的基础。语言的基础。传统的传统的面向过程面向过程程序设计程序设计 34面向对象语言面向对象语言(Object-Oriented Language)是一类以对是一类以对象作为基本程序结构单位的程序设计语言象作为基本程序结构单位的程序设计语言 一种是纯面向对象语言，如一种是纯面向对象语言，如Smalltalk、EIFFEL等等 。混合型面向对象语言，即在过程式语言及其它语言中混合型面向对象语言，即在过程式语言及其它语言中加入类、继承等成分，如加入类、继承等成分，如C+、Objective-C等。等。Visual BC, Java351 1、下列哪个（些）不是数据库软件的名称（、下列哪个（些）不是数据库软件的名称（ ）。）。NIOP10NIOP10 A. MySQL B. SQL Server C. Oracle A. MySQL B. SQL Server C. Oracle D D. Outlook E. Foxpro. Outlook E. Foxpro2 2、下列哪个（些）软件属于操作系统软件（、下列哪个（些）软件属于操作系统软件（ ）。）。NIOP10NIOP10 A. Microsoft Word A. Microsoft Word B B. Windows XP C. Foxmail . Windows XP C. Foxmail D. D. 金山影霸金山影霸 E E. Red Hat Linux. Red Hat Linux3 3、下列哪个（些）程序设计语言支持面向对象程序设计方法（、下列哪个（些）程序设计语言支持面向对象程序设计方法（ ）。）。NIOP10NIOP10 A. C+ B. Object Pascal C. C D. Smalltalk E. Java A. C+ B. Object Pascal C. C D. Smalltalk E. Java4 4、下列哪个（些）软件不是操作系统软件的名字（、下列哪个（些）软件不是操作系统软件的名字（ ）。）。NOIP9 NOIP9 A A）WindowsXP B) DOS C) Linux D) OS/2 WindowsXP B) DOS C) Linux D) OS/2 E E) ) Arch/Info Arch/Info 5 5、 在以下各项中，（在以下各项中，（ ）不是操作系统软件。）不是操作系统软件。noip14noip14A. Solaris B. Linux C. Sybase D. Windows Vista E. A. Solaris B. Linux C. Sybase D. Windows Vista E. SymbianSymbian3618. 18. 在下列关于计算机语言的说法中，正确的有（在下列关于计算机语言的说法中，正确的有（ ）。）。noip13noip13A. A. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高高级语言比汇编语言更高级，是因为它的程序的运行效率更高B. B. 随着随着PascalPascal、C C等高级语言的出现，机器语言和汇编语言已经退出了等高级语言的出现，机器语言和汇编语言已经退出了历史舞台历史舞台C. C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上算机上D. CD. C是一种面向过程的高级计算机语言是一种面向过程的高级计算机语言18.在下列关于计算机语言的说法中，正确的有（在下列关于计算机语言的说法中，正确的有（）。）。noip12A.Pascal和和C都是编译执行的高级语言都是编译执行的高级语言B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上机上C.C+是历史上的第一个支持面向对象的计算机语言是历史上的第一个支持面向对象的计算机语言D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高高级语言比汇编语言更高级，是因为它的程序的运行效率更高37五五、计算机指令系统计算机指令系统计算机能直接识别和执行的命令称为指令。指令本身是二进制代码。是要计算机执行某种操作的命令。用机器指令编写的程序称之为机器语言程序。一条指令通常由操作码和地址码两部分组成。38六六、计算机的数字系统计算机的数字系统数值信息在计算机内的表示方法就是用二进制数来表示。一般说来，如果数制只采用R个基本符号，则称为基R数值，R称为数制的基数，而数制中每一固定位置对应的单位值称为权。进制进制基数基数R基本符号基本符号二进制20，1八进制80,1,2,3,4,5,6,7十进制100,1,2,3,4,5,6,7,8,9十六进制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（对应十进制数的1015。）进位计数制的编码符合“逢R进位”的规则，各位的权是以R为底的幂，一个数可按权展开成为多项式。例如，一个十进制数256.47可按权展开为256.47=21025101610十410-1710-2391、R进制转换为十进制进制转换为十进制基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就是十进制数例:3506.28=68+081+582+383+28-1=1862.25例:0.2A16=216-1+1016-2=0.1640625402、十进制转换为、十进制转换为R进制进制进制整数转换成R进制的整数:除除R取余法取余法。十进制小数转换成R进制时:乘乘R取整取整.例：将0.312510转换成二进制数0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以0.312510=0.01012413、二、八、十六进制的相互转换、二、八、十六进制的相互转换每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的0不能省略，两头不够时可以补0。尤其是小数后末尾的0例如：将1011010.12转换成八八进制和十六十六进制数001011010.1001011010.12132.48132.401011010.10001011010.12=5A.8165A.8将十六进制数F7.28变为二二进制数F7.28F7.2816=11110111.00101211110111.0010100042十进制数2003等值于二进制数（）。(NOIP9)A）0100000111B）10000011C）110000111D）11111010011E）1111010011十进制书11/128可用二进制数码序列表示为:()。(NOIP8)A）1011/1000000B）1011/100000000C）0.001011D）0.0001011算式（2047）10（3FF）16（2000）8的结果是（）。(NOIP8NOIP7)A）（2048）10B）（2049）10C）（3746）8D）（1AF7）1664KB的存储器用十六进制表示，它的最大的地址码是()(NOIP7)A)10000B)FFFFC)1FFFFD)EFFFFDDAB43十进制算术表达式3*512+7*64+4*8+5的运算结果，用二进制表示为().(NOIP5)A10111100101B11111100101C11110100101D11111101101下列无符号数中，最小的数是（）(NOIP6)A.（11011001）2B.(75)10C.(37)8D.(2A)16运算式(2008)10-(3723)8的结果是（）。NOIP9A）(-1715)10B)(5)10C)(5)16D)(101)2E)(3263)8BCBCD448 8、十进制数、十进制数100.625100.625等值于二进制数（等值于二进制数（ ）（）（NOIP10NOIP10）。）。 A. 1001100.101 B. 1100100.101 C. 1100100.011 A. 1001100.101 B. 1100100.101 C. 1100100.011 D. 1001100.11 E. 1001100.01 D. 1001100.11 E. 1001100.011313、(2004)10 + (32)16(2004)10 + (32)16的结果是（的结果是（ ）。（）。（NOIP10NOIP10） A. (2036)16 B. (2054)10 C. (4006)8 A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10 D. (100000000110)2 E. (2036)103 3、 以下二进制数的值与十进制数以下二进制数的值与十进制数23.456 23.456 的值最接近的是（的值最接近的是（ ）（）（NOIP11NOIP11）。）。 A. 10111.0101 B. 11011.1111 C. 11011.0111 A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111 D. 10111.0111 E. 10111.111112. (3725)8 + (B)1612. (3725)8 + (B)16的运算结果是（的运算结果是（ ）。（）。（NOIP11NOIP11） A. (3736)8 B. (2016)10 C. (11111100000)2 A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16 D. (3006)10 E. (7E0)1612.(2010)16+(32)8的结果是（的结果是（）。）。noip12A.(8234)10B.(202A)16C.(100000000110)2D.(2042)16457 7、与十进制数、与十进制数28.562528.5625相等的四进制数是（相等的四进制数是（ ）。）。noip14noip14A. 123.21 B. 131.22 C. 130.22 D. 130.21 A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.20E. 130.2015.(2008)10+(5B)16的结果是（的结果是（）。）。noip14A.(833)16B.(2099)10C.(4063)8D.(100001100011)28 8、与十进制数、与十进制数17.5625 17.5625 对应的对应的8 8 进制数是（进制数是（ ）。）。noip13noip13A. 21.5625 B. 21.44 C. 21.73A. 21.5625 B. 21.44 C. 21.73D. 21.731 E. D. 21.731 E. 前前4 4 个答案都不对个答案都不对13. (2070)16 + (34)8 13. (2070)16 + (34)8 的结果是（的结果是（ ）。）。noip13noip13A. (8332)10 B. (208C)16A. (8332)10 B. (208C)16C. (100000000110)2 D. (20214)8C. (100000000110)2 D. (20214)89.与十进制数与十进制数1770.625对应的八进制数是（对应的八进制数是（）。）。noip12A.3352.5B.3350.5C.3352.1161D.3350.1151E.前前4个答案都不对个答案都不对4612.(2010)16+(32)8的结果是（的结果是（）。）。noip12A.(8234)10B.(202A)16C.(100000000110)2D.(2042)1647七、七、在计算机中带符号数的表示法在计算机中带符号数的表示法原码：原码：在在用用二二进进制制原原码码表表示示的的数数中中，符符号号位位为为0表表示示正正数数，符符号号位位为为1表表示示负负数数，其余各位表示数值部分。其余各位表示数值部分。如：如：10000010，00000010反码：反码：反码的定义如下反码的定义如下: : 对于正数，它的反码表示与原码相同。即对于正数，它的反码表示与原码相同。即xx反反=x=x原原对于负数，则除符号位仍为对于负数，则除符号位仍为“1”“1”外，其余各位外，其余各位“1”“1”换成换成”0”0”，”0”0”换成换成1”1”，即得到反码，即得到反码XX反。例如反。例如-1101001 -1101001 反反=10010110=10010110。对于对于0 0，它的反码有两种表示，它的反码有两种表示:+0 :+0 反反=000 -0 =000 -0 反反=111=11148补码：补码： 正数的补码就是该正数本身。正数的补码就是该正数本身。 01100100 01100100补补 0100010001000100 对于负数对于负数: :两头的两头的1 1不变，中间取反。不变，中间取反。 1 1010001001 10000补补 1101110011011100+0+0补补-0-0补补000000。 BCD码（码（8421码）码）BCD码码就就是是用用二二进进制制代代码码表表示示的的十十进进制制数数，也也称称BCD数数。它它是是用用4位位二二进进制制代代码码00001001来来表表示示十十进进制制数数0-9。如如：39的的BCD码为码为00111001。49已知x=（0.1011010）2，则x/2补=（）2。(NOIP8)A）0.1011101B）11110110C）0.0101101D）0.100110x补码=10011000，其原码为()(NOIP7)A)011001111B)11101000C)11100110D)01100101CB50八、八、信息存储单位信息存储单位位（位（bit，缩写为，缩写为b）：度量数据的最小单位，表示一位二进制信息。字节字节(byte，缩写为，缩写为B)：一个字节由八位二进制数字组成（lbyte8bit）。字节是信息存储中最常用的基本单位。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：KB1K=1024MB1M=1024KGB1G=1024MTB1t=1024G机机器器字字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位等。51九、计算机网络知识九、计算机网络知识1、计算机网络的拓扑结构计算机网络的拓扑结构网络中各个站点相互连接的方法和形式称之为网络拓扑总线拓扑总线拓扑星型拓扑星型拓扑环型拓扑环型拓扑树型拓扑树型拓扑522、计算机网络体系结构的核心是、计算机网络体系结构的核心是OSI模型模型国际标准化组织（ISO）提出的开放系统互联参考模型（OSI）已成为网络体系结构的标准在这些层中，除了最高的第7层没有需要服务的上一层、最低的第1层没有可利用服务的下一层外，其它的每一层都建立在下一层的基础上，利用下一层来实现自己的功能，并向上一级提供服务。主机A与主机B进行通信时，通信协议是在对等层之间进行的。其中，物理层与物理层之间的通信协议是直接的，其他对等层之间的通信协议都是间接的。7432539 9、TCP/IPTCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（传输控制协议（TCPTCP）和网际协议（）和网际协议（IPIP）。）。TCP/IP TCP/IP 协议把协议把InternetInternet网络网络系统描述成具有系统描述成具有四四个层次功能的网络模型个层次功能的网络模型, ,其中其中提供源节点和目的节点提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是之间的信息传输服务，包括寻址和路由器选择等功能的是（ ）。）。Noip14Noip14A. A. 链路层链路层 B B网络层网络层 C. C. 传输层传输层 D. D. 应用层应用层 E.E.会话层会话层TCP/IP（TransmissionControlProtocol/InternetProtocol)的简写，中文译名为传输控制协议传输控制协议/因特网互联协因特网互联协议议，又叫网络通讯协议 。超文本传输协议（HTTP），文件传输协议（FTP），Telnet和简单邮件传输协议（SMTP：发送收电子邮件 ，pop3：接收电子邮件 ） 543、Internet网络地址网络地址(IP地址地址)A类网络为大型网络；B类网络为中型网络；C类网络为小型网络。这三类网络的地址特征为A类网络以0开头，网络号码是7位，主机号码是24位B类网络以10开头，网络号码是14位，主机号码是16位C类网络以110开头，C类网络的网络号码是21位，主机号码是8位D类地址以1110开头，E类地址以11110开头。558. 8. 常见的邮件传输服务器使用（常见的邮件传输服务器使用（ ）协议）协议发送发送邮件。（邮件。（NOIp11NOIp11） A. HTTP B. SMTP C. TCP D. FTP E. POP3 A. HTTP B. SMTP C. TCP D. FTP E. POP39. 9. 不能在不能在Linux Linux 上使用的网页浏览器是（上使用的网页浏览器是（ ）。）。 （NOIp11NOIp11） A. Internet Explore B. Netscape C. Opera D. Firefox E. A. Internet Explore B. Netscape C. Opera D. Firefox E. MozillaMozilla8 8、下列哪个网络上常用的名字缩写是错误的（、下列哪个网络上常用的名字缩写是错误的（ ）。（）。（NOIP10NOIP10） A A、WWWWWW（World Wide WebWorld Wide Web） B B、URLURL（Uniform Resource LocatorUniform Resource Locator） C C、HTTPHTTP（Hypertext Transfer ProtocolHypertext Transfer Protocol） D D、FTPFTP（Fast Transfer ProtocolFast Transfer Protocol） E E、TCPTCP（Transfer Control ProtocolTransfer Control Protocol）。）。1010、一台计算机如果要利用电话线上网，就必须配置能够对数字信号和、一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（模拟信号进行相互转换的设备，这种设备是（ ）。）。 A. A. 调制解调器调制解调器 B. B. 路由器路由器 C. C. 网卡网卡 D. D. 网关网关 E. E. 网桥网桥56十、逻辑运算：十、逻辑运算：运算：运算： 与与: and : and 或或: or +: or + 非非: not : not 异或异或: xor: xor运算的优先级：非与或运算的优先级：非与或571、 “ “与与” ” 运算运算（ “”， “” ，and） 在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才在逻辑问题中，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之能发生，则这种因果关系称之“与与”逻辑逻辑( (并且并且) )。 “与与”运算又称为运算又称为逻辑乘逻辑乘，其运算符号为其运算符号为“”“”，有时也用，有时也用“”“”表示。表示。两变量“与”运算关系可表示为 F = ABF = AB 或者 F = ABF = AB58“与与”运算的运算法则为运算的运算法则为：00 = 0 10 = 000 = 0 10 = 001 = 0 11 = 101 = 0 11 = 1结论：若结论：若A A、B B均为均为1 1，则，则F F为为1 1；否则，；否则，F F为为0 0推广：推广：A0=0 A1=AA0=0 A1=A59、“或或”运算（运算（ “+”“+”， “” “” ,or） 在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只在逻辑问题的描述中，如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或或”逻辑。逻辑。 “ “或或”运算又称运算又称逻辑加逻辑加，其运算符号为，其运算符号为“+”“+”，有时也用，有时也用“”“”表示。两变表示。两变量量“或或”运算的关系可表示为运算的关系可表示为 F = A + B F = A + B 或者或者 F = A B F = A B“或或”运算的运算法则为运算的运算法则为：0 + 0 = 0 1 + 0 = 10 + 0 = 0 1 + 0 = 10 + 1 = 1 1 + 1 = 10 + 1 = 1 1 + 1 = 1结论：仅当结论：仅当A A、B B均为均为0 0时，时，F F才为才为0 0 推广：推广：A+0=A A+1=1A+0=A A+1=1603.“3.“非非”运算运算 在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件在逻辑问题中，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为发生的条件之间构成矛盾，则这种因果关系称为“非非”逻辑。逻辑。“非非”运算也叫求运算也叫求反运算反运算或者或者逻辑否定逻辑否定。其运算符号为。其运算符号为“- -”，有时也用，有时也用“ ”表示。表示。“非非”运算的逻辑关系可表示为运算的逻辑关系可表示为 F= F= 或者或者 F = A F = A“非非”运算的运算法则为运算的运算法则为 =1=1 =0=061(NOIP9)假设假设A=true,B=false,C=ture,D=ture,逻辑运算表达式逻辑运算表达式A/B/C/D的值是（的值是（）。）。A）trueB）falseC）0D）1E）NULL(NOIP8)已知已知A=35H，A/05H/A/30H的结果是：（的结果是：（）。）。A）30HB）05HC）35HD）53H11. 11. （NIOP11NIOP11）设）设A = trueA = true，B = falseB = false，C = falseC = false，D = trueD = true，以下逻辑，以下逻辑运算表达式值为真的有（运算表达式值为真的有（ ）。）。 A. (A B )(C D ) A. (A B )(C D ) B. (A B) C ) D B. (A B) C ) D C. A(B C ) D ) C. A(B C ) D ) D. (A(B C ) D D. (A(B C ) D E. (A B )(C D ) E. (A B )(C D )625 5已知已知A=11001010A=11001010，B=00001111B=00001111，C=01011100C=01011100，ABC=( )ABC=( )。(A)11001110 (B)01110110(A)11001110 (B)01110110(C)11101110 (D)01001100(C)11101110 (D)010011001313下列逻辑运算正确的是（下列逻辑运算正确的是（ ）。）。A) AA) A（A + B A + B ）= A= AB) A +B) A +（ABAB）= A= AC) AC) A（B + C B + C ）= AB + AC = AB + AC D) A +D) A +（BCBC）= =（A + BA + B）（A + CA + C）E) A+1=A E) A+1=A 635在在Pascal语言中，表达式语言中，表达式(21xor2)的值是（的值是（）noip12A.441B.42C.23D.24E.256在在Pascal语言中，判断语言中，判断a不等于不等于0且且b不等于不等于0的正确的条的正确的条件表达式是（件表达式是（）noip12A.nota=0ornotb=0B.not(a=0)and(b=0)C.not(a=0andb=0)D.(a0)or(b0)E.(a0)and(b0)11.设设A=B=D=true，C=E=false，以下逻辑运算表达式值为，以下逻辑运算表达式值为真的有（真的有（）。）。noip12A.( A B) (C D) EB.(A B) C) D E)C.A (B C D E)D.(A (B C) D E64竞赛环境的考察：竞赛环境的考察：16.在下列各软件中，属于在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（竞赛（复赛）推荐使用的语言环境有（）。）。noip12A.gcc/g+B.TurboPascalC.TurboCD.freepascal16.在下列各软件中，属于在下列各软件中，属于NOIP竞赛（复赛）推荐使用的语言环境有（竞赛（复赛）推荐使用的语言环境有（）。）。noip13A.gccB.g+C.TurboCD.freepascal19.NOIP竞赛推荐使用的语言环境有（竞赛推荐使用的语言环境有（）。）。noi14A.Dev-C+B.VisualC+C.freepascalD.Lazarus65信息学竞赛中的数学知识信息学竞赛中的数学知识 集合的运算 排列与组合66 集合及其运算1 1、集合的运算：并、交、补、差、集合的运算：并、交、补、差 2 2、容斥原理、容斥原理671 1、集合的运算：并、交、补、差、集合的运算：并、交、补、差并：并：交：交：补：补： 或或或或差差: -: -A AB BA AB BA AA AB BA BA BA BA BA-BA-B688. 8. （NOIP9NOIP9）设全集）设全集E=1E=1，2 2，3 3，4 4，55，集合，集合A=1A=1，44，B=1B=1，2 2，55，C=2C=2，44，则集合（，则集合（A BA B）C C 为（为（ ）。）。AA） 空集空集 B B） 1C 1C） 3 3，5D5D）11，5 E5 E） 11，3 3，551 1、（、（NOIP10NOIP10）设全集）设全集I = a, b, c, d, e, f, gI = a, b, c, d, e, f, g，集合，集合A = a, b, cA = a, b, c， B = b, d, e B = b, d, e，C = e, f, gC = e, f, g，那么集合为（，那么集合为（ ）。）。 A. a, b, c, d B. a, b, d, e A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c, d, e E. d, f, g C. b, d, e D. b, c, d, e E. d, f, g2. 2. （NOIP11NOIP11）设全集）设全集I = a, b, c, d, e, f, g, hI = a, b, c, d, e, f, g, h， 集合集合BABA = a, b, c, d, e, f= a, b, c, d, e, f， C A C A = c, d, e= c, d, e，AB = a, dAB = a, d，那么集合，那么集合C B A C B A 为（为（ ）。）。 A. c, e B. d, e C. e D. c, d, e E. d, f A. c, e B. d, e C. e D. c, d, e E. d, f692 2、容斥原理、容斥原理在计数时，为了使重叠部分不被重复计算，人们研在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为数的方法称为容斥原理容斥原理。70对有限集合对有限集合S S，用表示，用表示S S的元素个数的元素个数 容斥原理的第一形式：容斥原理的第一形式：设设A A，B B是有限集合，则是有限集合，则容斥原理的第二形式：设容斥原理的第二形式：设A A、B B、C C是有限集合，则是有限集合，则71 1 1、（、（NOIP10NOIP10）7575名儿童到游乐场去玩。他们可以骑名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中旋转木马，坐滑行铁道，乘宇宙飞船。已知其中2020人这三种东西都玩过，人这三种东西都玩过，5555人至少玩过其中的两人至少玩过其中的两种。若每样乘坐一次的费用是种。若每样乘坐一次的费用是5 5元，游乐场总共收元，游乐场总共收入入700700，可知有，可知有 名儿童没有玩过其中任何一种。名儿童没有玩过其中任何一种。2 2、某学校足球队有球衣、某学校足球队有球衣3030件，篮球队有球衣件，篮球队有球衣1515件，件，排球队有球衣排球队有球衣1818件，三队队员总数为件，三队队员总数为5050人，其中人，其中有有2 2人同时参加人同时参加3 3个队，那么同时个队，那么同时只只参加两个队的参加两个队的队员有多少？队员有多少？ 、分母是、分母是10011001的最简分数一共有多少个？的最简分数一共有多少个？10，972排列与组合排列与组合731.1.排列的定义排列的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,按照一定的顺序排成一按照一定的顺序排成一列列, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的一个排列个元素的一个排列. .排列数公式排列数公式: :全排列问题：全排列问题： n n个不同的元素排成一排，排列方法有：个不同的元素排成一排，排列方法有：=n*(n-1)*(n-2)*2*1=n!=n*(n-1)*(n-2)*2*1=n!742.2.组合的定义组合的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,并成一组并成一组, ,叫做从叫做从n n个个不同元素中取出不同元素中取出m m个元素的一个组合个元素的一个组合. .组合数公式组合数公式: :排列与组合的区别与联系排列与组合的区别与联系: :与顺序有关的为排列问题与顺序有关的为排列问题, ,与顺序与顺序无关的为组合问题无关的为组合问题. .75加法原理和乘法原理加法原理和乘法原理从从A到到C共有多少中走法？共有多少中走法？ABC76例例1 1:学校师生合影，共学校师生合影，共8 8个学生，个学生，4 4个老师，要个老师，要求老师在学生中间，且老师互不相邻，共有多求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？少种不同的合影方式？77解解 先排学生共有先排学生共有 种排法种排法, ,然后把老师插入学生然后把老师插入学生之间的空档，共有之间的空档，共有7 7个空档可插个空档可插, ,选其中的选其中的4 4个空档个空档, ,共共有有 种选法种选法. .根据乘法原理根据乘法原理, ,共有的不同坐法为共有的不同坐法为 种种. .结论结论1 1 插入法插入法: :对于某两个元素或者几个元素要求不对于某两个元素或者几个元素要求不相邻的问题相邻的问题, ,可以用插入法可以用插入法. .即先排好没有限制条件的即先排好没有限制条件的元素元素, ,然后将有限制条件的元素按要求插入排好元素然后将有限制条件的元素按要求插入排好元素的空档之中即可的空档之中即可. .78例例2 : 2 : 5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起, ,有多少种不同的排法有多少种不同的排法? ? 79解解因为女生要排在一起因为女生要排在一起, ,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一个人, ,与与5 5个男生作全排列个男生作全排列, ,有有 种排法种排法, ,其中女生内其中女生内部也有部也有 种排法种排法, ,根据乘法原理根据乘法原理, ,共有共有 种不同的排种不同的排法法. .结论结论2 2 捆绑法捆绑法: :要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题, ,可以用捆绑法来解决问题可以用捆绑法来解决问题. .即将需要相邻的元素合并即将需要相邻的元素合并为一个元素为一个元素, ,再与其它元素一起作排列再与其它元素一起作排列, ,同时要注意合同时要注意合并元素内部也可以作排列并元素内部也可以作排列. .80例例3 3 : : 袋中有不同年份生产的袋中有不同年份生产的5 5分硬币分硬币2323个个, ,不同年份生产的不同年份生产的1 1角硬币角硬币1010个个, ,如果从袋中取如果从袋中取出出2 2元钱元钱, ,有多少种取法有多少种取法? ?81解解把所有的硬币全部取出来把所有的硬币全部取出来, ,将得到将得到 0.0523+0.1010=2.150.0523+0.1010=2.15元元, ,所以比所以比2 2元多元多0.150.15元元, ,所所以剩下以剩下0.150.15元即剩下元即剩下3 3个个5 5分或分或1 1个个5 5分与分与1 1个个1 1角角, ,所以所以共有共有 种取法种取法. .结论结论3 3剩余法剩余法: :在组合问题中在组合问题中, ,有多少取法有多少取法, ,就有多少就有多少种剩法种剩法, ,他们是一一对应的他们是一一对应的, ,因此因此, ,当求取法困难时当求取法困难时, ,可可转化为求剩法转化为求剩法. .分析分析 此题是一个组合问题此题是一个组合问题, ,若是直接考虑取钱的问题若是直接考虑取钱的问题的话的话, ,情况比较多情况比较多, ,也显得比较凌乱也显得比较凌乱, ,难以理出头绪来难以理出头绪来. .但是如果根据组合数性质考虑剩余问题的话但是如果根据组合数性质考虑剩余问题的话, ,就会很就会很容易解决问题容易解决问题. .82例例4 4学校安排考试科目学校安排考试科目9 9门门, ,语文要在数学之前考语文要在数学之前考, ,有有多少种不同的安排顺序多少种不同的安排顺序? ?83解解 不加任何限制条件不加任何限制条件, ,整个排法有整个排法有 种种,“,“语文安排语文安排在数学之前考在数学之前考”,”,与与“数学安排在语文之前考数学安排在语文之前考”的排法的排法是相等的是相等的, ,所以语文安排在数学之前考的排法共有所以语文安排在数学之前考的排法共有 种种. .结论结论4 4对等法对等法: :在有些题目中在有些题目中, ,它的限制条件的肯定与它的限制条件的肯定与否定是对等的否定是对等的, ,各占全体的二分之一各占全体的二分之一. .在求解中只要求在求解中只要求出全体出全体, ,就可以得到所求就可以得到所求. .分析分析 对于任何一个排列问题对于任何一个排列问题, ,就其中的两个元素来讲就其中的两个元素来讲的话的话, ,他们的排列顺序只有两种情况他们的排列顺序只有两种情况, ,并且在整个排列并且在整个排列中中, ,他们出现的机会是均等的他们出现的机会是均等的, ,因此要求其中的某一种因此要求其中的某一种情况情况, ,能够得到全体能够得到全体, ,那么问题就可以解决了那么问题就可以解决了. .并且也避并且也避免了问题的复杂性免了问题的复杂性. .84例例5 5 某个班级共有某个班级共有4343位同学位同学, ,从中任抽从中任抽5 5人人, ,正、副正、副班长、团支部书记至少有一人在内的抽法有多少种班长、团支部书记至少有一人在内的抽法有多少种? ?85解解 43 43人中任抽人中任抽5 5人的方法有人的方法有 种种, ,正副班长正副班长, ,团支部团支部书记都不在内的抽法有书记都不在内的抽法有 种种, ,所以正副班长所以正副班长, ,团支部书团支部书记至少有记至少有1 1人在内的抽法有人在内的抽法有 种种. .结论结论5 5 排异法排异法: :有些问题有些问题, ,正面直接考虑比较复杂正面直接考虑比较复杂, ,而它而它的反面往往比较简捷的反面往往比较简捷, ,可以先求出它的反面可以先求出它的反面, ,再从整体中再从整体中排除排除. .分析分析 此题若是直接去考虑的话此题若是直接去考虑的话, ,就要将问题分成好几就要将问题分成好几种情况种情况, ,这样解题的话这样解题的话, ,容易造成各种情况遗漏或者重容易造成各种情况遗漏或者重复的情况复的情况. .而如果从此问题相反的方面去考虑的话而如果从此问题相反的方面去考虑的话, ,不不但容易理解但容易理解, ,而且在计算中也是非常的简便而且在计算中也是非常的简便. .这样就可这样就可以简化计算过程以简化计算过程. .86圆周排列：圆周排列： 从从n n个不同的元素中取个不同的元素中取r r个沿一圆周排列，排列的方案：个沿一圆周排列，排列的方案：/rN N个元素的圆周排列：个元素的圆周排列：/n= =（n-1n-1）! !87有重复元素的排列问题：有重复元素的排列问题：如：如：n n1 1个个a a，n n2 2个个b b，n n3 3个个c c，排成一排，有多少种排列方法。，排成一排，有多少种排列方法。88重复元素的组合问题：重复元素的组合问题： 从从n n种不同的元素中取种不同的元素中取r r个的元素的组合，允个的元素的组合，允许有重复元素的组合：许有重复元素的组合：典型模型：典型模型： r r个相同的小球，放到个相同的小球，放到n n个不同的盒子里，所有个不同的盒子里，所有的放置方法。的放置方法。892.2.（NOIP7NOIP7）平面上有三条平行直线，每条直线上分别有）平面上有三条平行直线，每条直线上分别有7 7，5 5，6 6个点，且不同直线上三个点都不在同一条直线上。个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？问用这些点为顶点，能组成多少个不同四边形？2 2、 （NOIP10NOIP10）由）由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有字符串中，构成的所有字符串中，包含子串包含子串“abc”“abc”的共有（的共有（ ）个。）个。 A. 40320 B. 39600 C. 840 D. 780 E. 60 A. 40320 B. 39600 C. 840 D. 780 E. 60901 1 (NOIP8)(NOIP8) 在书架上放有编号为在书架上放有编号为1 1 ，2 2 ，n n的的n n本书。本书。现将现将n n本书全部取下然后再放回去，当放回去时要求每本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：本书都不能放在原来的位置上。例如：n = 3n = 3时：时： 原来位置为：原来位置为：1 2 31 2 3 放回去时只能为：放回去时只能为：3 1 2 3 1 2 或或 2 3 1 2 3 1 这两种这两种 问题：求当问题：求当n = 5n = 5时满足以上条件的放法共有多少时满足以上条件的放法共有多少种？（不用列出每种放法）种？（不用列出每种放法）91错排问题：错排问题： n n个不同元素的错排问题：个不同元素的错排问题： 如：如：1 1，2 2，3 3，。，。，n n 的错排问题，的错排问题，i i不在第不在第i i个位置的排列方法。个位置的排列方法。分析：分析： 设设f(n)f(n)为为n n个不同元素的错排方案。个不同元素的错排方案。 第一部分：第一部分：n n先不动，把另外的先不动，把另外的n-1n-1个数错排，方案是：个数错排，方案是：f f（n-1n-1），然后），然后n n和和另外的另外的n-1n-1个每一个交换，共有个每一个交换，共有(n-1)*f(n-1)(n-1)*f(n-1)种方案。种方案。 第二部分：第二部分：n n和其他的和其他的n-1n-1个之一交换，其余的个之一交换，其余的n-2n-2个错排，共有个错排，共有 （n-1n-1）*f*f（n-2n-2）种方案。）种方案。由加法原理：由加法原理： f(n)=(n-1)*(f(n-1)+f(n-2)f(n)=(n-1)*(f(n-1)+f(n-2) f(1)=0;f(2)=1; f(1)=0;f(2)=1;4492错排的计算公式：错排的计算公式：93几类重要的递推关系：几类重要的递推关系：94一、第二类一、第二类Stirling数数问题一：放置小球问题一：放置小球n个有区别的球放到个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类表示，称为第二类Stirling数数 设有设有n个不同的球，分别用个不同的球，分别用b1,b2,bn表示。从中取出一个球表示。从中取出一个球bn，bn的放法有以下两种：的放法有以下两种：1)bn独自占一个盒子；那么剩下的球只能放在独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为个盒子中，方案数为S(n-1,m-1)2)bn与别的球共占一个盒子；那么可以事先将与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这这n-1个球放入个球放入m个盒个盒子中，然后再将球子中，然后再将球bn可以放入其中一个盒子中，方案数为可以放入其中一个盒子中，方案数为m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n1,m1)边界条件：边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)95问题二：集合划分问题。问题二：集合划分问题。设设S是一个包含是一个包含n个元素的集合，个元素的集合，S=b1,b2,b3,bn,现需要将现需要将S集集合划分为合划分为m个满足如下条件的集合个满足如下条件的集合S1,S2,Sm。Si ;SiSj= ;S1 S2 Sm=S;(1=I,j=m)则称则称S1,S2,Sm是是S的一个划分。的一个划分。编程：输入编程：输入n和和m的值，输出不同的划分方案数。的值，输出不同的划分方案数。要求：输入数据有一行，第一个数是要求：输入数据有一行，第一个数是n,第二个数第二个数m。样例：样例：输入：输入：43输出：输出：696noip131给定给定n 个有标号的球，标号依次为个有标号的球，标号依次为1，2，n。将这将这n 个球放入个球放入r 个相同的盒子里，不允许个相同的盒子里，不允许有空盒，其不同放置方法的总数记为有空盒，其不同放置方法的总数记为S(n,r)。例如，。例如，S(4,2)=7，这，这7 种不同的放置方法依次为种不同的放置方法依次为(1),(234), (2),(134), (3),(124), (4),(123), (12),(34), (13),(24),(14),(23)。当。当n=7,r=4 时，时，S(7,4)= _97二、二、Catalan数数问题一：凸问题一：凸n边形的三角形剖分边形的三角形剖分在一个凸在一个凸n边形中，通过不相交于边形中，通过不相交于n边形内部的对角线，把边形内部的对角线，把n边形拆分成若边形拆分成若干三角形，不同的拆分数目用干三角形，不同的拆分数目用f(n)表之，表之，f(n)即为即为Catalan数。例如五边形数。例如五边形有如下五种拆分方案，故有如下五种拆分方案，故f(5)=5。求对于一个任意的凸。求对于一个任意的凸n边形相应的边形相应的f(n)。98区域区域是一个凸是一个凸k边形，区域边形，区域是一个凸是一个凸n-k+1边形，边形，区域区域的拆分方案总数是的拆分方案总数是f(k)；区域区域的拆分方案数为的拆分方案数为f(n-k+1)；故包含故包含 P1PkPn的的n边形的拆分方案数为边形的拆分方案数为f(k)*f(n-k+1)种种F(n)=99问题二：二叉树数目问题二：二叉树数目问题描述：求问题描述：求n个结点能构成不同二叉数的数目。个结点能构成不同二叉数的数目。【问题分析】：【问题分析】：设设F(n)为为n个结点组成二叉树的数目。个结点组成二叉树的数目。容易知道：容易知道：f(1)=1;f(2)=2,f(3)=5选定其中选定其中1个结点为根，左子树结点的个数为个结点为根，左子树结点的个数为i，二叉树数目，二叉树数目f（i）种；右子树结点数目为种；右子树结点数目为n-i-1，二叉树数目，二叉树数目f（n-i-1）种，）种，I的可取范的可取范围围0，n-1。所以有：。所以有：F(n)=为了计算的方便：约定为了计算的方便：约定f（0）=1100问题三：出栈序列问题三：出栈序列问题描述：问题描述：N个不同元素按一定的顺序入栈，求不同的出栈序列数目。个不同元素按一定的顺序入栈，求不同的出栈序列数目。【问题分析】：【问题分析】：设设f（n）为）为n个元素的不同出栈序列数目。个元素的不同出栈序列数目。容易得出：容易得出：f（1）=1；f（2）=2。第第n个元素可以第个元素可以第i（1=i=n）个出栈，前面已出栈有）个出栈，前面已出栈有i-1个元素，出栈方个元素，出栈方法：法：f（i-1）；后面出栈）；后面出栈n-i个元素，出栈方法为：个元素，出栈方法为：f（n-i）。所以有：）。所以有：F(n)=101三、集合取数问题三、集合取数问题1、设、设f(n,k)是从集合是从集合1，2，。，。，n中能够选择的中能够选择的没有没有两个连续两个连续整数的整数的k个元素子集的数目，求递归式个元素子集的数目，求递归式f(n,k)。【问题分析】：【问题分析】：N有两种情况：有两种情况：当当n在子集时，则在子集时，则n-1一定不在子集中，即在一定不在子集中，即在1，2，。，。，。，n-2中选中选k-1个元素，数目为个元素，数目为f(n-2,k-1)。当当n不在子集中时，则在不在子集中时，则在1，2，。，。，n-1中选中选k个元素，数目为个元素，数目为f(n-1,k)。所以：所以：f(n,k)=f(n-2,k-1)+f(n-1,k)边界条件：边界条件：F(n,1)=n,f(n,k)=0(n=k)102noip142书架上有书架上有21本书，编号从本书，编号从1到到21，从其中选，从其中选4本，其本，其中每两本的编号都不相邻的选法一共有中每两本的编号都不相邻的选法一共有_种。种。103四、整数划分问题四、整数划分问题1、将整数、将整数n分成分成k份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同(不考不考虑顺序虑顺序)。例如：例如：n=7，k=3，下面三种分法被认为是相同的。，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。问有多少种不同的分法。输入：输入：n，k(6n=200，2=k=2，可以先那出，可以先那出j个个1分到每一分到每一份，然后再把剩下的份，然后再把剩下的i-j分成分成j份即可，分法有：份即可，分法有：f(i-j,j).2):j份中至少有一份为份中至少有一份为1的分法，可以先那出一个的分法，可以先那出一个1作为单独的作为单独的1份，剩下份，剩下的的i-1再分成再分成j-1份即可，分法有：份即可，分法有：f(i-1,j-1).所以所以：f(i,j)=f(i-j,j)+f(i-1,j-1)边界条件：边界条件：f（i，1）=1，f（i，j）=0，（ij）1042、自然数、自然数n的拆分方案。的拆分方案。n=5,拆分数拆分数6n=6,拆分数拆分数10n=7,拆分数拆分数141:5=1+42:5=1+1+33:5=1+1+1+24:5=1+1+1+1+15:5=1+2+26:5=2+3105用母函数法：用母函数法：当当n=5时：时：构造母函数如下：构造母函数如下：F(x)=(x0+x1+x2+x3+x4+x5)(x20+x21+x22)(x30+x31) (x40+x41)(x50+x51) =(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5) =1+x+2x2+3x3+5x4+7x5+106项项aiXi的系数的系数ai，ai-1即自然数即自然数i的拆分数的拆分数.减减1是因为包含了是因为包含了i=i的一种拆分方案。的一种拆分方案。采用采用a,b,c三个数组，三个数组，a：被乘数，：被乘数，b：乘数，：乘数，c：乘积。：乘积。多个多项式采用逐次相乘的方法。每次借助多个多项式采用逐次相乘的方法。每次借助k从从b中取中取项。项。1073、将整数、将整数n分成分成k份，且每份不能为空，且最大值不份，且每份不能为空，且最大值不超过超过m的分法的分法 。任意两种分法不能相同。任意两种分法不能相同(不考虑顺序不考虑顺序)。108刚才的发言，如刚才的发言，如有不当之处请多指有不当之处请多指正。谢谢大家！正。谢谢大家！109