集成电路的发展到目前为止,依次经历了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的主要功能不包括传输数据。
1
使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的指令集使编译优化工作更
2
简单。访问内存需要的机器周期比较少不是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）网中从源泉点到汇点（结束顶点）的最长路径。
3
一个具有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个元素的值，
4
则采用顺序表存储方式最节省时间。若琏表的最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用带头结点的双向循环链表存储方式最节省运算时间。 队列的特点是先进先出。设循环队列用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操作应谨慎检查，保证其使用的正确性，否则执行时可能发生死锁。
进程管理是操作系统的核心，如果设计不妥，会出现一种尴尬的局面死锁。处于死锁状态的进程不能继续运行又占用了系统资源，从而会阻碍其他进程的运行。对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于死锁的避免，破坏环路等待条件属于死锁的预防，而剥夺资源是死锁的解除的基本方法。死锁的检测是在需要的时刻执行，以发现系统是否于安全状态。
操作系统组织直接文件的关键在于采用什么方法进行从记录键值到磁盘物理地址的变换，例
5