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

信息学奥赛基础知识


Pascal 教程
1. 计算机基础知识
1.1 数制及其转换
第一章 计算机基础知识 第一节 数制及其转换
一、二、八、十六进制转十进制的方法:乘权相加法。 十六进制转十进制的方法:乘权相加法。

例如: (11010110)2 = 1×2 + 1×2 + 0×2 + 1×2 + 0×2 + 1×2 + 1×2 + 0

×2 = (214)10 (2365)8 = 2×8 + 3×8 + 6×8 + 5×8 = (1269)10 (4BF)16 = 4×16 + 11×16 + 15×16 = (1215)10
2 1 0 3 2 1 0 7 6 5 4 3 2 1 0

带小数的情况: (110.011)2 = 1×2 + 1×2 + 1×2 + 0×2 + 1×2 + 1×2 (5.76)8 = 5×8 + 7×8 + 6×8
0 -1 0 -1 -2 2 1 0 -1 -2 -3

= (6.375)10

= (5.96875)10
-2

(D.1C)16 = 13×16 + 1×16 + 12*16

= (13.109375)10

二、十进制化二进制的方法:整数部分除二取余法,小数部分乘二取整法。 十进制化二进制的方法:整数部分除二取余法,小数部分乘二取整法。

例一:(43) 101011) 例一:(43)10 = (101011)2 :(43

例二:(0.375) 0.011) 例二:(0.375)10 = (0.011)2 :(0.375

三、二进制转八进制的方法

1 位数八进制与二进制对应表

八进制 二进制

0 1 2 3 4 5 6 7

000 001 010 011 100 101 110 111

转换方法:对二进制以小数点为分隔,往前往后每三位划为一组,不足三位补 0,按上表用对应 的八进制数字代入即可。

例如:(10111011.01100111) = 010,111,011.011,001,110 = (273.36)8

三、二进制转十六进制的方法

1 位数十六进制与二进制对应表

十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F

二进制 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

转换方法:对二进制以小数点为分隔,往前往后每四位划为一组,不足四位补 0,按上表用对应 的十六进制数字代入即可。

例如:(10111011.01100111) = 1011,1011.0110,0111 = (BB.67)16

四、进制的英文表示法: 进制的英文表示法: 以上都是用括号加数字的表示方法,另外还有英文表示法,就是以 BIN、OCT、HEX、DEC 分 别代表二、八、十六、十进制。或者只写第一个字母。例如 1101B 表示是二进制。有些地方为了 避免“O”跟“0”混淆,把 O 写成 Q。

1.2 算术运算和逻辑运算 第二节 算术运算和逻辑运算
一、二进制的算术运算

1、加法运算规则: 0+0=0 0+1=1 1+0=1 1+1=10

2、减法运算规则: 0-0=0 0-1=1(向高位借 1) 1-0=1 1-1=0

3、乘法运算规则: 0×0=0 0×1=0 1×0=0 1×1=1

二、逻辑运算

1、基本运算 ① 逻辑乘,也称“与”运算,运算符为“·”或“∧” 0·0=0 0·1=0 1·0=0 1·1=1

使用逻辑变量时,A·B 可以写成 AB ② 逻辑加,也乘“或”运算,运算符为“+”或“∨”

0+0=0

0+1=1

1+0=1 1+1=1

③ 逻辑非,也称“反”运算,运算符是在逻辑值或变量符号上加“—” 0 = 1 1 = 0

2、常用运算 异或运算:A⊕B = A·B+A·B

2、基本公式

① 0,1 律 A·0=0 A·1=A A+0=A A+1=1

② 交换律 A+B=B+A A·B=B·A

③ 结合律 A+B+C =(A+B)+C = A+(B+C) A·B·C =(A·B)·C = A·(B·C)

④ 分配律 A·(B+C)= A·B + A·C

⑤ 重叠律 A+A+...+A = A A·A·...·A = A

⑥ 互补律 A + A = 1 A·A = 0

⑦ 吸收律 A+A·B = A A+A·B = A+B A·(A+B) = A A·(A+B) = A·B

⑧ 对合律 对一个逻辑变量两次取反仍是它本身

⑨ 德·摩根定理 A+B = A·B A·B = A+B

三、逻辑代数的应用 1、逻辑表达式化简 例如:

F = A·B+A·B+A·B =A·B+A(B+B) =A·B+A = A+B
(利用分配律) (利用互补律以及 0,1 律) (利用吸收律)

2、对指定位进行运算,假设变量 A 有八位,内容是 d7d6d5d4d3d2d1d0 ① 将变量 A 的 d5 位清零 A·(11011111)→A ② 将变量 A 的各位置 1 A+(11111111)→A

1.3 原码、反码和补码 原码、 第三节 原码、反码和补码

计算机中参与运算的数有正负之分, 计算机中的数的正负号也是用二进制表示的。 用二进制 数表示符号的数称为机器码。常用的机器码有原码、反码和补码。

一、原码

求原码的方法:设 X;若 X≥0,则符号位(原码最高位)为 0,X 其余各位取值照抄;若 X≤0, 则符号位为 1,其余各位照抄。 【例 1】X=+1001001 【例 2】X=-1001001 [X]原 = 01001001 [X]原 = 11001001

二、反码

求反码的方法:设 X;若 X≥0,则符号位(原码最高位)为 0,X 其余各位取值照抄;若 X≤0, 则符号位为 1,其余各位按位取反。 【例 3】X=+1001001 【例 4】X=-1001001 [X]反 = 01001001 [X]反 = 10110110

三、补码

求补码的方法:设 X;若 X≥0,则符号位(原码最高位)为 0,X 其余各位取值照抄;若 X≤0, 则符号位为 1,其余各位按位取反后,最低位加 1。 【例 5】X=+1001001 【例 6】X=-1001001 [X]补 = 01001001 [X]补 = 10110111

四、补码加减法 计算机中实际上只有加法,减法运算转换成加法运算进行,乘法运算转换成加法运算进行, 除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。

1、补码加法 [X+Y]补 = [X]补 + [Y]补 【例 7】X=+0110011,Y=-0101001,求[X+Y]补 [X]补=00110011 [Y]补=11010111

[X+Y]补 = [X]补 + [Y]补 = 00110011+11010111=00001010

注:因为计算机中运算器的位长是固定的,上述运算中产生的最高位进位将丢掉,所以结果 不是 100001010,而是 00001010。

2、补码减法 [X-Y]补 = [X]补 - [Y]补 = [X]补 + [-Y]补 其中[-Y]补称为负补, 求负补的方法是: 对补码的每一位 (包括符号位) 求反, 最后末位加“1”。 【例 8】X=+0111001,Y=+1001101,求[X-Y]补 [X]补=00111001 [Y]补=01001101 [-Y]补 = 10110011

[X-Y]补 = [X]补 + [-Y]补 = 00111001+10110011=11101100

五、数的表示范围 通过上面的学习, 我们就可以知道计算机如果用一个字节表示一个整数的时候, 如果是无符 号数,可以表示 0~255 共 256 个数(00000000~11111111),如果是有符号数则能表示-128~127 共 256 个数(10000000~01111111)。如果两个字节表示一个整数,则共有 65536 个数可以表示, 大部分程序设计语言中整数的范围都是-32768~32767 的原因, 可以看出这种整数类型是 16 位的 有符号数,而且是补码表示的。

1.4 浮点数的表示方法
第四节 浮点数的表示方法
一、浮点数表示

一个数的浮点形式(设基数是 2)可写成: N = M × 2
E

其中:M 代表尾数,E 代表阶码。

计算机中浮点数只用尾数和阶码表示,其形式如下:

阶码

尾数符号

尾数

浮点数的精度由尾数决定,数的表示范围由阶码的位数决定。

为了最大限度提高精度,尾数采用规格化形式,既 1/2≤M<1。采用二进制表示时,若尾数 大于零,则规格化数应该是 01XXXX 的形式;若尾数小于零,则规格化数应为 10XXXX 的形式。

二、机器零

当浮点数的尾数为 0 或阶码为最小值时, 计算机通常把该数当作零, 因此程序中进行浮点运 算时,判断某数是否为零,通常可以用小于某个极小值来代替。

三、实例

【例 1】设 X=0.0110×2 ,用补码、浮点数形式表示阶码为 Xj=011,尾数为 00110,这时由于 X 尾数不符合 01XXXX 的形式,因此不是规格化数,必须先进行规格化处理。 方法:若尾数小于 1/2,把尾数左移一位(不包括符号位),观察结果是否满足规格化条件,满 足则在把阶码减 1 即可,否则继续左移和调整阶码;若尾数大于 1,则把尾数右移一位(不包括 符号位) 观察结果是否满足规格化条件, , 满足则在把阶码加 1 即可, 否则继续右移和调整阶码。 上例中,00110 左移一位为 01100,符合规则化标准,此时阶码减 1,为 010 即得到浮点表示形 式。 这个数具体在计算机中如何表示要看计算机中规定的阶码和尾数的位数, 若阶码和尾数均为 16 位,则上面的数 X 在计算机内部表示就是 00000000000000100110000000000000 ,不足均用 零填充。

3

1.5 奇偶校验
第五节 奇偶校验
计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误,在 数据传输(存储)过程中要进行校验,常用的校验方法就是奇偶校验。 奇偶校验能发现一位或奇数位错误,且不能纠正错误。一般以字节(八位二进制)为单位加 1 位奇偶校验位。奇偶校验分奇校验和偶校验两种。

一、奇校验:一个字节前面加一位校验位使得“1”的个数保持为奇数,若八位二进制数中“1” 的个数为偶数,则校验位为“1”;若八位二进制数中“1”的个数为奇数,则校验位为“0”。 【例 1】给 1001100101101101 加奇校验结果为 110011001001101101

二、偶校验:一个字节前面加一位校验位使得“1”的个数保持为偶数,若八位二进制数中“1” 的个数为偶数,则校验位为“0”;若八位二进制数中“1”的个数为奇数,则校验位为“1”。 【例 2】给 1001100101101101 加偶校验结果为 010011001101101101

1.6ASCII 码表
第六节 ASCII 码表
代码 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ! ” # $ % & ’ ( ) * + , . / 字符 代码 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 > ? @ A B C < = 字符 4 5 6 7 8 9 : ; 代码 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 字符 H I J K L M N O P Q R S T U V W 代码 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 字符 \ ] ^ _ ` a b c d e f g h i j k 代码 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 字符 p q r s t u v w x y z { | } ~

48 49 50 51

0 1 2 3

68 69 70 71

D E F G

88 89 90 91

X Y Z [

108 109 110 111

l m n o

目前使用最广泛的西文字符集及其编码是 ASCII 字符集和 ASCII 码 ASCII 是 American ( Standard Code for Information Interchange 的缩写),它同时也被国际标准化组织 ( International Organization for Standardization, ISO )批准为国际标准。

基本的 ASCII 字符集共有 128 个字符, 其中有 96 个可打印字符, 包括常用的字母、 数字、 标点符号等,另外还有 32 个控制字符。标准 ASCII 码使用 7 个二进位对字符进行编码,对应 的 ISO 标准为 ISO646 标准。下表展示了基本 ASCII 字符集及其编码:

字母和数字的 ASCII 码的记忆是非常简单的。 我们只要记住了一个字母或数字的 ASCII 码 (例如记住 A 为 65 , 0 的 ASCII 码为 48 ),知道相应的大小写字母之间差 32 ,就可以 推算出其余字母、数字的 ASCII 码。

虽然标准 ASCII 码是 7 位编码,但由于计算机基本处理单位为字节( 1byte = 8bit ), 所以一般仍以一个字节来存放一个 ASCII 字符。每一个字节中多余出来的一位(最高位)在计 算机内部通常保持为 0 (在数据传输时可用作奇偶校验位)。

由于标准 ASCII 字符集字符数目有限,在实际应用中往往无法满足要求。为此,国际标准 化组织又制定了 ISO2022 标准, 它规定了在保持与 ISO646 兼容的前提下将 ASCII 字符集扩充 为 8 位代码的统一方法。 ISO 陆续制定了一批适用于不同地区的扩充 ASCII 字符集,每种扩 充 ASCII 字符集分别可以扩充 128 个字符,这些扩充字符的编码均为高位为 1 的 8 位代码 (即十进制数 128~255 ),称为扩展 ASCII 码。下表展示的是最流行的一套扩展 ASCII 字符 集和编码:

2.计算机硬件基础知识 计算机硬件基础知识
2.1 中央处理器
第二章 计算机硬件基础 第一节 中央处理器
一、中央处理器的组成 中央处理器简称 CPU,由控制器、运算器组成。

运算器及控制器的基本功能: 运算器是计算机进行算术和逻辑运算的部件, 控制器是整个计 算机中统一指挥和控制计算机各部件进行工作的控制中心。

二、运算器 运算器是负责对数据进行算术运算或逻辑运算的部件。运算器由算术逻辑单元(ALU)、累 加器、状态寄存器、通用寄存器组等组成。如图:

算术逻辑运算单元、累加器和通用寄存器的位数决定了 CPU 的字长。

三、控制器 是计算机的指令执行部件,其工作是取指令、解释指令以及完成指令的执行。 控制器由指令指针寄存器、指令寄存器、控制逻辑电路和时钟控制电路等组成。 指令指针寄存器(IP)用于 产生及存放一条待取指令的地址。

指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。

四、寄存器 寄存器数量增多可以提高 CPU 运行速度, 但是不能太多, 太多会使地址编码和指令长度变长, 增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等 组成。

五、指令基本格式 单目运算:操作码 地址码 二目运算:操作码 第一地址 第二地址

六、寻址方式:CPU 执行指令时寻找数据地址的方式 寻址方式: 1、立即寻址:ADD AH,78 其中 ADD 是操作码,表示做加法;AH 是寄存器名;78 是个常数;

该指令的意思是寄存器 AH 的值加上 78。 2、直接寻址:ADD AH,(78) 3、间接寻址:ADD AH,((78)) 4、相对寻址:ADD AH,*78 78 表示操作数的地址 78 表示操作数地址的地址 *78 表示本指令地址+78,78 称偏移量

5、变址寻址:ADD AH,(DI+78) DI 是变址寄存器,存放一个地址,操作数地址是寄存器地址+78

6、寄存器直接寻址:ADD AH,78 7、寄存器直接寻址:ADD AH,(BX)

AH 是一个寄存器名,即寄存器直接寻址 BX 是一个寄存器名,存放操作数的地址

七、指令分类 1、数据传送指令:MOV AH,BH IN AH,378 2、数据处理指令:算术运算、逻辑运算、移位、比较等 3、程序控制指令:转移、调用、返回 4、状态管理指令:中断、屏蔽中断

八、指令的执行过程 1、CPU 发出指令地址 2、读取指令 3、指令送指令寄存器 4、指令译码 5、按指令操作码执行 6、形成下条要执行的指令的地址

九、时钟周期 一个指令执行的时间称为指令周期 计算机完成一个操作(如读取指令等)所需时间称为总线周期 计算机中最基本的时间单位是时钟周期,有 CPU 的主频决定。

2.2 存储系统
第二节 存储器系统
一、存储器的分类

分类方法

名称

举例

半导体存储器 按存储介质 分 磁表面存储器 光存储器 随机存储器 按工作方式 分 只读存储器 顺序存储器

ROM、RAM(内存) 、闪存(优盘) 硬盘、软盘、磁带 CD-ROM、DVD-ROM RAM(内存) 、硬盘、软盘 ROM、CD-ROM 磁带

二、多层次存储体系:如图 多层次存储体系:

三、主存储器 1、特点:容量小、读写速度快、价格高 2、编址方式:存储容量与地址线条数相对应,64M 的存储器至少需要 26 跟地址线(2 =64M) 注:我们目前的计算机大都是 32 位,也就是地址线条数有 32 条,所以其支持的最大内存容 量为 4G 3、分类: ① 随机存储器(RAM):就是我们通常称的内存,主要参数是存储容量和工作频率。 例如:一条 64M×8 的内存条表示该内存条有 64M 个单元,每个单元 8 位。 ② 只读存储器(ROM):只能读不能写,一般用于存放计算机启动所需的最基本程序。 ③ 缓冲存储器(Cache):速度最快,一般集成于 CPU 中。
26

四、辅助存储器 1、磁带:顺序存储,一般只用在小型机以上的计算机中,用作数据备份。 2、软盘:目前常见的一般为 3.5 寸高密盘,容量为 1.44MB,软盘结构如图

注意:盘面最外层的磁道称为 0 磁道,0 磁道如果损坏,则盘片报废。 3、硬盘:硬盘由多个盘面组成一个柱形结构,其原来跟软盘类似,但是磁道更多。 4、光盘:利用光信号读取或写入的存储器。 ① CD-ROM:只读,容量 650MB 左右,一倍速为 150KB/s ② DVD-ROM:只读,容量 4.7GB 左右,一倍速为 1200KB/s ③ CD-RW、DVD-RW:可擦写的光盘,但必须专门的刻录机。

2.3 输入输出系统
第三节 输入输出系统
一、输入输出控制方式 1、程序查询方式:软件实现,效率低 2、中断方式:软硬件结合实现 中断请求-->中断响应-->中断处理-->中断返回 3、直接存储器访问方式(DMA):硬件实现 DMA 请求-->CPU 响应并把总线控制权交给 DMA 控制器-->数据交换-->交还总线控制权

二、系统总线 分类:数据总线、地址总线、控制总线 总线标准:ISA 总线、PCI 局部总线、MCA 总线

三、I/O 接口 1、显卡:分辨率、颜色数决定显示效果和所需显存 例如:显示分辨率为 1280×1024 的 32 位真彩色,所需显卡显存最少为 1280×1024×32÷8 = 5MB 2、硬盘接口: ① IDE、EIDE ② Ultra DMA ③ SCSI ④ SATA 3、串行口 4、并行口:通常接针式打印机 5、USB 接口:通用串行总线

四、显示器的有关知识 1、屏幕尺寸:15 寸、17 寸、19 寸等 2、点间距:屏幕上象素与象素之间的距离,决定了显示器能显示的最大分辨率。 越小表示 能显示的最大分辨率越大。

五、打印机:针式打印机、喷墨打印机、激光打印机。 打印机 激光打印机速度最快,针式打印机可以打印票据。

3.计算机网络知识 计算机网络知识
3.1 网络的组成与基本结构
第三章 网络基础知识

第一节 网络的组成与结构
一、网络组成
1、通信主体:服务器和工作站 2、通信设备:传输介质、网络设备 3、通信协议:通常是 TCP/IP 二、网络分类 按传输距离分:局域网(LAN)、城域网(MAN)、广域网(WAN) 按网络结构分:总线型、星型、环型、树型

三、网络拓扑结构

3.2 网络协议

第二节 网络协议
一、OSI 网络协议的层次 国际标准化组织 (ISO) 提出的“开放系统互连模型 (OSI) ”是计算机网络通信的基本协议。 该协议分为七层。如下表

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层

二、网络设备极其作用

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层 中继 器

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层

应用层 表达层 会话层 传输层 网络层 数据链路层 网桥 物理层

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层 路由 器

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层 网关

应用层 表达层 会话层 传输层 网络层 数据链路层 物理层

3.3 INTERNET 相关知识
第三节 Internet 相关知识
一、IP 地址 每台与 Internet 连接的主机都必须有一个 IP 地址,IP 地址采用分段式表示:共分 4 段, 每段用一个字节即八个二进制位表示,实际的 IP 把二进制转换成十进制书写。如 61.153.238.132,因为每段时一个字节,因此 IP 每段的数字大小最大为 255。 IP 地址分类如下表: 目前 32 位 IP 地址资源几近枯竭, 有人提出用 48 位表示 IP, IPV6 。 即

分 类 A类 0 七位网络 地址 14 位网络地址

二进制表示

十进制表示第一段数 字

24 位主机地址 16 位主机地址

<128

B 类 10

128~191

C 类 110

21 位网络地址

8 位主机地址

192~223

二、域名:Internet 的域名系统叫做 DNS,DNS 是树形结构的。 域名跟 IP 地址是多对一的关系 域名 1、域名分级系统:一个域名最右边的部分通常叫顶级域名,往前依次为二级域名、三级域 名等。 2、我国域名管理机构:CNNIC 3、常见域名含义: gov 政府 edu 教育 int 国际组织 com 商业组织 mil 军事部门 net 网络运行 组织 cn 中国 hk 香港 tw 台湾 uk 英国 jp 日本 org 其他

三、一些常见名词解释 1、Intranet:企业内部网 2、ISP(Internet Service Provider):因特网服务供应商 3、ICP(Internet Content Provider):因特网内容供应商 4、IAP(Internet Acess Provider):因特网接入供应商,目前一般都被 ISP 包含 5、BBS:电子公告栏,目前通常叫论坛

四、接入 Internet 的方法 1、PSTN 拨号接入:必须设备 MODEM,电话线,速度慢 2、DDN 专线接入:速度快,费用高。 3、ISDN 专线接入:利用传统电话网络的综合业务数字网。 4、分组交换接入 5、帧中继接入

4.其他相关基础知识 其他相关基础知识
4.1 计算机病毒
第四章 其他相关基础知识

第一节 计算机病毒
一、特点 寄生性、隐蔽性、非法性、传染性、破坏性

二、分类: 分类 1、引导型病毒:寄生在系统引导区,比较容易被清除,现在已经很少见。 2、文件型病毒:寄生在可执行文件中,感染速度快,较易清除。 3、目录型病毒:寄生在系统目录结构中 4、混合型病毒:多种类型的混合 5、宏病毒:专门感染 Microsoft Office 系列文件的病毒 6、蠕虫病毒:感染网络,使网速大大降低。 目前流行的病毒大多集成了黑客技术、 木马技术和病毒技术三种, 非常难以清除而且很容易 中。

三、一些常见危害较大的病毒 一些常见危害较大的病毒 1、CIH 病毒:文件型病毒,4 月 26 日发作时破坏性最大,首个能破坏硬件系统的病毒。 2、Melissa 病毒:宏病毒,邮件传播 3、冲击波、震荡波病毒:利用 WINDOWS 的漏洞,使计算机自动重启并堵塞网络。

4.2 数据库系统
第二节 数据库系统
一、数据库是数据的一种组织形式,目前存储大量数据基本都采用数据库 数据库是数据的一种组织形式, 常见的数据库软件有:FoxBase、FoxPro、Access、Sql Server、MySql、Sybase、Oracel 等。 除了最早的如 FoxBase 等软件,目前流行的数据库软件都是关系型数据库。

二、数据库数据结构 数据库系统的数据结构可以认为是多张二维表,二维表中的列称为字段,行存放数据。如下 图

二、数据操作 用以对数据库进行检索和更新(添加、删除、更新等)操作

三、数据的完整性约束条件 多个表之间的数据可能存在相互关联,必须保证其完整性

四、数据库操作语言 SQL 数据库操作语言 数据库常用的操作语言称为 SQL 语言, 是一种更高级化的语言, 只须告诉计算机做什么事情 即可。下面例举几条常用的语句。 1、SELECT 语句 语法:select <列名> from <表名> where <条件> 功能:从表中选出满足条件的记录列

2、INSERT 语句 语法:insert into <表名>[(列名表)] values(<值表>) 功能:在表中插入一条新记录。

3、DELETE 语句 语法:delete * from <表名> where <条件> 功能:删除满足条件的记录

4、UPDATE 语句 语法:update <表名> set <列名>=<值> where <条件>

功能:修改满足条件的表中某记录某字段的值

5.数据结构之线性结构 数据结构之线性结构
5.1 线性表
第一节 线性表
一、概念 线性表是指由有限个类型相同的数据元素组成的集合,它有以下的特点: 1.有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素); 2.除结点外,集合中的每个数据元素均只有一个前驱; 3.除尾结点外,集合中的每一个数据元素均只有一个后继。

二、线性表的存储结构 1、顺序结构:是通过数组说明分配连续地址的存储区,通过下标引用数组的相应元素。 2、链式结构:通过指引元素类型的变量对线性表中元素进行动态分配存储。

三、顺序存储结构 1、一维数组 ① 数组存储的结构在数组声明时就需要事先分配相应的连续内存空间用来存放数据。 ② 按首地址(表中第一个元素的地址)的位移来访问数组每一个元素的。 若第一个元素的地址是 a, 每个元素占用的存储空间为 L, 则数组的第 i 个元素的地址可以用 如下公式计算:

d(i)=a+(i-1)*L
2、二维数组 ① 定义方法:<数组名>:array[1..n,1..m] of <元素类型> ② 对于行为 n,列为 m 的二维数组的元素访问方法: 若第一个元素的地址是 a,每个元素占 用的存储空间为 L,则数组的第(i,j)个元素的地址可以用如下公式计算:

按行寻址:d(i,j)=a+(i-1)*m*L+(j-1)*L 按列寻址:d(i,j)=a+(j-1)*n*L+(i-1)*L
四、链式存储结构 链表是这样一种线性表, 它的元素由数据和指针两部分组成, 数据部分存放结点的有关信息, 指针部分存放下一个结点的位置。 优点:可根据需要分配数据元素的存储区,也可随时撤消链表中数据元素的存储区,插入删 除操作只须改变指针,无须移动数据。 缺点: 它的数据元素必须在数据项以外至少增加一个指向后继元素的指针类型的数据项, 查 找其中的某个元素时必须中从第一个元素开始逐个往后找。

一个实例: Type pointer=^node; node=Record; data:real;

next:pointer; End; Var head,next:pointer;

1.Head 为表的首指针,指向链表的第一个结点。 2.整个链表的存取必须从 head 指针出发, 沿着每个结点的 next 指针顺序进行, 最后个结点的 next 指针为“空”(nil).

5.2 栈
第二节 栈
一、栈的概念 栈是一种线性表,对它的插入和删除操作都限制在表的同一端进行。这一端叫做栈顶,另一 个端叫做栈底。 栈又被成为“后进先出表”(LIFO)。 定义方法: Const m=栈元素的上限; Type stack=array[1..m] of <元素类型> Var s:stack; t:integer;

二、栈的基本运算 1.入栈:过程 push(x),往栈 s 中压入一个元素 x。

procedure push(x:<元素类型>);

begin if t=m then writeln(‘overflow’) else begin t:=t+1; s[t]:=x; end; end;

2.出栈:函数 pop(x),从栈 s 中弹出一个元素。

function pop:<元素类型>; begin if t=0 then writeln('empty') else begin pop:=s[t]; t:=t-1; end; end;

3.读栈顶元素:函数 top,读取栈 s 的栈顶元素。

function top:<元素类型>; begin if t=0 then writeln('empty') else top:=s[t]; end;

5.3 队列

第三节 队列
一、栈的概念 队列是从日常生活中的排队抽象出来的, 根据排队的原则“先来先服务”。 所谓队列就是允 许在一端进行插入,另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个队尾指针 r 指向队尾元素;允许删除的一端称为队首,通常也用一个队首指针 f 指向排头元素的前面。初 始时,f=r=0。 队列又称为“先进先出(FIFO)”线性表。 定义方法: Const m=队列元素上限; Type duilie=array[1..m] of <元素类型>; Var q:duilie; r,f:integer;

二、队列的基本运算 1.过程 add(x):队列 q 插入元素 x

Procedure add(x:integer); begin if r=m then writeln(‘overflow’) else begin r:=r+1; q[r]:=x; end; end;

2.过程 del(x):取出队列 q 的队首元素 y

Procedure del(var y:integer); begin

if f=r then writeln(‘empty’) else begin f:=f+1; y:=q[f]; end; end;

6.数据结构之非线性结构 数据结构之非线性结构
见课件


相关文章:
信息学奥赛计算机基础知识复习材料
信息学奥赛计算机基础知识复习材料第一章 计算机的概念、诞生与发展、应用、分类 一、计算机的概念:是一种能迅速而高效的自动完成信息处理的电子设备,它能按照程序对...
信息学奥赛基础知识习题(答案版)
信息学奥赛基础知识习题(答案版) 一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统和软件系统总称为 ...
信息学奥赛基础知识习题NOIP(答案版)
信息学奥赛基础知识习题(答案版 信息学奥赛基础知识习题 答案版) 答案版一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的 横线上) 1. ...
信息学奥赛基础知识(一)
信息学奥赛基础知识 17页 免费 信息学奥赛——算法入门教... 35页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...
信息学奥赛基础知识习题 (1)
信息学奥赛基础知识习题一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统和软件系统总称为 C 。 (A)...
信息学奥赛基础知识习题
信息学奥赛基础知识习题_IT认证_资格考试/认证_教育专区。信息学奥赛基础知识习题 一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的 横线...
信息学奥赛基础知识
信息学奥赛基础知识_其它_总结/汇报_应用文书。有助于你的noip初赛,能的扩展在很大程度上也体现为所 阶§ 1 计算机概述 世界第一台电子数字式计算机于 存储程序...
(信息学奥赛辅导)排列与组合基础知识
(信息学奥赛辅导)排列与组合基础知识_学科竞赛_高中教育_教育专区。第1页 排列与组合基础知识 有关排列与组合的基本理论和公式: 加法原理:做一件事,完成它可以有...
edu_ecologychuanke1477647171
信息学奥赛基础语言及竞赛训练。视频教程,幼狮精英学馆全套教学,在线学习初中其他课程,信息学奥赛(NOIP)基础语言C++入门视频下载
计算机基础知识,信息学竞赛
计算机基础知识,信息学竞赛_学科竞赛_初中教育_教育专区。计算机基础知识 第一节 计算机的基本常识 1.1 计算机的产生与发展 计算机的产生是 20 世纪最重要的科学...
更多相关标签:
信息学奥赛 | 小学信息学奥赛 | 信息学奥赛辅导 | 信息学奥赛培训 | 国际信息学奥林匹克 | 高中信息学竞赛 | 信息学奥赛一本通 | 信息学奥赛知识点 |