资源描述
1.计算机系统知识计算机系统由硬件系统和软件系统组成。硬件由运算器、控制器、存储器、输入设备、输出设备5部分组成；软件由系统软件、应用软件组成。运算器：对数据进行处理的部件，主要完成算术和逻辑运算；控制器：从主存中取出指令，并指出下一条指令在主存中的位置，取出的指令经指令寄存器送往指令译码器，经过对指令的分析发出相应的控制和定时信息；控制器的组成部分为： 程序计数器 指令寄存器 指令译码器 状态条件寄存器 时序产生器 微信号发生器计算机硬件的典型结构：单总线、双总线(以cpu为中心、以存储器为中心)、采用通道的大型系统。2、二、八、十、十六进制间的转换方法 十进制转换成二进制：十进制整数转换成二进制整数通常采用除2取余法，小数部分乘2取整法。 例如，将30D转换成二进制数。 2| 30 .0 -最右位 2 15 .1 2 7 .1 2 3 .1 1 .1 -最左位 30D=11110B 八、十六进制转二进制方法类似。 二进制数转换成八进制数：对于整数，从低位到高位将二进制数的每三位分为一组，若不够三位时，在高位左面添0，补足三位，然后将每三 位二进制数用一位八进制数替换，小数部分从小数点开始，自左向右每三位一组进行转换即可完成。例如：将二进制数1101001转换成八进制数，则 001 101 001B | | | 1 5 1O 1101001B = 151O 八进制数转换成二进制数：只要将每位八进制数用三位二进制数替换，即可完成转换，例如，把八进制数(643.503)8，转换成二进制数，则 (6 4 3 . 5 0 3)8 | | | | | | (110 100 011 . 101 000 011)2 (643.503)8=(110100011.101000011)2 二进制与十六进制之间的转换 (1)二进制数转换成十六进制数：由于2的4次方=16，所以依照二进制与八进制的转换方法，将二进制数的每四位用一个十六进制数码来表示，整数部分以小数点为界点从右往左每四位一组转换，小数部分从小数点开始自左向右每四位一组进行转换。 (2)十六进制转换成二进制数 如将十六进制数转换成二进制数，只要将每一位十六进制数用四位相应的二进制数表示，即可完成转换。 例如：将(163.5B)16转换成二进制数，则 ( 1 6 3 . 5 B )16 | | | | | (0001 0110 0011. 0101 1011 )2 (163.5B)16=(101100011.01011011)2 二进制的算术、逻辑运算3、数据在计算机中的表示方法：各种数据在计算机中表示的形式称为机器数，其特点是用0,1表示，如0表示正号，1表示负号，小数点隐含表示而不占位置。机器数对应的实际数据称为真值。机器数分为无符号数和有符号数。无符号数表示正数。带符号的机器数可采用原码、反码、补码等码制进行计算。4、汉字编码：汉字处理包括汉字的编码输入、存储、输出等环节。输入码(数字编码、拼音码、字形编码)、内部码(简称汉字内码)(GB2312-80用2字节表示一个汉字，Unicode用4字节表示一个汉字)、字形码(点阵、矢量函数，汉字的输出方式)5、cpu的功能：程序控制、操作控制、时间控制、数据处理6、计算机系统分类：Flynn分类法（按指令流、数据流分类）、冯式分类法（按最大并行度分类） 指令流：机器执行的指令序列； 数据流：指令调用的数据序列。7、计算机系统结构和计算机组成的区别：系统结构是指计算机系统在总体上、功能上需要解决的问题；计算机组成是指在逻辑上如何具体实现的问题。8、计算机并行的发展：不同于同时性的是，并发性是指两个或两个以上事件在同一时间间隔内连续发生；分为存储器操作并行，处理器操作步骤并行（流水线处理机），处理器操作并行（阵列处理机），指令、任务、作业并行（多处理机、分布式处理系统、计算机网络）。9、存储器的层次结构：高速缓存、主存、辅存。（有人将cpu内部的寄存器也作为一个存储层次） 存储器的分类：存储器按位置分为内存（主存）和外存（辅存）；按工作方式分为读写存储器和只读存储器；按访问方式分为按地址访问和按内容访问的存储器；按寻址方式分为随机寻址、顺序、直接寻址存储器。 相连存储器是一种按内容访问的存储器。其工作原理是把数据作为关键字与存储器中的每一单元比较，找出与关键字相同的数据。相连存储器可用在高速缓存中；在虚拟存储器中用来作段表、页表或快表存储器；用在数据库和知识库中。 高速缓存：由控制部分和cache部分组成。cache部分放主存的部分拷贝信息，控制部分判断cpu要访问的信息是否在cache中命中，并按替换算法决定主存的哪一块信息放到cache中的哪一块里面。 一般来说，Cache的功能全部由硬件实现。 高速缓存与主存的地址映像方法有3种，即直接映像，全相连映像，组相连映像（组使用直接相连而组内的块使用全相连方式） 在Cache的替换算法中，“近期最少使用LRU算法”是命中率最高的一种算法。10、虚拟存储器，是由主存、辅存、存储管理单元和操作系统的存储管理软件组成的存储系统。它将大容量的外存也纳入存储管理器的管理范围，具体执行程序时要先判断程序是否在主存中，若不在则需从辅存中调入。按工作方式分为： 页式虚拟存储器 段式虚拟存储器 段页式虚拟存储器11、磁盘阵列raid，是由多台磁盘存储器组成的，一个大而快速、可靠的外存子系统。 raid0 是不具备容错能力的阵列，N个磁盘组成的0级阵列，其平均故障时间间隔是单个磁盘存储器的N分之一；但其数据传输速率是单 的N倍。 raid1 使用镜像容错技术 raid2 使用汉明码容错技术 raid3 一般使用一个检验盘 raid4 只使用一个检验盘 raid5 没有专门的检验盘，它在每块盘上都写数据和检验信息。12、CISC-复杂指令集计算机 RISC-精简指令集计算机RISC的特点： 指令种类少； 指令长度固定、格式少； 寻址方式少，适合于组合逻辑控制器； 设置最少的访问内存指令，访问内存比较花时间； 在CPU内部设置大量寄存器，使操作在CPU内部快速进行； 适合于流水线操作，容易并行执行。13、输入输出技术 内存与接口的编址方式分为内存和接口地址独立的编址方式，和内存、接口地址统一的编址方式。 直接程序控制（无条件传送方式、程序查询方式）（整个输入输出过程是在cpu执行程序的控制下完成） 中断方式 （cpu得用中断方式完成数据的输入输出操作） 直接存储器存取（DMA）方式 ，数据直接在内存与IO设备间成块传送，cpu只需在开始和结束时进行处理，过程中无须干涉。 DMA传送的一般过程为： 1）外设向DMA控制器提出DMA传送请求； 2）DMA控制器向CPU提出请求； 3）CPU允许DMA工作，处理总路线控制的转交； 4） 输入输出处理机（IOP）方式 ，由一个专用的处理机完成主机的输入输出操作。14、流水线技术，是将一条指令分解成一连串执行的子过程，在cpu中将一条指令的串行执行过程变为若干条指令的子过程重叠执行。 特点是，流水线可分成若干相互联系的子过程；执行每个子过程的时间尽量相等；形成流水处理需要准备时间；指令流发生不能顺序执行时会使流水线中断。 两个指标，吞吐率（单位时间里流水线处理机流出的结果数，对指令而言就是单位时间里执行的指令数）； 建立时间（所有子过程执行一遍用时之和）15、总线的分类-芯片内总线、元件级总线、内总线（即系统总线）、外总线（即通信总线）常见的几种内总线：ISA总线(长短两个插座，分别有64个、32个接点)，EISA总线，PCI总线。其中PCI总线的工作与处理器的工作是相对独立的，即总线时钟和处理器时间是独立、非同步的，PCI总线上的设备即插即用。 常见的几种外总线：RS-232C（是一条串行总线），SCSI（是一条并行总线），USB（由4条信号线组成，两条用于传送数据，另两条传送+5V 500mA的电源），IEE1394（是一条串行总线，由6条信号线组成，两条传数据两条传控制信号两条传电源，支持即插即用和热插拔）16、阵列处理机，又称并行处理机，它将重复设置的多个处理单元连成阵列，在控制部件的控制下，对分配给自己的数据进行处理，并行地完成一条指令规定的操作。这是一种单指令多数据流计算机（SIMD）17、多处理机，是由多台处理机组成的系统。每台处理机有自己的控制部件，可以执行独立的程序，共享一个主存和所有外设。它是多指令流多数据流计算机。 按其构成分为：异构（非对称）型多处理机系统，同构（对称）型多处理机系统，分布式处理系统4种多处理机的结构：总线结构，交叉开关结构，多端口存储器结构，开关枢纽式结构18、并行处理机，与采用流水结构的单机系统都是单指令流多数据流计算机，它们的区别是，并行处理机采用资源重复技术，而流水结构的单机系统使用时间重叠技术。并行处理机有2种典型结构：具有分布式存储器的，具有共享式存储器的。它们的共同点是在系统中设置多个处理单元，各个处理器按一定接方式交换信息，在统一的控制部件作用下，各自处理分配来的数据，并行的完成同一指令所规定的操作。19、信息安全的基本要素 机密性 完整性 可用性 可控性 可审查性20、计算机安全等级：技术安全性、管理安全性、政策法律安全性。一些重要的安全评估准则：“美国国防部和国家标准局的可信计算机系统评测标准TCSEC/TDI”、“欧共体的信息技术安全评估准则ITSEC”、“ISO/IEC国际标准”、“美国联邦标准”。其中TCSEC/TDI分了4个组7个等级，C2是安全产品的最低等级。21、安全威胁与影响数据安全的因素安全威胁是指某个人、物、事件对某一资源的机密性、完整性、可用性或合法性所造成的危害。典型的安全威胁有很多种。影响数据安全的因素有内部和外部两种。内部因素：可采取多种技术对数据加密；制定数据安全规划；建立安全存储体系；建立事故应急计划和容灾措施；重视安全管理并建立安全管理规范。 外部因素：按密级划分使用人员的权限；使用多种认证方式；设置防火墙；建立入侵检测、审计和追踪；同时注意物理环境的保护。22、加密技术包括两个元素：算法和密钥。加解密算法设计的关键是满足3个条件“可逆性”，“密钥安全”，“数据安全”。 数据加密技术分为对称加密（以DES算法为代表）、非对称加密（以RSA算法为代表）、不可逆加密3种。 目前常用的对称加密算法有：DES数据加密标准算法（使用56位密钥，对64位二进制数据块加密，基本加密运算为置换运算、移位运算 、模加运算）； 3DES（使用2个56位密钥，加、解、加）； RC-5； 国际数据加密算法IDEA（类似于3DES，使用128位密钥，PGP系统在使用该算法） 比较有名的非对称加密算法：RSA算法，它是建立在大素数因子分解的理论基础上的算法。其公钥密码长度大于100位，算法运算速度较慢，多用于加密信息量小的场合，可以使用RSA算法来实现数字签名。23、密钥管理，主要是指密钥对的管理，包括密钥的产生、选择、分发、更换和销毁、备份和恢复等。多密钥的管理可以使用KDC。24、数据完整性保护，是在数据中加入一定的冗余信息，从而能发现对数据的任何增删改。方法是在发送或写入时对所要保护的数据进行检验和作加密处理，产生报文验证码MAC，附在数据后面。在接受或读出数据时根据约定的密钥对数据进行检验和作加密运算，将所得的结果与MAC比较，根据结果是否一致判断数据是否完整。25、认证技术，主要是解决网络通信双方的身份认可。认证的过程涉及到加密和密钥交换。加密可使用对称加密、不对称加密和二者混合使用的方法。一般有账户名/口令认证、使用摘要算法认证、基于PKI公开密钥的认证。 PKI是一种遵守既定标准的密钥管理平台，它能为所有网络应用提供加密和数字签名等密码服务及必需的密钥和证书管理体系。PKI的基础技术包括加密、数字签名、数据完整性机制、数字信封、双重数字签名等。完整的PKI系统必须包括CA、数字证书库、密钥备份及恢复系统、证书作废系统、应用接口API等基本部分。 PKI使用证书进行公钥管理，通过CA将用户的公钥和用户其它住处绑在一起，以在因特网上验证用户身份。26、HASH函数，输入一个不定长的字符串，返回一个固定长度的字符串（即HASH值）。单向HASH函数用于产生信息摘要；信息摘要简要地描述了一份较长的信息或文件，可以被看作是一份文件的数字指纹，信息摘要用于创建数字签名。27、数字签名的过程： 信息发送者使用一单向HASH函数对信息生成信息摘要； 信息发送者使用自己的私钥加密信息摘要； 信息发送者将信息本身和已签名的信息摘要一并发送出去； 信息接收者使用发送者的公钥对信息摘要解密，再使用同一单向HASH算法对信息生成信息摘要并进行验证是否一致。28、数字加密的过程： 信息发送者先生成一个对称密钥，使用该密钥对信息加密； 信息发送者使用接收者的公钥加密上述对称密钥； 信息发送者将上两步的结果内容都传给接收者（这就是数字信封）； 信息接收者使用私钥解密对称密钥，并使用对称密钥解密信息本身。29、SSL安全协议，一个能够保证任何安装了SSL的客户和服务器之间事务安全性的协议，主要用于提高应用程序之间数据的安全系数。SSL提供3方面服务：客户和服务器的合法性认证；加密传送的数据；保护数据的完整性。30、数字时间戳技术，就是数字签名技术的一个变种，不同的是这个要由认证单位DTS提供数字签名。它的过程是：先形成需要加时间戳的信息的信息摘要；将信息摘要送到DTS，DTS记录收到的日期及时间；DTS进行数字签名，然后送回用户。31、计算机病毒的定义，它是一种程序，具有修改别的程序的特性，并使用被修改的程序也具有这样的特性。 病毒的特点：寄生性，隐毕性，非法性，传染性，破坏性。 按病毒的寄生方式和入侵方式分成：系统引导型病毒，文件外壳型，混合型病毒，目录型病毒，宏病毒（也叫数据病毒）。 需要注意的几点：变种、病毒程序加密、多形性病毒、病毒的伪装。 计算机病毒防治的手段：人工预防；软件预防；管理预防。 解决网络安全问题的技术包括：划分网段、局域网交换技术和VLAN；加密技术、数字签名和认证、VPN技术；防火墙技术；入侵检测技术；网络安全扫描技术。32、计算机的RAS技术，R（可靠性）、A（可用性）、S（可维修性）。 计算机可靠性的模型有：串联系统模型、并联系统、N模冗余系统。 串联系统可靠性 R = R1*R2*.Rn 平均故障率 = L1+L2+.Ln 并联系统可靠性 R = 1 - （1-R1）（1-R2）.（1-Rn) N模冗余系统由2n+1个子系统和一个表决器组成，只要n+1个子系统工作正常，系统就工作正常。 提高可靠性的办法：提高元件质量、改进加工工艺与工艺结构、完善电路设计、发展容错讲述。33、计算机性能评测的常用方法：时钟频率法、指令执行速度法、等效指令执行速度法、数据处理速率法、核心程序法。 基准测试程序有，整数测试程序、浮点测试程序、SPEC基准测试程序、TPC基准程序。34、计算机故障包括永久故障、间歇性故障和偶然故障。故障诊断分为故障检测和故障定位两方面。 容错，就是通过冗余方法来消除故障影响。硬件冗余有时间冗余和器件冗余两种。 故障处理步骤，封闭、检错、重复执行、诊断、重构与恢复、修复、重入。35、BCD（Binary-Coded Decimal）码又称为“二十进制编码”，专门解决用二进制数表示十进数的问题。 压缩BCD码 每一位数采用4位二进制数来表示，即一个字节表示2位十进制数。例如：二进制数10001001B，采用压缩BCD码表示为十进制 数89D。 非压缩BCD码 每一位数采用8位二进制数来表示，即一个字节表示1位十进制数。而且只用每个字节的低4位来表示09，高4位为0。 例如：十进制数89D，采用非压缩BCD码表示为二进制数是： 00001000 00001001B 36、ASCII是 AmericanStandardCodeforInformationInterchange的缩写，用来制订计算机中每个符号对应的代码，这也叫做计算机的内码(code)。每个ASCII码以1个字节(Byte)储存，从0到数字127代表不同的常用符号，例如大写A的ASCII码是65，小写a则是97，阿拉伯数字0则是 48。由于ASCII字节的七个位，最高位并不使用。 第032号及第127号(共34个)是控制字符或通讯专用字符，如控制符：LF（换行）、CR（回车）、FF（换页）、DEL（删除）、BEL（振铃）等；通讯专用字符：SOH（文头）、EOT（文尾）、ACK（确认）等； 第33126号(共94个)是字符，其中第4857号为09十个阿拉伯数字；6590号为26个大写英文字母，97122号为26个小写英文字 母，其余为一些标点符号、运算符号等。 注意：在计算机的存储单元中，一个ASCII码值占一个字节(8个二进制位)，其最高位(b7)用作奇偶校验位。所谓奇偶校验，是指在代码 传送过程中用来检验是否出现错误的一种方法，一般分奇校验和偶校验两种。奇校验规定：正确的代码一个字节中1的个数必须是奇数， 若非奇数，则在最高位b7添1；偶校验规定：正确的代码一个字节中1的个数必须是偶数，若非偶数，则在最高位b7添1。 37、按位与的特殊用途： 清零。 方法： 与一个各位都为零的数值相与，结果为零。 取一个数x中某些指定位。 方法： 找一个数，此数的各位是这样取值的：对应x数要取各位，该数对应位为1，其余位为零。此数与x 相就可以得到x中的某些位。 例：设X=10101110 (1)取X的低4位 (2)取X的bit2、bit4、bit6位38、某EPROM芯片上有24条地址线A0-A23，8条数据线D0-D7，则该芯片的容量为“16M”。 EPROM芯片上的地址线决定了该芯片有多少个存储单元，数据线数表明每个存储单元所存储的数据位数。24条地址线则有16M个存储单元，8条数据线决定了每个存储单元存1个字节。所以容量为16M字节。39、机内码、国标码、区位码 根据汉字的国家标准，用两个字节（16位二进制数）表示一个汉字。但使用16位二进制数容易出错，比较困难，因而在使用中都将其转换为十六进制数使用。国标码是一个四位十六进制数，区位码则是一个四位的十进制数，每个国标码或区位码都对应着一个唯一的汉字或符号，但因为十六进制数我们很少用到，所以大家常用的是区位码，它的前两位叫做区码，后两位叫做位码。 国标码规定，每个汉字（包括非汉字的一些符号）由2字节代码表示。每个字节的最高位为0，只使用低7位，而低7位的编码中又有34个适用于控制用的，这样每个字节只有27 - 34 = 94个编码用于汉字。2个字节就有94 94=8836个汉字编码。在表示一个汉字的2个字节中，高字节对应编码表中的行号，称为区号；低字节对应编码表中的列号，称为位号。 国标码与机内码转换关系：为了不与7位ASCII码发生冲突，把国标码每个字节的最高位由0改为1，其余位不变的编码就是汉字字符的机内码 。也可以理解为国标码加上8080H后得到机内码，或是机内码减去8080H后得到国标码。 国标码与区位码转换关系：将国标码减去2020H后，得到区位码。 如某汉字机内码是BFF0H，则国标码为3F70H，区位码为1F50H。40、在采用三总线的运算器中，三条总线分别与运算器的两个输入一个输出相连接，各自有自己的通路。因此执行一次操作只需一步即可完成。在运算器的两个输入和一个输出上不再需要设置暂存器。41、光盘上的信号是记录在光盘表面的凹坑及平面上。凹坑与平面的交接处代表1，因此在光盘上不允许有连续的两个142、磁盘非格式化容量 = 最大位密度*最内圈周长*总磁道数 -实际上就是使用磁盘的面积乘以位密度 格式化容量 = 每道扇区数*扇区容量*总磁道数 总磁道数为：（外半径 - 内半径）* 磁道密度 常识：有一个多盘片组成的盘组，在向磁盘记录一个文件时，如果超出了一个磁道容量，那么剩下的部分将存于其他盘面的同一编号的磁道上。因为盘组中的多个盘面形成一系列柱面，在向磁盘写入文件时会尽可能记录在同一柱面上，当一个柱面记录不下时，再记录到相邻的柱面上。 43、微指令根据编码方式的不同分为水平微指令和垂直微指令。 水平微指令，长度较长、操作具有高度并行性、编码简单、执行速度快，更多地体现了控制器的硬件细节； 垂直微指令，长度较短、并行度低、功能弱、效率低、编程容易但微程序长。 排列组合公式为： 求n上数中m个数的组合有多少， C = n(n-1)(n-2).(n-m+1)/m! 例如求n个数中每2个数组合的可能性，C = n(n-1)/2 种可能性2.数据结构与算法1、线性表的定义及特点 线性表是若干数据元素组成的有限集合； 线性表的特点是，有惟一的起始结点和惟一的终端结点，其它元素都有惟一的直接前驱和惟一的直接后继。 线性表的抽像数据类型定义包括2方面， 数据对象、关系的定义； 线性表有关操作的定义； 线性表的数据对象是具有相同性质数据元素的集合。 线性表的有关操作有： 基本操作：初始化线性表、撤消线性表、判/置空表、取表长、取前驱元素、取后继元素、取第i个元素、遍历等。 插删操作：在顺序结构下，结点的插入(n/2)和删除(n-1)/2主要是进行元素的移动；在链式结构下，结点的插删是调整指针的指向。 查找操作：在顺序表中可以进行折半查找，在链表中只能进行顺序查找。2、线性表的基本存储结构及特点，线性表有顺序和链式两种存储结构。 顺序存储结构是：用一组地址连续的存储单元依次存储线性表中的数据元素； 链式存储结构是：用一组地址任意的存储单元存储线性表中的数据元素。（存储单元节点可以是连续的，也可以是不连续的） 链式存储结构包括， 单链表（又称线性链表），结点的结构体有两个域，分别存储数据元素和当前元素有关系的其它元素所在结点的指针 双向链表，每个结点包含两个指针，分别指明直接前驱和直接后继元素，可以在两个方向上遍历其后及其前的元素； 循环链表，链表中最后一个结点的指针指向第一个结点，开成环状结构，可以在任意位置上方向不变地遍历全表； 静态链表，借助数组描述线性表的链式存储结构。3、栈的定义：是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。 栈的特点：是先进后出(FILO)。在线结构中，允许进行插、删操作的一端称为栈顶，相应另一端称为栈底。不含数据的栈称为空栈。 栈的基本运算有：置空栈、判空栈、元素入栈、出栈和读取栈顶元素的值。 栈的存储结构：顺序栈和链栈。 顺序栈指，用一组连续的存储单元依次存储自栈顶到栈底的元素，同时设置指针top指示栈顶元素的位置。顺序栈的空间容量是有限的，要预先定义。顺序栈的入栈和出栈操作是通过修改数组下标来完成。假设栈底对应于数组下标较大的一端，那么在元素入栈时就是下标减1，而元素出栈时就是下标加1。 链栈，类似于线性链表，栈顶指针就是链表首结点的位置，元素的插删操作限定在首结点处进行。 栈的应用：表达式计算，数制转换，括号匹配，迷宫问题，递归问题 4、队列的定义：是一种先进先出(FIFO)的线性表。 队列的特点：它只允许在表的一端插入元素而在表的另一端删除元素。在队列中允许插的一端叫队尾(rear)，允许删的一端叫队头(front)。 队列的基本运算：置队空、判队空、入队、出队、读队头元素等。 队列的存储结构：顺序队列和链队列。 顺序队列，又被叫作循环队列，设顺序队列Q，Q.front表示队头指针，Q.rear表示队尾指针，则Q.front和Q.rear相等且为0时为空队列；元素入队时Q.rear加1，元素出队时Q.front加1。因为顺序队列的空间容量是提前设定的，所以当Q.rear达到了上限时表示队列满。 为区别队列空和队列满两种情况下可能出现的Q.front = Q.rear，有两种方法。一个是设置一个标识位，以区别头尾指针相同时队列是空还是满；另一个方法是牺牲一个元素空间，约定以Q.rear所指的下一个位置是Q.front时表示队列满。 链队列，链队列为空的判定条件是头尾指针相同且均指向头结点。 队列的应用：常用于需要排队的场合，如操作系统中的打印队列，离散事件的复读机模拟等。5、串的定义：是仅由字符构成的有限序列。是取值范围受限的线性表。一般记为S = a1a2.an。 串的几个概念：空串、空格串、子串、串相等、串比较。 串的几个操作：赋值操作StrAssign(s,t)、联接操作Concat(s,t)、求串长StrLength(s)、串比较StrCompare(s,t)、求子串SubString(s,start,len)。 串的存储：静态存储(顺序存储)，是定长的存储结构。当串超长时，超过部分将被截断。 堆存储，通过程序语言提供的字符数组定义串的存储空间，事先不限定串的长度，在程序执行过程中动态地申请地址连续的串值的空间。 块链存储，使用链表存储串值，每个结点可以存储一个或多个字符，同时每个结点设置一个指针指向后继结点。 串的模式匹配：朴素的模式匹配法、KMP算法。6、数组：是定长线性表在维数上的扩张，即线性表中的每个元素又是一个线性表。N维数组是一种同构的数据结构，其每个数据元素类型相同，结构一致。 数组的特点： 数组元素数目固定。一旦定义了一个数组结构就不再有元素的增减变化； 数据元素具有相同的类型； 数据元素的下标关系受上下界的约束且下标有序。 数组的基本运算： 给定一组下标，存取相应的数据元素； 给定一组下标，修改相应的数据元素中的某个数据项的值。 数组的存储： 数组的固定结构适于使用顺序存储。对于数组，只要知道它的维数和长度，就可以为它分配存储空间。反之，只要给出一组下标就可以求出该数组元素的存储位置。就是说，在数组的顺序存储结构中，数据元素的位置是其下标的线性函数。 以行为主序； Loc(Aij) = Loc(Aij) + (i-1)*n + (j-1)*L 以列为主序； Loc(Aij) = Loc(Aij) + (j-1)*m + (i-1)*L 多维数组的顺序存储计算：例如3维数组A1.10, 5.8, -3.6，数组空间的起始位置是a，每个元素占4个存储单元，试以行为主存储和以列为主存储时给出数组元素Ai,j,k的存储地址。 解：理解上面给出的以行为主序和以列为主序的两个线性函数公式。把3维数组拆开计算，例如以行为主序时先将3维数组看成是有一个行和2个列的数组，算出此时以行为主占用了多少空间。然后再单独看两个列的组合Bj,k又会占用多少空间。前后结果相加就是这个3维数组元素在以行为主序存储时的地址。如下， 以行为主序时，Ai,j,k前面的元素个数是： (i-1)(8-5+1)(6-(-3)+1) + (j-5)(6-(-3)+1) + k-(-3) = 40i-40 + 10j-50 + k+3 = 40i + 10j + k -87 因此Ai,j,k的地址为a + (40i+10j+k-87)*4 以列为主序时，Ai,j,k的地址为a + (40k+10j+i+69)*47、特殊矩阵与稀疏矩阵，稀疏矩阵就是非零元素很少的矩阵，而特殊矩阵是非零元素分布有规律的一类矩阵。为节省空间，在存储它们时都使用压缩存储，特殊矩阵有压缩算法，稀疏矩阵使用三元组顺序表或使用十字链表存储矩阵元素。8、广义表的定义：是由零个或多个单元素或子表所组成的有限序列。广义表的长度是指广义表中元素的个数，深度是指广义表展开后所含的括号的最大层数。 广义表的基本运算：取表头head(LS)，非空广义表的第一个元素称为表头； 取表尾tail(LS)，非空广义表中除第一个元素之外，由其余元素构成的表称为表尾。表尾必定是一个表。 Head(LS)=a1, Tail(LS)=(a2,a3,.,an) 9、树的定义：树是n(n=0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余m个结点可分为m(m=0)个互不相交的有限集，其中每个子集合又都是一棵树，称为根结点的子树。 树的定义是递归的，树形结构具有明显的层次结构。 树的术语：双亲和孩子，兄弟，结点的度，叶子结点，内部结点，结点的层次，树的高度，有序树和无序树，森林。 树的基本操作是：先根遍历和后根遍历。 10、二叉树的定义：二叉树是另一种树形结构，它的特点是每个结点至多有两棵子树并且有左右之分，且左、右子树的次序不能颠倒。 满二叉树，若二叉树上每一层的结点数目都达到最大值，则称为满二叉树； 完全二叉树，若二叉树的除第H层以外，其余各层的结点数目达到了最大值，而第H层上的结点集中存放在左侧，则称为完全二叉树； 非完全二叉树，就是完全二叉树的相反情况。 二叉树的性质： 1）二叉树第i层(i=1)上至多有2(i-1)个结点； 2）深度为K的二叉树至多有2k -1 个结点(k=1)； 3）对任何一棵二叉树，若其终端结点个数为N0，度为2的结点个数为N2，则N0 = N2 + 1 ； 4）具有n个结点的完全二叉树的深度为log(2,n)+1; 5）对一棵有n个结点的完全二叉树的结点按层次自左至右进行编号，则对任一结点i (1=i1则其双亲为i/2; 若2in,，则结点i无左孩子，否则其左孩子为2i; 若2i+1n,则结点i无右孩子，否则其右孩子为2i+1; 例：一棵有124个叶结点的完全二叉树，最多有多少结点？ N0=N2+1 N=N0+N1+N2 N1=1 综合上面3个表达式可以求解。 例2：具有N个结点的满二叉树，其叶子结点个数为多少？ 设其深度为h，则: N0=2(h-1) N = 2h - 1 所以N0 = (n+1)/2 二叉树的存储结构： 二叉树的顺序存储结构，若采用二叉树的性质5对树中的结点进行编号，即树根结点的编号为1，若编号为i的结点存在左孩子，则其左孩子的编号为2i；若编号为i的结点存在右孩子，则其右孩子的编号为2i+1，这样利用数组元素的下标作为结点的编号，表示出结点间的关系。 二叉树的链式存储结构，二叉链表（有单向性）和三叉链表（有双向性）。 遍历二叉树，有4种方式：先序、中序、后序和层序遍历。 先序遍历二叉树的操作定义为：访问根结点；先序遍历根的左子树；先序遍历根的右子树。（若二叉树为空，则进行空操作） 中序遍历二叉树的操作定义为：中序遍历根的左子树；访问根结点；中序遍历根的右子树.（若二叉树为空，则进行空操作） 后序遍历二叉树的操作定义为：后序遍历根的左子树；后序遍历根的右子树；访问根结点。 层序遍历二叉树的操作定义为：从根结点开始，从或到右依次访问每层上的结点。 二叉树遍历思想的关键：首先在想象中把二叉树补齐为满二叉树，叶子结点也要被想象为有2个子结点。然后，画一条路线，从根出发，逆时针沿着二叉树的外缘移动，全程对每个结点均途经三次。若第一次经过时即访问，则是先序遍历；若是第二次经过结点时访问结点，则是中序遍历；若是第3次经过时访问则是后序遍历。这3种方法的路径相同，但结果不同。 遍历二叉树的基本操作就是，访问结点。-遍历二叉树实质上是按一定规则，将树中的结点排成一个线性序列。11、线索二叉树：对于有N个结点的二叉树的二叉链表存储表示，其中必有N+1个空指针。遍历时使结点中原本为空的左孩子指针或（和）右孩子指针指向结点的前驱或（和）后继，这样的处理称为对二叉树的线索化，指向前驱或后继的指针称为线索。加上线索的二叉树称为线索二叉树。 为了区分结点中的指针是孩子还是线索，在结点结构中增加标志域ltag, rtag。两个标志取值0，则lchild,rchild域分别指向左孩子和右孩子；两个标志取值1，则lchild,rchild域分别指向直接前驱和直接后继。 访问线索二叉树时，如何查找结点的前驱和后继？以中序线索二叉树为例，令P指向树中的某个结点， 当p-ltag = 0时，P的中序直接前驱一定是其左子树进行中序遍历得到的最后一个结点，也可以沿P的左子树根结点出发沿右孩子指针向下查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接前驱结点，也称为P的左子树中“最右下”的结点。 当P-rtag = 0时，P的中序直接后继一定是其右子树进行中序遍历得到的第一个结点， 也可以沿P的右子树根结点出发沿左孩子指针向上查找，直到找到一个没有右孩子的结点时为止，该结点就是P的直接后继结点，也称为P的右子树中“最左下”的结点。12、二叉树的应用：最优二叉树（又称霍夫曼树），是一种带权路径长度最短的树。 路径，是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。 树的路径长度，是从根到每一个叶子结点之间的路径长度之和。 结点的带权路径长度，是从该结点到树根之间的路径长度与该结点权的乘积。 树的带权路径长度，是树的所有叶子结点的带权路径长度之和，记为 WPL 。 如何构造最优二叉树？使用霍夫曼算法如下： 1）将给定的N个结点的权值构成N棵二叉树的集合F，其中每棵树Ti只有一个权为Wi的根结点，其左右子树为空； 2）在F中选取两棵根结点的权值最小的树作为左右子树，并新生成一个根结点，根结点的权值为左右子树的权值和； 3）从F中删除被取出的两棵树并将新生成的树放入F； 4）重复2，3步骤到只剩一棵树为止，这棵树就是最优二叉树。最优二叉树的形式不唯一，但其WPL值却是唯一确定的。 霍夫曼编码：若要设计长度不等的编码，则任一字符的编码都不是其他字符编码的前缀，这种编码称为“前缀编码”。要设计总长最短的二进制前缀编码，应以N种字符出现的频率作为权来构造一棵霍夫曼树，由此得到的二进制前缀编码称为霍夫曼编码。树的左右分枝分别标上0和1（或相反）。从根到叶子路径上的0，1组成的串就是每个字符的二进制编码。 13、树的存储结构 1）树的双亲表示法，用一组连续的存储单元存储树的结点，并在每个结点中附设一个指示器，指示其双亲结点在该存储结构中的位置； 2）树的孩子表示法，是在存储结构中用指针指出结点的每个孩子。要为树的每个结点的孩子建立一个链表，则N个结点的树具有N个单链表，这N个单链表的头指针又排成了一个线性表（头指针即树的存储结构中每个结点的指示器）。 将上两种方法结合起来可以形成树的双亲孩子表示法。 3）树的孩子兄弟表示法，是指用二叉链表表示树。在链表的结点中设置两个指针域，分别指向该结点的第一个孩子和下一个兄弟。 |firstchild| data |nextbrother| 若将树的孩子指针解释为左孩子、兄弟指针解释为右孩子，则可以得到这棵树的二叉树结构。14、树的遍历： 先根遍历； 后根遍历。 树进行先根遍历也就是对转换得到的二叉树进行先序遍历；对树进行后根遍历也就是对转换得到的二叉树进行中序遍历。 （先根遍历的顺序是：由根出发从左至右遍历每棵子树。后根遍历的顺序是从左至右从每棵子树的叶子结点向根的方向访问子树，最后访问根结点。） 15、森林的遍历： 先序遍历森林； 中序遍历森林。 先序遍历森林，若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵子树根结点的子树森林，再先序遍历除第一棵树之外的树所构成的森林。 中序遍历森林，若森林非空，中序遍历森林中第一棵树的子树森林，再访问第一棵树的根结点，再中序遍历除第一棵树以外的树所构成的森林。 16、树、森林和二叉树的转换 利用树的孩子兄弟表示法可以由一棵树转成唯一的一棵二叉树。 森林如何转换成二叉树呢？因为树根没有兄弟，所以树转换成二叉树后一定没有右子树，所以森林转换成二叉树的方法是： 1）先将森林中的每棵树全转成二叉树； 2）用第一棵树的根做新二叉树的根，第一棵树转为二叉树后得到的左子树做为新二叉树的左子树，第二棵树作为新二叉树的右子树，第三棵树作为新二叉树的右子树的右子树，依此类推，森林便转为了一棵二叉树。 17、图的定义：在数据结构中，图是一个由顶点集合和边集合构成的二元组，其中边表示顶点之间的关系。图的主要术语： 有向图，图中每条边都是有方向的，弧、弧尾、弧头； 无向图，图中的边是没有方向的，边； 无向完全图，图中的N个结点之间每两个结点间都有边，共有n(n-1)/2条边； 有向完全图，图中的N个结点之间每两个结点间都有方向相反的两条弧，共有n(n-1)条弧； 度、入度、出度，顶点v的度是指关联于该顶点的边的数目，记作D(v)。若是有向图则以该顶点为终点的有向边数目称为入度，从该顶点出发的有向边的数目称为出度，有向图的度是入库和出度的和。 路径，两个顶点之间由边组成的一条通路。若是有向图则路径也有方向。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路。若首尾顶点以外的顶点均不相同则是简单路径，若只有首尾顶点相同则称为简单回路。 子图，一个图的顶点集合与边集合都从属于另一个图，则称之为另一个图的子图； 连通图与连通分量，在无向图中若两个顶点之间有路径则称为这两个顶点是连通的。若无向图中任两个顶点间都是连通的则称其为连通图。该无向图的最大连通子图称为它的连通分量。 强连通图与强连通分量，是有向图的连通概念； 网，边（弧）带权值的图称为网； 生成树，是一个极小的连通子图，它包括图中的全部顶点，但只有构成一棵树的n-1条边； 有向树和生成森林，一个有向图恰有一个顶点的入度为0其它顶点的入度均为1，则这是一棵有向树。生成森林是一个有向图中的若干棵有向树组成，特点是含有全部顶点但只有足以构成若干棵不相交的有向树的弧。图的存储结构： 邻接矩阵表示法，用于表示图有顶点之间的关系。对于个有n个顶点的图G（V，E）来说，其邻接矩阵就是一个n阶方阵。依靠判断图的两顶点间是否存在边或弧来决定Aij=1或Aij=0；网的邻接矩阵，当两顶点间存在边或弧时Aij等于权值否则Aij等于无穷。 邻接链表表示法，为图的每个顶点建立一个单链表，单链表中的结点表示依附于相应顶点的边或弧，有表头结点和表结点两种结构类型。 图的遍历：深度优先搜索；广度优先搜索。一个类似于先根遍历，一个类似于层序遍历。生成树的概念：生成树是连通图的一个子图，它由全部顶点和一次遍历图所经过的边组成。图的生成树不惟一，按深度优先搜索得到深度优先生成树，按广度优先搜索得到广度优先生成树。一个非连通图，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，称为非连通图的生成树森林。18、最小生成树：连通网的边是带有权值的，将生成树的各边权值和称为生成树的权。其中权值最小的生成树称为最小生成树。构造最小生成树的两种算法： 普里母算法：以一个顶点集合U作为初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U至UV时为止。例如初始只给U一个顶点且边的集合TE；这种算法的时间复杂度为O（n2），因为它由顶点推算出的，所以适合于边稠密的网的最小生成树。 克鲁斯卡尔算法：假设连通网N（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T（V，），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。信此类推，直至T中所有顶点都在一个连通分量上为止。这种算法与顶点数无关，所以适合计算顶点多而边稀疏的网的最小生成树。 19、AOV网(active on vertex)：在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系，这样的网称为AOV网。在AOV网中不应出现有向环。拓朴排序：是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在Vj之前。拓朴排序的方法：在AOV网中选一个入度为0的顶点并输出它；从网中删除该顶点及与其有关的边；重复前两步至网中不存在入度为0的顶点为止。这样操作会有两种结果：一个是所有顶点已输出，也就是拓朴排序完成，说明网中不存在回路；另一个可能结果是尚有未输出的结点，剩余顶点均有前驱顶点，表明网中存在回路！也可以进行逆拓朴排序，即计算出度为0的顶点。拓朴算法的时间复杂度为O(n+e)。AOE网(active on edge)：，在带权有向图中，以事件表示顶点，以边表示活动，以边上的权值表示活动持续的时间，则这种网称为用边表示活动的网，简称AOE网。AOE网特点： 1）顶点所表示的事件是指该顶点的所有进入边所表示的活动已完成，所有发出边表示的活动可以开始的一种状态。 2）对一个工程来说，要有一个开始状态和一个结束状态，所以在AOE网中有一个入度为0的开始顶点，称为源点；有一个出度为0的结束顶点，称为汇点。AOE网中也不允许存在回路。 3）完成整个工程的时间是从开始顶点到结束顶点间的最长路径的长度（指该路径上的权值和）。活动的松驰时间：用活动的持续时间和该活动两侧的两个事件的关键路径时间，二者取差。关键路径：从源点到汇点的路径长度最长路径称为
展开阅读全文