数据库学习笔记

集成电路的发展到目前为止,依次经历了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/主振周期*平均机器周期含主振周期数*机器周期数）。若要得到平均每秒40万次的指令执行速度，则应采用主振频率为4MHZ的CPU芯片。（平均指令执行速度=1/{（1/主振频率）*主振周期数*机器周期数}） 单个磁头在向盘片的磁性涂层上写入数据时，是以串行方式写入的。 虚拟存储管理系统的基础是程序的局部性理论。此理论的基本含义是程序执行时对主存的访问是不均匀的。局部性有两种表现形式：时间局部性和空间局部性。它们的意义分别为最近被访问的单元，很可能在不久的将来还要被访问和最近被访问的单位，很可能在它附近的单元还要被访问。根据局部性理论，DENNING提出了工作集的理论。 设有四级流水线，分别完成取指、译码、运算、存数四步操作，各步时间依次为30ns\50ns,80ns和100ns。则流水线的操作周期应为100ns。（取平均时间取决于流水线最慢的一步）每步操作时间依次为60、100、50、70 ns。该流水线的操作周期应为100 ns。若有一小段程序需要用20条基本指令完成则得到第一条指令结果400ns，结果完成该段程序需2300 ns。在流水线结构的计算机中，频繁执行条件转移指令时会严重影响机器的效率。当有中断请求发生时，若采用不精确断点法，则将不仅影响中断响应时间，还影响程序的正确执行。 内存按字节编址，地址从A4000H到CBFFFH，共有160K字节（CBFFFH-A4000H=27FFFH=160K）。若用存储容量为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） 甲通过计算机网络给乙发消息，表示甲同意与乙签订，不久后甲不承认发过该消息。为了防止这种情况的出现，应该在计算机网络中采取数字签名技术 硬磁盘存储器的道存储密度是指沿磁盘半径方向上单位长度毫米或英寸上的磁道数，而不同磁道上的位密度是靠近圆心的密度大。 中央处理器CPU中的控制器是由基本的硬件部件构成的。外设接口部件不是构成控制器的部件。中央处理CPU主要由运算器和控制器组成，控制器中程序计数器保存了程序的地址。中央处理CPU的主要功能不包括传输数据。 使CACHE命中率最高的替换算法是替换最近最少使用的块算法LRU。一般来说CACHE的功能全部由硬件实现。某32位计算机的CACHE容量为16KB，CACHE块的大小为16B，若主存与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） 相联存储器的访问方式是按内容访问。 利用并行处理技术可以缩短计算机的处理时间，所谓并行性是指在同一时间完成两种或两种以上工作。可以采用多种措施来提高计算机系统的并行性，它们可分成三类即资源重复，资源共享和时间重叠。提供专门用途的一类并行处理机亦称阵列处理机以SIMD方式工作，它适用于矩阵运算。多处理机是目前性能较高计算机的基本结构，它的并行任务的派生是需要专门的指令来表示程序中并发关系和控制并发执行。 中断响应时间是指从发出中断请求到进入中断处理所用的时间。 虚拟存储器对应用程序员透明而对系统程序员不透明.虚拟存储器一定是多级存储器,而多级存储器不一定是虚拟存储器. 程序中10%的指令占用了90%的执行时间,这一规则被称为局部性原理。建立存储层次体系依据的原理是局部性原理。 可随机读写且只要不断电则基本存储信息就可一直保存的称为SRAM可随机读写但即便在不断电的情况下其存储的信息也要定时刷新才不致丢失的称为DRAM所存信息由生产厂家用掩膜技术写好后就无法再改变的称为ROM通过紫外线照射后可擦除所有信息然后重新写入新的信息并可多次进行的称为EPROM通过电信号可在数秒钟内快速删除全部信息但不能进行字节级别删除操作的称为Flash Memory 存储器读写速率越高每位的成本也越高,存储容量也越大,解决这一问题的方法是采用多级存储体系. 为了大幅度提高处理器的速度,当前处理器都采用了指令级并行处理技术如超级标量Superscaler它是指采用多个处理部件多条流水线并行执行.流水线组织是实现指令并行的基本技术影响流水线连续流动的因素除数据相关性、转移相关性能、功能部件冲突和中断系统.要发挥流水线的效率还必须重点改进编译系统在RISC中对转移相关性一般采用延迟转移方法解决 计算机执行程序所需时间P，可用P=I·CPI·T来估计，其中I是程序经编译后的机器指令数，CPI是执行每条指令所需的平均机器周期数，T为每个机器周期的时间。RISC计算机是采用虽增加I，但更减少CPI来提高机器的速度。它的指令系统具有指令种类少的特点。指令控制部件的构建，CISC更适于采用微程序控制，而RISC更知于采用硬布线控制逻辑。RISC机器又通过采用大量的寄存器加快处理器的数据处理速度。RISC的指令集使编译优化工作更简单。访问内存需要的机器周期比较少不是RISC的特点。 计算机总线在机内各部件之间传输信息.在同一时刻只可以有一个设备发数据,一个或多个设备收数据.系统总线由三总分构成.它们是地址总线、控制总线、数据总线。早期的微机，普遍采用ISA总线，它适合16位字长的数据处理为了适应增加字长和扩大寻址空间的需要，出现了EISA总线它与ISA总线兼容。目前在奔腾机上普遍使用，数据吞吐量可达2Gbit/s的局部总线是PCI总线。 在流水线操作时，每个阶段的执行时间应取3个阶段执行时间中的最大值。 SCSI是一种通用的系统级输入/输出接口，其中FASTSCSI-II标准的数据宽度为16位，数据传送率达20MB/S。大容量的辅助存储器采用RAID磁盘阵列。RAID是工业标准共有6级。其中RAIDI是镜像磁盘阵列，具有最高的安全性；RAID5是无独立校验盘的奇偶校验码磁盘阵列；RAID2是采用纠错海明码的磁盘阵列；RAID0则是既无冗余也无校验的磁盘阵列，它采用了数据分块技术，具有专长最高的I/O性能和磁盘空间利用率，比较容易管理，但没有容错能力。RAID是一种经济的磁盘冗余阵列，它采用智能控制器和多磁盘驱动器以提高数据传输率。RAID与主机连接较普遍使用工业标准接口为SCSI假脱机打印与脱机打印机有相似之处，但实际上其输出结果首先送往外部存储器保存，然后再在适当的时候将其调出打印出来。整个过程是由操作系统控制的。 数据加密是一种保证数据安全性的方法，数据解密则是逆变换，即由密文求出明文。密码体制可分为对称密钥和公开密钥两大类，例如常用的DES属于对称密钥，而RSA则属于公开密钥。DES的密钥长度为64位。破密都面临多种不同的问题，其从易到难排列依次为选择明文、已知明文、仅知密文。 虚拟存储器的作用是允许程序直接访问比内存更大的地址空间。它通常使用硬盘作为它一个主要组成部分。对它的高度方法与CACHE基本相似，即把要经常访问的数据驻留在高速存储器中，因为使用虚拟存储器，指令执行时必须先进行虚、实地址交换。在虚拟存储系统中常使用相联存储器进行管理，它是寄存器寻址的。 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素。线性链表中为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映像。存储直接后继存储位置的域为指针域。 设T是正则二叉树，它具有6片树叶，那么树T的高度最多可以是6，最小可以是4；树T的内结点数是4。如果T又是Huffman最优树，且各片树叶的数分别是1，2，3，4，5，6，则最优树T的非树叶结点的数之和是51，数为1的树叶的高度是5。（注：树的根结点高度为1） 当n>=2并且n为奇数时，无向完全图Kn都是欧拉图。为偶数时是哈密尔顿图。 递归算法的执行过程，一般来说，可先后分成递推和回归两个阶段。若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用递推算法，因为递推的效率比递归高。贪婪法是一种不求最优，只求满意的算法。 关键路径是指AOE（Activity On Edge）网中从源泉点到汇点（结束顶点）的最长路径。 一个具有767个结点的完全二叉树，其叶子结点个数为384。 若一个具有n个结点，K条边的非连通无向图是一个森林（n>k），则该森林中必有n-k棵树。 若G是一个具有36条边的非连通无向图，不含自回路和多重边，则图G至少有10个顶点。 将两个条度为N的递增有序表归并成一个长度为2N的递增有序表，最少需要进行关键字比较N次。 在数据压缩编码的应用中，哈夫曼算法可以用来构造具有前缀码的二叉树，这是一种采用了递推的算法。 一棵查找二驻树，其结点ABCDEF依次存放在一个起始地址为n假字地址以字节为单位顺序编号的连续区域中，每个结点占4个字节，前二个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E，则它的一种可能的前序遍历为EACBDF相应的层次遍历为EAFCBD在以上两种遍历情况下，结点C的左指针LC的存放地址为N+10，LC的内容为N+4。结点A的右指针RA的内容为N+8。 二叉树的前序、中序和后序遍历最适合采用递归程序来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为内部路径长度，而使上述路径长度总和达到最小的树称为丰满树，它一定是平衡树。在关于树的叙述中，只有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次。线性表采用链式存储时，其地址连续与否均可。 在内部排序方法中，平均比较次数最少的是快速排序，要求内存容量最少的是堆排序。SHELL排序是不稳定的排序方法。 用二分查找法的查找速度比用顺序查找法的查找速度不一定谁快谁慢。当N<50时折半的查找不优于顺序查找。 散列法存储的基本思想是根据关键码值来决定存储地址，冲突指的是不同关键码值对应相同的存储地址，负载因子越大，发生冲突的可能性就越大。处理冲突的两类主要方法是链地址法和开放地址法。 计算机算法是指解决某一问题的有限运算，算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是：空间复杂性和时间复杂性。算法在发生非法操作时可以作出处理的特性称为健状性。 线性表的两种结构是顺序结构和非顺序结构，若线性表最常用的操作是存取第I个元素的值，则采用顺序表存储方式最节省时间。若琏表的最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用带头结点的双向循环链表存储方式最节省运算时间。 队列的特点是先进先出。设循环队列用Q[N]来存放，其头尾指针分别为F和R，则队满条件是F=（R+1）%N，队列中的元素个数为（R-F+N）%N。 有N个结点的完全二叉树的深度是log2n+1，该树中有（n+1）/2个叶子结点。 已知某二叉树的结点的后序序列是BDECA，中序序列是BADCE则前序序列是ABCDE。 若一个叶子是某二叉树中序的最后一个结点，则必是该二叉树的中序最后一个结点是对的，若某二叉树的先序序列和后序序列正好相反，则该二叉树是高度等于其结点数，该二叉树一定满足其中只有一个叶子结点。 将树转换成二叉树，其对应的二叉树的根结点的右孩子为空，树的后先序遍历等同于该树对应的二叉树的中序遍历序列。 对于一个N个顶的无向图，它最多有N-1条边。 快速排序是交换排序。它所采用的策略是分治的方法。用快速排序算法对线性表排序，若选择表中第一个元素作为分界元素，当待排序的数据已有序时，排序效率最差，其时间复杂度为O（N2）。 关键码序列94,31,53,23,16,72是一个堆，堆排序是一种选择排序，它的一个基本问题是如何建堆，常用的建堆方法是1964年Floyd提出的筛选法。对含N个元素的序列进行排序时，堆排序的时间复杂性是O（nlog2n），所需的附加的存储结点是O（1）。 多道程序设计为了提高计算机的的处理机和外部设备的利用率,把多个程序同时放入主存储器在宏观上并行运行。并发程序设计把一个程序划分成若干个可同时执行的程序模块的设计方法。分时操作系统多个用户在终端设备上以交互方式输入、排错和控制其程序的运行。分布式操作系统多台计算机组成的一个系统，这些计算机之间可以通过通信来交换信息；互相之间无主次之分；它们共享系统资源；程序由系统中的全部或部分计算机协同执行。它是管理上述计算机系统的操作系统。实时操作系统有一类操作系统的系统响应时间的重要性超过系统资源的利用率，它被广泛地应用于卫星控制、导弹发射、飞机飞行控制、飞机订票业务等领域。 在操作系统中，解决进程间的同步、互斥问题的一种方法是使用信号量。同步是指进程间具有的一定逻辑关系。互斥是指进程间在使用共享资源方面的约束关系。对于信号量可以做P操作和V操作。P操作用于阻塞进程，V操作用于释放进程。程序中的P操作和V操作应谨慎检查，保证其使用的正确性，否则执行时可能发生死锁。 进程管理是操作系统的核心，如果设计不妥，会出现一种尴尬的局面死锁。处于死锁状态的进程不能继续运行又占用了系统资源，从而会阻碍其他进程的运行。对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于死锁的避免，破坏环路等待条件属于死锁的预防，而剥夺资源是死锁的解除的基本方法。死锁的检测是在需要的时刻执行，以发现系统是否于安全状态。 操作系统组织直接文件的关键在于采用什么方法进行从记录键值到磁盘物理地址的变换，例如可以采取散列函数的方法。 在操作系统中，处理机管理部分由作业管理和进程管理两部分组成。作业管理把作业流分成提交、后备、运行、完成四个状态。进程管理把进程分成就绪、执行、阻塞三个基本状态。作业从提交状态到后备状态由假脱机处理程序完成，从后备状态到运行状态由作业调度程序完成。进程从就绪状态到执行状态由进程调度程序完成，从执行状态到阻塞状态或就绪状态由交通控制程序完成，用户进程的优先进程是由作业调度程序建立的。 Netware是局域网操作系统，它的系统容错SFT分为三级，其中第三级系统容错采用文件服务器镜像。Netware是在局域网的基础上建立的网络操作系统，因此它不同于一般网络协议所需的完整的协议和通信传输功能，它有一个核心部份，是系统核心调度程序。 在UNIX中增加进程的唯一途径是通过调用fork()分时系统的为UNIX。UNIX的文件目录系统采用可装卸式多级树型目录结构。 UNIX操作系统是采用模块接口法方法实现结构设计。在UNIX操作系统中，当用户执行如下命令：link(“/user/include/myfile.sh”,”/usr/userwang/youfile.sh”)则文件名”/usr/userwang/youfile.sh”存放在userwang目录文件中。 假调在系统中一个文件有两个名字，它与一个文件保存有两个副本的区别是：前者改变与某个名字相联系的文件时，另一个名字相连的文件也改变；后者的另一个副本不改变。 一台PC计算机系统启动时，首先执行的是BIOS引导程序，然后加载操作系统，在设备管理中，虚拟设备的引入和实现是为了充分利用设备，提高系统效率，采用Spooling技术，利用磁盘设备来模拟低速设备输入机或打印机的工作。 因争用资源产生死锁的必要条件是互斥、循环等待、不可抢占和保持与等待。对于缓冲池大量缓冲区的管理，采用生产者-消费者方式解决同步或互斥时，通常需要用3个信号量。 后进先出调度算法不是页面调度算法。，采用总是把程序装入主存中最大的空闲区域的算法称为最差适应算法。 在文件存储设备管理中，有三类常用的空闲块管理方法，即位图向量法、空闲块链表链接法和索引法。 进程是操作系统中可以并行工作的基本单位，也是核心调度及资源分配的最小单位，它由程序、数据和PCB组成，它与程序的重要区别之一是它有状态，而程序没有。在SMP系统中，操作系统还提供了线程机制，它是处理器分配的最小单位。 进程是操作系统中的一个重要概念。进程是一个具有一定独立功能的程序在某个数据集合上的一次运行活动。进程是一个动态的概念，而程序是一个静态的概念。进程的最基本状态有运行、就绪、阻塞。在一个单处理机中，若有6个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有5个。 虚拟存储管理系统的基础是程序的局部性理论。这个理论的基本含义是当程序执行时往往会不均匀地访问内存。程序的局部性表现在时间局部性和空间局部性上。时间局部性是指最近被访问的存储单元可能马上又要被访问。空间局部性是指马上被访问的单元，而其附近的单元也可能马上被访问。根据这个理论，Denning提出了工作集理论。工作集是进程运行时被频繁也访问的页面集合。在进程运行时，如果它的工作页面都在主存储器内，能够使用进程有效地运行，否则会出现频繁的页面调入/调出现象。 操作系统主要的性能参数有吞吐率、周转时间和利用率等。吞吐率指的是单位时间内系统处理的作业量。周转时间指的是从作业或命令的输入到其结束的间隔时间，在分析性能时常用其倒数。利用率指的是一个给定时间内，系统的一个指定成分被使用的时间比例。操作系统的保护主要包括存储保护、程序保护和文件与数据保护等。采用存取权限控制方法时，任一需保护的客体，都对应于一个二元组（主体、允许动作），其中主体表示用户或进程或用户组或进程组。 当进程已用完该进程的可用主存空间时，选择淘汰哪些页或段，腾出空间放置调入的页或段的方法称为置换策略。在页式存储系统中，常用的淘汰算法有：最优算法，选择淘汰不再使用或最远的将来才使用的页；随机算法，随机的选择淘汰的页；先进先出算法，选择淘汰在主存驻留时间最长的页；最近最少使用算法，选择淘汰离当前时刻最的的一段时间内使用得最少的页。 在段页式管理的存储器中，实存等分为页，程序按逻辑模块分成段。在多道程序环境下，每道程序还需要一个基号作为用户标志号。每道程序都有对应的一个段表和一组页表。一个逻辑地址包括基号X、段号S，页号P和页内地址d这4个部分。假设总长为22位的逻辑地址格式分配为21-20位X，19-14位S，13-11位P，10-0位d。若X，S，P和d均以二进制数表示，其转换成的物理地址为（（（x）+s）+p）*211+d。 SMALLTALK80是支持动态汇集的语言。 任何一个程序都可看成是对一些数据及作用于该组数据上的操作的一种说明，数据具有存储类和类型、名称、作用域和生存期等属性。数据按类型可分为4种：Void、标量Scalar、函数和聚合aggregate。数据必须先说明后使用，数组、结构体、共用体和类属于聚合aggregate. 编译程序中语法分析器接受以单词为单位的输入，并产生有关信息供以后各阶段使用。算符优先法、LR分析法和递归下降法是几种常见的语法分析技术，其中算符优先法和LR分析法属于自下而上分析方法，而递归下降法属于自上而下的分析方法。LR分析法主要有SLR（1）、LR（0）、LR（1）、LALR（1）四种，其中LR（1）的分析能力最强，LR（0）的分析能力最弱。 编译系统一般可分成词法分析、语法分析、中间代码生成、优化处理和目标代码生成等五大部分。其中词法分析、语法分析和目标代码生成三部分是每个编译程序必不可少的，而中间代码生成和优化处理则是可有可无的。许多编译程序将词法分析编制成一个子程序，在语法分析的分析过程中根据需要调用词法分析，并且把语法分析和中间代码生成二部分结合起来边分析产生有关内容。此外，这五个部分在工作过程中都会涉及到表格处理和出错处理。 用高级语言编写程序时，子程序调用语句中的实在参数必须与子程序说明中的形式参数在个数、类型、顺序上保持一致。在允许子程序递归调用的高级语言环境中，需用动态存储管理法，它通常使用一个下堆栈存放子程序的调用记录。调用记录可包括：全局量存储区域的开始地址；调用点所在子程序的调用记录首地址；调用点的返回地址；形式参数和实际参数的通信区域；返回值；本子程序的局部量和临时变量存储区域等。 一个文法G=（N，T，P，S），其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号，令集合V=NUT，那么G所描述的语言是由S推导出的所有终结符号串的集合。 对于用private说明的成员，它只能被该类的成员函数访问，外界不能直接访问。 与正规式（a|b）*等价的正规式为a*。 语法分析方法大体上可分成自上而下和自下而上的两种。自下而上分析法，是从输入符号串开始逐步进行归约，直至归约成文法的起始符号。自上而下分析法，则是从文法的起始符号开始反复使用产生式进行推导直至推导出输入符号串。算符优先文法是一种自下而上分析方法，其文法的特点是文法产生式中不含两个相邻的非终结符。自上而下的分析方法，通常用求文法的产生式不以非终结符开头，如LL（1）文法就是一种可以自上而下分析的文法。 文法G=（{E}，{+，*，（，）a},P,E），其中P由下列产生式组成E，E+E|E+E|（E）|a它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于2型文法，其对应的自动机是下推自动机，如产生a*a+a，它的派生树是三叉树，且最左派生有2种，该文法是二义性的。 在编译程序中，安排中间代码生成的目的是利于目标代码优化和利于目标代码的移植。 各种程序设计语言中都有多种数据类型，纯量数据类型和结构数据类型是两大基本数据类型。例如，实型、布尔型和指针等都是前者，而数组、记录和联合都是后者。子程序通常分为两类：过程和函数，前者是命令的抽象，后者是为了求值。一些重要的程序语言（如C和Pascal）允许过程的递归调用。通常用栈来实现递归调用中的存储分配。 程序设计语言LISP和PROLOG分别是函数与逻辑型语言，它们的理论基础分别是入-演算与一阶谓词逻辑，它们的数据结构分别是S-表达式与项，它们的程序形式分别是函数与Horn子句，主要应用于人工智能。 在C++中引进了类的概念。说明类的成员要说明其访问控制属性，分为private、public和protected,具有private访问控制属性的成员只能在本类中被访问；具有public访问控制属性的成员在类的外部也可以访问。类具有封装性、继承性和多态性，有了封装性可以隐藏类对象内部实现的复杂细节，有效地保护内部所有数据不受外部破坏；继承性增强了类的共享机制，实现了软件的可重用性，简化了系统的开发工作；多态性可实现函数重载和运算符重载。 -a-(b*c/(c-d)+(-b)*a)的逆波兰表示是a-bc*cd-/b-a*+- 已知正规文法G=({S,C,B},{a,b,c},P,S)其中P内包含以下产生式:S-aS,S-aB,B-bB,B-bC,C-cC,C-c0则文法G对应的正规式为a*b*c* 对于下面的文法S是开始符号S-AB,S-bc,A-e,A-b,B-e,B-aD,C-AD,C-b,D-aS,D-C则该文法为非LL(1)文法. 已知文法G[S]:S-A0|B1,A-S1|1,B-S0|0该文法属于乔姆斯基定义的3型文法,它不能产生串0011 现有的数据处理和声音通信的信息网一般采用星型拓扑. 总线拓扑结构的LAN采用单根传输线作为所有节点的传输介质所采用的访问控制策略为分布式控制。总线不适合用于光纤传输。 国际标准化组织制定的开放系统互连OSI参考模型分为7层，在通信子网中通常只有下三层，它们依次是物理层、数据链路层和网络层。物理层传输非结构的位流及故障检测指示。 以太网遵循IEEE802.3标准，使用粗缆组网时每段不能大于500m。超过上述长度时，要分段，段间用重发器相连。同时，整个网的总长度不能大于2500m。若总长度超过上太述长度，则需分成两个网，网之间用网桥相连。这是ISO/OSI模型中的数据链路层连接。 局域网LAN已广泛应用于办公自动化、制造自动化等各个领域。LAN的标准化工作最早是由美国电气电子工程师协会IEEE进行的，发布了著名的IEEE802标准。在此基础上，国际标准化组织ISO已为LAN制定了相应的ISO8802国际标准。它涉及载波侦听多路访问/碰撞检测CSMA/CD、令牌传递token ring和时隙slotted等三种信息访问控制方法以及总线bus和环形ring两种拓扑结构。其中，时隙slotted方法的环形ring网只在ISO8802标准，而不在IEEE802标准中。常用的以太网Ethernet就是采用载波侦听多路访问/碰撞检测CSMA/CD方法的总线bus网的典型例子。 局域网的典型特性是覆盖区域小，数据率高和误码率低。 中继器的作用是再生物理信号。 网桥处理的信号是MAC帧。 确定数据传输质量和特性的决定因素取决于传输介质和信号的特性。 双绞线是用两根绝缘导线绞合而成的，绞合的目的是减少干扰。 在以太网上利用双绞线传输数字信号，不用中继器的传输距离可达到100m。 同轴电缆由内、外导体构成，其中外导体的作用是屏蔽。 因特网Internet采用数据报方式进行数据传输。 TCP/IP协议的安全机制先天足，如IP地址由软件配置，存在有假冒地址和欺骗地址的隐患；支持的路由方式也存在着路由攻击的隐患。因此又提供了两个TCP/IP安全协议，它们是Kerberos和SSL/SHTTP 在应用层实现安全功能的措施中，不含数据不完整性。 为了保证网络的安全常常使用防火墙技术。防火墙是指建立在内外网络边界上的过滤封锁机制。 Browser/serves结构是把Web技术和数据库技术结合起来的一种应用模式，这种应用模式把所有应用功能和数据库集中放在服务器，实现了开发环境与应用环境的分离，便于管理和系统维护。该模式最大的优点之一是客户端不用安装专用软件。 在TCP/IP协议分层结构中，SNMP是在UDP协议之上的异步请求/响应协议。SNMP协议管理操作中管理代理主动向管理进程报告事件的操作是Trap。在ISOOSI-RM基础上的公共管理信息服务/公共管理信息协议CMIS/CMIP是一个完整的网络管理协议簇，网络管理应用进程使用OSI参考模型的应用层。CMOT是要在TCP/IP协议簇上实现公共管理信息服务协议CMIS的服务，它是一个过渡性的解决，希望过渡到OSI网络管理协议被广泛采用。 因特网中路由器内路由选择表的大小仅取决于因特网中网络数目。 为了使因特网中的路由器报告差错或提供有关意外情况的信息，在TCP/IP中设计了一个特殊用途的报文机制，称之为ICMP。 携带ICMP报文的数据报与携带用户信息的数据报相比，具有完全相同的路由选择，相同的可靠性或优先级。 使用方便不是过滤路由器的缺点。 IPC不是传输层的安全技术。 计算机病毒常隐藏在引导扇区、文件或电子邮件附件中。假如某张软盘上已感染了病毒，那么为了防止病毒感染计算机系统，应在使用前，先用合适的杀毒软件对该软盘进行杀毒。 IPsec属于第三层VPN协议。 电子商务交易必须具备抗抵赖性，目的在于防止参与此交易的一方否认曾经发生过此次交易。 以太网100BASE-TX标准规定的传输介质是5类UTP。 许多网络通信需要进行组播，以下选项中不采用组播协议的应用是FTP。在IPv4中把D类地址作为组播地址。 将双绞线制作成交叉线一端按EIA/TIA568A线序，另一端按EIA/TIA568B线序该双绞线连接的两个设备可为网卡与网卡。 在DCE中，授权是通过资源的访问和控制列表来实现的,DEC系统中的用户、计算机和其他资源被组织成一个单元，其大小可不一样，但至少包含一个时间服务器、目录服务器和安全服务器，此外还需客户方和服务器方应用的设备。在DEC中，需要进行安全通信的用户或进程称之为一个元素，它有一个唯一的编号为二进制数。 目前互联网采用的IPV4系统是一个32位地址。IPV6是一个128的地址，作为新一代因特网技术的IPV6协议的最大优势是地址容量巨大。 速率为43.233Mbit/s通信服务名称为T3，ISDN综合业务数字网具有比一般电话线更高的传输速率，目前常用的B通道速率是64Kbit/s. 企业网络计算可采用不同的模型，其中可伸缩模型中，企业网络计算的同样软件可运行在企业内部的不同平台上。企业网络计算中，主要用于决策支持而且非常重要的一部分是数据仓库。 用POP3协议收信时，POPaccount就是登录名。 一些网络没有足够的IP地址分配给每一个用户，为了动态分配IP，这就需要网络有动态主机配置协议DHCP，用于域名和IP地址映射的服务器是DNS服务器，以太网的网络接口卡都有唯一的物理地址，其地址长度为48位。 ISO协议使用10种类型传送协议单元（PSDU）其中CR是连接请求，DC是拆除确认，RJ是拒绝。 实现应用进程利用OSI通信功能的唯一界面是应用实体。 目前，帧中继连接的最高数据传输速率可达45Mbit/s，在帧中继网络中，封装类型需要端设备之间确认，帧中继网强的物理层采用I.430/I.431协议。 X.25是一个平衡的协议，其链路层封装使用LAPB一个非x.25设备为了接入X.25网需要使用ROUTER，在X.25分组网中，ROUTER使用的协议有x.3,x.28,x.29 信道是传输信号的路径，它包括传输介质和有关的中间通信设备。从不同的角度我们可以对信道作不同的分类；以所有传输介质分类有无线信道和有线信道；以信道多路复用的形式分类有频分信道和时分信道；以信道传输的信息分类有模拟信道、数字信道及模拟——数字混合信道。 多路复用是使多个数据源共享使用一个公共线路的技术，复用是一种将若干个彼此独立的信号合并为一个可在同一信道上传输的复合信号。 在分组交换网络中，两种数据传输方式为虚电路方式和数据报方式，x.25分组长度的缺省值为128字节。 抑制广播风暴不是透明网桥的基本功能。 IP数字报的选项字段用于网络测试和调试。 FDDI网最多可连接1000个站点，其物理层采用4B/5B编码。 IP数据包在长度上是可变的，IPV4的每个IP地址可以用网络和主机来划分，一个IP信息单元可称为包packet. ATM导步传输模式是一种迅速崛起而备受关注的交换技术，以长度仅为48个固定长度的信元作为基本传输单元，可以实现155Mbps、622Mbps甚至更高的传输速率。 多媒体技术是当前计算机发展的一个热门方向。这里，多媒体的含义主要是指如文字、声音、图像等多种表达信息的形式。它强调多媒体信息的综合与集成处理。压缩技术是多媒体发展中要解决的关键技术之一。在SRAM、CD-ROM、磁带和高密度软盘四种存储器中，当前最适合用来存储多媒体信的是CD-ROM。 彩色图形显示和印刷设备采用三原色方法。CRT彩色显示器选用RGB红、绿、蓝三原色，是加色混色系统。彩色喷墨等彩色图形印刷设备选择CMY青、品红、黄三原色，是减色混色系统。黑色在这两种系统中的表示是RGB=000，CMY=111。某种颜色的补色是从白色减去该颜色成分后所呈现的色彩。CMY分别是RGB的补色，CRT显示的纯红色，在用彩色喷墨印刷输出时期限CMY=011，而白纸上的青色图形在CRT显示器中其RGB=011。 色彩的三要素是亮度、色调和色饱和度。色彩的亮度与光的颜色和强度有关。 进行图像压缩研究的起点是研究图像数据冗余，包括七种形式。空间冗余是其中最主要形式：时间冗余含在序列图像中，结构冗余存在于分布模式中，可以通过某一过程生成图像；当有些图像的理解与某些知识有相当大的相关性时产生知识冗余；有些图像纹理尽管不严格服从某一分布规律但是它在统计的意义上服从该规律，利用这种性质也可减少表示图像的数据量，我们称之为纹理的统计冗余。 视频信息在计算机中存放的具体格式很多，比较流行的有苹果公司的Quicktime和微软的AVI。AVI的一个很重要的特点是可伸缩性，使用AVI算法时的性能依赖于与它一起使用的基础硬件。向量量化是AVI的软件压缩技术之一。 电子出版物内容是以超文本的形式组织起来的，各主题之间可通过热字来连接。与印刷的书籍相比电子出版物有以下的优点：1用交互式多媒体技术提高了信息交流的效率2配有适当软件开发工具，辅以相应的硬件，用户可以用MPC来自行开发演示或制作部分电子出版物或把已有的电子出版物编辑在一起。 CD-RW类型的光碟允许用户多次向里写入信息。 一个典型的虚拟现实系统是由显示器、数据手套和计算机构成的。 超文本是一种信息管理技术，其组织形式以节点Node作为基本单位。 DVD-ROM光盘最多可存储的信息，比CD-ROM光盘的650MB大了许多。DVD-ROM光盘是通过减小读取激光波长，增大光学物镜数值孔径来提高存储容量的。 多媒体应用需要对庞大的数据进行压缩，常见的压缩编码方法可分为两大类，一类是无损压缩法，另一类是有损压缩法，也称熵压缩法、Huffman编码属于无损压缩法。 若每个像素具有8位的颜色深度，则可表示256种不同的颜色，若某个图像具有640/480个像素点，其未压缩的原始数据需占用307200字节的存储空间。 声音的三要素为音调、音强和音色，其中音色是由混入基音的泛音决定的。若对声音以22.05kHZ的采样频率、8位采样深度进行采样，则10分钟双声道立体声的存储量为26460000字节。 MPEG是一种音频、视频的压缩标准，它能够有高达200：1的压缩比。MPEG-1编码器输出视频的数据率大约为1.5Mb/s。PAL制式下其图像亮度信号的分辨率为352*288，帧速为25帧/秒。MPEG-4相对于MPEG的以前版本的最大特点是更强的交互能力。MPEG-7是多媒体内容描述接口标准。MPEG-4相对于MPEG以前版本的最大特点是更强的交互能力。在MPEG格式存储的图像序列中，不能随机恢复一幅图像的原因是它使用了帧间图像数据压缩技术，影响这种图像数据压缩比的主要因素是图像序列变化的程度。MPEG-1编码器输出视频的数据率大约为1.5mbps.MPEG-7不是一种多媒体压缩标准。MPEG视频压缩技术是针对运动图像的数据压缩技术。为了提高压缩比，帧间图像数据压缩和帧间图像数据压缩技术必须同时使用。帧内图像数据压缩与JPEG压缩算法大致相同，采用基于DCT的变换编码技术，用以减少空域冗余信息；帧间图像数据压缩算法采用预测法和插补法，可减少时域冗余信息，由于MPEG对视频随机存取的重要要求，和通过帧部运动补尝可有效地压缩数据比特数，MPEG采用了三种类的图像。帧内图可提供随机存取位置，但压缩比不大；插补图的数据压缩效果最显著，但不能作为其他图的预测参考图。MPEG-4是一套多媒体通信标注，MPEG-4主要由音频编码、视频编码、数据平面、场景描述、缓冲区管理和实时识别等部分构成，其中，数据平面包括传输关系和媒体关系两部分。MPEG视频中的时间冗余信息可以采用帧间预测和运动补偿的方法来进行压缩编码。 数据压缩技术是多媒体信息处理中的关键技术之一，数据压缩技术可分为可逆与不可逆两大类。Huffman是一种与频度相关的压缩和编码方法，MPEG主要用于视频信息的压缩，JPEG则常用于静止图片的信息压缩。由三基色RGB原理出发的RGB彩色空间，是在多媒体技术中最常用的，此外还有多种彩色空间，但IMG不是计算机上用的彩色空间。 在多媒体的音频处理中，由于人所敏感的声频最高为22K赫兹HZ，因此，数字音频文件中对音频的采样频率为44.1kHz，对一个双声道的立体声，保持1秒钟声音，其波形文件所需的字节数为88200，这里假设每个采样点的量化数为8位。 未经压缩的数字音频数据传输率的计算公式为采样频率HZ*量化位数BIT*声道数 彩色打印机中所采用的颜色空间是CMY彩色空间 计算机视觉是一种信息处理过程，一种流行的计算理论认为它分三个不同的层次：计算理论层回答视觉信息处理过程的输入输出是什么;表示和算法层进一步回答逻辑上如何实现这个计算理论层;计算理论层要解决在物理上如何实现这个表示和算法层.为此,上述视觉过程可分为三个阶段:早期视觉由输入图像而获得要素图把原始二维图像中重要信息表示出来;中期视觉由输入图像和要素图获得2.5维图,它包括在以观察者为中心坐标系中表示的可见表面法向、深度及不连续轮廓等；后期视觉由输入图像、要素图和2.5维图获得物体的三维表示，完成整个视觉过程。 数字化后的图像数据量是非常大的，例如：一幅分辨率是640*480具有224种色彩的图像需占用存储量约为7.4MB。如果要无闪烁显示动画10S，则全部图像占用存储量1850ＭＢ,除此之外还需要有极高通道数据传送率才行。所以，数据压缩技术是多媒体计算机的关键技术之一。目前公认的关于压缩编码的国际标准是：用于多灰度静止图像的JPEG标准，用于电视电话／会议电视的P*64标准和用于数字存储媒体运动图像的MPEG标准。 对流媒体说法正确的是用户可以用流媒体来进行实时广播。 声音的文件格式和表态图像的文件格式分别有WAV、MID和BMP、GIF、PNG。 在多媒体系统中，音频信号可分为两类：语音信号和非语音信号。音频信号的处理有如下特点：音频信号是时间依赖的连续媒体，对时序性要求很高；理想的合成声音应是立体声；对语音信号的处理，不仅是信号处理的问题，还要抽取语意等其他信息。在人与计算机交互的角度来看音频信号的处理包括：人与计算机通信（计算机接收音频信号）即音频获取。 第一声音频卡是在1987年由AdLib设计制造。通常音频录放采用量化位为8位/16位；基本编码方法PCM；音频卡的编辑与合成功能就像一部数字音频编辑器，它可以对声音文件进行多种特殊效果处理。音乐合成功能和性能依赖于合成芯片。目前Yamaha的合成器芯片占有率最高，其中主要是FMOPL系列，这种芯片采用调频方式。 从信息保持的角度讲，只有当信源本身具有冗余度，才能对其进行压缩。从时域来考虑，语音中的小幅度样本比大幅度样本出现的概率要高，语音信号取样值的幅度分布是非均匀；对语音波形的分析表明，取样数据的最大相关性存在于邻近样本之间；语音信号的周期之间存在着一定的相关性；如果在较长的时间间隔进行统计，便得到长时自相关函数。 假定每一车次肯一唯一的始发站和终点终。如果实体“列车时刻表”属性为车次、始发站、发车时间、终到站、到达时间，该实体的主键是车次；如果实体“列车运行表”属性为车次、日期、发车时间、到时间，该实体的主键是车次，日期。通常情况下，上述“列车时刻表”和“列车运行表”两实体型间存在一对多联系。 一级封锁协议解决了事务的并发操作带来的数据丢失修改不一致性的问题. 关于事务的故障与恢复，对日志文件设立检查点目的是为了提高故障恢复的效率。事务中的所有操作要么都执行，要么都不执行。 数据挖掘是采用适当的算法，从数据仓库的海量数据中提取中潜在的信息和知识。 E-R图可将现实世界应用中的信息抽象地表示为实体以及实体间的联系。 故障恢复是数据库系统可靠性、实用性的基本保证，任何一个系统都难免由于种种原因而发生故障。事务故障是由程序执行错误而引起事务非预计的，异常的终止。系统故障指引起系统停止运转，从而要重启动的事件。介质故障使数据库本身被破坏，并影响到出故障前的全部事务。 关系数据库系统中引入了快照概念后，可以允许用户仅对某些在特定时刻和特定范围的数据，缩小其数据范围而提高执行效率。关系代数可分为传统的集合运算和专门关系运算。 某高校五个系的学生信息存放在同一个基本表中，采取建立各系的行级视图，并将对该视图的读权限赋予该系的管理员的措施可使各系的管理员只能读取本系学生的信息。 外部视图是应用程序员所见到的局部数据库逻辑结构。概念模型数据库管理员必须考虑整个数据库的全局逻辑结构。数据库管理员所见到的特定的DBMS所处理的数据库的内容结构，其形式化描述称为内部视图。考虑数据在存储设备上的物理安置，对数据在存储设备上的物理组织的形式描述称为物理视图。 在关系数据模型中，通常可以把字段称为属性，而把记录类型称为关系模式。常用的关系运算是关系代数和关系演算。在关系代数中，对一个关系做投影操作后，新关系的元组个数小于或等于原来关系的元组个数。用表格形式表示实体类型和实体间的联系是关系模型的主要特征。 子模式对于加强数据的独立性和安全性，以及将问题局部化和简化使用等方面具有重要意义。在一些关系DBMS中，视图与通常意义上的外部模式有所差别，这里的视图可以动态地从一个或多个基本关系上导出。 数据库的特点是数据可以共享（或数据结构化）；数据独立性；数据冗余小，易扩充；统一管理和控制。数据库避免了一切数据的重复是不正确说法。数据的物理独立性是指用户的应用程序与存储在磁盘上数据库中的数据是相互独立的。 数据库系统有数据共享、减少冗余、保持数据的一致性、数据有独立性和数据有安全与完整性保障的特点。数据库系统的体系结构是数据库的一个总体的框架。而实际上数据库软件种类甚多，数据库语言有差别，且数据模型也有差异，但绝大多数数据库系统却都具有附图所示的三级模式结构特征：三级模式是指外模式、模式和内模式；其中外模式由称为子模式或用户模式是数据的局部逻辑结构，也是数据库用户看到的数据视图；模式又称为逻辑模式，是数据库的全体数据的全局逻辑结构，也是所有用户的公共数据视图；内模式又称为存储模式，是数据在数据库中的内部表示，即数据的物理结构存储方式。数据库系统的三级模式是数据的三个抽象级别，而数据的具体组织由数据库管理系统负责使用户能逻辑地处理数据。为实现三个抽象层次的转换，数据库系统在三级模式中提供了两次，外模式/内模式映象和模式/内模式映象，从而保持数据库管理的数据独立性。在数据库系统中，通常用三级模式来描述数据库，其中外模式是用户与数据库的接口，是应用程序可见到的数据描述，概念模式是对数据整体的逻辑结构的描述，而内模式描述了数据的物理结构。在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是数据库系统阶段。数据库是在计算机系统中按照一定的数据模型组织、存储和应用的数据的集合，支持数据库各种操作的软件系统叫做数据库管理系统，由计算机、操作系统、DBMS、数据库、应用程序及用户组成的一个整体叫做数据库系统。一个数据库系统必须能表示实体和关系。关系可与1个或1个以上实体有关。实体与实体之间的关系有一对一、一对多和多对多三种，其中层次模型不能描述多种多对多的联系。一般地，一个数据库系统可能有两种外视图，只能有一种概念视图，可能有两种数据子语言。数据库系统的最大特点是数据的三级抽象和二级独立性。数据库系统是由数据库管理系统、数据库管理员、数据库组成；而数据库应用系统是由数据库系统、应用程序系统、用户组成。数据库系统由数据库、数据库管理系统和硬件等组成，数据库系统是在文件系统的基础上发展起来的。数据库系统由于能减少数据冗余，提高数据独立性，并集中检查数据完整性，由此获得广泛的应用。数据库提供给用户的接口是数据库语言，它具有数据定义、数据操作和数据检查功能，可独立使用，也可嵌入宿主语言使用，SQL语言忆被国际标准化组织采纳为标准的关系数据库语言。 数据库管理系统中用于定义和描述数据库逻辑结构的语言称为数据库模式描述语言。 从逻辑上看关系模型是用表表示记录类型的，用表表示记录类型之间的联系；层次与网状模型是用结点表示记录类型，用连线表示记录类型之间的联系。从物理上看关系是相联寻址，层次与网状模型是用指针来实现两个文件之间的联系。 从外部视图到子模式的数据结构的转换是由应用程序实现的；模式与子模式之间的映像是由DBMS实现的；存储模式与数据物理组织之间的映像是由操作系统的存取方法因实现的。 数据库语言包括数据描述语言和数据操纵语言两大部分，前者负责描述和定义数据库的各种特性，后者用于说明对数据进行的各种操作。 数据库管理系统的主要功能有数据定义功能、数据操纵功能、数据库的运行管理和数据库的建立以及维护等四个方面。 以子模式为框架的数据库是用户数据库，以模式为框架的数据库是概念数据库，以物理模式为框架的数据库是物理数据库。 数据模型是由数据结构、数据操作和完整性约束三部分组成的。 按照数据结构的类型来命名，数据模型分为层次模型、网状模型和关系模型。 一个关系模式的定义主要包括关系名、属性名、属性类型、属性长度和关键字。 关系模式R（U，F），其中U={W，X，Y，Z}，F={WX-Y，W-X，X-Z，Y-W}。关系模式R的候选码是W和Y，P={R1（WXY），R2（XZ）}是无损连接并保持函数依赖的分解。 在关系代数的传统集合运算中，假定有关系R和S，运算结果为W。如果W中的元组属于R，或者属于S，则W为井运算的结果。如果W中的元组属于R而不属于S，则W为差运算的结果。如果W中的元组既属于R又属于S，则W为交运算的结果。 设有关系W（工号，姓名，工种，定额），将其规范化到第三范式正确的答案是W1（工号，姓名，工种）W2（工号，定额）。 关系数据库管理系统应能实现的专门关系运算包括选择、投影、连接。从表中取出满足条件的属性操作称为投影；从表中选出满足某种条件的元组的操作称为选择；将两个关系中具有共同属性值的元组连接到一起构成新表的操作称为连接。 设有关系R，按条件F对关系R进行选择，QF（R）。 关系规范化中的删除操作异常是指不该删除的数据被删除，插入操作异常是指应该插入的数据未被插入。 当关系模式R（A，B）已属于3NF，仍存在一定的插入和删除异常。 一个关系模式如果属于4NF，则一定属于BCNF：反之不成立。 函数依赖X-Y的有效性仅决定于两属性集的值；而多值依赖X—Y的有效性与属性集的范围有关。 有关系模式学生（学号，课程号，名次），若每一名学生每门课程有一定的名次，每门课