三级数据库背诵资料第一章 计算机根底知识“存储程序原理为根底，由运算器、存储器、控制器、输入设备和输出设备等五大部件组成。2、计算机指令系统：系列计算机：指令系统向下兼容。复杂指令系统计算机：CISC Complex Instruction Set Computer精简指令系统计算机：RISC Reduced Instruction Set Computer指令系统的类型：数据传送类指令、算术逻辑类指令和判定控制类指令。指令系统的寻址方式：立即寻址立即数寻址，指令中直接给出操作数。存放器寻址：操作数在存放器中。直接寻址：指令中直接给出操作数地址。存放器间接寻址：存放器给出操作数地址。存放器相对寻址：指令中给出操作数的地址偏移量3、微型处理器分类：通用微处理器、嵌入式微处理器和数字信号处理器等4、总线：PCI：不依附具体处理器的局部总线。USB：通用串行总线。1394总线：FireWire，为家用电器研制的一种高速串行总线。1394总线在数字视频设备数字摄像机中广泛应用。5、计算机的技术指标：运算速度MIPS(每秒百万条指令)影响计算机运算速度的因素很多，主要是CPU的主频和存储器的存取周期。存储器容量：根本单位B(Byte) 1KB=1024Byte 1MB=1024KB 1GB=1024MB 1TB=1024GB数据传输率：根本单位bps(每秒传输多少位) 1Kbps=103bps 1Mbps=103Kbps 1Gbps=103Mbps6、计算机中的信息表示非数字信息的表示：ASCII码 汉字的表示：三类代码体系：输入码，如：拼音码、五笔字形码等；机内码；交换码,如GB2312-80；7、计算机网络根底计算机网络的根本特征：资源共享。广域网与广域网的互联是通过路由器实现的。传输技术分为： 播送式网络通过一条公共信道实现点-点式网络通过存储转发实现。采用分组存储转发与路由选择是点-点式网络与播送网络的重要区别之一按规模分类：局域网LAN、城域网MAN、广域网WAN广域网远程网以下特点：1 适应大容量与突发性通信的要求。2 适应综合业务效劳的要求。3 开放的设备接口与标准化的协议。4 完善的通信效劳与网络管理。几种常见的广域网的特点：X.25：建立在速率低、误码率高的电缆介质上，X.25协议包括过失控制、流量控制和拥塞控制等，由通信子网完成,有时间延迟。FR帧中继：建立在速率高、误码率低的光纤上，对X.25协议进行简化，过失控制由用户终端完成。B-ISDN宽带综合业务数字网、N-ISDN窄带综合业务数字网ATM异步传输模式，一种数据传输与分组交换技术，能满足多媒体应用的高速率与低延迟的要求，具有线路交换实时性好和分组交换灵活性好的双重优点。各种城域网建设方案有几个相同点：传输介质采用光纤，交换接点采用基于IP交换的高速路由交换机或ATM交换机，在体系结构上采用核心交换层，业务会聚层与接入层三层模式。城域网MAN介于广域网与局域网之间的一种高速网络。8、网络协议为三局部：(1)语法,即用户数据与控制信息的结构和格式;(2)语义,即需要发出何种控制信息,以及完成的动作与做出的响应;(3)时序,即对事件实现顺序的详细说明.9、Internet的结构和组成协议：TCP/IP协议组TCP/IP参考模型可以分为：应用层，传输层TCP、UDP协议，互连层IP协议，主机-网络层应用层协议分为:a、依赖于面向连接的TCP协议：主要有: 文件传送协议FTP、电子邮件协议SMTP以及超文本传输协议 等。b、依赖于面向连接的UDP协议：主要有简单网络管理协议SNMP;简单文件传输协议TFTP。c、既依赖于TCP协议，也可以依赖于UDP协议：域名效劳DNS等。d、网络终端协议：Telnet；网络文件系统 NFS；路由信息协议RIP。10、域名与IP地址：IP地址由网络地址和机器地址组成：IP地址长度为32位，X.X.X.X表示，X为8为，表示0-255,(点分十进制地址。主要分为A类网络地址7位，机器地址24位、B类网络地址14位，机器地址16位、C类网络地址21位，机器地址8位；11、Internet 提供的效劳1WWW效劳：采用客户机/效劳器模式a、超文本和超媒体是WWW的信息组织形式b、HTML(超文本标记语言,网页语言)和 超文本传输协议是WWW工作的根底c、URL统一资源定位器：查找主页。由三局部组成：协议类型，主机名和文件名及路径(2)电子邮件效劳：电子邮件发送接收协议：发送协议，简单邮件传送协议SMTP，接收协议，可以使用邮局协议POP3和交互式邮件存取协议Interactive Mail Access Protocol，IMAP电子邮件内容协议 MIME(Multipurpose Internet Mail Extensions)，可以传送图像、声音等多媒体信息12、Internet的接入：ISPInternet Service Provider，ISPInternet效劳提供商局部网接入、 线接入ADSL(Asymmetrical Digital Subscriber Loop)非对称数字用户环路，基于 线，上、下行传输速率不同，上行可达1Mbps；下行可达8Mbps。13信息平安根底信息平安包括四方面内容： 信息保密、 完整性、 可用性、 可控性1密码体制：加密或密码体制由5局部组成：明文空间明文的集合、密文空间密文集合、加密密钥空间、解密密钥空间、加密和解密算法集单钥加密体制分为两类：流密码明文逐位加密和分组密码明文分组，逐组加密。密钥的分配和存储是最关键和困难的问题。2信息认证有关认证的实用技术中，主要的有数字签名技术、身份识别技术和信息的完整性校验技术消息认证3恶意软件：特洛依木马、登录陷阱网络钓鱼，虚假页面、逻辑炸弹在程序中设置的破环代码后门陷阱在程序中设置的绕开登录进入系统、缓冲区溢出、僵尸网络：一对多进行控制网络防病毒软件：允许用户设置3中扫描方式： 实时扫描、预置扫描、人工扫描4网络平安 网络平安效劳的主要内容：平安攻击、平安机制、平安效劳网络效劳攻击分类： 效劳攻击和非效劳攻击效劳攻击：对效劳器发起攻击，丧失效劳能力，比方对WWW效劳器攻击，主页被篡改。拒绝效劳DoS或DdoS分布式拒绝效劳。 非效劳攻击：对通信设备攻击，使设备瘫痪网络信息攻击： 攻击类型：截获、窃听、篡改和伪造等14、操作系统平安操作系统的平安措施一般可以从隔离、分层和内控3个方面来进行考虑。隔离可分为：注意后面的解释物理隔离：使不同平安要求的进程使用不同物理实体。时间隔离：使不同进程在不同时间运行。逻辑隔离：限制程序存取。密码隔离：进程以其他进程不知的方式隐蔽数据和计算。操作系统平安措施：访问控制、存储保护及文件保护与保密。访问控制：认证、访问权限、文件保护、审计。存储保护：防止地址越界、防止操作越权。第二章 数据结构算法1、数据：数据的根本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算3、主要的数据存储方式：顺序存储结构逻辑和物理相邻，存储密度大和链式存储结构顺序存储结构：顺序存储计算公式 LiL0(i1)K 顺序结构可以进行随机存取；插人、删除运算会引起相应节点的大量移动 链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小 b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点4、顺序表：一般情况下，假设长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2插入和n-1/2删除。5、链表：线性链表单链表和双向链表等等和非线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。注意结点的插入和删除操作6、栈：“后进先出(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等7、队列：“先进先出线性表。应用：树的层次遍历8、串：由零个或多个字符组成的有限序列。9、多维数组的顺序存储：10、稀疏矩阵的存储：下三角矩阵顺序存储其他常见的存储方法还有三元组法和十字链表法11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表12、树型结构：非线性结构。常用的树型结构有树和二叉树。二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。13、树森林与二叉树之间的转换要会转换14、二叉树和树的周游遍历 二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN) 周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游 树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同 按广度优先方式就是层次次序周游15、二叉树的存储和线索 二叉树的存储结构：二叉树的llink一rlink法存储表示 线索二叉树：在有n个节点的二叉树的且llink - rlink法存储表示中，必定有n+1个空指针域16、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。17、查找：1顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)2二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+13分块查找：先是块间查找，然后块内查找。4散列表哈希表Hash的存储和查找：处理冲突的方法：开地址法线性探测法、拉链法等负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数即表长二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度Olog2nB树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。18、排序 直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序第三章 操作系统1、操作系统概念：一是管理系统中的各种资源；二是给用户提供一个友好的界面。2、操作系统包括以下3个根本特征：并发性、共享性、随机性。3、功能：进程管理、存储管理、作业管理、文件管理、设备管理4、操作系统类型1批处理操作系统：成批、多道，交互性不强。系统目标：提高资源利用率、作业吞吐量和作业流程自动化。2分时操作系统：多路、交互性、