《数据库学习笔记》由会员分享，可在线阅读，更多相关《数据库学习笔记（26页珍藏版）》请在金锄头文库上搜索。
1、集成电路的发展到目前为止,依次经历了SSI,MSI,LSI,VLSI四个阶段。微型计算机可采用不同的主振频率的CPU芯片。叵现有芯片的主振频率为8MHZ，也就是说它的主振周期为0.125US，（主振周期=1/主振频率）若已知每个机器周期平均含有4个主振周期，该机的平均指令执行速度为0.8MI/S，那么该机的平均指令周期为1.25US,（平均指令周期=1/平均指令执行速度）平均每个指令周期含有2.5个机器周期（平均机器周期数=平均指令周期/平均机器周期）。若改用主振周期为0.4US的CPU芯片，则计算机的平均指令执行速度为0.25MI/S（平均指令执行速度=1/平均指令周期=1/主振周期*平均机
2、器周期含主振周期数*机器周期数）。若要得到平均每秒40万次的指令执行速度，则应采用主振频率为4MHZ的CPU芯片。（平均指令执行速度=1/（1/主振频率）*主振周期数*机器周期数）单个磁头在向盘片的磁性涂层上写入数据时，是以串行方式写入的。虚拟存储管理系统的基础是程序的局部性理论。此理论的基本含义是程序执行时对主存的访问是不均匀的。局部性有两种表现形式：时间局部性和空间局部性。它们的意义分别为最近被访问的单元，很可能在不久的将来还要被访问和最近被访问的单位，很可能在它附近的单元还要被访问。根据局部性理论，DENNING提出了工作集的理论。设有四级流水线，分别完成取指、译码、运算、存数四步操作，
3、各步时间依次为30ns50ns,80ns和100ns。则流水线的操作周期应为100ns。（取平均时间取决于流水线最慢的一步）每步操作时间依次为60、100、50、70 ns。该流水线的操作周期应为100 ns。若有一小段程序需要用20条基本指令完成则得到第一条指令结果400ns，结果完成该段程序需2300 ns。在流水线结构的计算机中，频繁执行条件转移指令时会严重影响机器的效率。当有中断请求发生时，若采用不精确断点法，则将不仅影响中断响应时间，还影响程序的正确执行。内存按字节编址，地址从A4000H到CBFFFH，共有160K字节（CBFFFH-A4000H=27FFFH=160K）。若用存储
4、容量为32K*8BIT的存储器芯片构成该内存，至少需要5片。（160K/32K=5）若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别是T取指=T分析=2NS，T执行=1NS，则100条指令全部执行完毕需203NS（T=100*2+3=203）在单指令流多数据流计算机SIMD中，各处理单元必须以同步方式，在同一时间内执行同一条指令。容量为64场面的CACHE采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为19位（4096*128=219字），主存区号应为6位。（4096/64=32）甲通过计算机网络给乙发消息，表示甲
5、同意与乙签订合同，不久后甲不承认发过该消息。为了防止这种情况的出现，应该在计算机网络中采取数字签名技术硬磁盘存储器的道存储密度是指沿磁盘半径方向上单位长度毫米或英寸上的磁道数，而不同磁道上的位密度是靠近圆心的密度大。中央处理器CPU中的控制器是由基本的硬件部件构成的。外设接口部件不是构成控制器的部件。中央处理CPU主要由运算器和控制器组成，控制器中程序计数器保存了程序的地址。中央处理CPU的主要功能不包括传输数据。使CACHE命中率最高的替换算法是替换最近最少使用的块算法LRU。一般来说CACHE的功能全部由硬件实现。某32位计算机的CACHE容量为16KB，CACHE块的大小为16B，若主存
6、与CACHE的地址映射采用直接映射方式，则主存在地址为1234E8F8的单元装入的CACHE地址为10 1000 1111 1000平均命中率最高的是近期最少使用LRU算法。设某流水线计算机主存的读/写时间为100ns,有一个指令和数据合一的CACHE已知该CACHE的读/写时间为10 ns，取指令的命中率为98%，取数的命中率为95%。在执行某类程序时，约有1/5指令需要存/取一个操作数。假设指令流水线在任何时间都不阻塞，则设置CACHE后，每条指令的平均访存时间约为12 ns。（4/5*10*98%+100*2%+1/5*1095%+100*5%=12 ns）相联存储器的访问方式是按内容访
7、问。利用并行处理技术可以缩短计算机的处理时间，所谓并行性是指在同一时间完成两种或两种以上工作。可以采用多种措施来提高计算机系统的并行性，它们可分成三类即资源重复，资源共享和时间重叠。提供专门用途的一类并行处理机亦称阵列处理机以SIMD方式工作，它适用于矩阵运算。多处理机是目前性能较高计算机的基本结构，它的并行任务的派生是需要专门的指令来表示程序中并发关系和控制并发执行。中断响应时间是指从发出中断请求到进入中断处理所用的时间。虚拟存储器对应用程序员透明而对系统程序员不透明.虚拟存储器一定是多级存储器,而多级存储器不一定是虚拟存储器.程序中10%的指令占用了90%的执行时间,这一规则被称为局部性原
8、理。建立存储层次体系依据的原理是局部性原理。可随机读写且只要不断电则基本存储信息就可一直保存的称为SRAM可随机读写但即便在不断电的情况下其存储的信息也要定时刷新才不致丢失的称为DRAM所存信息由生产厂家用掩膜技术写好后就无法再改变的称为ROM通过紫外线照射后可擦除所有信息然后重新写入新的信息并可多次进行的称为EPROM通过电信号可在数秒钟内快速删除全部信息但不能进行字节级别删除操作的称为Flash Memory存储器读写速率越高每位的成本也越高,存储容量也越大,解决这一问题的方法是采用多级存储体系.为了大幅度提高处理器的速度,当前处理器都采用了指令级并行处理技术如超级标量Superscale
9、r它是指采用多个处理部件多条流水线并行执行.流水线组织是实现指令并行的基本技术影响流水线连续流动的因素除数据相关性、转移相关性能、功能部件冲突和中断系统.要发挥流水线的效率还必须重点改进编译系统在RISC设计中对转移相关性一般采用延迟转移方法解决计算机执行程序所需时间P，可用P=ICPIT来估计，其中I是程序经编译后的机器指令数，CPI是执行每条指令所需的平均机器周期数，T为每个机器周期的时间。RISC计算机是采用虽增加I，但更减少CPI来提高机器的速度。它的指令系统具有指令种类少的特点。指令控制部件的构建，CISC更适于采用微程序控制，而RISC更知于采用硬布线控制逻辑。RISC机器又通过采
10、用大量的寄存器加快处理器的数据处理速度。RISC的指令集使编译优化工作更简单。访问内存需要的机器周期比较少不是RISC的特点。计算机总线在机内各部件之间传输信息.在同一时刻只可以有一个设备发数据,一个或多个设备收数据.系统总线由三总分构成.它们是地址总线、控制总线、数据总线。早期的微机，普遍采用ISA总线，它适合16位字长的数据处理为了适应增加字长和扩大寻址空间的需要，出现了EISA总线它与ISA总线兼容。目前在奔腾机上普遍使用，数据吞吐量可达2Gbit/s的局部总线是PCI总线。在流水线操作时，每个阶段的执行时间应取3个阶段执行时间中的最大值。SCSI是一种通用的系统级标准输入/输出接口，其
11、中FASTSCSI-II标准的数据宽度为16位，数据传送率达20MB/S。大容量的辅助存储器采用RAID磁盘阵列。RAID是工业标准共有6级。其中RAIDI是镜像磁盘阵列，具有最高的安全性；RAID5是无独立校验盘的奇偶校验码磁盘阵列；RAID2是采用纠错海明码的磁盘阵列；RAID0则是既无冗余也无校验的磁盘阵列，它采用了数据分块技术，具有专长最高的I/O性能和磁盘空间利用率，比较容易管理，但没有容错能力。RAID是一种经济的磁盘冗余阵列，它采用智能控制器和多磁盘驱动器以提高数据传输率。RAID与主机连接较普遍使用工业标准接口为SCSI假脱机打印与脱机打印机有相似之处，但实际上其输出结果首先送
12、往外部存储器保存，然后再在适当的时候将其调出打印出来。整个过程是由操作系统控制的。数据加密是一种保证数据安全性的方法，数据解密则是逆变换，即由密文求出明文。密码体制可分为对称密钥和公开密钥两大类，例如常用的DES属于对称密钥，而RSA则属于公开密钥。DES的密钥长度为64位。破密都面临多种不同的问题，其从易到难排列依次为选择明文、已知明文、仅知密文。虚拟存储器的作用是允许程序直接访问比内存更大的地址空间。它通常使用硬盘作为它一个主要组成部分。对它的高度方法与CACHE基本相似，即把要经常访问的数据驻留在高速存储器中，因为使用虚拟存储器，指令执行时必须先进行虚、实地址交换。在虚拟存储系统中常使用
13、相联存储器进行管理，它是寄存器寻址的。线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素。线性链表中为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映像。存储直接后继存储位置的域为指针域。设T是正则二叉树，它具有6片树叶，那么树T的高度最多可以是6，最小可以是4；树T的内结点数是4。如果T又是Huffman最优树，且各片树叶的数分别是1，2，3，4，5，6，则最优树T的非树叶结点的数之和是51，数为1的树叶的高度是5。（注：树的根结点高度为1）当n
14、=2并且n为奇数时，无向完全图Kn都是欧拉图。为偶数时是哈密尔顿图。递归算法的执行过程，一般来说，可先后分成递推和回归两个阶段。若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用递推算法，因为递推的效率比递归高。贪婪法是一种不求最优，只求满意的算法。关键路径是指AOE（Activity On Edge）网中从源泉点到汇点（结束顶点）的最长路径。一个具有767个结点的完全二叉树，其叶子结点个数为384。若一个具有n个结点，K条边的非连通无向图是一个森林（nk），则该森林中必有n-k棵树。若G是一个具有36条边的非连通无向图，不含自回路和多重边，则图G至少有10个顶点。将两个条度为N的递
15、增有序表归并成一个长度为2N的递增有序表，最少需要进行关键字比较N次。在数据压缩编码的应用中，哈夫曼算法可以用来构造具有前缀码的二叉树，这是一种采用了递推的算法。一棵查找二驻树，其结点ABCDEF依次存放在一个起始地址为n假字地址以字节为单位顺序编号的连续区域中，每个结点占4个字节，前二个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E，则它的一种可能的前序遍历为EACBDF相应的层次遍历为EAFCBD在以上两种遍历情况下，结点C的左指针LC的存放地址为N+10，LC的内容为N+4。结点A的右指针RA的内容为N+8。二叉树的前序、中序和后序遍历最适合采用递归程序来实现
16、。查找树中，由根结点到所有其他结点的路径长度的总和称为内部路径长度，而使上述路径长度总和达到最小的树称为丰满树，它一定是平衡树。在关于树的叙述中，只有M阶B-树中，具有K个后件的结点，必含有K-1个键值正确在一棵完全二叉树中，其根的序号为1，log2p=log2q可判定序号为p和q的两个结点是否在同一层。堆是一种数据结构，10，18，15，20，50，80，30，60是堆。小顶堆从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。若广义表L=（1，2，3），则L的长度和深度分别为1和2若对27个元素只进行三趟多路归并排离，则选取的归并路数为3。设按顺序分配的线性表含有N个元素。若在任何位置插入和删除元素的概率相同，则插入一个元素移动结点的平均次数为N/2次，删除一个元素移动结点的平均次数为（N-1）/2次。线性表采用链式存储时，其地址连续与否均可。在内部排序方法
