事业单位考试计算机专业课复习资

数据结构要点 第一章 概 论 ************************************************************************ 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 ************************************************************************ 数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 ************************************************************************ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。  ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。  ·优点是将数据和操作封装在一起实现了信息隐藏。 ************************************************************************ 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 ************************************************************************ 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 ************************************************************************ 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模n的函数。 算法的时间复杂度和空间复杂度合称算法复杂度。 第二章 线性表 ************************************************************************ 线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。 ************************************************************************ 线性表上定义的基本运算：·构造空表：Initlist(L) ************************************************* 顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关 系是一致的。地址计算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址为1） 在顺序表中实现的基本运算： ·插入：平均移动结点次数为n/2；平均时间复杂度均为O(n)。 ·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O(n)。 ************************************************************************ 线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储 了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命名。 ************************************************************************ 单链表运算：·建立单链表·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。 ·尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n) ·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。 ·查找·按序号：与查找位置有关，平均时间复杂度均为O(n)。 ·按值：与输入实例有关，平均时间复杂度均为O(n)。 ·插入运算：p=GetNode(L,i-1)；s->next=p->next；p->next=s；平均时间复杂度均为O(n) ·删除运算：p=GetNode(L,i-1)；r=p->next；p->next=r->next；free(r)；平均时间复杂度均为O(n) ************************************************************************ 单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。 采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表。 ************************************************************************ 双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一 确定。 双链表也可以头尾相链接构成双(向)循环链表。 双链表上的插入和删除时间复杂度均为O (1)。 ************************************************************************ 顺序表和链表的比较：·基于空间： ·顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。 ·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。   ·基于时间： ·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。 ·以插入和删除操作为主的线性表宜采用链表做存储结构。 ·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 第三章 栈和队列 ************************************************************************ 栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈 的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。 ************************************************************************ 栈的基本运算有六种： ·构造空栈：InitStack(S) ·判栈空: StackEmpty(S) ·判栈满： StackFull(S) ·进栈： Push(S,x) ·退栈： Pop(S) ·取栈顶元素：StackTop(S) ************************************************************************ 队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的 一端称为队尾(rear) ,队列的操作原则是先进先出的，又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储结 构。 ************************************************************************ 队列的基本运算有六种： ·置空队：InitQueue(Q)·判队空：QueueEmpty(Q)·判队满：QueueFull(Q)·入队：EnQueue(Q,x)·出队：DeQueue(Q)·取队头元素：QueueFront(Q) ************************************************************************ 顺序队列的"假上溢"现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。 为了克服"假上溢"现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。 判定循环队列是空还是满， 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 有三种： ·一种是另设一个布尔变量来判断； ·第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空；  ·第三种就是用一个计数器记录队列中的元素的总数。 ************************************************************************ 队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指 针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只 有一个结点时，出队后要同进修改头尾指针并使队列变空。 第四章串 ************************************************************************ 串的基本运算有： ·求串长strlen(char*s) ·串复制strcpy(char*to,char*from) ·串联接strcat(char*to,char*from) ·串比较charcmp(char*s1,char*s2) ·字符定位strchr(char*s,charc) ************************************************************************ .串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。 顺序串又可按存储分配的不同分为： ·静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、 链接操作。 ·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。 ************************************************************************ 串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。 为了解决"存储密度"低的状况，可以让一个结点存储多个字符，即结点的大小。 ************************************************************************ 第五章多维数组和广义表 数组一般用顺序存储的方式表示。存储的方式有： ·行优先顺序，也就是把数组逐行依次排列。PASCAL、C ·列优先顺序，就是把数组逐列依次排列。FORTRAN ************************************************************************ 地址的计算方法： ·按行优先顺序排列的数组：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d。    ·按列优先顺序排列的数组：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d。 ************************************************************************ 矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。 特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。 ************************************************************************ 稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示 。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表。 ************************************************************************ 广义表是n(n≥0)个元素的有限序列，其中的元素是原子或者是一个广义表。 第六章树 ************************************************************************ 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子(终端结点)；度不为0的结点称分支结点(非终端结点)；除根外的分支结点称内部 结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。 ************************************************************************ 二叉树的定义：是n≥0个结点的有限集，它是空集(n=0)或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组 成。 二叉树不是树的特殊情形，与度数为2的有序树不同。 二叉树的4个重要性质： ·.二叉树上第i层上的结点数目最多为2^(i-1)(i≥1).； ·深度为k的二叉树至多有(2^k)-1个结点(k≥1)； ·.在任意一棵二叉树中，若终端结点的个数为n0,度为2的结点数为n2，则n0=n2+1； ·.具有n个结点的完全二叉树的深度为int(log2n)+1。 满二叉树是一棵深度为k，结点数为(2^k)-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点； ************************************************************************ 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树） 树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree 型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，n+1个空指针。 ************************************************************************ 根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)。时间复杂度 为O(n). ************************************************************************ 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为"线索"，加上线索的 二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用 。 ************************************************************************ 树和森林及二叉树的转换是唯一对应的。 转换方法： ·树变二叉树：兄弟相连，保留长子的连线。   ·二叉树变树：结点的右孩子与其双亲连。   ·森林变二叉树：树变二叉树，各个树的根相连。 ************************************************************************ 树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代 。   ·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。 ·双亲孩子链表表示法：将双亲链表和孩子链表结合。 ·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。 ************************************************************************ 树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。 ************************************************************************ 树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）。 在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。 哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。 ************************************************************************ 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法 在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。 哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易，只要画 好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的最优 前缀码。 第七章图 ************************************************************************ 图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。 图GraphG=(V,E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。 有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*(n-1)条边的有向图；无向完全图：具有n*(n-1)/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径； 网络：是带权的图。 ************************************************************************ 图的存储结构：·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。 ·无向图：邻接矩阵是对称的。 ·有向图：行是出度，列是入度。 建立邻接矩阵算法的时间是O(n+n^2+e),其时间复杂度为O(n^2) ·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。 ·无向图称边表； ·有向图又分出边表和逆邻接表； ·邻接表结点结构为 adjvex | next， 时间复杂度为O(n+e).，空间复杂度为O(n+e).。 图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 ************************************************************************ 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生 成树。 最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树(MST)。 构造最小生成树的算法： ·Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。 ·Kruskal算法的时间复杂度为O(lge),主要取决于边数，较适合于稀疏图。 ************************************************************************ 最短路径的算法：·Dijkstra算法，时间复杂度为O(n^2).·类似于prim算法。 ************************************************************************ 拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若∈E(G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。 拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。  ·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。 第八章排序 ************************************************************************ 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。 排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小；改变指向记录的指针或移动记录。         ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为外排序。 内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 ************************************************************************ 插入排序：·直接插入排序： ·逐个向前插入到合适位置。 ·哨兵(监视哨)有两个作用： ·作为临变量存放R[i] ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2；移动次数为(n+4)(n-1)/2；  ·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1。 ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25)；移动次数为(1.6n^1.25)； 交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的 一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为n(n-1)/2；移动次数为3n(n-1)/2；   ·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n)，比较次数为n(n-1)/2； 选择排序：·直接选择排序： ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2；   ·堆排序  ·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。    ·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。。 归并排序： ·先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。      ·归并排序是非就地稳定排序，时间复杂度是O(nlog2n), 分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n).   ·基数排序：·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。 各种排序方法的比较和选择： ·.待排序的记录数目n；n较大的要用时间复杂度为O(nlog2n)的第九章查找 ************************************************************************ 查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。 衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL). ************************************************************************ 线性表查找的方法： ·顺序查找：逐个查找，ASL=(n+1)/2; ·二分查找：取中点int(n/2)比较,若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N。 ·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。 ************************************************************************ 二叉排序树(BST)定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点 的值； ·若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ·左、右子树本身又是一棵二叉排序树。 二叉排序树的插入、建立、删除的算法平均时间性能是O(nlog2n)。 二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。 ·*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p. ·*p有两个孩子,则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。 ************************************************************************ 关于B-树(多路平衡查找树)。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 ************************************************************************ 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。 常见的散列函数构的造方法： ·.平方取中法：hash=int((x^2)%100) ·.除余法：表长为m，hash=x%m ·.相乘取整法：hash=int(m*(x*A-int(x*A))；A=0.618 ·.随机数法：hash=random(x)。 ************************************************************************ 处理冲突的方法：·开放定址法： ·一般形式为hi=(h(key)+di)%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1。 ·开放定址法类型： ·线性探查法：address=(hash(x)+i)%m； ·二次探查法：address=(hash(x)+i^2)%m； ·双重散列法：address=(hash(x)+i*hash(y))%m；   ·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。 ·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象； ·链表上的结点空间是动态申请的适于无法确定表长的情况； ·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间； ·拉链法构造的散列表删除结点易实现。 ·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。 第十章文件 ************************************************************************ 文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。 文件　·逻辑结构是一种线性结构。 　　　·操作有：检索和维护。并有实时和批量处理两种处理方式。 文件　·存储结构是指文件在外存上的组织方式。 　　　·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。 　　　·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。 检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。 ************************************************************************ 顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。 一切存储在顺序存储器(如磁带)上的文件都只能顺序文件，只能按顺序查找法存取。 顺序文件的插入、删除和修改只能通过复制整个文件实现。 ************************************************************************ 索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。 索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。 若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。 索引顺序文件常用的有两种：　·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。 　　　　　　　　　　　　　　·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。 ************************************************************************ 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。 散列文件　·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。 　　　　　·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。 ************************************************************************ 多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。 倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。 计算机组成原理 第1章 概论 一、名词解释： 　　历年 真题 北京中考数学真题pdf四级真题及答案下载历年四级真题下载证券交易真题下载资料分析真题下载 ： 　　名词解释题： 　　（2002年）1．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。 　　（2003年）16．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。 　　（2004年）18．ALU算术逻辑运算单元，负责执行各种算术运算和逻辑运算。 　　（2005年）21．应用软件：完成应用功能的软件，专门为解决某个应用领域中的具体任务而编写。 　　近4年都考了名称解释，所以第一章的名称解释是考试的重点，这里给大家列出了名词解释大家要熟悉一下，这都是本章的基本概念，也有利于做选择题及填空题。 　　1．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。 　　2．CPU：中央处理器，是计算机的核心部件，由运算器和控制器构成。 　　3．运算器：计算机中完成运算功能的部件，由ALU和寄存器构成。 　　4．ALU：算术逻辑运算单元，负责执行各种算术运算和逻辑运算。 　　5．外围设备：计算机的输入输出设备，包括输入设备，输出设备和外存储设备。 　　6．数据：编码形式的各种信息，在计算机中作为程序的操作对象。 　　7．指令：是一种经过编码的操作命令，它指定需要进行的操作，支配计算机中的信息传递以及主机与输入输出设备之间的信息传递，是构成计算机软件的基本元素。 　　8．透明：在计算机中，从某个角度看不到的特性称该特性是透明的。 　　9．位：计算机中的一个二进制数据代码，计算机中数据的最小表示单位。 　　10．字：数据运算和存储的单位，其位数取决于具体的计算机。 　　11．字节：衡量数据量以及存储容量的基本单位。1字节等于8位二进制信息。 　　12．字长：一个数据字中包含的位数，反应了计算机并行计算的能力。一般为8位、16位、32位或64位。 　　13．地址：给主存器中不同的存储位置指定的一个二进制编号。 　　14．存储器：计算机中存储程序和数据的部件，分为内存和外存。 　　15．总线：计算机中连接功能单元的公共线路，是一束信号线的集合，包括数据总线．地址总线和控制总线。 　　16．硬件：由物理元器件构成的系统，计算机硬件是一个能够执行指令的设备。 　　17．软件：由程序构成的系统，分为系统软件和应用软件。 　　18．兼容：计算机部件的通用性。 　　19．软件兼容：一个计算机系统上的软件能在另一个计算机系统上运行，并得到相同的结果，则称这两个计算机系统是软件兼容的。 　　20．程序：完成某种功能的指令序列。 　　21．寄存器：是运算器中若干个临时存放数据的部件，由触发器构成，用于存储最频繁使用的数据。 　　22．容量：是衡量容纳信息能力的指标。 　　23．主存：一般采用半导体存储器件实现，速度较高．成本高且当电源断开时存储器的内容会丢失。 　　24．辅存：一般通过输入输出部件连接到主存储器的外围设备，成本低，存储时间长。 　　25．操作系统：主要的系统软件，控制其它程序的运行，管理系统资源并且为用户提供操作界面。 　　26．汇编程序：将汇编语言程序翻译成机器语言程序的计算机软件。 　　27．汇编语言：采用文字方式（助记符）表示的程序设计语言，其中大部分指令和机器语言中的指令一一对应，但不能被计算机的硬件直接识别。 　　28．编译程序：将高级语言程序转换成机器语言程序的计算机软件。 　　29．解释程序：解释执行高级语言程序的计算机软件，解释并立即执行源程序的语句。 　　30．系统软件：计算机系统的一部分，进行命令解释、操作管理、系统维护、网络通信、软件开发和输入输出管理的软件，与具体的应用领域无关。 　　31．应用软件：完成应用功能的软件，专门为解决某个应用领域中的具体任务而编写。 　　32．指令流：在计算机的存储器与CPU之间形成的不断传递的指令序列。从存储器流向控制器。 　　33．数据流：在计算机的存储器与CPU之间形成的不断传递的数据序列。存在于运算器与存储器以及输入输出设备之间。 　　34．接口：计算机主机与外围设备之间传递数据与控制信息的电路。计算机可以与多种不同的外围设备连接，因而需要有多种不同的输入输出接口。 　　 　　选择题没有考过 二、填空题： （2000年）系统软件主要包括：＿＿＿和＿＿＿及诊断程序等。 操作系统　语言处理程序 （2005年）18．构成中央处理器的两大部件是＿＿＿和＿＿＿。 运算器　控制器 三、改错题： （2000年）1．运算器的功能就是执行加、减、乘、除四则运算。 运算器的功能就是算术运算和逻辑运算 （2005年）18．构成中央处理器的两大部件是＿＿＿和＿＿＿。 硬盘的存储容量常用 GB 表示，1GB=1024MB 三、数据编码： 定点数编码： （2000年）2．如果X为负数，由[X]补求[-X]补是将（　）。 A．[X]补各值保持不变 B．[X]补符号位变反，其它各位不变 C．[X]补除符号位外，各位变反，未位加1 D．[X]补连同符号位一起各位变反，未位加1 　　【分析】：不论X是正数还是负数，由[X]补求[-X]补的方法是对[X]补求补，即连同符号位一起按位取反，末位加1。 　　【答案】：D （2001年）2．若x补 =0.1101010 ，则 x 原=（　 ）。 　　　　　A．1.0010101　　B．1.0010110　　C．0.0010110　　D．0.1101010 　　【分析】：正数的补码与原码相同，负数的补码是用正数的补码按位取反，末位加1求得。此题中X补为正数，则X原与X补相同。 　　【答案】：D （2002年）2．若x=1011,则[x]补=( 　)。 　　　　　A．01011　　　　B．1011　　　　 C．0101　　 　　D．10101 　　【分析】：x为正数，符号位为0,数值位与原码相同，结果为01011。 　　【答案】：A （2003年）8．若［X］补=1.1011 ，则真值 X 是（　）。 　　　　　A．-0.1011　　　B．-0.0101　　　C．0.1011　　　 D．0.0101 　　【分析】：[X]补=1.1011，其符号位为1，真值为负；真值绝对值可由其补码经求补运算得到，即按位取后得0.0100再末位加1得0.0101，故其真值为-0.0101。 　　【答案】：B （2004年）13．设有二进制数 x=－1101110，若采用 8 位二进制数表示，则［X］补（　）。 　　　　　A．11101101　　B．10010011　　　C．00010011　　D．10010010 　　【分析】：x=－1101110为负数，负数的补码是将二进制位按位取反后在最低位上加1，故[x] 补 =10010010。 　　【答案】：D （2005年）1．若[X]补=0.1011，则真值X=（　）。 　　　　　A．0.1011　　 B．0.0101　　　　 C．1.1011　　 D．1.0101 　　【分析】：[X]补=0.1011，其符号位为0，真值为正；真值就是0.1011。 　　【答案】：A 由上可见，有关补码每年都考。同学也要注意一下移码。 （2001）3．若定点整数 64 位，含 1 位符号位，补码表示，则所能表示的绝对值最大负数为（　）。 　　　　　A．-264　　　 B．-（264-1 ）　　C．-263　　 　D．-（263-1） 【分析】：字长为64位，符号位为1位，则数值位为63位。当表示负数时，数值位全0为负绝对值最大，为-263。 　【答案】：C （2002年）3．某机字长8位，含一位数符，采用原码表示，则定点小数所能表示的非零最小正数为（　） 　　　　　A．2-9　　　　B．2-8　　　　　　C．1-　　　　 D．2-7 【分析】：求最小的非零正数，符号位为0,数值位取非0中的原码最小值，此8位数据编码为：00000001，表示的值是：2-7。 　【答案】：D 第3章 存储系统 一、名词解释： 　　历年真题： 　　（2001年）2．DRAM：动态随机访问存储器，利用电容电荷存储信息。 　　（2001年）6．逻辑地址：程序员编程所用的地址以及CPU通过指令访问主存时所产生的地址。 　　（2001年）10．随机存取方式：可按地址访问存储器任一编址单元，其访问时间相同且与地址无关。 　　六年以来就考了这3个名称解释，而且近4年都没有考，所以第三章的名称解释不是考试的重点，这里给大家列出了名词解释大家要熟悉一下，这都是本章的基本概念，有利于做选择题及填空题。 　　1．RAM：随机访问存储器，能够快速方便的访问地址中的内容，访问的速度与存储位置无关。 　　2．ROM：只读存储器，一种只能读取数据不能写入数据的存储器。 　　3．SRAM：静态随机访问存储器，采用双稳态电路存储信息。 　　4．DRAM：动态随机访问存储器，利用电容电荷存储信息。 　　5．EDO DRAM：增强数据输出动态随机访问存储，采用快速页面访问模式并增加了一个数据锁存器以提高数据传输速率。 　　6．PROM：可编程的ROM，可以被用户编程一次。 　　7．EPROM：可擦写可编程的ROM，可以被用户编程多次。靠紫外线激发浮置栅上的电荷以达到擦除的目的。 　　8．EEPROM：电可擦写可编程的ROM，能够用电子的方法擦除其中的内容。 　　9．SDRAM：同步型动态随机访问存储器，在系统时钟控制下进行数据的读写。 　　10．快闪存储器：一种非挥发性存储器，与EEPROM类似，能够用电子的方法擦除其中的内容。 　　11．相联存储器：一种按内容访问的存储器，每个存储单元有匹配电路，可用于是cache中查找数据。 　　12．多体交叉存储器：由多个相互独立、容量相同的存储体构成的存储器，每个存储体独立工作，读写操作重叠进行。 　　13．访存局部性：CPU的一种存取特性，对存储空间的90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在90%的区域中。 　　14．直接映象：cache的一种地址映象方式，一个主存块只能映象到cache中的唯一一个指定块。 　　15．全相联映象：cache的一种地址映象方式，一个主存块可映象到任何cache块。 　　16．组相联映象：cache的一种地址映象方式，将存储空间分成若干组，各组之间用直接映象，组内各块之间用全相联映象。 　　17．全写法（写直达法）：cache命中时的一种更新策略，写操作时将数据既写入cache又写入主存，但块变更时不需要将调出的块写回主存。 　　18．写回法：cache命中时的一种更新策略，写cache时不写主存，而当cache数据被替换出去时才写回主存。 　　19．按写分配：cache不命中时的一种更新策略，写操作时把对应的数据块从主存调入cache。 　　20．不按写分配：cache不命中时的一种更新策略，写操作时该地址的数据块不从主存调入cache。 　　一般写回法采用按写分配法，写直达法则采用不按写分配法。 　　21．虚拟存储器：为了扩大容量，把辅存当作主存使用，所需要的程序和数据由辅助的软件和硬件自动地调入主存，对用户来说，好像机器有一个容量很大的内存，这个扩大了的存储空间称为虚拟存储器 　　22．层次化存储体系：把各种不同存储容量、不同访问速度、不同成本的存储器件按层次构成多层的存储器，并通过软硬件的管理将其组成统一的整体，使所存储的程序和数据按层次分布在各种存储器件中。 　　23．访问时间：从启动访问存储器操作到操作完成的时间。 　　24．访问周期时间：从一次访问存储的操作到操作完成后可启动下一次操作的时间。 　　25．带宽：存储器在连续访问时的数据吞吐率。 　　26．段式管理：一种虚拟存储器的管理方式，把虚拟存储空间分成段，段的长度可以任意设定，并可以放大或缩小。 　　27．页式管理：一种虚拟存储器的管理方式，把虚拟存储空间和实际存储空间等分成固定容量的页，需要时装入内存，各页可装入主存中不同的实际页面位置。 　　28．段页式管理：一种虚拟存储器的管理方式，将存储空间逻辑模块分成段，每段又分成若干页。 　　29．固件：固化在硬件中的固定不变的常用软件。 　　30．逻辑地址：程序员编程所用的地址以及CPU通过指令访问主存时所产生的地址。 　　31．物理地址：实际的主存储器的地址称为“真实地址”。 二、选择填空题： 历年真题评析： 2000年： 5．动态半导体存储器的特点是（　）。 　 A．在工作中存储器内容会产生变化 　 B．每次读出后，需要根据原存内容重新写入一遍 　 C．每隔一定时间，需要根据原存内容重新写入一遍 　 D．在工作中需要动态地改变访存地址 　　【分析】：动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会放电，必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍。 　　【答案】：C 8．地址线A15～A0（低），若选取用16K×1存储芯片构成64KB存储器则应由地址码　　　译码产生片选信号。 【分析】：用16K×1芯片构成64KB的存储器，需要的芯片数量为：(64K×8)/(16K×1)=32，每8片一组分成4组，每组按位扩展方式组成一个16K×8位的模块，4个模块按字扩展方式构成64KB的存储器。存储器的容量为64K=216，需要16位地址，选用A15-A0为地址线；每个模块的容量为16K=214需要14位地址，选用A13-A0为每个模块提供地址；A15、A14通过2-4译码器对4个模块进行片选。 　　【答案】：Al5，A14 9．有静态RAM与动态RAM可供选择，在构成大容量主存时，一般就选择（　　　）。 　　【分析】：静态RAM特点是存取速度快，单位价格（每字节存储空间的价格）较高；动态RAM则是存取速度稍慢，单位价格较低。所以考虑价格因素，在构成大容量的存储器时一般选择动态存储器。 　　【答案】：动态RAM 2001年： 11．高速缓冲存储器 Cache 一般采取（　）。 　　A．随机存取方式 　　B．顺序存取方式 　　C．半顺序存取方式 　　D．只读不写方式 　　【分析】：Cache是为提高存储器带宽而在主存储器和CPU之间增加的存储器，目的是用来存储使用频繁的数据和指令，存取方式应与主存储器相同，均为随机存取方式。 　　【答案】：A 12．若存储周期 250ns ，每次读出 16 位，则该存储器的数据传送率为（　）。 　　A．4 × 10 6 字节 / 秒　　　　　　　B．4M 字节 / 秒 　　C．8 × 10 6 字节 / 秒　　　　　　　D．8M 字节 / 秒 【分析】：存储周期250ns，换算为250×10-9秒；每个存储周期可读出16位，为两个字节，则数据传送率为：2字节／（250×10-9）秒，即8×106字节／秒。 　　【答案】：C 13．半导体静态存储器 SRAM 的存储原理是（　）。 　　A．依靠双稳态电路　　　　　　　　　B．依靠定时刷新 　　C．依靠读后再生　　　　　　　　　　D．信息不再变化 　　【分析】：半导体静态存储器SRAM是由双稳态电路构成，并依靠其稳态特性来保存信息；动态存储器DRAM是利用电容器存