当前位置:首页 >> 学科竞赛 >>

NOIP2013初赛知识复习


NOIP2013初赛 知识复习

重要更正
? 冯?诺依曼理论奖创建于1975年,每年颁发 一次,奖励给在运筹管理学领域做出奠基 性的、有深远影响力贡献的一名科学家或 一个研究群体。第一届得主是著名运筹学 家,被称为线性规划之父的乔治?丹茨格 (George Dantzig)。历届获奖者中不乏诺贝尔 经济学奖获得者,也有众多计算机科学, 控制论等领

域的创始人。

知识范围
内容与要求 1、计算机的基本常识 ●计算机和信息社会(信息社会的主要特征、计算机的主要特征、 数字通信网络的主要特征、数字化) ●信息输入输出基本原理(信息交换环境、文字图形多媒体信息的 输入输出方式) ●信息的表示与处理(信息编码、微处理部件MPU、内存储结构、 指令,程序,和存储程序原理、程序的三种基本控制结构) ●信息的存储、组织与管理(存储介质、存储器结构、文件管理、 数据库管理) ●信息系统组成及互连网的基本知识(计算机构成原理、槽和端口 的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协 议、HTTP协议、WEB应用的主要方式和特点) ●人机交互界面的基本概念(窗口系统、人和计算机交流信息的途 径(文本及交互操作)) ●信息技术的新发展、新特点、新应用等。

2、计算机的基本操作 ●WINDOWS和LINUX的基本操作知识 ●联网的基本使用常识 (网上浏览、搜索和查询等) ●常用的工具软件使用(文字编辑、电子邮件收发等) 3、程序设计的基本知识 数据结构 ●程序语言中基本数据类型(字符、整数、长整数、浮点) ●浮点运算中的精度和数值比较 ●一维数组(串)与线性表 ●记录类型(PASCAL)/结构类型(C) 程序设计 ●结构化程序设计的基本概念 ●阅读理解程序的基本能力 ●具有将简单问题抽象成适合计算机解决的模型的基本能力 ●具有针对模型设计简单算法的基本能力 ●程序流程描述(自然语言/伪码/NS图/其他) ●程序设计语言(PASCAL/C/C++,) 基本算法处理 ●初等算法(计数、统计、数学运算等) ●排序算法(冒泡法、插入排序、合并排序、快速排序) ●查找(顺序查找、二分法) ●回溯算法

◆ 计算机结构与组成原理

◆ 基本的数学知识 (集合的运算、排列与组合)

◆ 计算机结构与组成原理

一、计算机发展及应用
1、第一台电子计算机的诞生: ENIAC
1946年,世界上第一台数字式电于计算机是由美固宾夕法尼亚大学的物理 学 家 约 翰 · 克 利 ( John Mauchly ) 和 工 程 师 普 雷 斯 伯 · 克 特 莫 埃 ( J.hesper.Eckert ) 领 导 研 制 的 取 名 为 ENIAC ( Elecotmnic Nurnerical Integrator And Calculator)的计算杌。

2、第一台具有存储程序功能的计算机:EDVAC。
冯· 诺依曼依据存储程序的工作原理设计. 运算器、控制器、存储器、输人设备和输出设备这五部分组成,

同ENIAC相比,EDVAC方案有两个重大改进:
(1):采用了二进制;

(2):提出了“存储程序”,

1903年,冯· 诺伊曼(Neumann,John von)出生于匈牙利的布达佩斯

考题: NOIP10
1、美籍匈牙利数学家冯· 诺依曼对计算机科学发展所做出的贡献包括 ( )。 A) 提出理想计算机的数学模型,成为计算机科学的理论基础。 B) 提出存储程序工作原理,对现代电子计算机的发展产生深远影响。 C) 设计出第一台具有存储程序功能的计算机EDVAC。 D) 采用集成电路作为计算机的主要功能部件。 E) 指出计算机性能将以每两年翻一番的速度向前发展。

①图灵 (Alan Turing) 是 ( B)。(NOIP9) A) 美国人 B) 英国人 C) 德国人

D) 匈牙利人

艾伦· 麦席森· 图灵(Alan Mathison Turing,1912年6月23日 - 1954年6月7日),英国数学家
图灵机由三部分组成,包括一条 带子、一个读写头和一个控制装置。

图灵对于人工智能的发展有诸多贡献,例如:图灵曾写过一篇名为 《机器会思考吗?》(Can Machine Think?)的论文,其中提出了一 种用于判定机器是否具有智能的试验方法,即图灵试验。 图灵奖是美国计算机协会于1966年设立的,又叫"A.M.图灵奖",专 门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机 科学的先驱、英国科学家艾伦· 图灵,这个奖设立目的之一是纪念这 位科学家。

1、关于图灵机下面的说法哪个是正确的: 图灵机是世界上最早的电子计算机。 由于大量使用磁带操作,图灵机运行速度很慢。 图灵机只是一个理论上的计算模型。 图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。

10.1956年( )授予肖克利(William Shockley)、巴丁(John Bardeen) 和布拉顿(Walter Brattain),以表彰他们对半导体的研究和晶体管效应的 发现。 A. 诺贝尔物理学奖 B. 约翰· 诺依曼奖 冯· C. 图灵奖 D. 高德纳奖(Donald E. Knuth Prize)

6.提出“存储程序”的计算机工作原理的是()。
A.克劳德· 香农 B.戈登· 摩尔 C.查尔斯· 巴比奇 D.冯· 诺依曼

3. 在下面各世界顶级的奖项中,为计算机科学与技术领 域作出杰出贡献的科学家设立的奖项是( )。 noip12 A. 沃尔夫奖 B. 诺贝尔奖 C. 菲尔兹奖 D. 图灵奖 E. 南丁格尔奖
11. 在下列关于图灵奖的说法中,正确的有( )。noip14 A. 图灵奖是美国计算机协会于1966年设立的,专门奖励那些对计算机事业作 出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止,还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰· 图灵

2000 Andrew Chi-Chih Yao --- PhD, UIUC; Prof, Princeton (now at 清 华)因对计算理论做出了诸多根本性的重大贡献. (图灵奖自创立以来获得该 奖项的首位华裔学者,全球华人的骄傲)

②第一个给计算机写程序的人是( B )。(NOIP9) A)Alan Mathison Turing B)Ada Lovelace C) John von Neumann E) Edsger Wybe Dijkstr 1、英国著名诗人拜伦的女儿Ada Lovelace(爱达).由于她在程 序设计上的开创性工作,Ada Lovelace被称为世界上”第一 位程序员”。“世界上第一位软件工程师”。 2、董铁宝是“中国第一个程序员”。董铁宝1945年赴美国 学习,在伊利诺伊大学学习、研究时,他参与了第一代电子 计算机伊利亚克机的设计、编程和使用。董铁宝于1956年回 到中国并任教于北京大学,成为王选(计算数学专业院士) 的老师。董铁宝在1968年文化大革命期间自杀身亡。 D) John Mc-Carthy

3、计算机发展的几个阶段
第一代 (1946~ 1958)

第二代 (1958~ 1964)

第三代 (1964~ 1975)

第四代 (1975~至今) 大规模/超大规 模集成电路

主要电 子器件

电子管

晶体管

中小规模 集成电路

①微型计算机的问世是由于( C )的出现。(NOIP8)
A)中小规模集成电路 B)晶体管电路 C)(超)大规模集 成电路 D)电子管电路

4、计算机应用 ⑴科学计算(数值计算)。 ⑵数据处理(信息处理)。 ⑶人工智能。 ⑷自动控制。 ⑸计算机辅助设计和制造:
CAI (计算机辅助教学) CAT(计算机辅助测试) CAE (计算机辅助教育) CAM (计算机辅助制造) CAD(计算机辅助设计) CIMS(计算机集成制造系统)

二、保护知识产权: 《计算机软件保护条例》
最早是1991年6月4日国务院发布的<<计算机软件保护条例>>,现已废止。
现公布《计算机软件保护条例》,自2002年1月1日起实施 。

第二章 软件著作权 第八条 软件著作权人享有下列各项权利:
(二)署名权 (四)复制权; (六)出租权 (八)翻译权

(一)发表权 (三)修改权 (五)发行权 (七)信息网络传播权

(九)应当由软件著作权人享有的其他权利。

①计算机软件保护法是用来保护软件(D )的(NOIP7) A)编写权 B)复制权 C)使用权 D)著作权

三、计算机病毒
计算机病毒是一种功能较特殊的计算机程序,计算机 病毒的特征可以归纳为下面两点: ⑴能够将自身复制到其他程序中。

⑵不独立以文件形式存在,仅附加在别的程序上。
失去这两个特征中的任何一个,都不成其为病毒。

①计算机病毒是(

B

)(NOIP7)

A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 )(NOIP6) ②计算机病毒的特点是( C A. 传播性、潜伏性、易读性与隐蔽性 B. 破坏性、传播性、潜伏性与安全性 C. 传播性、潜伏性、破坏性与隐蔽性 D. 传播性、潜伏性、破坏性与易读性

③ 计算机病毒传染的必要条件是:( A)在内存中运行病毒程序

B

)。(NOIP8) B)对磁盘进行读写操作
D)复制文件

C)在内存中运行含有病毒的可执行的程序

四、计算机系统的组成: 1、硬件系统
2、软件系统
只有硬件没有安装软件的计算机称为“裸机”

1、硬件系统的组成:
五个基本部分组成: (1)运算器 (2)控制器 (3)存储器 (4)输人设备 (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 ◆ 高速缓存器>内存速度 > 外存速度

主机的概念: 包括:CPU和内存储器

①CPU访问内存的速度比访问下列哪个(些)存储设备要慢 ( AD )。(NOIP9) A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘

②微型计算机中,( c

)的存取速度最快。(NOIP8)

A)高速缓存 B)外存储器 C)寄存器 D)内存储器

③在计算机硬件系统中,cache是( D A)只读 B)可编程只读

)存储器 (NOIP7) D)高速缓冲

C)可擦除可编程只读

4、下面哪个部件对于个人桌面电脑的正常运行不是必需的( )。NOIP10 A.CPU B. 图形卡(显卡) C. 光驱 D. 主板 E. 内存 5、用静电吸附墨粉后转移到纸张上,是哪种输出设备的工作方式( )。NOIP10 A.针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘 图仪 6、下列哪个(些)不是计算机的存储设备( )。NOIP10 A.文件管理器 B. 内存 C. 显卡 D. 硬盘 E. U盘 7 、下列说法中正确的有( )。NOIP10

A.CPU的基本功能就是执行指令。 B.CPU的主频是指CPU在1秒内完成的指令周期数,主频越快的CPU速度一定越快。 C.内部构造不同的CPU运行相同的机器语言程序,一定会产生不同的结果。 D.在一台计算机内部,一个内存地址编码对应唯一的一个内存单元。 E.数据总线的宽度决定了一次传递数据量的大小,是影响计算机性能的因素之 一。 8、彩色显示器所显示的五彩斑斓的色彩,是由哪三色混合而成的( )。NOIP10 A.红 B. 白 C. 蓝 D. 绿 E. 橙 9、下列哪个(些)是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

NOIP11 6. 下列设备中没有计算功能的是( )。 A. 笔记本电脑B. 掌上电脑C. 智能手机 D. 电子计算器 E. 液晶显示器 7. Intel的首颗64 位处理器是( )。 A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium 15. 下列外设接口中可以通过无线连接的方式连接设备的是( )。 A. USB 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. 以下断电之后将不能保存数据的有( CD noip12 A. 硬盘 B. ROM C. 显存 D. RAM

)。

17. 以下断电之后仍能保存数据的有( AB )。noip13 A. 硬盘 B. ROM C. 显存 D. RAM

12.计算机在工作过程中,若突然停电,( AC )中 的信息不会丢失。 noip14 B. CPU C.ROM D. RAM A. 硬盘

2.微型计算机中,控制器的基本功能是( A )。noip14 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 存储各种控制信息 D. 获取外部信息 E. 存放程序和数据 1. 在以下各项中,( D )不是CPU 的组成部分。noip13 A. 控制器 B. 运算器 C. 寄存器 D. 主板 E. 算术逻辑单元 (ALU)

1. 在以下各项中。( E)不是CPU的组成部分。 noip12 A. 控制器 B. 运算器 C. 寄存器 D. ALU E. RAM

2、 BIOS(基本输入输出系统)是一组固化在计算机内(C ) 上一个ROM芯片上的程序。noip12 A. 控制器 B. CPU C. 主板 D. 内存条 E. 硬盘

2、 关于BIOS下面的说法哪个是正确的: A) BIOS是计算机基本输入输出系统软件的简称。 B) BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的 驱动程序。 C) BIOS一般由操作系统厂商来开发完成。 D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

1、关于CPU下面哪些说法是正确的:AB A)CPU全称为中央处理器(或中央处理单元)。 B)CPU能直接运行机器语言。 C)CPU最早是由Intel公司发明的。 D)同样主频下,32位的CPU比16位的CPU运行速度 快一倍 2、关于计算机内存下面的说法哪些是正确的:BD A)随机存储器(RAM)的意思是当程序运行时,每次具体分配给程序的内存位置是随机 而不确定的。 B)一般的个人计算机在同一时刻只能存/取一个特定的内存单元。 C)计算机内存严格来说包括主存(memory)、高速缓存(cache)和寄存器(register) 三个部分。 D)1MB内存通常是指1024*1024字节大小的内存。 3、关于操作系统下面说法哪些是正确的:BC A.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。 B.在操作系统的管理下,一个完整的程序在运行过程中可以被部分存放在内存中。 C.分时系统让多个用户可以共享一台主机的运算能力,为保证每个用户都得到及时的响应 通常会采用时间片轮转调度的策略。 D.为了方便上层应用程序的开发,操作系统都是免费开源的。

8.主存储器的存取速度比中央处理器(CPU)的工作速度慢很多,从而使 得后者的效率受到影响。而根据局部性原理,CPU 所访问的存储单元通常 都趋于聚集在一个较小的连续区域中。于是,为了提高系统整体的执行效 率,在 CPU 中引入了() A.寄存器 B.高速缓存 C.闪存

D.外存

4.寄存器是( )的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器(CPU)

4.汇编语言( )。 A. 是一种与具体硬件无关的程序设计语言 B. 在编写复杂程序时,相对于高级语言而言代码量较大,且不易调试 C. 可以直接访问寄存器、内存单元、I/O端口 D. 随着高级语言的诞生,如今已完全被淘汰,不再使用

目前计算机芯片(集成电路)制造的主要原料是( ),它是一种可以 在沙子中提炼出的物质。 A. 硅 B. 铜 C. 锗 D. 铝

2、计算机的三总线结构:
总线是一组导线、是公共通路,微型计算机中各个组成部件之间的 信息传输都是通过它们来实现的

地址总线(AB)是单向总线,用以传送CPU向外设或存储器发出的地址信息。 数据总线(DB)是双向总线,用以CPU与内存或接口之间传输数据信息。 控制总线(CB)是双向总线,有的作为输出,有的作为输入,用以CPU与内存或I/O 接口之间传送控制信息。 分别传送地址信号、数据信号和控制信号。

①中央处理器(CPU)能访问的最大存储器容量取决于 ( A )。(NOIP8 NOIP7) A)地址总线 B)数据总线 C)控制总线 D)实际内存容量 ②计算机系统总线上传送的信号有( B )(NOI6) A.地址信号与控制信号 B. 数据信号、控制信号与地址信号 C.控制信号与数据信号 D. 数据信号与地址信号

二)软件系统
包括:
1、系统软件: (1)操作系统软件: dos, OS/2 ,windows95,windows98,windows 2000,windowsxp windows Server,windows NT ,unix,linux,Netware , Windows Vista (2)计算机语言: 机器语言 汇编语言 高级语言:basic,pascal,c,c++,viscal basic 2、应用软件:office (word,powerpoin,excel),3dmax,flash,photoshop等.

什么是面向对象程序设计(

模块化

):

? 面向对象程序设计(英语:Object Oriented

Programming,缩写:OOP),指一种程序设计范型, 同时也是一种程序开发的方法论。它将对象作为程序的 基本单元,将程序和数据封装其中,以提高软件的重用 性、灵活性和扩展性。 ? 20世纪70年代的SmallTalk语言在面向对象方面堪称经 典--以至于30年后的今天依然将这一语言视为面向对象 语言的基础。 ? 传统的面向过程程序设计

面向对象语言(Object-Oriented Language)是一类以对 象作为基本程序结构单位的程序设计语言
? 一种是纯面向对象语言,如Smalltalk、EIFFEL等 。 ? 混合型面向对象语言,即在过程式语言及其它语言中

加入类、继承等成分,如C++、Objective-C等。 ? Visual B\C, Java

1、下列哪个(些)不是数据库软件的名称( )。NIOP10 A. MySQL B. SQL Server C. Oracle D. Outlook
2、下列哪个(些)软件属于操作系统软件( )。NIOP10 A. Microsoft Word B. Windows XP C. Foxmail E. Red Hat Linux D. 金山影霸

E. Foxpro

3、下列哪个(些)程序设计语言支持面向对象程序设计方法( )。NIOP10 A. C++ B. Object Pascal C. C D. Smalltalk E. Java

4、下列哪个(些)软件不是操作系统软件的名字( )。NOIP9 B) DOS C) Linux D) OS/2 E) Arch/Info A)WindowsXP
5、 在以下各项中,( A. Solaris B. Linux )不是操作系统软件。noip14 C. Sybase D. Windows Vista

E. Symbian

Solaris :Sun Microsystems研发的计算机 操作系统。它被认为是UNIX操作系统的衍生版本之一 Symbian是一个实时性、多任务的纯32位操作系统,具有功耗低、内存占用少等特点,常见于手 机上,作为目前智能手机的主要操作系统之一。

18. 在下列关于计算机语言的说法中,正确的有( CD )。noip13 A. 高级语言比汇编语言更高级,是因为它的程序的运行效率更高 B. 随着Pascal、C等高级语言的出现,机器语言和汇编语言已经退出 了历史舞台 C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计 算机上 D. C是一种面向过程的高级计算机语言
18. 在下列关于计算机语言的说法中,正确的有( AB )。 noip12 A. Pascal和C都是编译执行的高级语言 B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计 算机上 C. C++是历史上的第一个支持面向对象的计算机语言 D. 高级语言比汇编语言更高级,是因为它的程序的运行效率更高

3、关于操作系统下面说法哪些是正确的:BC A.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。 B.在操作系统的管理下,一个完整的程序在运行过程中可以被部分存放在内 存中。 C.分时系统让多个用户可以共享一台主机的运算能力,为保证每个用户都得 到及时的响应通常会采用时间片轮转调度的策略。 D.为了方便上层应用程序的开发,操作系统都是免费开源的。

4. A. B. 试 C. D.

汇编语言( )。BC 是一种与硬件无关的程序设计语言 在编写复杂程序时,相对于高级语言而言代码量较大,且不易调 可以直接访问寄存器、内存单元、I/O端口 随着高级语言的诞生,如今已完全被淘汰,不再使用

Ada语言
? 来源 ? 美国国防部之所以把这种语言取名为Ada,是为了 纪念奥左斯特. 艾达.洛夫莱斯伯爵夫人 (Augusta Ada Lovlace 1815-1852),她是英格兰诗人拜伦 (Byron)勋爵的女儿,曾对现代计算机技术之父查尔 斯.巴贝奇(Charles Babage)的笔记,手稿进行了整 理和修正。从某种意义上说,她是世界上第一位 计算机程序员。 ? 军事用语言 中国军方有再用

五、计算机指令系统 计算机能直接识别和执行的命令称为指令。

指令本身是二进制代码。是要计算机执行某种操作的命令。
用机器指令编写的程序称之为机器语言程序。 一条指令通常由操作码和地址码两部分组成。

六、计算机的数字系统 数值信息在计算机内的表示方法就是用二进制数来表示。 一般说来,如果数制只采用R个基本符号,则称为基R数值,R称 为数制的基数,而数制中每一固定位置对应的单位值称为权。
进制 二进制 八进制 十进制 十六进制 基数R 2 8 10 16 0,1 0,1,2,3,4,5,6,7 0,1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F(对应十进制数的10—15。) 基本符号

进位计数制的编码符合“逢R进位”的规则,各位的权是 以R为底的幂,一个数可按权展开成为多项式。例如,一 个十进制数256.47可按权展开为 256.47=2×102+5×101+6×10°十4×10-1+7×10-2

1、R进制转换为十进制 基数为R的数字,只要将各位数字与它的权相乘,其积相加,和 数就是十进制数 例: 3506.28 =6×8°+0×81+5×82+3×83+2×8-1 =1862.25 例: 0.2A16

=2×16-1+10×16-2
=0.1640625

2、十进制转换为R进制 +进制整数转换成R进制的整数: 除R取余法。 十进制小数转换成R进制时: 乘R取整. 例:将0.312510转换成二进制数
0.3125×2 =0.625 0.625×2 =1.25 0.25×2=0.5 0.5×2 =1.0 所以0.312510=0.01012

3、二、八、十六进制的相互转换
每位八进制数相当于三位二进制数,每位十六进制数相当于四位二进 制数。
在转换时,位组划分是以小数点为中心向左右两边延伸,中间的0不能 省略,两头不够时可以补0。尤其是小数后末尾的0 例如: 将1011010.12转换成八进制和十六进制数 001 011 010. 100 1 3 2. 4 1011010.12=5A.816 1011010.12=132.48

0101 1010. 1000 5 A. 8

将十六进制数F7.28变为二进制数 F 7. 2 8 F7.2816=11110111.001012

1111 0111.0010 1000

①十进制数2003等值于二进制数( D )。(NOIP9) A) 0100000111 B) 10000011 C) 110000111 D) 11111010011 E) 1111010011

②十进制书11/128可用二进制数码序列表示为:( D )。(NOIP8)
A)1011/1000000 B)1011/100000000

C)0.001011

D)0.0001011

③算式(2047)10-(3FF)16+(2000)8的结果是( A )。 (NOIP8 NOIP7) A)(2048)10 B)(2049)10 C)(3746)8 D)(1AF7)16 ④64KB的存储器用十六进制表示,它的最大的地址码是 ( B )(NOIP7)

A)10000

B)FFFF

C)1FFFF

D)EFFFF

⑤十进制算术表达式 3*512 + 7*64 + 4*8 + 5的运算结果,用二 进制表示为( B ).(NOIP5) A· 10111100101 B· 11111100101 C· 11110100101 D· 11111101101 ⑥下列无符号数中,最小的数是( C )(NOIP6) A.(11011001)2 B.(75)10 C.(37)8 D.(2A)16 ⑦运算式(2008)10-(3723)8 的结果是( B CD)。NOIP9 C) (5)16 A)(-1715)10 B) (5)10 E) (3263)8 D) (101)2

8、十进制数100.625等值于二进制数( A. 1001100.101 B. 1100100.101 D. 1001100.11 E. 1001100.01

)(NOIP10)。 C. 1100100.011

)。(NOIP10) 13、(2004)10 + (32)16的结果是( A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10 3、 以下二进制数的值与十进制数23.456 的值最接近的是( A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111 )(NOIP11)。

12. (3725)8 + (B)16的运算结果是( )。(NOIP11) A. (3736)8 B. (2016)10 C. (11111100000)2 D. (3006)10 E. (7E0)16

12. (2010)16 + (32)8的结果是( A. (8234)10 B. (202A)16 C. (100000000110)2 D. (2042)16

)。noip12

7、与十进制数28.5625相等的四进制数是( )。noip14 A. 123.21 B. 131.22 C. 130.22 E. 130.20 15. (2008)10 + (5B)16的结果是( )。noip14 A. (833)16 B. (2099)10 C. (4063)8 8、与十进制数17.5625 对应的8 进制数是( A. 21.5625 B. 21.44 C. 21.73 D. 21.731 E. 前4 个答案都不对 13. (2070)16 + (34)8 的结果是( A. (8332)10 B. (208C)16 C. (100000000110)2 D. (20214)8

D. 130.21

D. (100001100011)2

)。noip13

)。noip13

9. 与十进制数1770.625 对应的八进制数是( A. 3352.5 B. 3350.5 C. 3352.1161 D. 3350.1151 E. 前4个答案都不对

)。noip12

12. (2010)16 + (32)8的结果是( A. (8234)10 B. (202A)16 C. (100000000110)2 D. (2042)16

)。noip12

七、在计算机中带符号数的表示法 原码:
在用二进制原码表示的数中,符号位为0表示正数,符号位为1表示负数, 其余各位表示数值部分。 如:10000010,00000010

反码:
反码的定义如下: ⑴对于正数,它的反码表示与原码相同。即[x]反=[x]原 ⑵对于负数,则除符号位仍为“1”外,其余各位“1”换成”0”,”0”换成 1”,即得到反码[X]反。例如[-1101001] 反=10010110。 ⑶对于0,它的反码有两种表示:[+0] 反=00?0 [-0] 反=11?1

补码:
正数的补码就是该正数本身。 [01100100]补 =01000100 对于负数:两头的1不变,中间取反。 [10100100]补 =11011100 [+0]补=[-0]补=00?0。

BCD码(8421码) BCD码就是用二进制代码表示的十进制数,也称BCD数。 它是用4位二进制代码0000—1001来表示十进制数0---9。如: 39的BCD码为00111001。

有关补码
4、 在字长为16位的系统环境下,一个16位带符号整数的二进制补码为 1111111111101101。其对应的十进制整数应该是:B A)19 B)-19 C)18 D)-18

4.在整数的补码表示法中,以下说法正确的是( )AC A.只有负整数的编码最高为1 B.在编码的位数确定后,所能表示的最小整数和最大整数的绝对值相同 C.整数0 只有唯一的一个编码 D.两个用补码表示的数相加时,如果在最高位产生进位,则表示运算溢出 三、补码定点加减运算是怎样判断溢出的? 通常用符号位产生的进位与最高有效位产生 的进位异或操作后,按其结果进行判断。若 异或结果为1,表示溢出;异或结果为0,则 无溢出。也就是说最高位和次高位同时进位, 无影响;但其中只有一个进位,产生溢出

①已知x =(0.1011010)2 ,则[ x / 2 ]补 =( C)2。(NOIP8)
A)0.1011101 C)0.0101101 B)11110110 D)0.100110 B )(NOIP7)

② [x]补码=10011000,其原码为( A)011001111 C)11100110 B)11101000 D)01100101

有关阶码

? 解析:此题旨在考查科学记数法方面的知识。

? 浮点数是属于有理数中某特定子集的数的数字表示,在计算机中用以 近似表示任意某个实数。具体的说,这个实数由一个整数或定点数( 即尾数)乘以某个基数(计算机中通常是2)的整数次幂得到,这种 表示方法类似于基数为10的科学记数法。 ? 在计算机中表示一个浮点数,其结构如下: ? 尾数部分(定点小数)E阶码部分(定点整数),如1.340987E+016表 示1.340987*1016。其中尾数(如1.340987)可以确定精度,阶码(如 16)可以确定范围。 ? 答案:A

八、信息存储单位 ⑴位(bit,缩写为b):度量数据的最小单位,表示一位二进 制信息。

⑵字节(byte,缩写为B):一个字节由八位二进制数字组成(l byte=8bit)。字节是信息存储中最常用的基本单位。
计算机存储器(包括内存与外存)通常也是以多少字节来表示 它的容量。常用的单位有:
KB 1K=1024

MB 1M=1024K
GB 1G=1024M TB 1t=1024G

机器字(word):字是位的组合,并作为一个独立的信息单 位处理。字又称为计算机字,它取决于机器的类型、字长以及 使用者的要求。常用的固定字长有8位、16位、32位等。

九、计算机网络知识
1、计算机网络的拓扑结构
网络中各个站点相互连接的方法和形式称之为网络拓扑

总线拓扑

星型拓扑

环型拓扑

树型拓扑

2、计算机网络体系结构的核心是OSI模型 国际标准化组织(ISO)提出的开放系统互联参考模型(OSI) 已成为网络体系结构的标准
7432

在这些层中,除了最高的第7 层没有需要服务的上一层、最 低的第1层没有可利用服务的 下一层外,其它的每一层都建 立在下一层的基础上,利用下 一层来实现自己的功能,并向 上一级提供服务。 主机A与主机B进行通信时, 通信协议是在对等层之间进行 的。其中,物理层与物理层之 间的通信协议是直接的,其他 对等层之间的通信协议都是间 接的。

Osi模型对tcp模型
? http://www.ruanyifeng.com/blog/2009/03/tc p-ip_model.html

有关算法时间复杂度
? 算法复杂度算法复杂度分为时间复杂度和空间复杂度。其作用: 时间 复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这 个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计 算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存 器)资源,因此复杂度分为时间和空间复杂度。)

? 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运 行测试才能知道。但我们不可能也没有必要对每个算法都上机测试, 只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。 并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算 法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数 称为语句频度或时间频度。记为T(n)。 ? 计算方法 ? 1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函 数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))

? 分析:随着模块n的增大,算法执行的时间 的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效 率越高。 ? 2. 在计算时间复杂度的时候,先找出算法 的基本操作,然后根据相应的各语句确定 它的执行次数,再找出 T(n) 的同数量级 (它的同数量级有以下:1,log(2)n,n,n log(2)n ,n的平方,n的三次方,2的n次方, n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))

? 例:算法: ? for (i=1;i<=n;++i) ? { ? for (j=1;j<=n;++j) ? { ? c[i][j]=0; //该步骤属于基本操作 执行次数:n的平方 次 ? for (k=1;k<=n;++k) ? c[i][j] += a[i][k]*b[k][j]; //该步骤属于基本操作 执行次数:n的三 次方 次 ? } ? }

? 则有 T(n) = n 的平方+n的三次方,根据上面括号里的同数量级,我们 可以确定 n的三次方 为T(n)的同数量级 ? 则有 f(n) = n的三次方,然后根据 T(n)/f(n) 求极限可得到常数c ? 则该算法的时间复杂度:T(n) = O(n^3) 注:n^3即是n的3次方。

复杂度分类
? ? ? ? 分类 按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n^2),立方 阶O(n^3),..., ? k次方阶O(n^k),指数阶O(2^n)。随着问题规 模n的不断增大,上述时间复杂度不断增大, 算法的执行效率越低。

常见的算法复杂度

? 8、 快速排序平均情况和最坏情况下的算 法时间复杂度分别为: A) 平均情况O(nlog(2,n)),最坏情况O(n^2) B) 平均情况O(n),最坏情况O(n^2) C) 平均情况O(n),最坏情况O(nlog(2,n)) D) 平均情况O(log(2,n)),最坏情况O(n^2)

? 6. 在使用高级语言编写程序时,一般提 到的“空间复杂度”中的“空间”是指(A ) ? A. 程序运行时理论上所占的内存空间 ? B. 程序运行时理论上所占的数组空间 ? C. 程序运行时理论上所占的硬盘空间 ? D. 程序源文件理论上所占的硬盘空间

? ? ? ? ? ?

应用快速排序的分治思想,可以实现一个求第K大数的程序。假定不考虑极端的最坏情 况,理论上可以实现的最低的算法时间复杂度为( )。 A. O(n^2) B. O(n log n) C. O(n) D. O(1) 解析:快排的时间复杂度是O(nlogn),利用快速排序的思想,从数组S中随机找出一 个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有 两种情况: 1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数; 2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)。 答案:C

? ? ?

排序的稳定性
? 相等的值如果发生交换 则可认为该排序算 法是不稳定的 ? 牵涉到常识性问题 ? http://baike.baidu.com/link?url=RuQx1uQn4o cO5mit2HJijBuzkp8tkbv6fO4WePoRzhHKwNJc FnNMDIcaXpzgnf2q

散列表
? 散列函数 ? 质数求余最常用 关键点是希望这个函数平 均分布最好 不然就是差的函数 ? 解决冲突的方法 ? 开放寻址法 往后找没有被占用的占用 ? 拉链法

前缀 中缀 后缀表达式
? 加括号去除法 出题的挺喜欢这个

二叉树
? 先序 中序 后序便利法 ? 满二叉树 完全二叉树 堆 ? 节点的度

图论相关
? 图的遍历问题 ? 深搜 (递归or栈) ? 广搜 (队列)

最短路径算法
? ? ? ? Bellman-ford (松弛技术,可找负权回路) Dijkstra(队列 贪心 不可用于含负值图) Spfa(bellman的优先队列优化算法) 还有一个基于dp的算法

最小生成树的两种算法
? Prim ? 克鲁斯卡尔

最优前缀编码(Huffman编码)
? 7、 最优前缀编码,也称Huffman编码。这 种编码组合的特点是对于较频繁使用的元 素给与较短的唯一编码,以提高通讯的效 率。下面编码组合哪一组不是合法的前缀 编码: ? A)(00,01,10,11) ? B)(0,1,00,11) ? C)(0,10,110,111) ? D)(1,01,000,001)

链式存储结构

拓扑排序

9、TCP/IP是一组构成互联网基础的网络协议,字面上包括两组协议: 传输控制协议(TCP)和网际协议(IP)。TCP/IP 协议把Internet网络 系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点 之间的信息传输服务,包括寻址和路由器选择等功能的是( )。 Noip14 A. 链路层 E.会话层 B.网络层 C. 传输层 D. 应用层

TCP/IP(Transmission Control Protocol/Internet Protocol)的简写,中文译名为传输控制协议/因特网互联协 议,又叫网络通讯协议 。
超文本传输协议(HTTP),文件传输协议(FTP),Telnet和简单邮件传输协 议(SMTP:发送收电子邮件 ,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. POP3 9. 不能在Linux 上使用的网页浏览器是( )。 (NOIp11) A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla 8、下列哪个网络上常用的名字缩写是错误的( )。(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. 网关 E. 网桥

Html语言

常识性问题

数学相关

十、逻辑运算:
◆ 运算: 与: 或: 非: 异或: ◆ and or ∨ not xor


+ ?

·

运算的优先级:非>与>或

1、 “与” 运算( “·”, “∧” ,and)?
在逻辑问题中,如果决定某一事件发生的多个条件必须同时具备,事件 才能发生,则这种因果关系称之“与”逻辑(并且)。 “与”运算又称为逻辑乘, 其运算符号为“·”,有时也用“∧”表示。 两变量“与”运算关系可表示为? F = A· 或者 F = A∧B B

“与”运算的运算法则为?:
0· = 0 0 ? 0· = 0 1 1· = 0 0

1· = 1 1

结论:若A、B均为1,则F为1;否则,F为0
推广:
A· 0=0 A· 1=A

2、“或”运算(

“+”, “∨” ,or)?

在逻辑问题的描述中,如果决定某一事件是否发生的多个条件中,只要 有一个或一个以上条件成立,事件便可发生,则这种因果关系称之为“或” 逻辑。 “或”运算又称逻辑加,其运算符号为“+”,有时也用“∨”表示。两 变量“或”运算的关系可表示为 F = A + B 或者 F = A ∨ B?

“或”运算的运算法则为?:
0 + 0 = 0 ? 0 + 1 = 1 1 + 0 = 1
1 + 1 = 1

结论:仅当A、B均为0时,F才为0 推广:A+0=A A+1=1

3.“非”运算 ? ? 在逻辑问题中,如果某一事件的发生取决于条件的否定,即事件与事件发 生的条件之间构成矛盾,则这种因果关系称为“非”逻辑。 。“非”运算也叫求反运算或者逻辑否定。其运算符号为“-”,有时也用“? ” 表示。 “非”运算的A 逻辑关系可表示为

F=

或者

F = ? A

“非”运算的运算法则为 0

1
=0

=1

① (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)53H

11. (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,A∨B∧C=( (A)11001110 (C)11101110 (B)01110110 (D)01001100

)。

13.下列逻辑运算正确的是( A) A· (A + B )= A B) A +(A· B)= A C) A· (B + C )= A· + A· B C

)。

D) A +(B· C)=(A + B)· (A + C) E) A+1=A

5.在Pascal语言中,表达式 (21 xor 2)的值是( ) noip12 A. 441 B. 42 C.23 D.24 E.25

6.在Pascal语言中,判断a不等于0且b不等于0的正确的条 件表达式是( ) noip12 A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)
11. 设A=B=D=true,C=E=false,以下逻辑运算表达式值为 真的有( )。 noip12 A. (?A∧B)∨(C∧D)∨ ?E B. ?(((A∧B)∨C)∧D∧E) C. A∧(B∨C∨D∨E) D. (A∧(B∨C)) ∧D∧E

竞赛环境的考察:
16.在下列各软件中,属于NOIP竞赛(复赛)推荐使用的语言环境有( )。 noip12 A. gcc/g++ B. Turbo Pascal C. Turbo C D. free pascal 16.在下列各软件中,属于NOIP 竞赛(复赛)推荐使用的语言环境有( )。 noip13 A. gcc B. g++ C. Turbo C D. free pascal

19. NOIP竞赛推荐使用的语言环境有( )。noi14 A. Dev-C++ B. Visual C++ C. free pascal

D.

Lazarus

信息学竞赛中的数学知识
◆ 集合的运算

◆ 排列与组合

◆ 集合及其运算
1、集合的运算:并、交、补、差 2、容斥原理

1、集合的运算:并、交、补、差

并:∪
交:∩ 补:^或~或 差: -

A

B

A
A ∩ B

B

A

A

B
A-B

A ∪ B

A

8.

(NOIP9)设全集E={1,2,3,4,5},集合A={1,4},B={1,2,5},C={2, 4},则集合(A ∩B)∪~C 为( )。 A) 空集 B) {1} C) {3,5} D){1,5} E) {1,3,5}

1、(NOIP10)设全集I = {a, b, c, d, e, f, g},集合A = {a, b, c}, B = {b, d, e},C = {e, f, g},那么集合为( )。 A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g} 2. (NOIP11)设全集I = {a, b, c, d, e, f, g, h}, 集合B∪A?= {a, b, c, d, e, f}, C∩ A?= {c, d, e},A∩~B = {a, d},那么集合C∩ B∩ A ?为( )。 A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}

2、容斥原理
在计数时,为了使重叠部分不被重复计算,人们研 究出一种新的计数方法,这种方法的基本思想是: 先不考虑重叠的情况,把包含于某内容中的所有对 象的数目先计算出来,然后再把计数时重复计算的数目 排斥出去,使得计算的结果既无遗漏又无重复,这种计 数的方法称为容斥原理。

对有限集合S,用 S 表示S的元素个数

容斥原理的第一形式:设A,B是有限集合,则

A?B ? A ? B ? A?B
容斥原理的第二形式:设A、B、C是有限集合,则

A?B?C ? A ? B ? C ? B?C ? C?A ? A?B ? A?B?C

1、(NOIP10)75名儿童到游乐场去玩。他们可以骑 旋转木马,坐滑行铁道,乘宇宙飞船。已知其中 20人这三种东西都玩过,55人至少玩过其中的两 种。若每样乘坐一次的费用是5元,游乐场总共收 入700,可知有 名儿童没有玩过其中任何一种。

2、某学校足球队有球衣30件,篮球队有球衣15件, 排球队有球衣18件,三队队员总数为50人,其中 有2人同时参加3个队,那么同时只参加两个队的 队员有多少?
3、分母是1001的最简分数一共有多少个?

10,9

◆排列与组合

1.排列的定义: 从n个不同元素中,任取m个元素,按照一定的顺序排成一 列,叫做从n个不同元素中取出m个元素的一个排列. 排列数公式:

全排列问题:

n个不同的元素排成一排,排列方法有:

P

n =n*(n-1)*(n-2)*?*2*1=n! n

2.组合的定义:
从n个不同元素中,任取m个元素,并成一组,叫做从n个 不同元素中取出m个元素的一个组合. 组合数公式:
m P n ? n(n ?1)(n ? 2 )?(n ? m ?1) ? Cn m m! Pm n! ? m!(n ? m)! m

排列与组合的区别与联系:与顺序有关的为排列问题,与顺序 无关的为组合问题.

加法原理和乘法原理 从A到C共有多少中走法?

A

B

C

例1 :学校师生合影,共8个学生,4个老师,要 求老师在学生中间,且老师互不相邻,共有多 少种不同的合影方式?

解 先排学生共有 P 8 8 种排法,然后把老师插入学生 之间的空档,共有7个空档可插,选其中的4个空档,共 有 P 74 种选法.根据乘法原理,共有的不同坐法为P 8 8P 74 种. 结论1 插入法:对于某两个元素或者几个元素要求 不相邻的问题,可以用插入法.即先排好没有限制条 件的元素,然后将有限制条件的元素按要求插入排好 元素的空档之中即可.

例2 : 5个男生3个女生排成一排,3个女生要排在一起, 有多少种不同的排法?



因为女生要排在一起,所以可以将3个女生看成是

一个人,与5个男生作全排列,有P 66 种排法,其中女生内 部也有P 33种排法,根据乘法原理,共有 P 6 6P 3 3种不同的排 法. 结论2 捆绑法:要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题.即将需要相邻的元素合并 为一个元素,再与其它元素一起作排列,同时要注意合 并元素内部也可以作排列.

例3 : 袋中有不同年份生产的5分硬币23个, 不同年份生产的1角硬币10个,如果从袋中取 出2元钱,有多少种取法?

分析 此题是一个组合问题,若是直接考虑取钱的问 题的话,情况比较多,也显得比较凌乱,难以理出头绪 来.但是如果根据组合数性质考虑剩余问题的话,就 会很容易解决问题. 解 把所有的硬币全部取出来,将得到 0.05×23+0.10×10=2.15元,所以比2元多0.15元,所 以剩下0.15元即剩下3个5分或1个5分与1个1角,所以 共有 C23 3 ?C23 1 ?C10 1 种取法. 结论3 剩余法:在组合问题中,有多少取法,就有多少 种剩法,他们是一一对应的,因此,当求取法困难时,可 转化为求剩法.

例4 学校安排考试科目9门,语文要在数学之前考,有 多少种不同的安排顺序?

分析 对于任何一个排列问题,就其中的两个元素来讲 的话,他们的排列顺序只有两种情况,并且在整个排列 中,他们出现的机会是均等的,因此要求其中的某一种 情况,能够得到全体,那么问题就可以解决了.并且也避 免了问题的复杂性. 解 不加任何限制条件,整个排法有 P 99 种,“语文安排

在数学之前考”,与“数学安排在语文之前考”1 的排法 是相等的,所以语文安排在数学之前考的排法共有99P
2

否定是对等的,各占全体的二分之一.在求解中只要求 出全体,就可以得到所求.

例5 某个班级共有43位同学,从中任抽5人,正、副 班长、团支部书记至少有一人在内的抽法有多少种?

分析 此题若是直接去考虑的话,就要将问题分成好几 种情况,这样解题的话,容易造成各种情况遗漏或者重 复的情况.而如果从此问题相反的方面去考虑的话,不 但容易理解,而且在计算中也是非常的简便.这样就可 以简化计算过程. 5 解 43人中任抽5人的方法有C43种,正副班长,团支部 5 书记都不在内的抽法有 C40 种,所以正副班长,团支部书
5 5

结论5 排异法:有些问题,正面直接考虑比较复杂,而它 的反面往往比较简捷,可以先求出它的反面,再从整体中 排除.

圆周排列:
从n个不同的元素中取r个沿一圆周排列,排列的方案:

P /r
N个元素的圆周排列:

r n

P /n =(n-1)!

n n

有重复元素的排列问题:
如:
n1个a,n2个b,n3个c,排成一排,有多少种排列方法。

(n1 ?n2 ?n3)! n1!*n2!*n3!

重复元素的组合问题:
从n种不同的元素中取r个的元素的组合,允 许有重复元素的组合:

C
典型模型:

r n?r?1

r个相同的小球,放到n个不同的盒子里,所有 的放置方法。

2.(NOIP7)平面上有三条平行直线,每条直线上分别有7, 5,6个点,且不同直线上三个点都不在同一条直线上。 问用这些点为顶点,能组成多少个不同四边形? 2、 (NOIP10)由3个a,5个b和2个c构成的所有字符串中, 包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60

1. (NOIP8) 在书架上放有编号为1 ,2 ,...,n的n本书。 现将n本书全部取下然后再放回去,当放回去时要求每 本书都不能放在原来的位置上。例如:n = 3时: 原来位置为:1 2 3 放回去时只能为:3 1 2 或 2 3 1 这两种 问题:求当n = 5时满足以上条件的放法共有多少 种?(不用列出每种放法)

错排问题:
n个不同元素的错排问题: 如:1,2,3,。。。,n 的错排问题,i不在第i个位置的排列方法。 分析: 设f(n)为n个不同元素的错排方案。 第一部分:n先不动,把另外的n-1个数错排,方案是:f(n-1),然后n和 另外的n-1个每一个交换,共有(n-1)*f(n-1)种方案。 第二部分:n和其他的n-1个之一交换,其余的n-2个错排,共有 (n-1)*f(n-2)种方案。 由加法原理:

f(n)=(n-1)*(f(n-1)+f(n-2)) f(1)=0;f(2)=1;
44

错排的计算公式:
1 ? 1? 1 ? 1 ......(?1) f (n) ? n!( 2! 3! 4! 5!
n

1 ) n

几类重要的递推关系:

一、第二类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) (n>1,m>1)
边界条件:S2(n,1)=1;S2(n,n)=1;S2(n,k)=0(k>n)

问题二:集合划分问题。
设S是一个包含n个元素的集合,S={b1,b2,b3,…,bn},现需要将S集 合划分为m个满足如下条件的集合S1,S2, …Sm。 Si≠∮; Si∩Sj=∮; S1∪S2∪…∪Sm=S; (1<=I ,j<=m) 则称S1,S2, …,Sm是S的一个划分。 编程:输入n和m的值,输出不同的划分方案数。 要求:输入数据有一行,第一个数是n,第二个数m。 样例: 输入:4 3 输出:6

noip13
? 1.给定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)= _____________

二、Catalan数
问题一:凸n边形的三角形剖分 在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若 干三角形,不同的拆分数目用f(n)表之,f(n)即为Catalan数。例如五边形 有如下五种拆分方案,故f(5)=5。求对于一个任意的凸n边形相应的f(n)。

区域①是一个凸k边形,区域②是一个凸n-k+1边形,

区域①的拆分方案总数是f(k);
区域②的拆分方案数为f(n-k+1); 故包含△P1PkPn的n 边形的拆分方案数为f(k)* f(n-k+1)种

F(n)=

?f(i)
n?1 i?2

*f(n -i ?1)

问题二:二叉树数目
问题描述:求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(i) *f(n -i-1)
n?1 i?0

为了计算的方便:约定f(0)=1

1 n C2n n?1

问题三:出栈序列
问题描述: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)=

?f(i -1)*f(n -i)
n i?1

三、集合取数问题 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)

noip14
? 2.书架上有21本书,编号从1到21,从其中选4本,其

中每两本的编号都不相邻的选法一共有______种。

3060 C

4 18

? 插空问题:

四、整数划分问题
1、将整数n分成k份,且每份不能为空,任意两种分法不能相同(不 考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}
【问题分析】: 用f(i,j)表示将整数i分成j分的分法,可以划分为两类: 1) :j分中不包含1的分法,为保证每份都>=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, (i<j)

? 2、自然数n的拆分方案。 ? n=5,拆分数6 ? n=6,拆分数10 ? n=7,拆分数14
? 1:5=1+4 ? 2:5=1+1+3 ? 3:5=1+1+1+2 ? 4:5=1+1+1+1+1 ? 5:5=1+2+2 ? 6:5=2+3

?[f(n-j,j)+ f(n-1,j-1)]
n j=2

? 用母函数法: ? 当n=5时: ? 构造母函数如下: ? F(x)=(x0+x1+x2+x3+x4+x5)([x2]0+[x2]1+[x2]2)([x3]0+[x3]1) ? ([x4]0+[x4]1)([x5]0+[x5]1) ? =(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5) ? =1+x+2x2+3x3+5x4+7x5+……

? 项a[i]Xi的系数a[i],a[i]-1即自然数i的拆分数. ? 减1是因为包含了i=i的一种拆分方案。 ? 采用a,b,c三个数组,a:被乘数,b:乘数,c:乘积。 ? 多个多项式采用逐次相乘的方法。每次借助k从b中取

项。

? 3、将整数n分成k份,且每份不能为空,且最大值不

超过m的分法 。任意两种分法不能相同(不考虑顺序)。


相关文章:
noip初赛复习资料(全)
noip初赛复习资料(全)_学科竞赛_高中教育_教育专区。noip初赛复习资料(全) 分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中...
NOIP2013普及组初赛试题
NOIP2013普及组初赛试题_财会/金融考试_资格考试/认证_教育专区。2013 年第十九届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 一、单项选择题(共 20 ...
noip
NOIP 12页 免费 NOIP2013初赛知识复习 暂无评价 163页 1下载券 NOIP2012初赛第...(NOIP2006) 全国信息学奥林匹克联赛(NOIP2006)复赛 信息学奥林匹克联赛竞赛时间...
1999-2013年NOIP初赛基础知识题
1999-2013NOIP初赛基础知识题_学科竞赛_高中教育_教育专区。1999-2013NOIP初赛提高组的基础知识题及答案1999-2013 年全国青少年信息学奥林匹克联赛初赛试题(提高组...
NOIP初赛理论知识复习资料要点摘录
NOIP初赛理论知识复习资料要点摘录_学科竞赛_高中教育_教育专区。要点摘录 ?计算机的诞生与发展 ?微型机的主要技术指标 ?计算机的工作原理 ?总线与接口 ?计算机中数...
NOIP初赛复习
NOIP初赛复习_学科竞赛_高中教育_教育专区。.初赛复习 一 题型 单项选择题(共 ...数据结构的基本知识 线性表的知识 :(1)栈: 先进后出(FILO)(2)队列:先进先...
NOIP初赛相关知识点及参考答案
相关知识点与参考答案一.单项选择题 1、操作系统是系统软件的核心,是有效利用...noip2002初赛试题及答案 7页 免费 NOIP初赛知识复习总结 86页 1下载券 NOIP...
NOIP2013初赛提高组c试题
NOIP2013初赛提高组c试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2013 年 10 月 13 日 14:30~...
信息学奥赛NOIP初赛复习知识点
信息学奥赛 NOIP 初赛复习知识点 1、计算机相关科学家: A:被西方人誉为“计算机之父”的美籍匈牙利科学家、 数学家 冯 ·诺依曼 于 1945 年发表了一个 全新的...
NOIP2013初赛提高组Pascal试题及答案
NOIP2013初赛提高组Pascal试题及答案_学科竞赛_高中教育_教育专区。NOIP2013初赛提高...NOIP初赛复习资料 60页 1下载券 NOIP提高组初赛基础知识... 2页 1下载券 第...
更多相关标签: