信息学奥赛-计算机基础知识精编版

1、第一章计算机基础知识2第一节数制及其转换2第二节算术运算和逻辑运算3第三节原码、反码和补码5第四节浮点数的表示方法6第五节奇偶校验7第六节ASCII 码表8第二章计算机硬件基础9第一节中央处理器9第二节存储器系统10第三节输入输出系统11第三章网络基础知识12第一节网络的组成与结构12第二节网络协议13第三节Internet 相关知识13第三节Internet 相关知识14第四章其他相关基础知识15第一节计算机病毒15第二节数据库系统15第五章数据结构之线性结构16第一节线性表16第二节栈17第三节队列18第六章数据结构之非线性结构19第一节树的概念19第二节树的表示方法和存储结构20第三节二

2、叉树的概念22第四节二叉树的遍历24第五节普通树的遍历27第六节根据两种遍历顺序确定树结构29第七节二叉排序树30第八节最优二叉树 (哈夫曼树 )31AOE 网321第一章计算机基础知识第一节数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。例如：76543210（11010110）2 = 1×2+ 1×2 + 0×2+ 1×2 + 0×2 + 1×2+ 1×2 + 0×2= （214） 10（ 2365）83210=2×8+3×8+ 6×8+ 5 ×8 = （12

3、69）10（4BF）16 = 4 ×162 +11 ×161 + 15 ×160 = (1215)10带小数的情况：210-1-2-3（ 110.011 ）2） 10=1 ×2+1×2+1×2+ 0×2 + 1×2+ 1×2= （6.375（5.76 ）8= 50-1-2（5.96875） 10×8 +7×8 + 6×8 =（ D.1C）16= 13 ×160+ 1 ×16-1 + 12*16 -2= （13.109375 ）10二、十进制化二进制的方法：

4、整数部分除二取余法，小数部分乘二取整法。例一：（ 43）10 = （101011）2例二：（ 0.375 ）10 = （0.011 ）2三、二进制转八进制的方法一位数八进制与二进制对应表八进制二进制 转换方法 : 对二进制以小数点为分隔，往前往后每三位划为一组，0000不足三位补 0，按上表用对应的八进制数字代入即可。1001例如： (10111011.01100111)2010=010,111,011.011,001,11 030114100=（273.36 ）85 1016 1107 1112三、二进制转十六进制的方法一位数十六进制与二进制对应表十六进制二进制转换方法 : 对二进制以小数点

5、为分隔，往前往后每四位划00000为一组，不足四位补 0，按上表用对应的十六进10001制数字代入即可。20010例如： (10111011.01100111)30011= 1011,1011.0110,01114010050101= （ BB.67）1660110701118100091001A1010B1011C1100D1101E1110F1111四、进制的英文表示法：以上都是用括号加数字的表示方法， 另外还有英文表示法， 就是以 BIN、OCT、HEX、DEC分别代表二、八、十六、十进制。或者只写第一个字母。例如 1101B表示是二进制。有些地方为了避免“ O”跟“ 0”混淆，把 O写

6、成 Q。第二节算术运算和逻辑运算一、二进制的算术运算1、加法运算规则：0+0=00+1=11+0=1 1+1=102、减法运算规则：0-0=00-1=1 （向高位借 1） 1-0=1 1-1=03、乘法运算规则：0×0=00×1=01×0=01×1=1二、逻辑运算1、基本运算 逻辑乘，也称“与”运算，运算符为“·”或“”0·0=00·1=01·0=01·1=1使用逻辑变量时， A·B可以写成 AB 逻辑加，也乘“或”运算，运算符为“+”或“”30+0=00+1=11+0=1 1+1=1 逻辑非，

7、也称“反”运算，运算符是在逻辑值或变量符号上加“”0=11=02、常用运算异或运算： AB = A· B A ·B2、基本公式 0，1律A·0=0A·1=AA 0=AA 1=1 交换律A B=B A A·B=B·A 结合律ABC =（AB） C = A（ BC）A·B·C =（A·B）·C = A ·（B·C） 分配律A·（ BC）= A·B A·C 重叠律AA.A = AA·A·. ·A = A 互补律A+A =1

8、A·A =0 吸收律AA·B = AA·（ AB） = AA A·B = ABA·（ AB） = A·B 对合律对一个逻辑变量两次取反仍是它本身 德·摩根定理AB=A·BAB=A+B三、逻辑代数的应用1、逻辑表达式化简例如： F=A·BA· BA·B= A · B A（ B B）（利用分配律）4= A · B A（利用互补律以及0，1律）= A B（利用吸收律）2、对指定位进行运算，假设变量A 有八位，内容是 d7d6d5d4d3d2d1d0 将变量 A 的 d5

9、位清零A·（ 11011111）A 将变量 A 的各位置 1A （ 11111111）A第三节原码、反码和补码计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。一、原码求原码的方法：设 X；若 X0，则符号位（原码最高位）为 0， X 其余各位取值照抄；若 X0，则符号位为 1，其余各位照抄。【例 1】X=+1001001X = 01001001【例 2】X=-1001001X= 11001001二、反码求反码的方法：设 X；若 X0，则符号位（原码最高位）为 0， X 其余各位取值照抄；若 X0

10、，则符号位为 1，其余各位 按位取反 。【例 3】X=+1001001X = 01001001【例 4】X=-1001001X = 10110110三、补码求补码的方法：设 X；若 X0，则符号位（原码最高位）为 0， X 其余各位取值照抄；若 X0，则符号位为 1，其余各位 按位取反后，最低位加 1。【例 5】X=+1001001X = 01001001【例 6】X=-1001001X= 10110111四、补码加减法计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。1、补码加法X+Y= X+ Y5【例

11、 7】X=+0110011,Y=-0101001，求 X+YX=00110011Y=11010111X+Y= X+ Y= 00110011+11010111=00001010注：因为计算机中运算器的位长是固定的，上述运算中产生的最高位进位将丢掉，所以结果不是1 00001010，而是 00001010。2、补码减法X-Y= X- Y= X+ -Y其中 -Y称为负补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“ 1”。【例 8】X=+0111001,Y=+1001101，求 X-YX =00111001Y=01001101-Y= 10110011X-Y = X+ -Y= 001

12、11001+10110011=11101100五、数的表示范围通过上面的学习， 我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0255 共 256 个数（ 0000000011111111），如果是有符号数则能表示 -128127 共 256 个数（1000000001111111）。如果两个字节表示一个整数，则共有 65536 个数可以表示，大部分程序设计语言中整数的范围都是-3276832767 的原因，可以看出这种整数类型是16 位的有符号数，而且是补码表示的。第四节浮点数的表示方法一、浮点数表示一个数的浮点形式（设基数是2）可写成：N=M×2E

13、其中 :M 代表尾数 ,E 代表阶码。计算机中浮点数只用尾数和阶码表示，其形式如下：阶码尾数符号尾数浮点数的精度由尾数决定，数的表示范围由阶码的位数决定。为了最大限度提高精度， 尾数采用规格化形式， 既 1/2 M<1。采用二进制表示时，若尾数大于零，则规格化数应该是01XXXX的形式；若尾数小于零，则规格化数应为10XXXX的形式。二、机器零6当浮点数的尾数为 0 或阶码为最小值时，计算机通常把该数当作零，因此程序中进行浮点运算时，判断某数是否为零，通常可以用小于某个极小值来代替。三、实例3【例 1】设 X=0.0110×2 , 用补码、浮点数形式表示阶码为Xj =011，尾

14、数为 00110，这时由于 X 尾数不符合 01XXXX的形式，因此不是规格化数，必须先进行规格化处理。方法：若尾数小于 1/2 ，把尾数左移一位（不包括符号位），观察结果是否满足规格化条件，满足则在把阶码减 1 即可，否则继续左移和调整阶码；若尾数大于 1，则把尾数右移一位（不包括符号位） ，观察结果是否满足规格化条件， 满足则在把阶码加 1 即可，否则继续右移和调整阶码。上例中， 00110 左移一位为 01100，符合规则化标准，此时阶码减 1，为 010 即得到浮点表示形式。这个数具体在计算机中如何表示要看计算机中规定的阶码和尾数的位数，若阶码和尾数均为 16 位，则上面的数 X 在计

15、算机内部表示就是，不足均用零填充。第五节奇偶校验计算机中数据在进行存储和传输过程中可能会发生错误。 为了及时发现和纠正这类错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。奇偶校验能发现一位或奇数位错误，且不能纠正错误。一般以字节（八位二进制）为单位加 1 位奇偶校验位。奇偶校验分奇校验和偶校验两种。一、奇校验：一个字节前面加一位校验位使得“ 1”的个数保持为奇数，若八位二进制数中“ 1”的个数为偶数，则校验位为“ 1”；若八位二进制数中“ 1”的个数为奇数，则校验位为“ 0”。【例 1】给加奇校验结果为二、偶校验：一个字节前面加一位校验位使得“ 1”的个数保持为偶数，若八

16、位二进制数中“ 1”的个数为偶数，则校验位为“ 0”；若八位二进制数中“ 1”的个数为奇数，则校验位为“ 1”。【例 2】给加偶校验结果为7第六节 ASCII码表代码字符代码字符代码字符代码字符代码字符3252472H92112p33!53573I93113q34”54674J94114r35#55775K95_115s36$56876L96116t37%57977M97a117u38&58:78N98b118v3959;79O99c119w40(60<80P100d120x41)61=81Q101e121y42*62>82R102f122z43+63?83S103g123

17、44,6484T104h124|45-65A85U105i12546.66B86V106j12647/67C87W107k48068D88X108l49169E89Y109m50270F90Z110n51371G91111o目前使用最广泛的西文字符集及其编码是ASCII 字符集和 ASCII码（ ASCII 是 AmericanStandard Code for Information Interchange的缩写），它同时也被国际标准化组织（ International Organization for Standardization, ISO）批准为国际标准。基本的 ASCII字符集共有1

18、28 个字符， 其中有 96 个可打印字符， 包括常用的字母、 数字、标点符号等，另外还有32个控制字符。标准ASCII 码使用 7个二进位对字符进行编码，对应的ISO 标准为 ISO646 标准。下表展示了基本ASCII 字符集及其编码：字母和数字的ASCII 码的记忆是非常简单的。 我们只要记住了一个字母或数字的ASCII码（例如记住 A 为 65， 0的 ASCII 码为 48），知道相应的大小写字母之间差32 ，就可以推算出其余字母、数字的ASCII码。虽然标准 ASCII 码是 7位编码，但由于计算机基本处理单位为字节（1byte = 8bit），所以一般仍以一个字节来存放一个ASC

19、II字符。每一个字节中多余出来的一位（最高位）在计算机内部通常保持为0 （在数据传输时可用作奇偶校验位）。由于标准 ASCII字符集字符数目有限， 在实际应用中往往无法满足要求。为此， 国际标准化组织又制定了 ISO2022标准，它规定了在保持与ISO646 兼容的前提下将ASCII 字符集扩充为8 位代码的统一方法。ISO陆续制定了一批适用于不同地区的扩充ASCII字符集，每种扩充ASCII字符集分别可以扩充128 个字符，这些扩充字符的编码均为高位为1 的8 位代码（即十进制数128255 ），称为扩展ASCII 码。下表展示的是最流行的一套扩展ASCII字符集和编码：8第二章计算机硬件基

20、础第一节中央处理器一、中央处理器的组成中央处理器简称 CPU，由控制器、运算器组成。运算器及控制器的基本功能：运算器是计算机进行算术和逻辑运算的部件，控制器是整个计算机中统一指挥和控制计算机各部件进行工作的控制中心。二、运算器运算器是负责对数据进行算术运算或逻辑运算的部件。运算器由算术逻辑单元（ ALU）、累加器、状态寄存器、通用寄存器组等组成。如图：算术逻辑运算单元、 累加器和通用寄存器的位数决定了CPU的字长。三、控制器是计算机的指令执行部件， 其工作是取指令、解释指令以及完成指令的执行。控制器由指令指针寄存器、 指令寄存器、控制逻辑电路和时钟控制电路等组成。指令指针寄存器（ IP ）用于

21、产生及存放一条待取指令的地址。指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。四、寄存器寄存器数量增多可以提高 CPU运行速度，但是不能太多，太多会使地址编码和指令长度变长，增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等组成。五、指令基本格式单目运算：操作码地址码二目运算：操作码第一地址 第二地址六、寻址方式： CPU执行指令时寻找数据地址的方式1、立即寻址： ADDAH,78 其中 ADD是操作码，表示做加法； AH是寄存器名； 78是个常数；该指令的意思是寄存器AH的值加上 78。2、直接寻址： ADD AH,(78)78 表示操作数的地址3、

22、间接寻址： ADD AH,(78)78 表示操作数地址的地址4、相对寻址： ADD AH,*78*78 表示本指令地址 +78， 78 称偏移量5、变址寻址： ADD AH,(DI+78) DI 是变址寄存器 , 存放一个地址 , 操作数地址是寄存器地址 +786、寄存器直接寻址 :ADD AH,78AH 是一个寄存器名 , 即寄存器直接寻址7、寄存器直接寻址 :ADD AH,(BX)BX 是一个寄存器名 , 存放操作数的地址9七、指令分类1 、数据传送指令： MOV AH,BHIN AH,3782 、数据处理指令 : 算术运算、逻辑运算、移位、比较等3 、程序控制指令：转移、调用、返回4 、

23、状态管理指令：中断、屏蔽中断八、指令的执行过程1 、CPU发出指令地址2 、读取指令3 、指令送指令寄存器4 、指令译码5 、按指令操作码执行6 、形成下条要执行的指令的地址九、时钟周期一个指令执行的时间称为指令周期计算机完成一个操作（如读取指令等）所需时间称为总线周期计算机中最基本的时间单位是时钟周期，有 CPU的主频决定。第二节存储器系统一、存储器的分类分类方法名称举例半导体存储器ROM 、 RAM （内存）、闪存（优盘）按存储介质分磁表面存储器硬盘、软盘、磁带光存储器CD-ROM 、 DVD-ROM随机存储器RAM （内存）、硬盘、软盘按工作方式分只读存储器ROM 、 CD-ROM顺序存

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

25、于CPU中。四、辅助存储器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：可擦写的光盘，但必须专门的刻录机。第三节输入输出系统一、输入输出控

26、制方式1 、程序查询方式：软件实现，效率低2 、中断方式：软硬件结合实现中断请求 -> 中断响应 -> 中断处理 -> 中断返回3 、直接存储器访问方式（DMA）：硬件实现11DMA请求 ->CPU 响应并把总线控制权交给DMA控制器 -> 数据交换 -> 交还总线控制权二、系统总线分类：数据总线、地址总线、控制总线总线标准： ISA 总线、 PCI 局部总线、 MCA总线三、 I/O 接口1 、显卡：分辨率、颜色数决定显示效果和所需显存例如：显示分辨率为1280×1024 的 32 位真彩色，所需显卡显存最少为1280×1024

27、5;32÷8 = 5MB2 、硬盘接口： IDE 、 EIDE Ultra DMA SCSI SATA3 、串行口4 、并行口：通常接针式打印机5 、 USB接口：通用串行总线四、显示器的有关知识1 、屏幕尺寸： 15 寸、 17 寸、 19 寸等2 、点间距：屏幕上象素与象素之间的距离， 决定了显示器能显示的最大分辨率。越小表示能显示的最大分辨率越大。五、打印机 ：针式打印机、喷墨打印机、激光打印机。激光打印机速度最快，针式打印机可以打印票据。第三章网络基础知识第一节网络的组成与结构一、网络组成1 、通信主体：服务器和工作站2 、通信设备：传输介质、网络设备3 、通信协议：通常是

28、TCP/IP 二、网络分类按传输距离分：局域网（ LAN）、城域网（ MAN）、广域网（ WAN）按网络结构分：总线型、星型、环型、树型三、网络拓扑结构12第二节网络协议一、 OSI 网络协议的层次国际标准化组织 （ISO）提出的“开放系统互连模型 （OSI）”是计算机网络通信的基本协议。 该协议分为七层。如下表应用层表达层会话层传输层网络层数据链路层物理层二、网络设备极其作用第三节 Internet相关知识一、 IP 地址每台与 Internet连接的主机都必须有一个 IP地址， IP 地址采用分段式表示：共分 4 段，每段用一个字节即八个二进制位表示，实际的IP 把二进制转换成十进制书写。

29、如 61.153.238.132，因为每段时一个字节，因此IP 每段的数字大小最大为 255。IP 地址分类如下表：目前32 位 IP 地址资源几近枯竭，有人提出用 48 位表示IP ，即 IPV6 。分二进制表示十进制表示第一段数字类A24 位主机地址<1280 七位网络地址类B14 位网络地址16 位主机地址12819110类C21 位网络地址8 位主机地址192223110类二、域名 ： Internet 的域名系统叫做 DNS，DNS是树形结构的。域名跟 IP 地址是多对一的关系1 、域名分级系统：一个域名最右边的部分通常叫顶级域名，往前依次为二级域名、三级域名等。2 、我国域名

30、管理机构 :CNNIC3 、常见域名含义：gov政府 edu 教育 int国际组织 com 商业组织 mil军事部门 net网络运行 org 其他组织cn中国hk香港tw台湾uk英国 jp日本三、一些常见名词解释1 、 Intranet:企业内部网2、 ISP（Internet Service Provider）：因特网服务供应商3、 ICP（Internet Content Provider）：因特网内容供应商4、 IAP（Internet Acess Provider）：因特网接入供应商，目前一般都被 ISP包含5 、 BBS：电子公告栏，目前通常叫论坛四、接入 Internet 的方法1

31、、 PSTN拨号接入：必须设备 MODEM，电话线，速度慢2 、 DDN专线接入：速度快，费用高。3 、 ISDN专线接入：利用传统电话网络的综合业务数字网。4 、分组交换接入5 、帧中继接入14第四章其他相关基础知识第一节计算机病毒一、特点寄生性、隐蔽性、非法性、传染性、破坏性二、分类 ：1 、引导型病毒：寄生在系统引导区，比较容易被清除，现在已经很少见。2 、文件型病毒：寄生在可执行文件中，感染速度快，较易清除。3 、目录型病毒：寄生在系统目录结构中4 、混合型病毒：多种类型的混合5 、宏病毒：专门感染Microsoft Office系列文件的病毒6 、蠕虫病毒：感染网络，使网速大大降低。

32、目前流行的病毒大多集成了黑客技术、木马技术和病毒技术三种，非常难以清除而且很容易中。三、一些常见危害较大的病毒1 、 CIH 病毒 : 文件型病毒， 4 月 26 日发作时破坏性最大，首个能破坏硬件系统的病毒。2 、 Melissa 病毒：宏病毒，邮件传播3 、冲击波、震荡波病毒：利用 WINDOWS的漏洞，使计算机自动重启并堵塞网络。第二节数据库系统一、数据库是数据的一种组织形式，目前存储大量数据基本都采用数据库常见的数据库软件有： FoxBase、FoxPro、 Access、Sql Server 、 MySql、Sybase、 Oracel 等。除了最早的如 FoxBase等软件，目前流

33、行的数据库软件都是关系型数据库。二、数据库数据结构数据库系统的数据结构可以认为是多张二维表， 二维表中的列称为字段， 行存放数据。如下图15二、数据操作用以对数据库进行检索和更新（添加、删除、更新等）操作三、数据的完整性约束条件多个表之间的数据可能存在相互关联，必须保证其完整性四、数据库操作语言 SQL数据库常用的操作语言称为 SQL语言，是一种更高级化的语言，只须告诉计算机做什么事情即可。下面例举几条常用的语句。1 、 SELECT语句语法： select <列名 > from < 表名 > where < 条件 >功能：从表中选出满足条件的记录列2 、

34、INSERT 语句语法： insert into <表名 >( 列名表 ) values(<值表 >)功能：在表中插入一条新记录。3 、 DELETE语句语法： delete * from <表名 > where < 条件 >功能：删除满足条件的记录4 、 UPDATE语句语法： update < 表名 > set < 列名 >=<值> where < 条件 > 功能：修改满足条件的表中某记录某字段的值第五章数据结构之线性结构第一节 线性表一、概念线性表是指由有限个类型相同的数据元素组成的集合，它有

35、以下的特点：1. 有唯一的头结点 ( 即第一个数据元素 ) 和尾结点 ( 即最后一个数据元素 ) ；2. 除结点外，集合中的每个数据元素均只有一个前驱；3. 除尾结点外，集合中的每一个数据元素均只有一个后继。二、线性表的存储结构1 、顺序结构：是通过数组说明分配连续地址的存储区，通过下标引用数组的相应元素。2 、链式结构：通过指引元素类型的变量对线性表中元素进行动态分配存储。三、顺序存储结构1 、一维数组 数组存储的结构在数组声明时就需要事先分配相应的连续内存空间用来存放数据。 按首地址（表中第一个元素的地址）的位移来访问数组每一个元素的。若第一个元素的地址是 a，每个元素占用的存储空间为 L

36、，则数组的第 i 个元素的地址可以用如下公式计算：d(i)=a+(i-1)*L2 、二维数组 定义方法： <数组名 >:array1.n,1.m of <元素类型 >16 对于行为 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四、链式存储结构链表是这样一种线性表，它的元素由数据和指针两部分组成，数据部分存放结点的有关信息，指针部分存放下一

37、个结点的位置。优点：可根据需要分配数据元素的存储区，也可随时撤消链表中数据元素的存储区，插入删除操作只须改变指针，无须移动数据。缺点：它的数据元素必须在数据项以外至少增加一个指向后继元素的指针类型的数据项，查找其中的某个元素时必须中从第一个元素开始逐个往后找。一个实例：Typepointer=node;node=Record;data:real;next:pointer;End;Varhead,next:pointer;1.Head 为表的首指针，指向链表的第一个结点。2. 整个链表的存取必须从 head 指针出发，沿着每个结点的 next 指针顺序进行，最后个结点的 next 指针为“空”（

38、 nil ）.第二节 栈一、栈的概念栈是一种线性表，对它的插入和删除操作都限制在表的同一端进行。这一端叫做栈顶，另一个端叫做栈底。 栈又被成为“后进先出表”（ LIFO）。定义方法：Constm=栈元素的上限；Typestack=array1.m of <元素类型 >Vars:stack;t:integer;二、栈的基本运算1. 入栈：过程 push(x) ，往栈 s 中压入一个元素 x。procedure push(x:<元素类型 >);begin17if t=mthen writeln(overflow )else begint:=t+1;st:=x;end;end

39、;2. 出栈：函数 pop(x) ，从栈 s 中弹出一个元素。function pop:<元素类型 >beginif t=0then writeln('empty')else beginpop:=st;t:=t-1;end;end;3. 读栈顶元素：函数 top ，读取栈 s 的栈顶元素。function top:<元素类型 >beginif t=0then writeln('empty')else top:=st;end;第三节队列一、栈的概念队列是从日常生活中的排队抽象出来的，根据排队的原则“先来先服务”。 所谓队列就是允许在一端进行

40、插入，另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r 指向队尾元素；允许删除的一端称为队首，通常也用一个队首指针 f 指向排头元素的前面。 初始时， f=r=0 。 队列又称为“先进先出 （FIFO）”线性表。定义方法：Constm=队列元素上限 ;Typeduilie=array1.m of <元素类型 >Varq:duilie; r,f:integer;二、队列的基本运算1. 过程 add(x) ：队列 q 插入元素 x Procedure add(x:integer);beginif r=m18then writeln(overflow )else be

41、ginr:=r+1;qr:=x;end;end;2. 过程 del(x) ：取出队列 q 的队首元素 y Procedure del( var y:integer);beginif f=rthen writeln(empty)else beginf:=f+1;y:=qf;end;end;第六章数据结构之非线性结构第一节树的概念一、树的定义树是一种常见的非线性的数据结构。树的定义：树是 n(n>0) 个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上。这条路

42、径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；二、结点的分类在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类 : 根结点：没有前驱的结点。 在树中有且仅有一个根结点。如上图（ b）中的 r ；19 分支结点：除根结点外，有后驱的结点称为分支结点。如上图（ b）中的 a，b，c，x，t ，d，i 。分支结点亦是其子树的根； 叶结点：没有后驱的结点称为树叶。如上图（b）中的 w，h，e，f ，s，m，o，n，j ，u 为叶结点。由树的定义可知，树叶本身也是其父结点的子树。根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（

43、b）中，从根 r 到结点 i 的唯一路径为rcti。三、有关度的定义 结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点 i度为 3，结点 t 的度为 2，结点 b 的度为 1。显然，所有树叶的度为0。 树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。四、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。 即若某个结点在第k 层，则该结点的后件均处在第k+1 层。图（ b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。五、森林所谓森林，是指若干棵互不相交的树的集合。如图（ b）去掉根结点 r ，其原来的三棵子树 Ta，Tb， Tc 的集合 Ta ，Tb，Tc就为森林，这三棵子树的具体形态如图（ c）。六、有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。第二节树的表示方法和存储结构一、树的表示方法树的表示方法一般有两种： 自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。 括号表示法：先将根结点