nbhkdz.com冰点文库

全国青少年信息学奥林匹克联赛初赛讲义


全国青少年信息学奥林匹克联赛初赛复习讲义
2011-09-14 12:04:41| 分类: 牛妈的教学工作 | 标签:奥赛讲义 全国青少年信息学奥林匹克联赛初赛复习讲义 初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识, 而问题解决类型的题目更加重视能力的考查。一般说来,选择题只要多用心积累就可以了。问题解决题目 的模式比较固定,大家

应当做做以前的题目。写运行结果和程序填空也需要多做题目,并且培养良好的程 序阅读和分析能力,就像语文的阅读理解一样。 近几年来,初赛的考查范围有了很大的变化,越来越紧跟潮流了。这就需要大家有比较广泛的知识, 包括计算机硬件、软件、网络、简单的数据结构(例如栈、队列、树和图等)和简单的算法(例如排序、 查找和搜索等),程序设计语言以及一些基本的数学知识和技巧(例如排列组合)。但最主要的,还是取 决于你对程序设计语言的熟悉程度,再加上认真仔细的心态。 硬件知识 一、计算机发展。计算机发展可划分: |字号大中小 订阅

年代 第一代 第二代 第三代 第四代 1946-1958 1959-1964 1965-1970 1971-今

元件 电子管 晶体管 集成电路 大规模集成电路

1946 年 2 月,在美国宾夕法尼亚大学诞生了世界上第一台电子计算机 ENIAC (Electronic Numerical Integrator And Computer),这台计算机占地 170 平方米,重 30 吨,用了 18000 多个电子管,每秒能进 行 5000 次加法运算。 二、冯· 诺依曼理论。1944 年,美籍匈牙利数学家 冯· 诺依曼 提出计算机基本结构和工作方式的设 想,为计算机的诞生和发展提供了理论基础。时至今日,尽管计算机软硬件技术飞速发展,但计算机本身 的体系结构并没有明显的突破,当今的计算机仍属于冯· 诺依曼架构。其理论要点如下: 1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备 5 部分组成。 2、存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序,然后把程序和数据一起 输入计算机,计算机对已存入的程序和数据处理后,输出结果。 三、我国的计算机发展情况 · 我国从 1956 年开始计算机的科研和教学工作; · 1960 年我国第一台自行设计的通用电子计算机 107 机诞生; · 1964 年我国研制成大型通用电子计算机 119 机;

· 1983 年每秒运行一亿次的银河巨型计算机在国防科技大学诞生; · 1992 年研制成功每秒运行 10 亿次的―银河Ⅱ‖巨型计算机; · 1997 年又研制成功每秒运行 130 亿次的―银河Ⅲ‖巨型计算机; · 我国较有名的微型计算机品牌有:―联想‖、―长城‖、―方正‖等; 四、微型机的主要技术指标 1、字长:知己算计能够直接处理的二进制数据的位数。单位为位(BIT) 2、主频:指计算机主时钟在一秒钟内发出的脉冲数,在很大程度上决定了计算机的运算速度。 3、内存容量:是标志计算机处理信息能力强弱的一向技术指标。单位为字节(BYTE)。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量:一般指软盘、硬盘、光盘。

五、计算机的特点: 运算速度快,运算精度高,具有记忆能力,具有逻辑判断能力,具有自动控制能力; 六、计算机的应用:1、数值计算:弹道轨迹、天气预报、高能物理等等。2、信息管理:企业管理、 物资管理、电算化等。3、过程控制:工业自动化控制,卫星飞行方向控制。4、辅助工程:CAD、CAM、 CAT、CAI 等。 七、计算机硬件的五大部件。 计算机硬件由五大部分组成:运算器、控制器、存储器、输入设备、输出设备。 1、

中央处理器。中央处理器(CPU——Central Processing Unit)由运算器、控制器和一些寄存器组成;运算 器进行各种算术运算和逻辑运算;控制器是计算机的指挥系统;CPU 的主要性能指标是主频和字长。 2、存储器。 (1)内部存储器。中央处理器能直接访问的存储器称为内部存储器,它包括快速缓冲存储器和主存 储器,中央处理器不能直接访问的存储器称为外部存储器,外部存储器中的信息必须调入内存后才能为中 央处理器处理。主存储器:内存也常泛称主存,但严格上说,只有当内存中只有主存,而没有快速缓冲存 储器时,才能称为主存。主存储器按读写功能,可分只读存储器(ROM)和随机存储器(RAM)两种。 (2)外部存储器。外存储器:也称为辅助存储器,一般容量较大,速度比主存较慢。 硬盘(Hard disk):目前的硬盘大多采用了温彻斯特技术,所以又称为―温盘‖; 温氏技术的特点是:将盘片、读写磁头及驱动装置精密地组装在一个密封盒里;采用接触式起停, 非接触式读写的方式(磁盘不工作时,磁头停在磁盘表面的起停区,一旦加电后,磁头随着盘片旋转的气 流―飞‖起来,悬浮在磁盘表面,进行读写)。

软盘(Floppy Disk):目前常见的是 3.5 英寸/1.44 MB 的软盘。 光盘存储器(CD-ROM):普通的 CD-ROM,只能读,不能写; CD 盘片的存储量大约是 650 MB。 3、输入设备:(1)键盘(Keyboard):目前大多使用 104 或 108 键盘。(2)鼠标(Mouse): 主要有机械型鼠标和光电型鼠标两种。 (3 ) 手写笔。 (4) 触摸屏。 (5) 麦克风。(6) 扫描仪 (Scanner) 。 (7)视频输入设备。(8)条形码扫描器。 4、输出设备 · 显示器(Monitor):目前主要有 CRT(阴极射线管)显示器和 LCD 液晶显示器。 · 打印机(Printer):主要有针式打印机、喷墨打印机、激光打印机。 · 绘图仪 · 音箱

进制与编码 一、四种常用的数制

进制

基数

基数个 数



进数规律

十进制

0、1、2、3、4、5、6、7、8、9

10

1 0i 2 i 8 i 1 6i 一

逢十进一

二进制

0、1

2

逢二进一

八进制

0、1、2、3、4、5、6、7

8

逢八进一

十六进 制

0、1、2、3、4、5、6、7、8、9、 16 A、B、C、D、E、F

逢十六进

二、二进制与十进制间的相互转换: 1 二进制转十进制。方法:―按权展开求和‖ 例: (1011.01)2 =(1×23+0×22+1×21+1×20+0×2-1+1×2-2 )10 =(8+0+2+1+0+0.25)10=(11.25)10 规律:个位上的数字的次数是 0,十位上的数字的次数是 1,......,依奖递增,而十 分位的数字的次数是-1,百分位上数字的次数是-2,......,依次递减。 注意:不是任何一个十进制小数都能转换成有限位的二进制数。 (2)十进制转二进制。

整数部分转换方法:除以 2 取余,逆序排列(短除反取余法)。例:(89)10 =(1011001)2

2 2 2 2 2 2

89 44 22 11 5 ……1 ……0 ……0 ……1

2 ……1

2 1 ……0 0 ……1 小数部分转换方法:―乘以 2 取整,顺序排列‖(乘 2 取整法)。 例: (0.625)10= (0.101)2 0.625 X 2

1.25 X 0.5 X 2 1.0

1 2 0

1

2.八进制与二进制的转换:

二进制数转换成八进制数:从小数点开始,整数部分向左、小数部分向右,每 3 位为一组用一位八 进制数的数字表示,不足 3 位的要用―0‖补足 3 位,就得到一个八进制数。 八进制数转换成二进制数:把每一个八进制数转换成 3 位的二进制数,就得到一个二进制数。

例:将八进制的 37.416 转换成二进制数: 3 7 . 4 1 6

011 111 .100 001 110 即:(37.416)8 =(11111.10000111)2

例:将二进制的 10110.0011 转换成八进制: 010 110.001100

2

6 . 1

4

即:(10110.011)2 = (26.14)8

3.十六进制与二进制的转换: 二进制数转换成十六进制数:从小数点开始,整数部分向左、小数部分向右,每 4 位为一组用一位 十六进制数的数字表示,不足 4 位的要用―0‖补足 4 位,就得到一个十六进制数。 十六进制数转换成二进制数:把每一个八进制数转换成 4 位的二进制数,就得到一个二进制数。

例:将十六进制数 5DF.9 转换成二进制: 5 D F . 9

0101 1101 1111 .1001 即:(5DF.9)16 =(10111011111.1001)2

例:将二进制数 1100001.111 转成十六进制: 0110 0001 . 1110 6 1 . E

即:(1100001.111)2 =(61.E)16

注意:以上所说的二进制数均是无符号的数。这些数的范围如下表: 无符号位二进制数位数 8 位二进制数 16 位二进制数 数值范围 0~255 (255=28-1) 0~65535 (65535=216-1) 32 位二进制数 0~232-1 H 三、带符号数的机器码表示方法 1.带符号二进制数的表示方法:用最高位的一位数来表示符号:0 表示正,1 表示负。 含符号位二进制数位数 8 位二进制数 16 位二进制数 32 位二进制数 数值范围 -128 ~ +127 -32768 ~ +32767 -2147483648 ~ +2147483647 FH 十六进制范围表示法 80H~7FH 8000H~7FFFH 80000000H~7FFFFFF 00000000H~0FFFFFFFF 十六进制范围表示法 00~0FFH 0000H~0FFFFH

2、符号位的表示:最常用的表示方法有原码、反码和补码。 (1)原码表示法:一个机器数 x 由符号位和有效数值两部分组成,设符号位为 x0,x 真值的绝对值 |x|=x1x2x3...xn,则 x 的机器数原码可表示为: [x]原= ,当 x>=0 时,x0=0,当 x<0 时,x0=1。

例如:已知:x1=-1011B,x2= +1001B,则 x1,x2 有原码分别是 [x1] 原=11011B,[x2]原=01001B 规律:正数的原码是它本身,负数的原码是取绝对值后,在最高位(左端)补―1‖。 (2)反码表示法:一个负数的原码符号位不变,其余各位按位取反就是机器数的反码表示法。正数 的反码与原码相同。

按位取反的意思是该位上是 1 的,就变成 0,该位上是 0 的就变成 1。即 1=0,0=1 (3)补码表示法:首先分析两个十进制数的运算:78-38=41,79+62=141。如果使用两位数的运算 器,做 79+62 时,多余的 100 因为超出了运算器两位数的范围而自动丢弃,这样在做 78-38 的减法时,用 79+62 的加法同样可以得到正确结果。 模是批一个计量系统的测量范围,其大小以计量进位制的基数为底数,位数为指数的幂。如两位十 进制数的测量范围是 1——9,溢出量是 100,模就是 102=100,上述运算称为模运算,可以写作:79+ (-38) =79+62 (mod 100)

进一步写为 -38=62,此时就说 –38 的补法(对模 100 而言)是 62。计算机是一种有限字长的数字 系统,因此它的运算都是有模运算,超出模的运算结果都将溢出。n 位二进制的模是 2n, 一个数的补码记作[x]补,设模是 M,x 是真值,则补码的定义如下:

例:设字长 n=8 位,x=-1011011B,求[x]补。 解:因为 n=8,所以模 M=28=100000000B,x<0,所以 [x]补=M+x=100000000B-1011011B=10100101B 注意:这个 x 的补码的最高位是―1‖,表明它是一个负数。对于二进制数还有一种更加简单的方法由 原码求出补码: (1)正数的补码表示与原码相同; (2)负数的补码是将原码符号位保持―1‖之后,其余各位按位取反,末位再加 1 便得到补码,即取其 原码的反码再加―1‖:[x]补=[x]反+1。 下表列出 的 8 位二进制原码,反码和补码并将补码用十六进制表示。

真值 +127

原码(B) 0 111 1111

反码(B) 0 111 1111

补码(B) 0 111 1111

补码 (H) 7F

+39 +0 -0 -39 -127 -128

0 010 0111 0 000 0000 1 000 0000 1 010 0111 1 111 1111 无法表示

0 010 0111 0 000 0000 1 111 1111 1 101 1000 1 000 0000 无法表示

0 010 0111 0 000 0000 0 000 0000 1 101 1001 1 000 0001 1 000 0000

27 00 00 D9 81 80

从上可看出,真值+0 和-0 的补码表示是一致的,但在原码和反码表示中具有不同形式。8 位补码机 器数可以表示-128,但不存在+128 的补码与之对应,由此可知,8 位二进制补码能表示数的范围是 -128——+127。还要注意,不存在-128 的 8 位原码和反码形式。 四、定点数和浮点数 (一)定点数(Fixed-Point Number)。计算机处理的数据不仅有符号,而且大量的数据带有小数, 小数点不占有二进制一位而是隐含在机器数里某个固定位置上。通常采取两种简单的约定:一种是约定所 有机器数的小数的小数点位置隐含在机器数的最低位之后,叫定点纯整机器数,简称定点整数。另一种约 定所有机器数的小数点隐含在符号位之后、有效部分最高位之前,叫定点纯小数机器数,简称定点小数。 无论是定点整数,还是定点小数,都可以有原码、反码和补码三种形式。 (二)浮点数(Floating-Point Number)。计算机多数情况下采作浮点数表示数值,它与科学计数 法相似,把一个二进制数通过移动小数点位置表示成阶码和尾数两部分:

其中:E——N 的阶码(Expoent),是有符号的整数 S——N 的尾数(Mantissa),是数值的有效数字部分,一般规定取二进制定点纯小数形式。 例:1011101B=2+7*0.1011101,101.1101B=2+3*0.1011101,0.01011101B=2-1*0.1011101 浮点数的格式如下: E 0 阶符 阶 尾符 尾数 E1E2……………En E0 E1E2……………En

浮点数由阶码和尾数两部分组成,底数 2 不出现,是隐含的。阶码的正负符号 E0,在最前位, 阶反映了数 N 小数点的位置,常用补码表示。二进制数 N 小数点每左移一位,阶增加 1。尾数是这点小数, 常取补码或原码,码制不一定与阶码相同,数 N 的小数点右移一位,在浮点数中表现为尾数左移一位。尾 数的长度决定了数 N 的精度。尾数符号叫尾符,是数 N 的符号,也占一位。 例:写出二进制数-101.1101B 的浮点数形式,设阶码取 4 位补码,尾数是 8 位原码。 -101.1101=-0.1011101*2+3 浮点形式为: 阶码 0011 尾数 11011101

补充解释:阶码 0011 中的最高位―0‖表示指数的符号是正号,后面的―011‖表示指数是―3‖;尾数 11011101 的最高位―1‖表明整个小数是负数,余下的 1011101 是真正的尾数。 例:计算机浮点数格式如下,写出 x=0.0001101B 的规格化形式,阶码是补码,尾数是原码。 x=0.0001101=0.1101*10-3 又[-3]补=[-001B]补=[1011]补=1101B 所以 浮点数形式是 1 01 1 0 000 1101

五、ASCII 码 。( American Standard Code for Information Interchange )美国标准信息交换代码简 称 ASCII 码。将每个字符用 7 位的二进制数来表示,共有 128 种状态。包括:大小字母、0…9、其它符号、 控制符。? 0 ‘ ――48,? A ‘―― 65,? a ‘――97 六、汉字信息编码 1. 汉字输入码。汉字输入方法大体可分为:区位码(数字码)、音码、形码、音形码。 · 区位码:优点是无重码或重码率低,缺点是难于记忆; · 音码:优点是大多数人都易于掌握,但同音字多,重码率高,影响输入的速度; · 形码:根据汉字的字型进行编码,编码的规则较多,难于记忆,必须经过训练才能较好地掌握;重 码率低; · 音形码:将音码和形码结合起来,输入汉字,减少重码率,提高汉字输入速度。 2.汉字交换码。汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使 用的代码标准。自国家标准 GB2312-80 公布以来,我国一直延用该标准所规定的国标码作为统一的汉字 信息交换码 。 GB2312-80 标准包括了 6763 个汉字 , 按其使用频度分为一级汉字 3755 个和二级汉字 3008 个。一级汉字按拼音排序,二级汉字按部首排序。此外,该标准还包括标点符号、数种西文字母、图形、 数码等符号 682 个。由于 GB2312-80 是 80 年代制定的标准,在实际应用时常常感到不够,所以,建议 处理文字信息的产品采用新颁布的 GB18030 信息交换用汉字编码字符集,这个标准繁、简字均处同一平 台,可解决两岸三地间 GB 码与 BIG5 码间的字码转换不便的问题。 3.字形存储码。字形存储码是指供计算机输出汉字(显示或打印)用的二进制信息,也称字模。通 常,采用的是数字化点阵字模。 软件与操作系统 一、计算机软件的组成。计算机软件可分为系统软件和应用软件两大类。 (1)· 系统软件:用来支持应用软件的开发和运行的,主要是操作系统软件,如:DOS、 Windows95/98/2000、Unix、Linux、WindowsNT; (2)应用软件:为了某个应用目的而编写的软件,主要有文字处理软件、电子表格软件、数据库管 理软件等。 如:Office 2003、QQ、C 语言、360 安全卫士等 二、操作系统(OS——Operating System)

操作系统是控制与管理计算机系统资源的软件,是硬件的第一层扩充,任何应用软件的运行都必须 依靠操作系统的支持。 (一)Windows 系列操作系统。Windows 是 Microsoft 公司开发的图形化界面的操作系统。 1、基本概念:图标、任务栏、标题栏、菜单栏、滚动条、工具栏、对话框、开始菜单…… 2、基本操作: (1)鼠标操作:单击、双击、拖动,左键、右键功能; (2)窗口操作:最大(小)化、大小调整、拖动、关闭、排列、切换; (3)菜单操作:激活、选择; ★ 命令项的约定—— 正常显示和灰色显示;命令后带―…‖:执行命令则弹出对话框;带快捷键:某些菜单命令的 后面标有对应的键盘命令,称为该命令的快捷键或热键;选中标志:某些命令选项的左侧有用打勾表示的 选中标志,说明此命令功能正在起作用;命令后带―?‖:级联:此命令后会有下一级的子命令菜单弹出供用 户作进一步选择; ★快捷菜单——当鼠标位于某个对象上,单击鼠标右键,可打开有关对象的快捷菜单; (4)剪贴板:复制(Ctrl-C)、粘贴(Ctrl-V)、剪切(Ctrl-X)、复制屏幕图像:可将当 前屏幕图形以 BMP 格式传送到剪贴板…… (5)其它:查找、运行、切换 Windows、进入 DOS 环境、文件夹选项 3、中文输入法:输入法切换,中、英文切换,半角/全角切换;软键盘:是在屏幕上显示的一个键盘 图形,用户可用鼠标点击其中某个键以替代实际的按键; 4、各种文件的后缀名:bat、com、exe、sys、tmp、zip、……;doc、xls、txt、htm、……;bmp、 gif、jpg、psd、……;wav、avi、mp3、swf……。 (二)DOS(Disk Operating System)操作系统 由美国 Microsoft 公司发行的 DOS 称为 MS-DOS,主要由 IO.sys、MSDOS.sys、COMMAND.COM 三个基本文件和几十个内、外部命令文件组成。 1、主要内部命令: (1)DIR——显示磁盘文件目录;(2)CD——改变当前目录;(3)MD——建立目录; (4)RD——删除目录; (5)DATE——显示和设置系统日期;

(6)TIME——显示和设置系统时间;(7)COPY——复制文件;(8))DEL——删除文件; (9)REN——文件重命名; (10)TYPE——显示文本文件内容

2、主要外部命令:(1)FORMAT——磁盘格式化;(2)DISKCOPY——全盘复制; (3)BACKUP——文件备份; (4)CHKDSK——检查磁盘 信息安全

一、计算机安全。计算机安全(computer security)是指防范与保护计算机系统及其信息资源在生存过 程中免受蓄意攻击、人为失误和自然灾害等引起的损失和破坏。 二、计算机病毒。计算机病毒是人类自己想像和发明出来的,它是一种特殊的程序,有着与生物病 毒极为相似的特点。一是寄生性,它们大多依附在别的程序上面。二是隐蔽性,它们是悄然进入系统的, 人们很难察觉。三是潜伏性,它们通常是潜伏在计算机程序中,只在一定条件下才发作的。四是传染性, 它们能够自我复制繁殖,通过传输媒介蔓延。五是破坏性,轻则占用一定数量的系统资源,重则破坏整个 系统。 对于计算机病毒,我们不必谈虎变色,而应采取积极的防治态度。首先,要防止―病从口入‖,因为病 毒不是自生的,而是外来的。另外,要用优秀的防杀病毒软件,对外来的软件和资料要进行严格的检查和 杀毒。注意,防杀病毒软件需要及时更新(主要是其中的数据文件),一般每周一次,不更新基本上等于没 有防杀毒功能。 20 世纪 50、60 年代,黑客(hacker)曾是编程高手的代名词。后来,黑客成为一个独特的群体,他们 通过各种渠道交流技艺,不少人以攻击计算机及其网络系统为乐趣。黑客们的胆大妄为已经给社会造成了 很大的影响,一些黑客已经蜕变为威胁社会安全的罪犯。要防止―黑客‖攻击,主要方法是加强安全措施, 例如设置防火墙(见图 3.1.1)。防火墙是一种计算机设备,它设置在内部网络与外部网络之间,起一个隔 离的作用,既可以阻止外部信息非法进入内部系统,也可以阻止内部人员非法访问外部系统。 网络知识 一、关于网络的一些定义: 所谓计算机网络,就是利用通信线路和设备,把分布在不同地理位置上的多台计算机连接起来。计 算机网络是现代通信技术与计算机技术相结合的产物。网络中计算机与计算机之间的通信依靠协议进行。 协议是计算机收、发数据的规则。 1、TCP/IP:用于网络的一组通讯协议。包括 IP(Internet Protocol)和 TCP(Transmission Control Protocol) 。 TCP/IP 是一组协议 , 包括上百个各种功能的协议 , 其中 TCP 和 IP 是最核心的两个协议 。 TCP/IP 协议把 Internet 网络系统描述成具有四个层次功能的网络模型。 (1)链路层:这是 TCP/IP 结构的第一层,也叫网络接口层,其功能是提供网络相邻节点间的信息 传输以及网络硬件和设备驱动。 (2)网络层:(IP 协议层)其功能是提供源节点和目的节点之间的信息传输服务,包括寻址和路由 器选择等功能。 (3)输屋:(TCP 协议)其功能是提供网络上的各应用程序之间的通信服务。 (4)应用层:这是 TCP/IP 最高层,其功能是为用户提供访问网络环境的手段,主要提供 FTP、 TELNET、GOPHER 等功能软件。 IP 协议适用于所有类型网络。TCP 协议则处理 IP 协议所遗留的通信问题,为应用程序提供可靠的 通信连接,并能自动适应网络的变化。TCP/IP 目前成为最为成功的网络体系结构和协议规范。 2、Netbeui:一种非常简单的协议,MICROSOFT 开发。 3、IPX:用于 NOVELL 网络。 二、网络基础知识 (一)网络的发展。计算机网络的发展过程大致可以分为三个阶段:

远程终端联机阶段:主机—终端 计算机网络阶段:计算机—计算机 Internet 阶段: Internet (二)网络的主要功能:(1)资源共享;(2)信息传输;(3)分布处理更新;(4)综合信息服 务 (三)网络的分类。计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输 介质等分类。 1、按地理范围分类 ①局域网 LAN(Local Area Network)。局域网地理范围一般几百米到 10km 之内,属于小范围内的连 网。如一个建筑物内、一个学校内、一个工厂的厂区内等。局域网的组建简单、灵活,使用方便。 ②城域网 MAN(Metropolitan Area Network)。城域网地理范围可从几十公里到上百公里,可覆盖一个 城市或地区,是一种中等形式的网络。 ③广域网 WAN(Wide Area Network)。广域网地理范围一般在几千公里左右,属于大范围连网。如几 个城市,一个或几个国家,是网络系统中的最大型的网络,能实现大范围的资源共享,如国际性的 Internet 网 络。 2、按传输速率分类。网络的传输速率有快有慢,传输速率快的称高速网,传输速率慢的称低速网。传 输速率的单位是 b/s(每秒比特数,英文缩写为 bps)。一般将传输速率在 Kb/s—Mb/s 范围的网络称低速网, 在 Mb/s—Gb/s 范围的网称高速网。也可以将 Kb/s 网称低速网,将 Mb/s 网称中速网,将 Gb/s 网称高速网。 网络的传输速率与网络的带宽有直接关系。带宽是指传输信道的宽度,带宽的单位是 Hz(赫兹)。按照 传输信道的宽度可分为窄带网和宽带网。一般将 KHz—MHz 带宽的网称为窄带网,将 MHz—GHz 的网称为 宽带网,也可以将 kHz 带宽的网称窄带网,将 MHz 带宽的网称中带网,将 GHz 带宽的网称宽带网。通常情 况下,高速网就是宽带网,低速网就是窄带网。 3、按传输介质分类。传输介质是指数据传输系统中发送装置和接受装置间的物理媒体,按其物理形态 可以划分为有线和无线两大类。 ①有线网。传输介质采用有线介质连接的网络称为有线网,常用的有线传输介质有双绞线、同轴电缆 和光导纤维。 ●双绞线是由两根绝缘金属线互相缠绕而成,这样的一对线作为一条通信线路,由四对双绞线构成双绞 线电缆。双绞线点到点的通信距离一般不能超过 100m。目前,计算机网络上使用的双绞线按其传输速率分 为三类线、五类线、六类线、七类线,传输速率在 10Mbps 到 600Mbps 之间,双绞线电缆的连接器一般为 RJ-45。 ●同轴电缆由内、外两个导体组成,内导体可以由单股或多股线组成,外导体一般由金属编织网组成。 内、外导体之间有绝缘材料,其阻抗为 50Ω。同轴电缆分为粗缆和细缆,粗缆用 DB-15 连接器,细缆用 BNC 和 T 连接器。 ●光缆由两层折射率不同的材料组成 。 内层是具有高折射率的玻璃单根纤维体组成,外层包一层折射率 较低的材料。光缆的传输形式分为单模传输和多模传输,单模传输性能优于多模传输。所以,光缆分为单模光 缆和多模光缆,单模光缆传送距离为几十公里,多模光缆为几公里。光缆的传输速率可达到每秒几百兆位。光

缆用 ST 或 SC 连接器。光缆的优点是不会受到电磁的干扰,传输的距离也比电缆远,传输速率高。光缆的 安装和维护比较困难,需要专用的设备。 ②无线网。采用无线介质连接的网络称为无线网。目前无线网主要采用三种技术:微波通信,红外线 通信和激光通信。这三种技术都是以大气为介质的。其中微波通信用途最广,目前的卫星网就是一种特殊形 式的微波通信,它利用地球同步卫星作中继站来转发微波信号,一个同步卫星可以覆盖地球的三分之一以上 表面,三个同步卫星就可以覆盖地球上全部通信区域。 4、按拓扑结构分类。计算机网络的物理连接形式叫做网络的物理拓扑结构。连接在网络上的计算机、 大容量的外存、高速打印机等设备均可看作是网络上的一个节点,也称为工作站。计算机网络中常用的拓扑 结构有总线型、星型、环型等。 ①总线拓扑结构。总线拓扑结构是一种共享通路的物理结构。这种结构中总线具有信息的双向传输 功能,普遍用于局域网的连接,总线一般采用同轴电缆或双绞线。总线拓扑结构的优点是:安装容易,扩充或 删除一个节点很容易,不需停止网络的正常工作,节点的故障不会殃及系统 。 由于各个节点共用一个总线作为 数据通路,信道的利用率高。但总线结构也有其缺点:由于信道共享,连接的节点不宜过多,并且总线自身的 故障可以导致系统的崩溃。 ②星型拓扑结构。星型拓扑结构是一种以中央节点为中心,把若干外围节点连接起来的辐射式互联结 构。这种结构适用于局域网,特别是近年来连接的局域网大都采用这种连接方式。这种连接方式以双绞线或 同轴电缆作连接线路。星型拓扑结构的特点是:安装容易,结构简单,费用低,通常以集线器(Hub)作为中央节 点,便于维护和管理。中央节点的正常运行对网络系统来说是至关重要的。 ③环型拓扑结构。环型拓扑结构是将网络节点连接成闭合结构。信号顺着一个方向从一台设备传到 另一台设备,每一台设备都配有一个收发器,信息在每台设备上的延时时间是固定的 。 这种结构特别适用于实 时控制的局域网系统。环型拓扑结构的特点是:安装容易,费用较低,电缆故障容易查找和排除。有些网络系 统为了提高通信效率和可靠性,采用了双环结构,即在原有的单环上再套一个环,使每个节点都具有两个接收 通道。环型网络的弱点是,当节点发生故障时,整个网络就不能正常工作。 (四)网络的体系结构 OSI 的七层体系结构: 应用层 表示层 会话层 运输层 网络层 数据链路层 物理层 (五)局域网的工作方式。通常有两种: (1)客户机/服务器(Client/Server): 提供资源并管理资源的计算机称为服务器;使用共享资源的计算机称客户机; (2)对等(Peer-to-Peer):

不使用服务器来管理网络共享资源,所以的计算机处于平等的地位。 三、Internet 国际互联网 1、Internet 的形成与发展。Internet 又称国际互联网,规范的译名是―因特网‖,指当前各国、各地区 众多开发的网络连接在一起而形成的全球性网络。 2、我国 Internet 的发展情况: · 八十年代末,九十年代初才起步。 · 1989 年我国第一个公用分组交换网 CNPAC 建成运行。 · 我国已陆续建成与 Internet 互联的四个全国范围的公用网络: · 中国公用计算机互联网(CHINANET)、中国金桥信息网(CHINAGBN) · 中国教育和科研计算机网(CERNET)、中国科学技术网(CSTNET) 3、IP 地址:我们把整个 Internet 看作一个单一的、抽象的网络,所谓 IP 地址,就是为 Internet 中 的每一台主机分配一个在全球范围唯一地址。IP v4 地址是由 32 位二进数码表示的,为方便记记忆,把这 32 位二进制数每 8 个一段用―.‖ 隔开,再把每一段的二进制数化成十进制数,也就得到我们现在所看到的 IP 地址形式。 IP 地址是用―.‖隔开地四个十进制整数,每个数字取值为 0—255。 IP 地址分 A、B、C、D;E 五类,目前大量使用的是 A、B、C 三类,D 类为 Internet 体系结构委员 会 IAB 专用,E 类保留在今后使用。最高位 1..126 为 A 类,128..191 是 B 类,192..223 是 C 类。 4、域名:域名地址采用层次结构,一个域名一般有 3-5 个子段,中间用―. ‖隔开。IP 地址作为 Internet 上主机的数字标识,对计算机网络来说是非常有效的。但对于使用者来说,很难记忆这些由数字组成的 IP 地址了。为此,人们研究出一种字符型标识,在 Internet 上采用―名称‖寻址方案,为每台计算机主机都分配 一个独有的―标准名称‖,这个用字符表示的―标准名称‖就是我们现在所广泛使用的域名(DN,domain name)。因此主机的域名和 IP 地址一样,也采用分段表示的方法。其结构一般是如下样式:计算机名.组 织结构名.网络名.最高层域名。 顶级域名有三类: (1)国家顶级域名,如 cn(中国)、us(美国)、uk(英国); (2)国际顶级域名—— int ,国际性组织可在 int 下注册; (3)通用顶级域名,如:com、net、edu、gov、org、…… 有了域名标识,对于计算机用户来说,在使用上的确方便了很多。但计算机本身并不能自动识别这 些域名标识,于是域名管理服务器 DNS (domain name system) 就应运而生了。所谓的域名管理系统 DNS (domain name system)就是以主机的域名来代替其在 Internet 上实际的 IP 地址的系统,它负责将 Internet 上主机的域名转化为计算机能识别的 IP 地址。从 DNS 的组织结构来看,它是一个按照层次组织 的分布式服务系统;从它的运行机制来看,DNS 更像一个庞大的数据库,只不过这个数据库并不存储在任 一计算机上,而是分散在遍布于整个 Internet 上数以千计的域名服务器中而已。 通过上面的 IP 地址、域名 DN 和域名管理系统 DNS,就把 Internet 上面的每一台主机给予了唯一 的定位。三者之间的具体联系过程如下:当连接网络并输入想访问主机的域名后,由本地机向域名服务器 发出查询指令,域名服务器通过连接在整个域名管理系统查询对应的 IP 地址,如找到则返回相应的 IP 地

址,反之则返回错误信息。说到这里,想必大家都明白了为什么当我们在浏览时,浏览器左下角的状态条 上会有这样的信息:―正在查找 xxxxxx‖、―xxxxxx 已经发现,正在连接 xxxxxx‖,其实这也就是域名通过 DNS 转化为 IP 地址的过程。 当然域名通过 DNS 转化为 IP 地址需要等待一段时间,因为如果你所使用的域名服务器上如果没有 你所需要域名的对应 IP 地址,它就会向上级域名服务器查询,如此类推,直至查到结果,或返回无效信 息。一般而言,这个查询过程都非常短,你很难察觉到。 5、Internet(译为因特网或国际互联网)的服务与工具。Internet 的服务有:电子邮件、远程登陆、 文件传输、信息服务等; (1) 电子邮件(E-Mail):电子邮件地址格式为:收信人邮箱名@邮箱所在主机的域名。例: winner01@ 21cn.com ,qfit168@yahoo.com.cn,xfszldg@163.com,xfkjxxldg@163.com 等 (2)远程登陆(Telnet):指通过 Internet 与其它主机连接。登陆上另一主机,你就可以使用该主 机对外开放的各种资源,如联机检索、数据查询。 (3)文件传输(FTP):用于在计算机间传输文件。如下载软件等。 6、全球信息网(WWW-World Wide Web):又称万维网,是一个全球规模的信息服务系统,由遍 布于全世界的数以万计的 Web 站点组成。

数据结构与算法 一、算法 (一)算法的基本概念。计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2.算法的基本要素:算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求 (二)算法的复杂度 1、算法的时间复杂度:指执行算法所需要的计算工作量。2、算法的空间复杂 度:执行这个算法所需要的内存空间 二、数据结构 (一)数据结构的定义 1、数据的逻辑结构:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、 线形结构、树形结构和图形结构四种。 2、数据的存储结构:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的 存储结构有顺序、链接、索引等存储结构。 (二).数据结构的图形表示:在数据结构中,没有前件的结点称为根结点;没有后件的结点成为终 端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 三、线性表及其顺序存储结构

(一)线性结构和非线性结构。根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数 据结构分为两大类型:线性结构和非线性结构。 线性结构:非空数据结构满足:有且只有一个根结点;每个结点最多有一个前件,最多只有一个后 件。非线性结构:如果一个数据结构不是线性结构,称之为非线性结构。 常见的线性结构:线性表、栈、队列 (二)线性表的定义 线性表是 n 个元素构成的有限序列 (A1,A2,A3……) 。表中的每一个数据元素,除了第一个以外, 有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表,或可以表示为 (a1,a2,……an), 其中 ai(I=1,2,……n)是属于数据对象的元素,通常也称其为线性表中的一个结点。非空 线性表有如下一些特征:(1)有且只有一个根结点 a1,它无前件;(2)有且只有一个终端结点 an,它无 后件;(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表中结 点的个数 n 称为线性表的长度。当 n=0 时称为空表。 (三)线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征:1、线性表中的所有元素所占的存储空间是连续的; 2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。即线性表逻辑上相邻、物理也相邻,则已 知第一个元素首地址和每个元素所占字节数,则可求出任一个元素首地址。 假设线性表的每个元素需占用 K 个存储单元,并以所占的第一个单元的存储地址作为数据元素的存 储位置。则线性表中第 i+1 个数据元素的存储位置 LOC(ai+1)和第 i 个数据元素的存储位置 LOC(ai)之间满 足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ①

其中,LOC(a1)是线性表的第一个数据元素 a1 的存储位置,通常称做线性表的起始位置或基地址。 因为在顺序存储结构中,每个数据元素地址可以通过公式①计算得到,所以线性表的顺序存储结构是随机 存取的存储结构。 在线性表的顺序存储结构下,可以对线性表做以下运算:插入、删除、查找、排序、分解、合并、 复制、逆转 (四)顺序表的插入运算 线性表的插入运算是指在表的第 I 个位置上,插入一个新结点 x,使长度为 n 的线性表 (a1,a2 …ai…an)变成长度为 n+1 的线性表(a1,a2…x,ai…an). 该算法的时间主要花费在循环的结点后移语句上,执行次数是 n-I+1。当 I=n+1,最好情况,时间复杂 度 o(1) 当 I=1, 最坏情况,时间复杂度 O(n);算法的平均时间复杂度为 O(n) (五)顺序表的删除运算 线性表的删除运算是指在表的第 I 个位置上,删除一个新结点 x,使长度为 n 的线性表 (a1,a2 …ai…an)变成长度为 n-1 的线性表(a1,a2…ai-1,ai+1…an)。当 I=n,时间复杂度 O(1),当 I=1, 时间复杂度 o(n) ,平均时间复杂度为 On)。

四、栈及其基本运算 1.什么是栈? 栈实际上也是一个线性表,只不过是一种特殊的线性表。栈是只能在表的一端进行插 入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为栈底(BOTTOM)。当表中 没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被 插入的元素,从而也是最后才能被删除的元素。 假设栈 S= (a1,a2,a3,……an) ,则 a1 称为栈底元素,an 称为栈顶元素。栈中元素按 a1,a2,a3……an 的次序进栈,退栈的第一个元素应该是栈顶元素。即后进先出。 2.栈的顺序存储及其运算。用 S(1:M)作为栈的顺序存储空间。M 为栈的最大容量。 栈的基本运算有三种:入栈、退栈与读栈顶元素。 入栈运算:在栈顶位置插入一个新元素。首先将栈顶指针进一(TOP+1),然后将新元素插入到栈 顶指针指向的位置。 退栈运算:指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素赋给一个指定的变量,然后将 栈顶指针退一(TOP-1) 读栈顶元素:将栈顶元素赋给一个指定的变量。栈顶指针不会改变。 五、队列及其基本运算 1、什么是队列。队列是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做对头,允 许插入的一端叫做对尾。队列的修改是先进先出。往队尾插入一个元素成为入队运算。从对头删除一个元 素称为退队运算。 2.循环队列及其运算。 在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空 间的最后一个位置绕到第一个位置,形成逻辑上的环状空间。 在循环队列中,,用队尾指针 rear 指向队列中的队尾元素,用排头指针 front 指向排头元素的前一个 位置,因此,从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列 中的元素。 在实际使用循环队列时,为了能区分队满还是队列空,通常需要增加一个标志 S: 队列空,则 S=0,rear=front=m 队列满,则 S=1,rear=front=m

循环队列主要有两种基本运算:入队运算和退队运算 (1)入队运算:入队运算指在循环队列的队尾加入一个新元素,首先 rear=rear+1,当 rear=m+1 时, 置 rear=1,然后将新元素插入到队尾指针指向的位置。当 S=1,rear=front,说明队列已满,不能进行入队运 算,称为―上溢‖。 (2)退队运算:退队运算指在循环队列的排头位置退出一个元素并赋给指定的变量。首先 front=front+1,并当 front=m+1 时,置 front=1,然后将排头指针指向的元素赋给指定的变量。当循环队列为 空 S=0,不能进行退队运算,这种情况成为―下溢‖。 六、线性单链表的结构及其基本运算 1、线性单链表的基本概念

一组任意的存储单元存储线性表的数据元素,因此,为了表示每个数据元素 ai 与其直接后继数据元 素 ai+1 之间的逻辑关系,对数据元素 ai 来说,除了存储其本身的信息之外,还需存储一个指示其直接后 继的信息(即直接后继的存储位置)。这两部分信息组成数据元素 ai 的存储映象,成为结点。它包括两个 域:其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。指针域中存储的信 息称做指针或链。N 个结点链结成一个链表,即为线性表(a1, a2,……,an)的链式存储结构。又由于此链表 的每个结点中只包含一个指针域,故又称线性链表或单链表。 有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点,它指向表中第一个结点。头 结点的数据域可以不存储任何信息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向 第一个结点的指针(即第一个元素结点的存储位置)。 在单链表中,取得第 I 个数据元素必须从头指针出发寻找,因此,单链表是非随机存取的存储结构, 链表的形式:单向,双向 2、线性单链表的存储结构 3、带链 4、带链的栈与队列。栈也是线性表,也可以采用链式存储结构。队列也是线性表,也可以采用链式 存储结构。 5、线性链表的基本运算:(1)线性链表的插入 (2)线性链表的删除 6、双向链表的结构及其基本运算:在双向链表的结点中有两个指针域,其一指向直接后继,另一指 向直接前驱。 7、循环链表的结构及其基本运算。循环链表是另一种形式的链式存储结构,它的特点是表中最后一 个结点的指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他结点。 七、树与二叉树 (一)树的定义。树是一种简单的非线性结构。树型结构的特点:1、每个结点只有一个前件,称为 父结点,没有前件的结点只有一个,称为树的根结点。2、每一个结点可以有多个后件结点,称为该结点的 子结点。没有后件的结点称为叶子结点。3、一个结点所拥有的后件个数称为树的结点度。4、树的最大层 次称为树的深度。 (二)二叉树的定义及其基本性质 1、二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于 2 的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 2、二叉树的基本性质 ①在二叉树的第 I 层上至多有 2i-1 个结点。 ②深度为 k 的二叉树至多有 2k-1 个结点(k>=1) ③在任意一个二叉树中,度为 0 的结点总是比度为 2 的结点多一个; ④具有 n 个结点的二叉树,其深度至少为[log2n]+1。 一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都是最大 结点数。

3、满二叉树与完全二叉树。 满二叉树:除最后一层以外,每一层上的所有结点都有两个子结点。在满二叉树的第 K 层上有 2K-1 个结点,且深度为 M 的满二叉树右 2M-1 个结点 完全二叉树:除最后一层以外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干 结点。具有 N 个结点的完全二叉树的深度为[log2n]+1 完全二叉树总结点数为 N,若 N 为奇数,则叶子结点数为(N+1)/2 若 N 为偶数,则叶子结点数为 N/2。 4、二叉树的存储结构。二叉树通常采用链式存储结构 (三)二叉树的遍历。就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。 一般先左后右。1、前序遍历 DLR:首先访问根结点,然后遍历左子树,最后遍历右子树。2、中序遍历 LDR:首先遍历左子树,然后根结点,最后右子树。3、后序遍历 LRD:首先遍历左子树,然后遍历右子 树,最后访问根结点。 八、查找技术 1、顺序查找 在两种情况下只能用顺序查找:线性表为无序表、链式存储结构的有序表 2、二分查找 只适用于顺序存储的有序表(从小到大)。 对于长度为 N 的有序线性表,在最坏情况下,二分查找只需要比较 log2N 次,而顺序查找要比较 N 次。 九、排序技术。排序指将一个无序序列整理成按值非递减顺序排列的有序序列。 (一)交换类排序法。冒泡排序与快速排序法属于交换类的排序方法 1、冒泡排序法 假设线性表的长度为 N,则在最坏的情况下,冒跑排序需要经过 N/2 遍的从前往后 的扫描和 N/2 遍的从后往前的扫描,需要的比较次数为 N(N-1)/2 2、快速排序法 (二)选择类排序法 1.简单选择排序法 2.堆排序法 (三)插入类排序法 1.简单插入排序法 2.希尔排序法

最坏情况 下 交 换排序 快速排序 n(n-1)/2 N) 插 入排序 序 希尔排序 O(n1.5) 简单插入排 n(n-1)/2 冒泡排序 n(n-1)/2 下

最好情况

说明

最简单的交换排序。在待排序的元素 序列基本有序的前提下,效率最高 O(Nlog2 每个元素距其最终位置不远时适用

选 择排序 序

简单选择排

n(n-1)/2

适用于较大规模的线性表

堆排序

O(nlog2n)

排列组合 一、排列与组合重点整理 (一)乘法原理 1.若完成某一件事情要经过个 k 步骤,而第一个步骤有 m1 种方法,第二个步骤有 m2 种方法,……, 第 k 个步骤有 mk 种方法,则完成这件事情共有 m1×m2×…×mk 种方法。 (二)阶乘及其运算:从 1 开始连续 n 个自然数相乘,叫做阶乘。记作:n!= n(n-1)(n-2) ....3.2. 1。 其中「n!」念作「n 阶乘」,n 为自然数,同时规定 0!=1。 (三)相异物的直线排列 从 n 个相异物中,任意选取 r 个( ,不许重复),然后按序作直线排列,其排列总数记为 ,亦可记 为 P(n,r)或 ,则 推论→从 n 个相异物中,全取的直线排列数为 n! (四)不完全相异物的直线排列 1、n 个事物中,有 m 个相同,其余都不相同,全取排列数为 。 2、n 个事物中,假设有 k 类,而第一类有 m1 个相同,第二类有 m2 个相同,……第 k 类有 mk 个相同,其中 m1+m2+…+mk=n,则此 n 个全取排列数为 。 (五)重复排列:从 n 个不同的对象中,任意选出 m 个,但每件对象均可重复选取的重复排列数为 。 (六)环状排列 1、自 n 个不同物件中,任取 m 个( 且不重复)作环状排列,则其排列总数为 。 推论→将 n 个不同对象全取的环状排列总数为 。 2、项圈排列数= 。 (七)组合 1、从 n 个不同对象中,每次不重复地取出 r 个( )为一组,则其组合数为 推论→1、 (剩余公式) 2、 (八)重复组合

1.从 n 类相异物中(每类不得少于个),每次取 r 个为一组,各组的对象可以任意重复,则此种组合 称为取的重复组合,其重复组合数以符号 表示,且 推论→方程式 的非负整数解个数为 ;正整数解的个数则为 十、两条计数原理 用古典方法求概率,经常需要用到排列与组合的公式。现简要介绍如下: 排列与组合是两类计数公式,它们的获得都基于如下两条计数原理。 (1)乘法原理:如果做某件事需经 k 步才能完成,其中做第一步有 m1 种方法,做第二步 m2 种 方法,…,做第 k 步有 mk 种方法,那么完成这件事共有 m1×m2×…×mk 种方法。 例如, 甲城到乙城有 3 条旅游线路,由乙城到丙城有 2 条旅游线路,那么从甲城经乙城去丙城共 有 3×2=6 条旅游线路。 (2) 加法原理:如果做某件事可由 k 类不同方法之一去完成,其中在第一类方法中又有 m1 种完 成方法, 在第二类方法中又有 m2 种完成方法,… ,在第 k 类方法中又有 mk 种完成方法, 那么完成这件 事共有 m1+m2+…+mk 种方法。 例如,由甲城到乙城去旅游有三类交通工具: 汽车、火车和飞机,而汽车有 5 个班次,火车有 3 个班次,飞机有 2 个班次,那么从甲城到乙城共有 5+3+2=10 个班次供旅游选择。 (3)排列与组合的定义及其计算公式如下: ①排列:从 n 个不同元素中任取 个元素排成一列称为一个排列。按乘法原理,此种排列共有 n×(n-1) ×…×(n-r+1)个,记为 。若 r=n,称为全排列,全排列数共有 n!个,记为 Pn,即: = n×(n-1) ×…×(n-r+1), Pn= n! ②重复排列:从 n 个不同元素中每次取出一个作记录后放回,再取下一个,如此连续取 r 次所得 的排列称为重复排列。按乘法原理,此种重复排列共有 个。注意,这里的 r 允许大于 n。 例如,从 10 个产品中每次取一个做检验,放回后再取下一个,如此连续抽取 4 次,所得重复排 列数为 。假如上述抽取不允许放回,则所得排列数为 10×9×8×7=5040。 ③组合:从 n 个不同元素中任取 个元素并成一组 (不考虑他们之间的排列顺序)称为一个组合, 此种组合数为:规定 0!=1,因而 。另外,在组合中,r 个元素"一个接一个取出"与"同时取出"是等同的。 来源:考试大的美女编辑们 例如,从 10 个产品中任取 4 个做检验,所有可能取法是从 10 个中任取 4 个的组合数,则不同 取法的种数为: 这是因为取出的任意一组中的 4 个产品的全排列有 4!=24 种 。 而这 24 种排列在组合中只算一种 。 所以 。 注意:排列与组合都是计算 "从 n 个不同元素中任取 r 个元素"的取法总数公式,他们的主要差 别在于: 如果讲究取出元素间的次序,则用排列公式;如果不讲究取出元素间的次序,则用组合公式。至于 是否讲究次序,应从具体问题背景加以辨别。 [例 1.1-5] 一批产品共有 N 个,其中不合格品有 M 个,现从中随机取出 n 个 , 问:事件 Am= "恰好有 m 个不合格品"的概率是多少?

从 N 个产品中随机抽取 n 个共有 个不同的样本点,它们组成这个问题的样本空间 。来源: www.examda.com 其中―随机抽取‖必导致这 个样本点是等可能的。以后对―随机抽取‖一词都可以作同样理解。下面 我们先计算事件 A0、A1 的概率,然后计算一般事件 Am 的概率。 事件 A0="恰好有 0 个不合格品"="全是合格品",要使取出的 n 个产品全是合格品,那么必须从 该批中 N-M 个合格品中抽取,这有 种取法。故事件 A0 的概率为: 事件 A1="恰好有 1 个不合格品" , 要使取出的 n 个产品只有一个不合格品 , 其他 n-1 个是合格品 , 可分二步来实现。第一步从 M 个不合格品中随机取出 1 个,共有 种取法;第二步从 N-M 个合格品中随机取 出 n-1 个,共有 种取法。依据乘法原则,事件 A1 共含有 个样本点。故事件 A1 的概率为: 最后,事件 Am 发生,必须从 M 个不合格品中随机抽取 m 个,而从 N-M 个合格品中随机抽取 n-m 个,依据乘法原则,事件 Am 共含有 个样本点,故事件 Am 的概率是:来源:考试大 其中 r=min(n,M)为 n, M 中的较小的一个数,它是 m 的最大取值,这是因为 m 既不可能超过取 出的产品数 n, 也不可能超过不合格品总数 M,因此 。 假如 N=10.M=2 和 n=4,下面来计算诸事件 Am 的概率:来源:www.examda.com 而 A3,A4 等都是不可能事件,因为 10 个产品中只有 2 个不合格品,而要从中抽出 3 个或 4 个 不合格品是不可能的,因而 P(A3)=P(A4)=0 。来源:www.examda.com 三、排列组合的解题方法 排列组合是计数问题,从解法上看,大致有以下几种: (1)有附加条件的排列组合问题,大多需用分类讨论的方法; (2)排列与组合的混合型问题,需分步骤,要用乘法原理解决; (3)不相邻问题插空法,相邻问题捆绑法; (4)排除法,将不符合条件的排列或组合剔除掉; (5)枚举法,将符合条件的所有排列或组合一一写出来,或写出一部分发现规律; (6)定序问题―无序化‖,即若某几个元素必须保持一定的顺序,则可按通常排列后再除以这几个元素的 排列数; (7)隔板法,例如:10 个相同的小球分给三人,每人至少 1 个,有多少种方法?可将 10 个球排成一 排,再用 2 块―隔板‖将它们分成三个部分,有种方法。 整个解题过程遵循的基本原则是:―特殊对象优先考虑‖、先―分类‖后―分步‖、先―取‖后―排‖等原则。 突出分类相加,分步相乘;有序排列,无序组合; 除了上述方法外,有时还可以通过设未知数,借助方程来解答,简单一些的问题可采用列举法等。 解此类题常用的数学思想是:分类讨论的思想,转化思想和对称思想等三种。排列组合是高中数学的重点 和难点之一,也是进一步学习概率的基础。事实上,许多概率问题也可归结为排列组合问题。这一类问题 不仅内容抽象,解法灵活,而且解题过程极易出现―重复‖和―遗漏‖的错误,这些错误甚至不容易检查出来, 所以解题时要注意不断积累经验,总结解题规律,掌握若干技巧,最终达到能够灵活运用。 C 语言程序设计

第一章 概述 1.程序设计语言:机器语言、汇编语言、高级语言。 2.高级语言翻译成机器语言的两种方式:编译方式、解释方式。 3.算法+数据结构=程序 4.结构化程序设计的三种基本结构:顺序结构、分支(选择)结构、循环结构 5.算法的表示方法:自然语言、传统的程序流程图、N-S 流程图。 6.C 语言由函数组成,有且仅有一个 main 函数。 7.函数:说明部分、函数体。 8.一条复杂语句分行书写,用反斜杠(\)续行。 9.注释用/*……*/ 第二章 基本输入输出语句 1.单字符输入/出:getchar()、putchar(字符变量)。 2.字符串:gets(字符数组名)、puts(数组名)。 3..格式化输入: scanf(―格式控制符‖,地址列表); 格式控制符:%c、 %d 、 %o 、 %x、 %s、 %f 若输入 long 型、double 型应加 l,如%ld、 %lo、 %lf 格式%s 输入字符串不包含空格,且对应地址表列是字符数组名。 默认分隔符:空格、回车、Tab 键(也可按域宽截取) 格式控制符间不宜加其它字符,如加入其它字符,输入时应原样输入,否则数据接收错误。如: scanf(―%d, %d‖,&a,&b); 输入数据时两数据间要有逗号;scanf(―%d %d‖,&a,&b); %d 间有两个空格, 则输入数据时至少有两个空格。 输入函数中%f 格式不能带小数,如:scanf(―%7.2f‖,&a)是错误的。 %c 格式输入单字符,空格字符和转义字符都作为有效字符接收。 %*d 表示跳过它对应的输入数据。 4..格式化输出:printf(―格式控制符‖,输出列表); 格式控制符部分可加入其它字符,原样输出。如:提示语或使输出结果清楚显示 输出列表:可以是变量、常量、表达式、函数调用等。 转义字符:以斜杠(\)开始,作为一个字符,如求字符串长度:―jk\\gk\bl\0k\nlj‖,长度为 7。 注意:输出 long 、double 型数据,用%ld、%lf 可设定输出宽度,m 和 n,如:%5d、%6.2f、%.2f 负号表示域内向左对齐,如:%-12d

第三章 数据类型 1.常量: 整型常量:235、0235、-0x235(前可加负号),长整型:-12l、-065l、0x55l 等。 实型常量:小数形式、指数形式。 字符常量:用单引号,如?c‘(注意转义字符)。 字符串常量:用双引号,如―hglhg‖、―a‖,内存占用为实际长度加 1。 符号常量:无参宏(#define)。 2.变量: 标识符命名规则:4 条。 各种类型变量的长度。 数据类型转换:自动、强制。 注:强制类型转换只得到所需类型的结果值,原变量或表达式的类型仍为原类型。如(float)(x+y) 3.各种运算符运算规则及其优先级。 4.补充---逻辑表达式的优化运算: &&运算:只要算出第一个表达式为 0,第二个表达式不再运算。 ||运算:只要算出第一个表达式为 1,第二个表达式不再运算。 如:int i=0,j=0,a=6; if ((++i>0)||(++j>0)) a++; a 为 7。 5.其它运算符:条件运算、逗号运算、长度运算符(形式:sizeof 第四章 控制语句 1.if、while、for 中的表达式,一般是逻辑或关系表达式,也可以是任意类型表达式。如 while(a=5)…. 2.如果有多条语句,必须用大括号括起,构成复合语句。 3.switch 语句中 case 后面只能是常量值;若执行完某 case 后的语句没遇到 break,则继续执行下一 个 case 语句。 4.循环程序:注意循环变量的初值、修正值、循环条件等,以及循环中用到的某些变量赋初值,如求 累加和变量。 5.一般是先判断条件,再执行循环体;但 do—while 语句是先执行一遍循环体,再判断条件。 6.break、continue 语句。 7.本章主要是算法构思。(先考虑好需要那些变量,即数据结构,再考虑怎样求解问题) 第五章 数组 1.数组定义:int a[10];或 int a[N](N 需要事先定义为符号常量:#define N 10 ); 表达式 或 sizeof (数据类型)) printf(%d%d%d‖,i,j,a); 结果 i 为 1,j 为 0,

数组长度必须是常量值,不能是变量,可以是在程序开始前定义的符号常量,进行长度定义。 2.下标引用:0~N-1,切记不能引用到 N。(int a[5]; a[5]=10;这种引用是错误的) 3.数组初始化时可省略长度定义。 4.数组定义后如没有给任何一个元素赋初值,对于 static 类型,各元素初值为 0;对于 auto 类型,各 元素值不定。 5.数组不能整体赋值。数组中各元素值的输入/出,应使用循环程序逐个输入/出;字符数组例外 (gets、 puts)。 6.数组中的两种排序方法: 冒泡法:外循环为 i=0;i<n-1;内循环为 j=0;j<n-1-i;循环中比较 a[j]和 a[j+1]两个元素,并互换。 选择法:外循环为 i=0;i<n-1;内循环为 j=i;j<n;内循环开始前,先赋初值 min=i;循环中比较 a[min] 和 a[j]两个元素,不互换,只让 min=j;内循环结束后再进行互换, a[i]和 a[min]互换。 7.二维数组:按行存放;赋初值的 5 种情况 P83 页。 8.字符数组:通常定义较长长度,如:char s[50]; 通常用于存放字符串,结束标志为?\0‘。 可用字符串常量为其初始化,如:char s[]=―sdkhg‖; 也可由键盘输入,如 gets(s);输出用 puts(s); 注意:char s[5]={?a‘,‘d‘,‘f‘,‘g‘,‘w‘};此种形式不是字符串,无字符串结束标志,仅仅是普通一维字符 数组,不能用 puts 输出,只能用%c 格式逐个输出。 字符数组的输入/出还有两种形式:%c、%s。 9.字符串函数:strcpy(s1,s2)、 strcat(s1,s2)、 strcmp(s1,s2)、 strclen(s)、 strupr(s)、 strlwr(s) 第六章 函数 1.函数定义:int func(int a,int y);如定义时没指明函数类型,如:fun(int a);默认是 int 型,返回 值不确定。 2.声明:函数定义在前,使用在后,可省略函数声明,反之需要在使用前声明。函数声明的几种变通 形式。 函数声明后加分号,而函数定义后没有分号。 3.函数调用:函数名(实参表); 实参与形参个数、类型、位置一致。 形参与实参占据不同的存储单元;形参只在函数调用时才为其分配存储单元,函数调用结束后释放。 实参与形参之间是传值调用,单向传递关系,形参值改变,不会影响实参值。 补充:函数可嵌套调用,不可嵌套定义。 嵌套调用:一个函数内部又调用另外一个函数。 递归调用:一个函数调用它自身。(考试不作要求) 4.数组作为函数参数:void func(int a[],int n);

传递的是实参数组的首地址。调用时实参是数组名,如 func(a,10); 5.多维数组: void func(int a[][5],int n);(可省略第一维,但不能省略其它高维)。 6.从作用域角度,变量分为:全局变量、局部变量。 局部变量:在函数内部定义,只能在该函数中使用,包括函数的形参和复合语句中定义的变量,main 函数中定义的变量也是局部变量,不能被其它函数使用。 不同函数内定义的同名变量,互不影响,因其作用域不同,内存空间独立。 全局变量:在函数外部定义,作用域从定义开始到本文件结束。其间的所有函数都可以使用它,可 在各函数间传递值,但容易带来副作用,降低模块独立性。 7.变量的存储类别:auto、static、register、extern。 8.局部变量的存储类别: auto、static、register。 auto 型的生存周期时函数被调期间,两次调用之间不保留值。

void func(int n) { static int a=1; a+=n; printf(―%d,‖,a); } main() { int b=2; func(b); func(b); } 程序运行结果为 3,5,

static 型的生存期是整个程序运行期间,保留上一次调用后的值,且只赋一次初值(在程序运行前初始化, 默认初值为 0)。 9.全局变量的存储类别: static、extern。 全局变量总是存放在静态存储区间,生存期是整个程序运行期间,只赋一次初值,在程序运行前初 始化,默认初值为 0。 用 extern 对全局变量加以声明,可以将其作用域扩充到整个文件或其它文件。 定义全局变量时加上 static,可将其作用域限制在本文件中,不能被其它文件使用。

10.函数的作用域是全局的,可被其它函数调用。 函数存储类别:static、extern。默认为 extern 型。

#define SQR(x) x*x main( ) { int a,k=3; a=++SQR(k+1); printf("%d\n",a); } 替换后的表达是为 a=++k+1*k+1 结果为 9

如:static int func(int a);则函数不被其它文件使用,所以两文件中的同名静态函数,互不干扰。 第七章 预处理与宏命令 1.预处理命令以―#‖开头,末尾不加分号。在程序编译之前处理。 2.宏替换:将函数中出现宏名的地方用宏体进行替换。 宏体可以是数字、也可以是组成 C 表达式或语句的其它字符,还可以引用已定义的其它宏名。 宏的作用域:定义宏之后到本源文件结束,可用#undef 提前结束。 无参宏(符号常量):#define PI 3.14

注意:函数中双引号内的宏名不替换,如 printf(―PI‖); 有参宏:#define 宏名(形参表) 引用:宏名(实参表) 注意有参宏如果宏体和参数没用括号括起,可能有副作用。 分析有参宏的程序时,必须先将宏替换后的表达式写到纸上,再分析结果。 文件包含:#include <文件名> 搜索系统标准目录 #include ―文件名‖ 先搜索当前目录, 找不到再搜索系统标准目录 第七章 文件 1.流式文件:文本文件、二进制文件。 文本文件:若干字符序列,较长,可用 type 命令或记事本查看。 二进制文件:若干字节序列,短,存取速度快,不能用 type 或记事本等查看。 2.文件操作:读操作、写操作。使用有关文件函数来完成,需包含头文件 stdio.h 宏体

3.操作步骤: ①定义文件类型指针 ②打开文件 ③检测指针 ④读/写 4.打开文件时的使用方式各 6 种。

⑤关闭文件。

5.读/写函数:fgetc(fp)、fputc(ch,fp)、fread(*p,size,n,fp)、 fwrite(*p,size,n,fp)、fgets(*str,n,fp)、 fputs(*str,fp) fscanf(fp, ―格式控制符‖ ,地址列表)、fprintf(fp, ―格式控制符‖ ,输出列表),以上函数是简要书写. 6.三个标准设备文件指针:stdin、stdout、stderr 7.有关文件操作函数 ferror(fp)、feof(fp)、clearerr(fp); 8.控制循环:while((ch=fgetc(fp)) !=EOF) 或 while(!feof(fp)) EOF 是在头文件中定义的符号常量,值为-1 代表文件结束。


全国青少年信息学奥林匹克联赛初赛讲义

全国青少年信息学奥林匹克联赛初赛讲义_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛讲义全国青少年信息学奥林匹克联赛初赛复习讲义 2011-09-14 12:04...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲_学科竞赛_高中教育_教育专区。全国青少年信息学...四、试题形式 每次联赛的试题分四组:普及组初赛题 A1、普级组复赛题 A2、...

noip2015第二十一届全国青少年信息学奥林匹克联赛初赛

第二十一届全国青少年信息学奥林匹克联赛初赛 普及组 Pasca1 语 言试题竞赛时间 2015 年 10 月 11 日 14:30~16:30 选手注意: ●试题纸共有 7 页,答题纸...

18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)

第十八届全国青少年信息学奥林匹克联赛初赛 (普及组 Pascal 语言试题) 竞赛时间:2012 年 10 月 13 日 14:30~16:30 选手注意 · 试题纸共有 10 页,答题纸...

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言试题

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言...

全国青少年信息学奥林匹克联赛初赛试题2009-2015

第十五届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 单项...

第二十一届全国青少年信息学奥林匹克联赛初赛

第二十一届全国青少年信息学奥林匹克联赛初赛 普及组 Pasca1 语 言试题竞赛时间 2015 年 10 月 11 日 14:30~16:30 选手注意: ●试题纸共有 7 页,答题纸...

全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案

全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档全国青少年信息学奥林匹克联赛初赛练习卷(八)...

第十七届全国青少年信息学奥林匹克联赛初赛试题

第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组●● Pascal 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、 单项...

2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)

2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)_学科竞赛_高中教育_教育专区。2015 年第二十一届全国青少年信息学 奥林匹克竞赛初赛 提高组一...