三级数据库基础知识汇编.pdf

三级数据库 基础知识汇编 1 第1章基础知识.71.1 知识点.71.1.1 计算机发展阶段.71.1.2 计算机系统的组成.7LL3计算机应用领域.81.1.4 计算机分类.81.L5计算机语言.81.1.6 计算机软件.91.1.7 计算机网络.91.1.8 数据通信基本原理.101.1.9 网络体系结构与TC尸P协议.101.1.10 信息安全基础.1.1.11 操作系统安全.1.2重点难点.121.2.1 计算机网络的组成及其拓扑结构.121*2.2 勺.1.2.3 计算机网络与分布式系统.13124计算机局域网.13125计算机病毒及其特征.15第2章数据结构与算法.162.1知识点.162.1.1 数据结构的基本概念.162.1.2 算法的基本概念.172.1.3 线性表.172.1.4 线性表的存储.172.1.5 线性表的运算.182.1.6 数组.182.1.7 稀疏矩阵.192.1.8 广义表.192.1.9 树.192.L11二 叉树的存储结构.202.1.12 二叉树和树的遍历.212.1.13 排序.212.1.14 查找.212.2重点难点.212.2.1 数据的逻辑结构.212.2.2 数据存储结构.222.2.3 二叉树的性质.242.2.4 二叉树和树的遍历.25225二叉树的转换.272.2.6 二叉排序树.2722.7 3 树和 5+树.2832.2.8 排序.292.2.9 查找.33第3章操作系统.343.1 知识点.343.1.1 操作系统的概念.343.1.2 操作系统的功能.343.1.3 操作系统的类型.343.1.4 批处理操作系统.343.1.5 分时操作系统.353.1.6 实时操作系统.353.1.7 网络操作系统.353.1.8 分布式操作系统.353.1.9 进程的基本概念.353.1.10 线程的基本概念.353.1.11 存储管理.363.1.12 存储器分类.363.1.13 虚拟内存.363.1.14 设备管理.363.2 重点难点.373.2.1 操作系统的概念.373.2.2 进程间的通信.373.2.3 进程间的同步与互斥.3743.2.4 信号量和尸操作.373.2.5 消息缓冲通信.383.2.6 进程与线程的比较.383.2.7 单一连续的存储管理.393.2.8 分区存储管理.393.2.9 页式存储管理.393.2.10 页面淘汰算法.403.2.11 段页式存储管理.403.2.12 缓冲技术.403.2.13 文件和文件目录.403.2.14 网络环境卜质力dows安全特性.413.2.15 计算机病毒的特性.41第4章 数据库技术基础.424.1 知识点.424.1.1 信息、数据与数据处理.424.1.2 数据管理技术的发展.424.1.3 数据库(.DB,DataBase).434.1.4 数据库管理系统(DBMS,DataBase Management System).434.1.5 数据库系统(DBS,DataBase System).434/6数据模型.434.1.7 数据模型的要素.4354.1.8 信息世界中的基本概念.434.1.9 概念模型E-R模型.444.1.10 常用数据结构模型.444.1.11 数据库系统中模式的概念.444.1.12 数据库系统的三级模式结构.444.1.13 数据库的二层映像.444.2 重点难点.454.2.1 数据库的基本概念.454.2.2 数据管理技术的发展.454.2.3 数据库系统的用户.47424数据模型.484.1.5 常用的数据结构模型.484.1.6 数据库系统的模式结构.49第5章 关系数据库系统.505.1 知识点.5051/关系数据库系统.505/2关系数据模型.505.1.3 关系模型的基本术语.515.1.4 关系的形式定义.515.1.5 关系数据库对关系的限定.525.1.6 关系模型的完整性约束.525.1.7 实体完整性规则.5265.1.8 参照完整性规则.525.1.9 用户定义的完整性.525.1.10 关系代数.535.1.11 传统的集合运算.535.1.12 专门的关系运算.535.2 重点难点.54521关系模型的数据结构.545.2.2 关系数据库对关系的限定.565.2.3 关系模型完整性规则.566.2.4用完整性规则检查数据库操作.585.2.5关系代数.59第6章 关系数据库标准语言SQL.636.1 知识点.636.1.1 结构化查询语言SQL.636/2 SQL数据库体系结构.636.1.3 SQL的数据定义.636.1.4 基本表.646.1.5 索弓1.656.1.6 视图.666.1.7S.QL的数据操纵.666.1.8查 询语句.666.1.9修 改语句.6676.1.10S.QL的数据控制.676.1.11 嵌入式 S0.676.2 重点难点.686.2.1 数据查询.687.2.2 数据修改.796.2.3 视图.816.2.4 嵌入式SQL.84第7章关系数据库规范化理论与数据库设计.867.1 知识点.867.1.1 关系模式的设计问题.867.1.2 数据依赖.867.1.3 函数依赖.867.1.4 多值依赖.877.1.5 函数依赖的逻辑蕴含.877.1.6 码.877.1.7 Armstrong 公理系统.877.1.8 范式.877.1.9 关系模式的分解.887.1.10 关系模式分解的等价标准.887.1.11 数据库设计.897.1.12 需求分析.897.L13概念结构设计.8987.1.14 逻辑结构设计.897.1.15 物理设计.907.1.16 数据库的实现与维护.907.2重点难点.907.2.1 函数依赖.907.2.3 关系模式的范式.927.2.5 数据库设计的目标、内容和方法.947.2.6 数据库设计的步骤.96第8章 数据库应用开发工具.988.1 知识点.988.1.1 数据库管理系统概述.988.1.2 数据库管理系统的结构和运行过程.988.1.3 Oracle数据库系统.998.1.4 IBM DB2数据库系统.998.1.5S.YBASE 数据库系统.1008.1.6 Microsoft SQL Server 数据库系统.1018.2 重点难点.1028.2.1 新一代数据库应用开发工具概念.1028.2.2 应用开发工具的选择.1038.2.3 CASE 工具-Po werDesigner.1038.2.5 应用开发工具-PowerBuilder.1048.2.6 企业应用开发平台-UN/E4CE.1049第1章基础知识1.1 知识点1.1.1 计算机发展阶段以计算机物理器件的变革作为标志，计算机的发展经历了四代：第一代（1946年1958年）是电子管计算机。代表机型有：ENIAC IBM650（小型机）、IBM709（大型机）等。第二代（1959年1964年）是晶体管计算机。代表机型有：IBM7090、IBM7094、CDC7600 等。第三代（1965年1970年）是集成电路计算机。代表机型有：IBM360 系列、富士通F 230系列等。第四代（1971年至今）是大规模和超大规模集成电路计算机。这个 时期，计算机的类型除了小型、中型、大型机之外，开始向巨型机和微型机两个方面发 展。1.1.2 计算机系统的组成一个完整的计算机系统包括硬件系统和软件系统两个部分。硬件系统计算机硬件是组成计算机物理设备的总称，它们由各种器件和电子线 路组成，是计算10机完成工作的物质基础。计算机硬件由5个部分组成：运算器、控制器、存储器、输入设备和 输出设备。（1）运算器。运算器又称算术逻辑单元（ALU）,它接收由存储器 送来的二进制代码，并对代码进行算术和逻辑运算。文本框：考纲要求1.计算机系统的组成和应用领域。2.计算机软件基础知识3.计算机网络的基础知识和应用知识4.信息安全的基本概念（2）控制器。控制器是用于控制计算机的各个部件，并按照从存储器取出的指令，向各部件发出操作指令，同时，它接收由各部件传来的反馈信息，并对 这些信息进行分析，决定下一步操作。（3）存储器。存储器是存放源数据、中间数据、程序以及最终结果的部件。它在计算机运行过程中，一方面不停的向运算器提供数据，另一方面又保存从 运算器送回的计算结果，存储器还保存程序，且不断的取出指令传送给控制器。（4）输入设备。输入设备接收用户提交给计算机的源程序、数据及11各种信息，并把它们转换成为二进制代码，传送给存储器。（5）输出设备。输出设备的功能是将计算机内部的二进制信息转换 为人和设备能识别的信息。通常将运算器和控制器合称为中央处理器（CP U）；中央处理器和内 存储器合成为主机；输入设备、输出设备和外存储器合称为外部设备，外部设备通过接口 线路与主机相连。软件系统没有配置任何软件的计算机称为裸机，只有配置了相关系统软件的系统才是完整的计算机系统。软件分为系统软件和应用软件，系统软件是在计算机上的第一层应用 功能扩展。1.1.3 计算机应用领域当前计算机的应用已经遍布人类社会各个领域，按照其所涉及的技术 内容，计算机应用可以分为几种类型。科学和工程计算科学计算也称数值计算。在科学试验和工程设计过程中，经常会遇到 各种数学问题需12要求解，利用计算机并应用数值方法进行求解是解决这类问题的主要途径，这种应用被称为科学和工程计算，其特点是计算量大，而逻辑关系相对简单。数据和信息处理数据处理是指对数据的收集、存储、加工、分析和传送的全过程。过程控制过程控制是生产自动化的重要技术内容和手段，它是由计算机对所采集到的数据按一定方法经过计算，然后输出到指定执行机构去控制生产的过程。辅助设计计算机辅助设计不仅应用于产品和工程辅助设计，而且还还包括辅助制造、辅助测试、辅助教学以及其他多方面的内容。人工智能计算机模拟人脑的过程称为人工智能，人工智能是利用计算机来模拟人的思维的过程，并利用计算机程序来实现这些过程。1.1.4 计算机分类根据计算机在信息处理系统中的地位和作用，并且考虑到计算机分类的演变过程和可能的发展趋势，IEEE提出一种分类方法将计算机分成六类：巨型计算机(Supercomputer)o巨型计算机也称为超级计算机，它 13采用大规模并行处理的体系结构，具有极强的运算能力。巨型计算机通常应用在尖端科 技研究、重大工程项目研究等领域。世界上仅有少数几个国家研究开发巨型计算机。小巨型机(MiniSupercomputer)。小巨型计算机也称为小型超级计 算机，它的性能接近巨型计算机，但使用了更加先进的大规模集成电路与制造技术，体 积小、成本低。价格比巨型计算机便宜许多。大型机(Mainframe)。大型机或称主干机、主机。它的运算速度快、处理能力强、存储容量大、可扩充性好、通信联网功能完善，并且有丰富的系统软件 和应用软件。大型计算机一般落户于大中型企事业单位，由专人管理维护。超级小型计算机(SuperMinicomputer)。超级小型计算机为中小企 业所拥有。工作站(Workstatloii)。工作站主要应用于有特殊要求的专业领域，如图形工作站等。它具有高速运算能力和很强的图形处理功能。个人计算机(Personal Computer)0个人计算机也称为个人电脑(P C 机)或微机。个人计算机因为其性能价格比高而得以快速普及和广泛应用。个人计算14机可分为台式机和便携机两大类。1.1.5 计算机语言计算机语言计算机语言是一类面向计算机的人工语言，它是进行程序运行的工具，又称为程序设计语言。现有的程序设计语言可分为3类：机器语言、汇编语言、高 级语言。机器语言机器语言是最初级的依赖于硬件的计算机语言。机器语言直接在计算机硬件级上执行，所以效率比较高，能充分发挥计算机高速计算的能力。汇编语言用有助于记忆的符号和地址来表示指令的程序设计语言叫做汇编语言。也称为符号语言。用汇编语言编写的程序与机器语言相比，除较直观和易记忆外，仍然存在工作量大，面向机器、无通用性等缺点，所以，汇编语言又称作“低级语言”。高级语言高级语言是一类人工设计的语言，它对具体的算法进行描述，所以又 称作为算法语言。高级语言是一类面向问题的程序设计语言，且独立于计算机的硬件，15其表达方式接近于被描述的问题，易于人们的理解和掌握。1.1.6 计算机软件计算机软件可以分为系统软件和应用软件两种。系统软件系统软件一般包括：操作系统、语言处理程序和数据库管理系统以及 服务程序等。操作系统是系统软件的核心，它管理计算机软件、硬件资源，调度用户作业程序和处理各种中断，从而保证计算机各个部分协调有效的工作。语言处理程序的任务，就是将各种高级语言编写的源程序翻译成机器语言表示的目标程序。语言处理程序按照处理的方式不同，可以分为解释型程序与编 译型程序两大类。解释型程序的处理采用边解释边执行的方法，不产生目标程序，称为对 源程序的解释执行。编译型程序先将源程序翻译成为目标程序才能够执行，称为对源程序 的编译执行。数据库管理系统是对计算机中所存放的大量数据进行组织、管理、查 询并提供一定处理功能的大型系统软件。16服务型程序是一类辅助性的程序，它提供各种运行所需的服务。应用程序应用软件是为解决实际应用问题所编写的软件的总称，它涉及到计算机应用的所有领域，各种科学和工程计算的软件和软件包、各种管理软件、各种辅助 设计软件和过程控制软件都属于应用软件的范围。1.1.7 计算机网络计算机网络的功能计算机网络具有下列基本功能：（1）资源共享。其目的是让网络上的用户都能使用网络中的程序、设备，尤其是数据，而不管资源和用户在什么地方。换言之，用户即使是在本地也能使用 千里之外的数据。（2）高可靠性。依靠可替代的资源来提供高可靠性。例如，所有文 件可以在两台或三台计算机上进行备份，如果其中之一由于硬件故障不能使用，可使用 其他备份。（3）可用性。当工作负荷增大时，只要增加更多的处理器，就能逐 步改善系统的性能。对集中式主机而言，一旦系统能力达到极限，就必须用更强大的主机 替代它，而这样做代17价大，对用户的影响也大。(4)实现分布式的信息处理。对于综合的大型问题，可以采用合适的算法，将任务分散到网络中不同的计算机上进行分布处理。多台微型机通过网络可连成具有高性能的计算机系统，使它具有解决复杂问题的能力，而费用大为降低。(5)提供强大的通信手段。通过网络，两个或多个生活在不同地方的人可以共同起草报告。当某人对联机文档的某处作了修改时，其他人员可以立即看到 这个变更，而不必花几天的时间等待信件。这种速度上的提高使得广泛分布的群体之间的 合作变得很容易。网络的分类计算机网络的分类方法很多，可以从不同的角度进行分类。(1)从网络的交换功能进行分类：电路交换网、报文交换网、分组交换网和ATM网。(2)从网络的拓扑结构进行分类：星型、环型、总线型和网状型。(3)从网络的作用范围进行分类：广域网、局域网和城域网或市域 网。1.1.8 数据通信基本原理所谓的数据通信是指传统的通信技术通过使用计算机来实现信 息的传输、交换、存储和处理。现代通信系统由数据传输系统和数据 18处理系统两部分组成。数据传输系统又称为通信子系统或通信子网，其主要任务是实现不同数据终端设备之间的数据传输；数据处理 系统又称为资源子系统或资源子网，它是由许多数据终端设备组成，负责提供信息、接受信息和处理信息。物理信道按照传输介质的类型可以把信道分为有线信道和无线 信道。传输介质是数据传输系统中收方和发方之间的物理路径。有多种物理介质可用于实际 传输，每一种物理介质在带宽、延迟、成本和安装维护难度上都不相同。介质可以大致分 为有线介质和无线介质。其中有线介质包括双绞线、同轴电缆、光纤等；无线信道包括微 波信道和卫星信道。所谓基带，就是指信号所固有的基本频带，基带 信号通常是由数据直接转换成的、未经频率调制的波形。与基带信号 频谱相适应的信道称为基带信道。将数字设备（如计算机）发出的数 字信号（即基带信号）直接在信道中进行传输，称为基带传输。所谓频带传输就是把数字信号调制成音频信号后在电话线路上 传输，到达接收端时再把音频信号解调还原成原来的数字信号。在频带传输中，要求在发送 端安装调制器，在接收端安装解调器。19用一对传输线同时传送几路信息，称为多路复用。多路复用的典 型方式有两类，即频分多路复用和时分多路复用。通过多路复用，可以提高线路的利用率。所谓频分多路复用，就是将传输线路的总频带划分成若干个子频 带，每一个子频带作为一条逻辑信道提供给一对终端使用。频分多路 适用于传输模拟信号，多用于电话系统。波分多路复用是在光纤信道上使用频分多路复用的一个变种。在这种 方法中，两条光纤连到一个棱柱，每条光纤的能量处于不同的波段。两束光通过棱柱,合成到一条共享的光纤上，传送到远方的目的地，随后再将它们分解开。任何两个终端间的通信业务量分布总是非均匀的，建立固定的点到点连接从线路利用效率来说很不经济，特别是当终端数目增加时，要在每对终端间建立起固定的点到点线路就更显得既无必要也不切合实际。解决这个问题的方法就是将各地的 终端连到一个具有某种交换能力的交换网络。这个交换网络包括若干条通信线路和交换 机，由交换机根据每次通信的要求和网络运行状态动态地选择通信路径。目前在计算机网络 中使用的交换技术有如下几种：电路交换、报文交换、分组交换、帧中继和异步转移模式20（ATM）o1.1.9 网络体系结构与TCP/IP协议计算机网络的分层及其所使用的协议的集合，就是所谓的网络体系结 构。具体地说，网络体系结构即是层次与协议的集合。体系结构的描述必须包含足够的信息，使实现者可以用来为每一层编写软件和设计硬件，并使之符合有关协议。网络协议是关于双方通信过程中的一组约定规则，用来建立通信关系，进行数据交换。完整的通信协议相当复杂。为了简化协议的设计，便于协议的实现及 维护，大多数网络都将协议按层（Layer）或级（Level）的方式组织。每层都向它的上层 提供一定的服务，而将如何实现服务的细节对上层屏蔽，即低层协议对高层而言是透明的。相邻两层之间为层间接口。国际标准化组织制定了一个开放系统互连参考模型（OSI）。该标准规定，整个网络的通信功能划分为7个层次。每一层完成系统信息交换所需的部分功 能，通过层间的接口与其相邻层连接，从而实现不同系统之间、不同结点之间的信息交换。TCP/IP（Transmission Control P rotoc ol/Intemet P rotoc ol）传输控制协21议/网际协议最初由美国国防部高级研究计划局(Department of Defenc e Advanc edResearc h P rojec t Agenc y,DARP A)在1969年提出，并把它用在ARP ANET中。随着ARP ANET在规模和作用范围的日益扩大，TCP/IP协议也逐渐完善，最终成为Internet的基础，并且应用范围也愈来愈广，几乎已成为广域网和局域网内的标准网络协议。TCP/IP是个协议集，根据OSI的七层理论，TCP/IP可以分为四层。分别是接口层、网络层、传输层和应用层。1.1.10 信息安全基础信息安全信息安全的目的，就是要防止非法的攻击和病毒的传播，以保证计算机系统和通信系统的正常运行；就是要保证信息的保密性、完整性、可用性和可控性；就是保证电子信息的有效性。信息保密信息保密是信息安全的重要方面，为保密而进行加密是防止破译信息系统中机密信息的技术手段。加密的办法就是使用数学方法来重新组织信息，使除合22法接收者外的其他任何人要看懂变化后的数据或信息是非常困难或不可能的。加密前的信息称为明文，加密后的信息称为密文。信息认证信息认证是信息安全的另一个重要方面，信息认证，首先是验证信息的发送者的真实性，即不是假冒的；其次是验证信息的完整性，即验证信息在传送或存储过程中未被篡改、重放或延迟等。认证是防止对系统进行主动进攻的重要技术手段。主要的信息认证技术有：数字签名技术、身份识别技术和信息完整性校验技术等。密钥管理密钥管理影响到密码系统的安全，而且还会涉及到系统的可靠性、有效性和经济性。密钥管理包括密钥的产生、存储、装入、分配、保护、丢失、销毁以及保密等内容。其中解决密钥的分配和存储是最关键的技术。1.1.11 操作系统安全操作系统应提供的安全服务服务包括：内存保护、文件保护、存取控制和存取鉴别等，以防止由于用户程序的缺陷而损害系统。23操作系统安全方法一般操作系统的安全措施可从隔离、分层、和内控3个方面考虑。隔 离是操作系统安全保障的措施之一，它又可以分为：物理隔离、时间隔离、逻辑隔离 和密码隔离。物理隔离是指使不同安全要求的进程使用不同的物理实体。时间隔离是指使不同的进程在不同的时间运行。逻辑隔离是指限制程序的存取，是操作系统不能存取允许范围以外的 实体。密码隔离是指进程以其他进程不了解的方式隐蔽数据和计算。操作系统的安全措施访问控制是保障信息安全的有效措施，访问控制的目的是：（1）保护存储在计算机上的需要保护的信息秘密性，通过对访问进行控制，使机密信息保密。（2）保护存储在计算机内的个人信息保密性。（3）维护计算机内信息的完整性。拒绝非授权用户访问，减少非法用户对重要文件进行修改的机会。（4）减少病毒感染的机会，从而减少和延缓病毒的传播。存储保护是对安全操作系统的基本要求。存储保护保证系统内的任务 互不干扰。在多24道程序系统中，内存中既有操作系统，也有用户程序，为避免内存中程序相互干扰，必须对内存中的程序和数据进行保护，采用的措施一般有：防止地址越界，规定每个进程都具有相对对立的进程空间，当进程运行时地址越界，可能侵犯其他进程的空间，从而影响其他进程的正常工作。也可能侵 犯操作系统，导致系统混乱，因此必须对进程所产生的地址进行检查，发现地址越界时产 生中断，再由操作系统进行处理。防止操作越权，对于多个进程共享的公共区域，每个进程都享有访问权，如有些进程可执行写操作，而其他进程只能进行读操作，因此需要对公共区域的 访问加以限制和检查。文件保护措施是为了防止由于误操作而对文件造成破坏，文件保密措 施是为了防止未经授权的用户对文件的进行访问。1.2重点难点1.2.1 计算机网络的组成及其拓扑结构计算机网络拓扑的定义计算机网络设计首先需要解决计算机网络在满足响应时间、吞吐量和 可靠性的条件下25通过选择合适的线路、线路通信容量、接入方式，实现整个网络的结构合理，成本低廉，为了解决复杂的网络结构设计，人们提出了网络拓扑的概念。拓扑学是几何学的一个分支，它从图论演化而来。拓扑首先需要将实体抽象成与现实中大小、形状无关的点，将他们之间的线路抽象成线，进而研究点、线、面之间的关系。计算机网络拓扑是通过网中结点与通信线路时间的几何关系表示网络结构，反映出各个试题之间的结构关系。拓扑结构设计是计算机网络设计的第一步，也是 实现各种网络协议的基础，他对网络性能、系统可靠性和通信费用都有重大的影响。计算 机网络拓扑结构主要是指通信子网的拓扑结构。网络拓扑的分类方法网络拓扑可以根据通信子网中通信信道类型分为两类：(1)点一点线路通信子网的拓扑。(2)广播信道通信子网的拓扑。在点一点线路的通信子网中，每条物理线路连接一对结点，它有4中 基本的拓扑构型：星型、环型，树型，网状型。采用广播信道的通信子网中，一个公共的通信信道被多个网络结点共26享，它也有4中基本拓扑构型：总线型，树型，环型，无线通讯和卫星通信型。在星型结构中，结点通过点一点通信线路与中心结点相连，中心结点控制整个网络的通信，任何两个结点之间的通信都要通过中心结点。这种拓扑结构具 有结构简单，容易实现，方便管理的特点，但是由于网络中心负责整个网络的可靠性通信,所以中心结点的故障将导致整个网络的瘫痪。在环型结构中，结点通过点一点通信线路连接成闭合环路，环中的数据将沿着一个方向往逐个往下一站发送。这种结构比较简单，传输延时稳定，但是环中的每个结点与通信结点之间的线路都是整个环路中的瓶颈，所以环中的任何一个节点出现线路故障，都可能导致整个网络瘫痪。为了保证环路正常工作，需要复杂的控制和维护 技术。树型结构是星型结构的一个扩展。在树型结构中节点按层次进行连接，信息交换主要发生在上、下节点之间。网状拓扑结构又称为无规则型。在这种结构中，结点之间的连接是任 意的，可以没有27任何规律。网状结构的特点是可靠性高，网内的任何一个结点的故障都不会影响到整个网络的正常运行。但是它的结构复杂，必须要采用合适的路由选择算法和介质访问控制方式及流量控制。1.2.2 计算机网络的构成计算机网络主要由多个计算机及通信设备构成，具体如下：(1)各种类型的计算机。(2)网络适配器。网络适配器提供通信网络与计算机相连的接口。(3)网络传输介质，包括双绞线、光纤以及无线通信等。(4)共享的外部设备。(5)局部网络通信设备，如集线器、中继器。(6)网络互联设备，如调制解调器、网桥、路由器、交换机。(7)网络软件。1.2.3 计算机网络与分布式系统计算机网络与分布式系统(Distributed System)是两个不同的概念。用户透明性观点定义计算机网络“存在一个能为用户自动管理计算机资源的网络操作系统，由它调用完成拥护任务所需要的资源，而整个网络对用户是透明的。”它所描述的就是一个分布式系统。分布式系统有5个特征：28（1）系统拥有多种通用的物理和逻辑资源，可以动态的给他们分配 任务。（2）系统中分散的物理和逻辑资源通过计算机网络实现信息交换。（3）系统中存在一个以全局方式管理系统资源的分布式操作系统。（4）系统中联网的各计算机既合作又自治。（5）系统内部结构对用户是完全透明的。从以上的讨论可以看出分布式系统和计算机网络系统的共同点是：多数分布式系统是建立在计算机网络之上的，所以分布式系统与计算机网络在物理结构 上是基本相同的。他们的区别在于：分布式操作系统的设计思想和网络操作系统是不同 的，这决定了它们在结构、工作方式和功能上也不同。网络操作系统要求网络用户在 使用网络资源时首先必须了解网络资源，网络用户必须知道网络中各个计算机的功能与配 置、软件资源、网络文件结构等情况，在网络中如果用户要读一个共享文件时，用户必须 知道这个文件放在那一台计算机的那一个目录下；分布式操作系统是以全局方式管理系统 资源的，它可以为用户任务调度网络资源，并且调度过程是“透明”的。当用户提交一个 作业时，分布式操作29系统能够根据需要在系统中选择最合适的处理器，将用户的作业提交到该处理程序，在处理器完成作业后，将结果传给用户。在这个过程中，用户并不会意识到有多个处理器的存在，这个系统是就像是一个处理器一样。所以，分布式系统与计算机网络的最主要的区别不在于它们的物理结构，而是在系统软件上。分布式系统是一个建立在网络之上的软件系统，这种软件系统保证了系统高度的一致性和透明性，分布式系统不需要用户关心网络环境中的资源分布情况和各个联网计算机的性能差异，系统的作业管理和文件管理对用户是完全透明的。1.2.4 计算机局域网局域网(LAN)是在小范围内通过传输介质及一定的接口电路将许多数据设备互相连接起来进行数据通信、资源共享的计算机网络系统。数据设备可以是个人计算机、小型计算机、中型计算机或大型计算机，也可以是终端或外围设备(如打印机)，但主要是个人计算机。将数据设备互连成局域网，可以实现软、硬件资源共享，如共享贵重的激光打印机、30绘图仪、共享数据库及复杂的软件包等，也便于各种设备间及时交换 数据，实现信息的实时采集、处理及报表输出，对办公自动化及管理决策提供必要的支持。局域网的特点局域网具有以下几个方面的特点：（1）覆盖的地理范围不大，一般属于一个单位所有。（2）通常采用专用的传输线路（也有用宽带、无线等传输方式），数据传输速率高。（3）拓扑结构简单，容易实现。一般常采用总线型、星型或环型结 构。（4）与广域网相比，LAN软件规范设计多限制在物理层、数据链路 层和传输层。（5）通信延迟时间较低，可靠性较好。（6）能按广播方式或组播方式进行通信。从原理上讲，决定局域网性能和费用的主要技术问题是网络拓扑结 构、传输介质及通道访问控制策略。与OSI参考模型相比，局域网只相当于OSI的最低两层物理层和数 据链路层。物理层用于计算机的物理连接以及数据在媒体上的传输。局域网的数据链路 层分为两个子层：媒体接入控制或媒体访问控制子层和逻辑链路控制子层。由于局域网不31存在路由选择问题，因此局域网可以没有网络层。局域网的分类局域网的分类可以从拓扑结构、传输介质和通道访问控制方式三个方 面进行。按网络拓扑结构分类，局域网可分为星型、树型、环型、总线型和混 合型几种。星型网属于集中控制方式，协议简单，易于监测和管理，扩充比较方便，一个工作站出现故障不会波及全网，但交换中心是全网的核心，其可靠性极为重要。在环型拓扑结构中，通过点到点链路将接口处理机联接成一个闭合环路，每个接口处理机都与两条链路相联，而工作站则直接与接口处理机连接。环型网 络是一种分布式控制方式，适用于实时传输要求较高的场合，性能受网络负载影响较小，由于采用遍绕环的传播方式，避免了复杂的中央控制和路由选择功能，协议相对简单。但 对环上结点和链路的可靠性要求较高，如果一个结点出现故障，则会导致全网无法工作。一般须在网络结点接头处采用旁路措施将故障结点从网上隔离；而对链路故障，只有换新 线或排除故障后才能32使环型网恢复工作。总线型拓扑结构是一种非常流行且广为采用的一种结构。在该结构 中，每个工作站均通过一个接口电路挂在一条总线传输介质上，共享一条公共的总线进 行数据传输。总线型局域网适于实时要求不高、通信距离短、负载较轻的场合。它扩充方 便，可靠性较高，属分散控制。但其网络性能受负载变化影响很大，重负载时总线上报文 碰撞的机会增大，网络性能降低。局域网中的传输介质种类很多，一般有双绞线、同轴电缆、光纤等有 线介质，还有诸如电磁波、微波、卫星通信、无线通信、激光等空间介质。如果从使用频带看，又可分为基带和宽带两种传输介质。基带传输时，通道中为数字信号，整个通 道的频谱均为一路数字信号所占用。宽带传输通道中的信号为模拟信号，通道可以采用频 率划分方式进行通道的多路复用，多采用75W的同轴电缆作为传输介质，容易实现多种用途的通道复用，例如图像或语音传输，也可用于数字传输。通道访问技术是局域网的关键技术之一。所谓通道访问技术，就是研33究如何有效地利用通信信道问题，目的是使网络如何适应数据传输的突发性特点。采 用恰当的策略，可以提高通信信道的利用率，减少数据传输中的时延，提高网络的吞吐率。网络的性能在很大程度上都与网络所采用的通道访问技术有关。通道访问控制也叫通道 访问协议。以太网以太网（Ethernet）是常用的局域网之一，它是一种公共总线型局域 网，适用于小型机和微型机连网。在以太网中，所有的节点通过专门的网卡（网络适配 器）连接到一条总线上，并采用广播方式进行通信而无需路由功能。以太网在1972年由Xerox（施乐）公司首先开始研制，1975年Xerox 公司和Stanford（斯坦福）大学合作推出了 Ethernet产品。IEEE 802.3 国际标准是在Ethernet标准的基础上制定的。现在，根据不同的物理介质又发展出多种子标准，形成了 一个 IEEE 802.3 标准系列。Ethernet中的计算机相互通信时采用的是载波侦听多路访问/冲突检 测的方法，即CSMA/CD（Carrier Sense Multiple Ac c ess/Collision Detec tion），它在 34轻负载情况下具有较高的网络传输效率。Ethernet的组网非常灵活和简便，既可以使用细缆 和粗缆组成总线型局域网，也可以使用3类无屏蔽双绞线组成星型网络（即10BASE-T技 术），还可以将同轴电缆的总线型网络与UTP双绞线的星型网络混合起来。Ethernet是目前 国内外应用最为广泛的10Mbps局域网。以太网大多采用集线器和双绞线进行组网。集线器（Hub）有共享式 和交换式之分。共享式是一种无源耦合器，具有多个端口，支持节点通过双绞线接入Hub,虽然物理上看上去是多级星形结构，但实际的媒体访问控制方式仍然是总线方式，联结在总线上的所有设备共享该总线的带宽。交换式Hub则不同，联结在总线上的每一个设备，各自独享一定的带宽。F DDI网络F DDI网络又称为光纤分布式数字接口网。F DDI网主要用于主机与其外围设备之间、主机之间、各宽带工作站间的互连，又可作为主干网与IEEE 802局域网互连。此外F DDI-II作35为F DDI的改进型，除了处理常规数据外，还具有电路交换能力，可 以传输声音、图像等综合数据。由于采用光纤作为传输介质，F DDI具有高数据传输率、抗电磁干扰和信号传输衰减的特点。另一方面，F DDI也具有环形网重负载时效率高、覆 盖面大、具有实时和优先访问等优点。F DDI对同步和异步数据传输都适用，能处理数字 电话和图像的实时业务，主要采用分组交换，也允许用电路交换。此外F DDI还具有重构 特性，可靠性较高。1.2.5 计算机病毒及其特征计算机病毒的定义计算机病毒是一种特殊的具有破坏性的计算机程序，它具有自我复制 能力，可以通过非授权入侵而隐藏在可执行程序或数据文件中，当计算机运行时病毒 能够把自身精确拷贝或者有修改的拷贝到其他程序体中，影响和破坏正常程序的正确性。计算机病毒的特征计算机病毒是一类特殊的程序，它与其他程序一样可以存储和执行，但它具有其他程序没有的特性。（1）传染性。计算机病毒的传染性是指病毒具有把自身复制到其他 36程序中的特性。（2）破坏性。破坏性包括占用计算机CP U时间；占用内存空间；破 坏数据和文件；干扰系统的正常运行。（3）潜伏性。计算机病毒的潜伏性是指计算机病毒具有依附其他程 序而存在的能力。（4）隐蔽性。计算机病毒的隐藏性表现在两个方面。一是传染的隐 蔽性，大多数病毒在进行传染的时候速度很快，一般没有外部表现，不容易被发现。二 是病毒存在的隐蔽性，病毒大多潜伏在正常的程序之中，在其发作或产生破坏作用之前，一 般不容易被发现。（5）可激发性。在一定条件下，通过外界刺激可使病毒活跃起来，激发是一种条件控制，由病毒的设定。1.2.6 计算机病毒的危害、分类和防治计算机病毒的破坏作用病毒造成的危害是严重和多方面的，主要表现在以下几个方面：（1）破坏磁盘文件分配表，使用户在磁盘上的文件无法使用。（2）删除磁盘上的可执行文件或数据文件。（3）修改或破坏文件中的数据。（4）将非法的数据写入内存参数区，造成死机甚至引起系统崩溃。37（5）改变磁盘分配表，造成数据写入错误。（6）在磁盘上产生坏的扇区，使磁盘空间减少。（7）更改或重写磁盘卷标。（8）因病毒程序自身在系统中的多次复制而使内存可用空间减少。（9）对整个磁盘或磁盘的特定磁道或扇区进行格式化。（10）在系统中产生新的信息。（11）改变系统的正常运行过程。计算机病毒的结构计算机病毒程序主要包括三个部分：一是传染部分（传染模块）；二 是表现和破坏部分；三是触发部分（触发模块）。计算机病毒的分类（1）按传染的方式可分为：引导型病毒、一般应用程序型、系统程 序型。（2）按寄生的方式可分为：操作系统型病毒、外壳型病毒、入侵型 病毒、源码型病毒。计算机病毒的预防计算机病毒以预防为主，防止病毒的入侵要比入侵后再去发现和排除 要好的多。主要的预防措施有：（1）采用抗病毒的硬件。（2）计算机硬件安全措施。38(3)社会措施。第2章数据结构与算法2.1 知识点2.1.1 数据结构的基本概念数据是描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。数据对象是具有相同性质的数据元素的集合。通常，一个数据对象中的数据元素不是孤立的，而是彼此之间存在着一定的联系，这种联系就是数据结构。数据对象中数据元素之间的联系需要在对数据进行存储和加工中反映出来，因此，数据结构概念一般包括三方面的内容：数据之间的逻辑关系、数据在计算机中的存储方式、