数据结构要点
第一章概论
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
************************************************************************
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型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)
************************************************************************
顺序队列的"假上溢"现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。
为了克服"假上溢"现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试（(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中所有顶点排成一个线性序列，若
拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。
第八章排序
************************************************************************
记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小；改变指向记录的指针或移动记录。
·存储结构：顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。
************************************************************************
插入排序：·直接插入排序：·逐个向前插入到合适位置。
·哨兵(监视哨)有两个作用：·作为临变量存放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章概论
一、名词解释：
历年真题：
名词解释题：
（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.0010101B．1.0010110C．0.0010110D．0.1101010
【分析】：正数的补码与原码相同，负数的补码是用正数的补码按位取反，末位加1求得。此题中X补为正数，则X原与X补相同。
【答案】：D
（2002年）2．若x=1011,则[x]补=( )。
A．01011B．1011C．0101D．10101
【分析】：x为正数，符号位为0,数值位与原码相同，结果为01011。
【答案】：A
（2003年）8．若［X］补=1.1011 ，则真值X 是（）。
A．-0.1011B．-0.0101C．0.1011D．0.0101
【分析】：[X]补=1.1011，其符号位为1，真值为负；真值绝对值可由其补码经求补运算得到，即按位取后得0.0100再末位加1得0.0101，故其真值为-0.0101。
【答案】：B
（2004年）13．设有二进制数x=－1101110，若采用8 位二进制数表示，则［X］补（）。
A．11101101B．10010011C．00010011D．10010010
【分析】：x=－1101110为负数，负数的补码是将二进制位按位取反后在最低位上加1，故[x] 补=10010010。
【答案】：D
（2005年）1．若[X]补=0.1011，则真值X=（）。
A．0.1011B．0.0101C．1.1011D．1.0101
【分析】：[X]补=0.1011，其符号位为0，真值为正；真值就是0.1011。
【答案】：A
由上可见，有关补码每年都考。同学也要注意一下移码。
（2001）3．若定点整数64 位，含 1 位符号位，补码表示，则所能表示的绝对值最大负数为（）。
A．-264B．-（264-1 ）C．-263D．-（263-1）
【分析】：字长为64位，符号位为1位，则数值位为63位。当表示负数时，数值位全0为负绝对值最大，为-263。
【答案】：C
（2002年）3．某机字长8位，含一位数符，采用原码表示，则定点小数所能表示的非零最小正数为（）
A．2-9B．2-8C．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是利用电容器存储电荷的特性存储数据，依靠定时刷新和读后再生对信息进行保存，而ROM中的信息一经写入就不再变化。
【答案】：A
2002年：
6．一般来讲，直接映象常用在（）。
A．小容量高速Cache B．大容量高速Cache
C．小容量低速Cache D．大容量低速Cache
【分析】：直接映象的地址转换速度快，但块的冲突概率较高。在大容量高速Cache系统中使用直接映象方式，即可以发挥Cache 的高速度，又可以减少块的冲突概率。
【答案】：B
7．下列存储器中，（）速度最快。
A．硬盘B．光盘C．磁带D．半导体存储器
【分析】：由于存储器原理和结构的不同，各种存储器的访问速度各不相同。以上存储器中访问速度由快到慢的顺序为：半导体存储器、硬盘、光盘、磁带。
【答案】：D
2003年：
15．在下列Cache 替换算法中，一般说来哪一种比较好（）。
A．随机法B．先进先出法
C．后进先出法D．近期最少使用法
【分析】：在Cache替换算法中，随机法是随机地确定替换的存储单元，先进先出法是替换最早调入的存储单元，它们都没有根据程序访存局部性原理，命中率较低；近期最少使用法比较正确地利用了程序访存局部性原理，替换出近期用得最少的存储块，命中率较高，是一种比较好的替换算法。而后进先出法不是Cache所使用的替换算法，此法在堆栈存储结构中使用。
【答案】：D
2004年：
8．表示主存容量的常用单位为（）。
A．数据块数B．字节数C．扇区数D．记录项数
【分析】：表示主存容量的常用单位字节B，是基本单位。此外还有KB、MB、GB、TB。
【答案】：B
11．存储器的随机访问方式是指（）。
A．可随意访问存储器
B．按随机文件访问存储器
C．可对存储器进行读出与写入
D．可按地址访问存储器任一编址单元，其访问时间相同且与地址无关
【分析】：存储器的随机访问方式是指可按地址访问存储器任一编址单元，其访问时间相同且与地址无关。
【答案】：D
2005年：
6．动态存储器的特点是（）。
A．工作中存储内容会产生变化
B．工作中需要动态改变访存地址
C．工作中需要动态地改变供电电压
D．需要定期刷新每个存储单元中存储的信息
【分析】：此题与2000年考题基本相同。动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会放电，必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍。
【答案】：D
7．组相联映象和全相联映象通常适合于（）。
A．小容量Cache B．大容量Cache
C．小容量ROM D．大容量ROM
【分析】：直接映象的地址转换速度快，但块的冲突概率较高。在大容量高速Cache系统中使用直接映象方式，即可以发挥Cache 的高速度，又可以减少块的冲突概率。组相联映象和全相联映象速度较低，通常适合于小容量Cache。
【答案】：A
第4章指令系统
一、名词解释：
历年真题：
2001年
3．堆栈：数据的写入写出不需要地址，按先进后出的顺序读取数据的存储区。
4．立即寻址方式：操作数直接在指令中给出。
六年以来就考了这2个名称解释，而且近4年都没有考，所以第四章的名称解释不是考试的重点，这里给大家列出了名词解释大家要熟悉一下，这都是本章的基本概念，有利于做选择题、改错题和填空题。
1．指令系统：计算机中各种指令的集合，它反映了计算机硬件具备的基本功能。
2．计算机指令：计算机硬件能识别并能直接执行操作的命令，描述一个基本操作。
3．指令编码：将指令分成操作码和操作数地址码的几个字段来编码。
4．指令格式：指定指令字段的个数，字段编码的位数和编码的方式。
5．立即数：在指令中直接给出的操作数。
6．指令字长度：一个指令字所占有的位数。
7．助记符：用容易记忆的符号来表示指令中的操作码和操作数。
8．汇编语言：采用文字方式（助记符）表示的程序设计语言，其中大部分指令和机器语言中的指令一一对应，但是不能被计算机的硬件直接识别。
9．伪指令：汇编语言程序所提供的装入内存中的位置信息，表示程序段和数据段开始信息及结束信息等。且不转换成2进制机器指令。
10．大数端：当一个数据元素的位数超过一个字节或者一个字的宽度，需存储在相邻的多个字节的存储位置时，将数据的最低字节存储在最大地址位置的存储方式。
11．小数端：当一个数据元素的位数超过一个字节或者一个字的宽度，需存储在相邻的多个字节的存储位置时，将数据的最低字节存储在最小地址位置的存储方式。
12．操作数寻址方式：指令中地址码的内容及编码方式。
13．系统指令：改变计算机系统的工作状态的指令。
14．特权指令：改变执行特权的指令，用于操作系统对系统资源的控制。
15．自陷指令：特殊的处理程序，又叫中断指令。
16．寻址方式：对指令的地址码进行编码，以得到操作数在存储器中的地址的方式。
17．相对转移：转移到的目标指令的地址与当前指令的地址有关，是用当前指令的PC与一个偏移量相加，和为目标指令的PC。
18．绝对转移：转移到的目标指令的地址与当前指令的地址无关，指令中给定的目标地址即为目标指令的PC。
19．无条件转移：一种转移指令类型，不管状态如何，一律进行转移操作。
20．条件转移：一种转移指令类型，根据计算机中的状态决定是否转移。
21．RISC：精简指令系统计算机，即指令系统中的指令数量少，且指令功能相对简单。
22．CISC：复杂指令系统计算机，即指令系统中的指令数量多，且指令功能相对较强。
23．堆栈：数据的写入写出不需要地址，按先进后出的顺序读取数据的存储区。
二、选择填空题：
历年真题
2000年：
3．在堆栈寻址中，设A为累加器，SP为堆栈指示器，Msp为SP指示的栈顶单元。如果进栈操作顺序是：（SP）-1→SP，（A）→Msp；那么出栈操作的顺序应是（）。
A．（Msp）→A，（SP）+1→SP
B．（SP）+1→SP，（Msp）→A
C．（SP）-1→SP，（Msp）→A
D．（Msp）→A，（SP）-1→SP
【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的操作有入栈和出栈两种，两者的操作完全相反，包括功能和顺序均相反。
【答案】：A
6．在按字节编址的存储器中，每个编址单元中存放（）。
A．1位B．8位C．16位D．32位
【分析】：在按字节编址在存储器中，每个编址单元的容量为一个字节，一个字节由8位二进制数组成，一个字节存储单元可以存放8位二进制位。
【答案】：B
4．在CPU的状态寄存器中，常设置以下状态位：零标志位（Z），负标志位（N），（）和（）。
【分析】：在CPU中专门设置有一个存储计算机状态的寄存器，称为状态寄存器SR,其中通常包括如下标志位：零标志位（Z）、负标志位（N）、溢出标志位（V）、进位或借位标志位（C）等。
【答案】：溢出标志位（V）、进位或借位标志位（C）
5．如指令中给出形式地址为D，则间接寻址方式获得操作数的有效地址为。
【分析】：在存储器间接寻址方式中，操作数的地址在主存储器中，其存储器地址在指令中给出。也就是说在指令中给出的既不是操作数，也不是操作数的地址，而是操作数地址的地址，则有效地址为以形式地址D为地址的存储单元的内容。
【答案】：以D为地址的存储单元的内容
13．如果说变址寻址方式主要是面向用户的，那么基址寻址一般是面向（）的。
【分析】：变址寻址方式是面向用户的，常用于访问字符串、向量数据结构和循环程序设计；而基址寻址方式是面向系统的，对由逻辑地址空间到物理地址空间的变换提供支持，用以解决程序在存储器中再定位和扩大寻址空间等问题。
【答案】：系统
2001年：
9．为了缩短指令中某个地址段的位数，有效的方法是采取（）。
A．立即寻址B．变址寻址
C．间接寻址D．寄存器寻址
【分析】：由于计算机中寄存器的数量一般很少，采用寄存器寻址时可用少量的代码来指定寄存器，这样可以减少对应地址段的代码位数，也可减少整个指令的代码长度。
【答案】：D
10．堆栈指针SP 的内容是（）。A．栈顶单元内容B．栈顶单元地址C．栈底单元内容D．栈底单元地址【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的访问由堆栈指针寄存器SP控制，其内容为堆栈中栈项单元的地址，即入栈时数据保存在SP指向的单元，出栈时将SP指向单元的内容取出。
【答案】：B
2002年：
8．采用直接寻址方式，则操作数在（）中。
A．主存B．寄存器C．直接存取存储器D．光盘
【分析】：直接寻址方式是指在指令中直接给出操作数在存储器中的地址，操作数在主存储器中，指令中的地址直接作为有效地址，对存储器进行访问即可取得操作数。
【答案】：A
9．零地址指令的操作数一般隐含在（）中。
A．磁盘B．磁带C．寄存器D．光盘
【分析】：零地址指令只有操作码，没有操作数。这种指令有两种情况：一是无需操作数，另一种是操作数为默认的（隐含的），默认为操作数在寄存器中，指令可直接访问寄存器。
【答案】：C
2003年：
3．假设寄存器R 中的数值为200 ，主存地址为200 和300 的地址单元中存效的内容分别是300 和400 ，则什么方式下访问到的操作数为200（）。
A．直接寻址200
B．寄存器间接寻址（R）
C．存储器间接寻址（200）
D．寄存器寻址R
【分析】：直接寻址200的操作数为300,寄存器间接寻址(R)的操作数300,存储器间接寻址（200）的操作数为400，寄存器寻址R 的操作数为200。
【答案】：D
5．单地址指令（）。
A．只能对单操作数进行加工处理
B．只能对双操作数进行加工处理
C．无处理双操作数的功能
D．既能对单操作数进行加工处理，也能在隐含约定另一操作数（或地址）时，对双操作数进行运算
【分析】：单地址指令既能对单操作数进行加工处理，也能对双操作数进行运算。当处理双操作数时，一个操作数在指令中给出，另一个操作数则是隐含约定的，例如堆栈操作指令中的入栈指令PUSH,指令中只给出源操作数，而目的操作数则由计算机中的堆栈指针（SP）确定，在指令中不需要指定。
【答案】：D
2004年：
14．反映计算机基本功能的是（）。
A．操作系统B．系统软件C．指令系统D．数据库系统
【分析】：指令系统：计算机中各种指令的集合，它反映了计算机硬件具备的基本功能。
【答案】：C
2005年：
8．在大多数情况下，一条机器指令中是不直接用二进制代码来指定（）。
A．下一条指令的地址
B．操作的类型
C．操作数地址
D．结果存放地址
答案：A
9．在存储器堆栈中，若栈底地址为A，SP指针初值为A-1，当堆栈采用从地址小的位置向地址大的位置生成时，弹出操作应是（）。
A．先从堆栈取出数据，然后SP指针减1
B．先从堆栈取出数据，然后SP指针加1
C．SP指针先加1，然后从堆栈取出数据
D．SP指针先减1，然后从堆栈取出数据
【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的访问由堆栈指针寄存器SP控制，当堆栈采用从地址小的位置向地址大的位置生成时，入栈操作是SP指针先加1，然后将数据存入堆栈，从堆栈取出弹出操作是先从堆栈取出数据，然后SP指针减1。
【答案】：A
10．转移指令执行结束后，程序计数器PC中存放的是（）。
A．该转移指令的地址
B．顺序执行的下条指令地址
C．转移的目标地址
D．任意指令地址
【分析】：转移指令执行过程中，将转移指令所指的子程序的起始地址装入PC，因此转移指令执行结束后，程序计数器PC中存放的是转移的目标地址。
【答案】：C
三、改错题：
3．在寄存器寻址方式中，指定寄存器中存放的是操作数地址。（2000）
【分析】：在寄存器间接寻址方式中，指定寄存器中存放的是操作数地址；而在寄存器寻址方式中，指定寄存器中存放着操作数。
【答案】：在寄存器寻址方式中，指定寄存器中存放着操作数。
1．在计算机中，各指令周期的时间长度是相同的。（2002）
【分析】：在计算机中，由于指令的种类不同，功能不同，执行每条指令时机器所进行的操作可能就不同，所需要的时间长短也可能不相同，所以各指令周期的时间长度不一定相同。
【答案】：一般说，由于各指令功能的不同，它们的指令周期有长有短，不一定相同。
22．转移指令执行结束后，目标地址可放在任意寄存器中。（2004年）
【分析】：转移指令执行过程中，将转移指令所指的子程序的起始地址装入PC，因此转移指令执行结束后，程序计数器PC中存放的是转移的目标地址。
【答案】：转移指令执行结束后，目标地址放在程序计数器PC中。
第5章控制器
一、名词解释：
历年真题：
（2001年）6．逻辑地址：程序员编程所用的地址以及CPU通过指令访问主存时所产生的地址。与内存物理地址无固定对应关系的地址。
（2001年）7．微程序控制器：将执行指令所需要的微命令以代码形式编成微指令序列（微程序），存入一个控制存储器，需要时从该存储器中读取。按这种方式工作的控制器为微程序控制器。
（2002年）3．控制存储器（CPU内的）：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制存储器。
（2004年）20．垂直型微指令：一种微指令类型，设置微操作码字段，采用微操作码编码法，由微操作码规定微指令的功能。
（2005年）23．微程序控制器：将执行指令所需要的微命令以代码形式编成微指令序列（微程序），存入一个控制存储器，需要时从该存储器中读取。按这种方式工作的控制器为微程序控制器。
近年以来每年考本章的名词解释，所以第五章的名称解释是考试的重点。这里给大家列出了本章的名词解释，大家要熟悉一下，这都是本章的基本概念，有利于做名称解释、选择题、改错题和填空题。
1．指令周期：从一条指令的启动到下一条指令的启动的间隔时间。
2．机器周期：指令执行中每一步操作所需的时间。
3．指令仿真：通过改变微程序实现不同机器指令系统的方式，使得在一种计算机上可以运行另一种计算机上的指令代码。
4．指令模拟：在一种计算机上用软件来解释执行另一种计算机的指令。
5．硬连线逻辑：一种控制器逻辑，用一个时序电路产生时间控制信号，采用组合逻辑电路实现各种控制功能。
6．微程序：存储在控制存储中的完成指令功能的程序，由微指令组成。
7．微指令：控制器存储的控制代码，分为操作控制部分和顺序控制部分。
8．微操作：在微程序控制器中，执行部件接受微指令后所进行的操作。
9．微地址：微每时令在控制存储器中的存储地址。
10．控制存储器：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制存储器。
11．相容性微操作：在同时或同一个CPU周期内可以并行执行的微操作。
12．相斥性微操作：不能在同时或不能在同一个CPU周期内并行执行的微操作。
二、选择题和填空题：
2000年：
4．在取指周期中，是按照（）的内容访问主存，以读取指令。
A．指令寄存器IR B．程序状态寄存器PS
C．存储器数据寄存器MDR D．程序计数器PC
【分析】：每一条指令的执行都是从取指令开始，需要对主存储器进行访问。程序计数器PC是用来存放将要读取并执行的指令在主存储器中的地址，对主存储器访问时所需要的地址由程序计数器PC来提供，即需要按程序计数器PC的内容来访问主存储器。
【答案】：D
7．在微程序控制中，一个节拍中所需要的一组微命令，被编成一条（。
【分析】：控制部件通过控制总线向执行部件发出的控制命令称为微命令，它是计算机中最基本的、不可再分的命令单元。在一个节拍中，一组实现一定功能的微命令的组合构成一条微指令。
【答案】：微指令
2002年：
10．微程序存放在（）。
A．主存中B．堆栈中C．只读存储器中D．磁盘中
【分析】：微程序控制的基本思想是把指令执行所需的所有控制信号存放在存储器中，需要时从这个存储器中读取。由于每一条微指令执行时所发出的控制信号是事先设计好的，不需要改变，故此存放所有控制信号的存储器应为只读存储器，并将其集成到CPU 内，称其为控制存储器。
【答案】：C
11．在微程序控制方式中，机器指令和微指令的关系是（）。
A．每一条机器指令由一条微指令来解释执行
B．每一条机器指令由一段（或一个）微程序来解释执行
C．一段机器指令组成的工作程序可由一条微指令来解释执行
D．一条微指令由若干条机器指令组成
【分析】：在微程序控制方式中，控制部件通过控制总线向执行部件发出的各种控制命令称为微命令，在一个CPU周期中，一组实现一定功能的微命令的组合构成一条微指令，有序的微指令序列构成一段微程序。微程序的作用是实现一条对应的机器指令，即每一条机器指令是由一段（或一个）微程序来解释执行的。
【答案】：B
2003年：
7．下列说法中，合理的是（）。
A．执行各条指令的机器周期数相同，各机器周期的长度均匀
B．执行各条指令的机器周期数相同，各机器周期的长度可变
C．执行各条指令的机器周期数可变，各机器周期的长度均匀
D．执行各条指令的机器周期数可变，各机器周期的长度可变
【分析】：机器周期是指令执行中每一步操作所需要的时间，一般以CPU中完成一个运算操作所需的时间作为机器周期的基本时间，其长度是均匀的，而各种指令的功能不同，因而各指令执行时所需的机器周期数是可变的。
【答案】：C
10．微地址是指微指令（）。
A．在主存的存储位置B．在堆栈的存储位置
C．在磁盘的存储位置D．在控制存储器的存储位置
【分析】：微程序控制的基本思想是：把指令执行所需要的所有控制信号存放在控制存储器中，需要时从这个存储器中读取，即把操作控制信号编成微指令，存放在控制存储器中。一条机器指令的功能通常用许多条微指令组成的序列来实现，这个微指令序列称为微程序。微指令在控制存储器中的存储位置称为微地址。
【答案】：D
2004年：
5．在微程序控制中，把操作控制信号编成（）。
A．微指令B．微地址C．操作码D．程序
【分析】：微程序控制的基本思想是：把指令执行所需要的所有控制信号存放在控制存储器中，需要时从这个存储器中读取，即把操作控制信号编成微指令，存放在控制存储器中。一条机器指令的功能通常用许多条微指令组成的序列来实现，这个微指令序列称为微程序。微指令在控制存储器中的存储位置称为微地址。
【答案】：A
6．从一条指令的启动到下一条指令的启动的间隔时间称为（）。
A．时钟周期B．机器周期C．工作周期D．指令周期
【分析】：指令周期：从一条指令的启动到下一条指令的启动的间隔时间。机器周期：指令执行中每一步操作所需的时间，又称CPU周期。时钟周期：计算机主频周期。
【答案】：D
2005年：
11．通常，微指令的周期对应一个（）。
A．指令周期B．主频周期C．机器周期D．工作周期
【分析】：指令周期：从一条指令的启动到下一条指令的启动的间隔时间。机器周期：指令执行中每一步操作所需的时间，又称CPU周期。时钟周期：计算机主频周期。微指令周期等于读出一条微指令加上执行该微指令的所需时间。通常微指令周期与指令的机器周期相等。
【答案】：C
19．在微程序控制器中，控制存储器由（）构成，用于存放。
【分析】：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制存储器。
【答案】：只读存储器微程序
三、改错题：
历年真题：
（2000年）9．单总线结构系统是指：各大功能部件之间用一根信号线连接。
【答案】：单总线结构系统是指各寄存器及ALU之间的数据通路只用一条总线构成。
（2002年）2．CPU只是计算机的控制器。
【分析】：计算机硬件系统是由运算器、控制器、存储器、输入设备和输出设备等五大部分组成，其中将运算器和控制器合在一起称为中央处理器，简称为CPU。
【答案】：CPU是由控制器和运算器组成的。
（2003年）21．硬连线方式是用时序电路产生时间控制信号，用存储逻辑电路实现各种控制功能。
【分析】：在采用组合逻辑和时钟信号相结合的硬连线控制器中，时间控制信号是由时序电路产生，而各种控制功能则是由组合逻辑电路实现。
【答案】：硬连线方式是用时序电路产生时间控制信号，用组合逻辑电路实现各种控制功能。
（2004年）21．在一条微指令中，顺序控制部分的作用是发出指挥全机工作的控制信号。
【分析】：在一条微指令中，控制字部分的作用是发出指挥全机工作的控制信号；顺序控制部分的作用是产生后继微指令的地址。
【答案】：在一条微指令中，顺序控制部分的作用是产生后继微指令的地址。
四、简答题：
历年真题：
（2000年）4．在CPU中，哪些寄存器属于控制用的指令部件？它们各起什么作用？（5分）
【答案】：
（1）程序计数器PC，提供取指地址，从而控制程序执行顺序。
（2）指令寄存器IR，存放现行指令，作为产生各种微操作命令的基本逻辑依据。
（3）程序状态寄存器PS，记录程序运行结果的某些特征标志，或用来设置程序运行方式与优先级，参与形成某些微操作命令。
（2001年）1．硬连线控制器如何产生微命令？产生微命令的主要条件是哪些？
【答案】：
硬连线控制器依靠组合逻辑电路产生命令；（1分）
组合逻辑电路的输入是产生微命令的条件，主要有：①指令代码；②时序信号；③程序状态信息与标志位；④外部请求信号。（4分）
（2002年）3．微程序控制器怎么产生操作控制信号，这种控制器有何优缺点？
【答案】：
操作控制信号的产生：事先把操作控制信号以代码形式构成微指令，然后存放到控制存储器中，取出微指令时，其代码直接或译码产生操作控制信号。
优点：规整、易于修改和扩展。
缺点：速度较慢。
（2003年）26．当读取并执行一条指令时，控制器的主要功能是什么？
【答案】：
①从主存取指令，并计算下一条指令在主存中的地址；
②对指令进行译码，产生相应的操作控制信号；
③控制指令执行的步骤和数据流动的方向。
（2004年）28．与硬连线控制器相比，微程序控制器有哪些优缺点？
【答案】：与硬连线控制器相比，微程序控制器的优点是设计规整、易于修改和扩展。缺点是比硬连线控制器速度慢。
（2005年）28．硬连线控制器主要由哪几部分构成？它是如何产生控制信号的？
【答案】：硬连线控制器主要由时钟源、环形脉冲发生器、控制信号编码器电路和指令译码器电路构成。硬连线控制器采用组合逻辑与时钟信号结合的方式产生控制信号。
由上可见，每年都会考本章的简答题。考试的两个重点：一个是硬连线控制器的有关知识，另一个是微程序控制器有关内容。这两方面大家一定重点掌握。
下面一些知识也要求大家了解
微程序控制器的构成：控制存储器、微指令寄存器μIR、微地址寄存器μAR、地址转移逻辑等。
微指令控制字编码的方式：微指令编码的3种方式分别是：直接表示法、编码表示法、混合表示法。
直接表示法是将每个控制信号都作为微指令中的一个位。这种方法的特点是简单直观，其输出直接用于控制，但编码效率低。
编码表示法是将微指令进行分组编码，将不同时出现的相斥信号分在一个组中，然后将其编码成较短的代码。这种方法减少了控制存储器所需要的存储器的代码的数量，但是编码的指令代码需要译码器译码，增加了控制信号的延迟，影响CPU的工作频率。
混合表示法是把直接表示法与编码方法相结合使用，即采用部分直接表示部分编码的方法，将一些速度要求较高，或与其他控制信号都相容的控制信号以直接方式表示，而将剩余信号以编码方式。混合表示法便于综合考虑指令字长、灵活性和执行速度方面的要素。
微地址的形成方法：（微指令中顺序控制字段的编码）微地址的形成方法有三种方式：计数器方式、断定方式和结合方式。
计数器方式，又称增量方式。用微程序计数器μPC来产生指令的微地址，将微程序中的各条微指令按顺序安排在控制存储器中，后继地址由现行微地址加上一个增量形成。
断定方式，根据机器状态决定下一条微指令的地址，下一条微指令的地址包含在当前微指令的代码中。
结合方式，是将计数器方式和断定方式相结合。
中央处理器的基本功能：计算机的中央处理器（CPU）具有以下4个方面的基本功能：
（1）指令控制，即对程序运行的控制；
（2）操作控制，即对指令内操作步骤的控制；
（3）数据运算，即对数据进行算术运算和逻辑运算，这是CPU的最基本功能；
（4）异常处理和中断处理，如处理运算中的溢出等错误情况以及处理外部设备的服务请求等此外，CPU还具有存储管理、总线管理、电源管理等扩展功能
第6章总线系统
一、名词解释：
历年真题：
（2001年）5．总线：计算机中连接功能单元的公共线路，是一束信号线的集合，包括数据总线、地址总线和控制总线。
（2001年）8．同步通信方式：采用这种方式的总线传输中，所有的设备都从一个公共的时钟信号中获得定时信息。
（2002年）4．主设备：获得总线控制权的设备。
（2003年）19．猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式。
（2004年）16．总线的同步通信方式：采用这种方式的总线传输中，所有的设备都从一个公共的时钟信号中获得定时信息。
（2005年）24．总线从设备：被主设备访问的设备。
近年以来每年考本章的名词称解释，所以第五章的名称解释是考试的重点。这里给大家列出了本章的名词解释，大家要熟悉一下，这都是本章的基本概念，有利于做名称解释、选择题、改错题和填空题。
1、猝发转输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式。
2、四边沿协议（全互锁）：全互锁的总线通信异步方式，就绪信号和应答信号的上升边沿和下降边沿都是触发边沿。
3、码元：信息传输通道中，携带数据信息的信号单元。
4、波特率：码元传输速率，每秒通过信道传输的码元数。（传的是信号）
5、比特率：信息位传输速率，每秒钟通过信道传输的有效信息量。（传的是信息）
6、UART：通用异步接收器/发送器，一种典型的集成电路异步串行接口电路。
7、主设备：获得总线控制权的设备。
8、从设备：被主设备访问的设备。
9、总线事务：从总线的请求到完成总线的使用的操作序列。
10、总线协议：总线通信同步方式规则，规定实现总线数据传输的定时规则。
11、总线访问延迟：是主设备为获得总线控制权而等待的时间。
12、总线周期：是主设备占用总线的时间。
13、总线裁决方式：决定总线由哪个设备进行控制的方式。
14、系统总线：是用来连接系统内各大功能模块或设备，实现系统种各电路板的连接。
15、数据帧：串行数据传输的位格式，包括起始位，数据位，校验位，结束位和空闲位。
16、同步通信：所有的设备都从一个公共的时钟信号中获得定时信息。
17、异步通信：使用一个在CPU和设备之间的"握手"信号，去除了公共的时钟信号，从而使得操作变成异步的。非互锁、半互锁、全互锁。
18、链式查询方式（菊花链方式）：各申请总线的设备合用一条总线作为请求信号线，而总线控制设备的响应信号线则串接在各设备间。
19、计数器定时查询方式：集中式总线裁决方式之一，设备要求使用总线时通过一条公用请求线发出，总线控制器按计数的值对各设备进行查询。
20、独立请求方式：集中式总线裁决方式之一，每一个设备都有一个独立的总线请求信号线送到总线控制器，控制器也给各设备分别发送一个总线响应信号。
21、串行传输：是指数据的传输在一条线路上按位进行。（只需一条数据传输线，线路的成本低，适合于长距离的数据传输）
22、并行传输：每个数据位都需要单独一条传输线，所有的数据位同时进行传输。（在采用并行传输方式的总线中，除了有传输数据的线路外，还可以具有传输地址和控制信号的线路，地址线用于选择存储单元和设备，控制线用于传递操作信号）
23、复合传输：又称总线复用的传输方式，它使不同的信号在同一条信号线上传输，不同的信号在不同的时间片中轮流地身总线的同一条信号线上发出。（它与并串传输的区别在于分时地传输同一数据源的不同信息。）
24、消息传输方式：总线的信息传输方式之一，将总线需要传送的数据信息、地址信息、和控制信息等组合成一个固定的数据结构以猝发方式进行传输。
25、总线：一组可由多个部件分时共享的信息传输线。
二、选择填空题：
历年真题：
2000年：
8．“总线忙”信号由（）建立。
A．获得总线控制权的设备B．发出“总线请求”的设备
C．总线控制器D．CPU
【分析】：在总线控制机制中，准备使用总线的设备向总线控制器发出“总线请求”由总线控制器进行裁决。如果经裁决允许该设备使用总线，就由总线控制器向该设备发出一个“总线允许”信号。该设备接收到此信号后，发出一个“总线忙”信号用来通知其他设备总线己被占用。当该设备使用完总线时，将“总线忙”信号撤销，释放总线。
【答案】：A
12．系统总线是用来连接（）的总线。
【分析】：按总线的连线类型不同，总线可分为：①芯片级总线（CPU内部总线）：连接CPU内部运算器、控制器、寄存器等的数据通路。②扳级总线：连接主板中的CPU和主存等部件，也称局部总线。③系统总线是用来连接系统内各大功能模块或设备。
【答案】：系统内各大功能模块或设备
14．并行接口与I/O设备之间同时传送的位数，大多是（）位。
【分析】：并行接口与I/O设备之间同时传送的8位数（1个字节）
【答案】：8
2001年：
14．在不同速度的设备之间传送数据，（）。
A．必须采用同步控制方式
B．必须采用异步控制方式
C．可以选用同步方式，也可选用异步方式
D．必须采用应答方式
【分析】：在不同速度的设备之间进行数据传送，既可以使用同步方式，也可以使用异步方式。异步方式主要是用于在不同的设备之间进行通信，而如果两种速度的设备使用同一个时钟信号进行控制，采用同步的数据传送方式，同样可以进行数据的传送，只是快速设备的速度性能发挥不出来。
【答案】：C
15．挂接在总线上的多个部件（）。
A．只能分时向总线发送数据，并只能分时从总线接收数据
B．只能分时向总线发送数据，但可同时从总线接收数据
C．可同时向总线发送数据，并同时从总线接收数据
D．可同时向总线发送数据，但只能分时从总线接收数据
【分析】：为了使总线上的数据不发生“碰撞”，挂接在总线上的多个设备只能分时地向总线发送数据，即每一个时刻只能有一个设备可以向总线传送数据，而从总线上接收数据的设备可有多个，因为接收数据的设备不会对总线产生“干扰”。
【答案】：B
2002年：
12．异步传送方式常用于（）中，作为主要控制方式。
A．微型机的CPU内部控制
B．硬连线控制器
C．微程序控制器
D．串行I/O总线
【分析】：异步传输方式主要用于控制两种速度有一定差别的设备的信息传送，一般用在快速CPU与慢速的外设之间进行串行通信的场合。
【答案】：D
13．串行总线主要用于（）。
A．连接主机与外围设备
B．连接主存与CPU
C．连接运算器与控制器
D．连接CPU内部各部件
【分析】：串行通信方式由于其信息传送速度慢、信息传送的距离较长、所使用的信号线数量较少等特点，主要用于连接主机和慢速的外围设备，例如主机与串行鼠标之间的信息传送。
【答案】：A
2003年：
4．下列说法中正确的是（）。
A．半双工总线只能在一个方向上传输信息，全双工总线可以在两个方向上轮流传输信息
B．半双工总线只能在一个方向上传输信息，全双工总线可以在两个方向上同时传输信息
C．半双工总线可以在两个方向上轮流传输信息，全双工总线可以在两个方向上同时传输信息
D．半双工总线可以在两个方向上同时传输信息，全双工总线可以在两个方向上轮流传输信息
【分析】：根据总线上信号的传递方向，总线可分为单向传输（单工）总线和双向传输（双工）总线，而双工总线又可分为半双工总线和全双工总线。其中单工总线只能向一个方向传递信号，半双工总线可以在两个方向上轮流传递信号，全双工总线可以在两个方向上同时传递信号。【答案】：C
9．在总线上，同一时刻（）。
A．只能有一个主设备控制总线传输操作
B．只能有一个从设备控制总线传输操作
C．只能有一个主设备和一个从设备控制总线传输操作
D．可以有多个主设备控制总线传输操作
【分析】：总线上的设备要控制总线必须先获得总线的控制权，获得总线控制权的设备称为主设备，被主设备访问的设备称为从设备。在总线上信息的传输由主设备启动，一条总线上可以有多个设备能成为主设备，但在同一时刻只能有一个主设备控制总线的传输操作。
【答案】：A
2004年：
4．系统级的总线是用来连接（）。
A．CPU 内部的运算器和寄存器
B．主机系统板上的所有部件
C．主机系统板上的各个芯片
D．系统中的各个功能模块或设备
【分析】：按总线的连线类型不同，总线可分为：①芯片级总线（CPU内部总线）：连接CPU内部运算器、控制器、寄存器等
834 计算机专业基础综合(数据结构、计算机网络) 研究生入学考试大纲 数据结构部分（占60%） 【考试范围】 线性表（包括队列、堆栈等特殊线性表）的基本逻辑结构特征理解与应用；线性表（包括队列、堆栈等特殊线性表）的物理存贮结构；特殊矩阵的存贮及应用；树、图等非线性结构的基本逻辑结构特征理解与应用；树、图等非线性结构的物理存贮结构。排序与查找算法；一些算法的设计与时间复杂度分析。 【具体内容】 一绪论 1引言 2 什么是数据结构 3 相关基本概念和术语 4 算法的基本特征 5 算法分析相关概念 二线性表 1 线性表的概念，线性表的抽象数据类型，基本操作 2 线性表的顺序存储结构：静态分配，动态分配 3 顺序表的插入删除算法，移动元素次数分析 4 顺序存储结构的优缺点，引出单链表的结构类型定义 5 单链表的算法：生成先进先出单链表，后进先出单链表 6 单链表的算法：生成不带表头的递增有序单链表，生成带表头的递增有序单链表 7 单链表的算法：在指定位置插入一个新结点；删除指定值的结点；在指定位置删除一个结点； 8 单链表的合并：两个递增有序的单链表合并成一个递增有序的单链表 9 循环链表的概念，双向循环链表的概念，插入和删除结点 10 多项式的链表表示，算法思想 三栈和队列 1 栈的相关概念与特性 2 顺序栈的基本操作 3 链式栈的基本操作 4 栈的应用 5 队列的相关概念
6 链式队列的基本操作 7 顺序队列的基本操作 四数组 1 抽象数据类型数组的说明 2 数组的物理结构 3 特殊矩阵的压缩存储: 对称矩阵与三对角矩阵的压缩存储 4 稀疏矩阵的压缩存储：三元组顺序表与十字链表 5 稀疏矩阵的运算（转置算法） 6 广义表的概念：概念、物理结构、递归算法 五树与二叉树 1 树的有关概念 2 二叉树的定义与性质 3 二叉树的存储结构 4 二叉树的遍历 5二叉树遍历的应用 6 树的存储结构 7 树与二叉树的相互转换 8 树与森林的遍历 9 哈夫曼树 10、哈夫曼算法 六图 1 图的定义及术语 2 图的物理存贮结构：邻接矩阵、邻接表、十字链表和邻接多重表 3 图的遍历：深度优先搜索遍历与广度优先搜索遍历 4 图的连通性问题：DFS与BFS生成树、强连通分量的求解，最小生成树 5 有向无环图及应用: 拓扑排序、关键路径 6 最短路径：迪杰斯特拉算法、弗洛伊德算法 七查找 1 查找问题概述 2 顺序查找法 3 折半查找法 4 分块查找法 5 二叉排序树查找法 6 平衡二叉排序树查找法 7 B-树查找法和B+树查找法 8 键树查找法 9 哈希查找法
2015 年全国硕士研究生入学统一考试 计算机学科专业基础综合试题 一、单项选择题：140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只 有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。 1．已知程序如下： int s(int n) {return (n<=0) ? 0 : s(n-1) +n;} void main() {cout<< s(1);} 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ． main()->S(1)->S(0)B． S(0)->S(1)->main() C． main()->S(0)->S(1) D ． S(1)->S(0)->main() 2．先序序列为a,b,c,d 的不同二叉树的个数是 A．13B．14C．15D．16 3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是 A ． 24， 10，5 和 24，10， 7 C．24， 10，10 和 24， 14， 11 4．现在有一颗无重复关键字的平衡二叉树B． 24， 10， 5 和 24， 12， 7 D． 24，10， 5 和 24， 14， 6 （AVL 树） ,对其进行中序遍历可得到一个降 序序列。下列关于该平衡二叉树的叙述中，正确的是 A ．根节点的度一定为2 C．最后插入的元素一定是叶节点B．树中最小元素一定是叶节点D ．树中最大元素一定是无左子树 5．设有向图 G=(V,E)，顶点集 V={V 0,V 1,V 2,V 3} ，边集 E={
前言： IGCSE 国际考必考的内容。依照剑桥大学出版的教材同步编写的。 计算机其实就是一个“ 1. 获得输入数据； 2. 运算处理数据； 3. 输出新的数据；”的机器。 第一节二进制 1. 计算机的核心硬件包括： 中央处理器(CPU), 内存(Memory), 硬盘(Hard disc) ，显卡(Graphics card)。 这些硬件互相配合，接收输入的数据，然后进行运算再输出。 2.是通过什么来传送数据信号的呢？ l 计算机采用的是电平信号。并且只有两种信号：高电平和低电平。 l 电平是个电压范围，规定输出高电平>2.4V,输出低电平<0.4V。 l 因为只有两种信号，精确度就会比较高，不容易因为硬件的故障损耗，产生误差。能保证我发出去的信号，别人接收的时候是准确的。不会因为电路硬件问题导致输出的信号变弱，使得接收者接收了错误的信号。 l 高电平用1表示，低电平用0表示。 3.二进制系统(Binary Systems) 计算机因为只能传输和识别高低电平两种信号，所以我们采用了1和0来表示信号，也就产生了二进制。 二进制说是满二进一的计数制度。这是根据计算机传输信号的特点而定制的。 4.二进制转换 十进制转化成二进制：有一个最简单的方法，就是不断除以2。余数写在右边。然后从最后一个得到的商倒回去（商余数排列起来），得到的数就是二进制要表达的结果了
二进制转化十进制：2^(n-1) + 2^(n-2) + ...+2^0 第二节位和字节 1.保存数据的方式 计算机只能传送高低电平信号，所以需要采用二进制。内存保存数据的时候，也是要采用二进制的方式来保存的。 2.数据怎么断开，几位二进制数算做一个数据？ l 保存一个二进制数据的内存空间称做“ 位（bit ），只能保存一个二进制数，并且值只有0或者1两种。 l 我们规定8位空间称为一个字节（byte）。 l 通常用字节来作为存储单位。正常情况下一个英文字符，一个整数数字都是占用一个字节。长整数，浮点数，汉字等占用两个字节。 第三节存储单位
2015年全国硕士研究生入学统一考试 计算机学科专业基础综合试题 一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题目要求。请在答题卡上将所选项的字母涂黑。 1．已知程序如下： int s(int n) { return (n<=0) ? 0 : s(n-1) +n; } void main() { cout<< s(1); } 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main() C．m ain()->S(0)->S(1) D．S(1)->S(0)->main() 2．先序序列为a,b,c,d的不同二叉树的个数是 A．13 B．14 C．15 D．16 3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是 A．24，10，5和24，10，7 B．24，10，5和24，12，7 C．24，10，10和24，14，11 D．24，10，5和24，14，6 4．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是 A．根节点的度一定为2 B．树中最小元素一定是叶节点 C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树 5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={
计算机基础试题及答案 一、选择题 1. 冯·诺依曼计算机工作原理的设计思想是。(B) A. 程序设计 B. 程序存储 C. 程序编制 D. 算法设计 2. 计算机的逻辑判断能力决定于(C) A. 硬件 B. 体积 C. 编制的软件 D. 基本字长 3. 构成计算机物理实体的部件称为(C) A. 计算机软件 B. 计算机程序 C. 计算机硬件 D. 计算机系统 4. 微型计算机的微处理器芯片上集成了(A) A. 控制器和运算器 B. CPU和RAM C. 控制器和RAM D. 运算器和I/O接口
5. 计算机中运算器的主要功能是完成。(C) A. 代数和四则运算 B. 代数和逻辑运算 C. 算术和逻辑运算 D. 算术和代数运算 6. 将十进制数93转换为二进制数为(D) A．1110111 B．1110101 C．1010111 D．1011101 7. 具有多媒体功能的微型计算机系统，通常都配有CD-ROM，这是一种 (D) A. 只读内存储器 B. 只读大容量光盘 C. 只读硬盘存储器 D. 只读光盘存储器 8. 在Windows XP中，可以同时运行多少个程序。(D) A）1 B）2 C）10 D）多个 9. 在Windows XP中，如果进行了多次剪切操作，则剪贴板中的内容是 ( B ) A．第一次剪切的内容 B．最后一次剪切的内容 C．所有剪切的内容 D．什么内容也没有 10. 在Windows XP中，下面关于文件夹的描述正确的是 ( A ) A．文件夹中可以包含子文件夹和文件 B．文件夹中只能包含子文件夹 C．文件夹中只能包含文件 D．文件夹中不能包含子文件夹和文件 11. 当已选定文件夹，下列操作中不能删除该文件夹的是( D )
计算机专业基础知识 一、计算机的概念 计算机是一种能快速、高效、自动地完成信息处理的电子设备，它能按照程序对信息进行加工、处理、存储。二、计算机的诞生与发展 1. 诞生：1946年，美国为计算弹道轨迹而研制成功了世界第一台计算机ENIAC （Electronic Numerical Integrator And Computer）。在第一台计算机的基础上，美籍匈牙利科学家冯·诺伊曼提出存储程序的通用电子计算机EDVAC的方案，大大推动了计算机的发展。 微型计算机的发展史实际上就是微处理器的发展史。 2. 发展： 阶段时间逻辑器件应用范围 第一代 1946——1958 真空电子管科学计算、军事研究第二代 1959——1964 晶体管数据处理、事物处理第三代 1965——1970 集成电路包括工业控制的各个领域第四代 1971——大规模集成电路应用到了各个领域 三、计算机的主要应用 1. 科学计算：弹道轨迹、天气预报、高能物理等 2. 信息处理：企业管理、物资管理、电算化等 3. 过程控制：工业自动化控制，卫星飞行方向控制 4. 辅助工程：CAD（计算机辅助设计）、CAM（计算机辅助制造）、CAT（计算机辅助 测试）、CAI（计算机辅助教学）等 5. 电子商务 四、微型机的主要性能指标 1. 字长：指计算机能够直接处理的二进制数据的位数。单位为：位（BIT）。字长越长，计算机处理数据的精度越高。 2. 主频：指计算机主时钟在一秒钟内发出的脉冲数。它在很大程度上决定了计算机的运算速度。 3 . 内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 8BIT＝1BYTE 1024B＝1KB 1024KB＝1MB 1024MB＝1GB 4. 存取周期：内存储器完成一次完整的读操作或写操作所用的时间。 5. 运算速度：计算机每秒钟所能执行的指令条数，单位是：百万条/秒（MIPS）。五、计算机语言 主要包括：机器语言、汇编语言、高级语言六、计算机病毒 计算机病毒是人为编制的特殊程序，它潜伏在计算机系统中，能够在特定的条件下被激活，进行复制、传播，从而达到破坏计算机系统和数据的目的。它具有传染性、隐蔽性、触发性、潜伏性、破坏性等特点。七、计算机在会计核算中的作用 1. 提高工作效率 2. 提高工作质量 3. 促进会计工作规范化 4. 打破传统会计工作的范围，促进企业管理信息化 第二部分计算机系统的组成 计算机系统由硬件系统和软件系统组成，结构如图：
大学计算机基础模拟题 一、单选题 1、完整的计算机系统由（C）组成。 A、运算器、控制器、存储器、输入设备和输出设备 B、主机和外部设备 C、硬件系统和软件系统 D、主机箱、显示器、键盘、鼠标、打印机 2、以下软件中，（D）不是操作系统软件。 A、Windowsxp B、unix C、linux D、microsoft office 3、用一个字节最多能编出（D）不同的码。 A. 8个 B. 16个 C. 128个 D. 256个 4、任何程序都必须加载到（C）中才能被CPU执行。 A. 磁盘 B. 硬盘 C. 内存 D. 外存 5、下列设备中，属于输出设备的是（A）。 A、显示器 B、键盘 C、鼠 标D、手字板 6、计算机信息计量单位中的K代表（B）。 A. 102 B. 210 C. 103 D. 28 7、RAM代表的是（C）。
A. 只读存储器 B. 高速缓存器 C. 随机存储 器 D. 软盘存储器 8、组成计算机的CPU的两大部件是（A）。 A、运算器和控制器 B. 控制器和寄存器 C、运算器和内存 D. 控制器和内存 9、在描述信息传输中bps表示的是（D）。 A、每秒传输的字节数 B、每秒传输的指令数 C、每秒传输的字数 D、每秒传输的位数 10、微型计算机的内存容量主要指（A ）的容量。 A.RAM B.ROM C.CMOS D.Cache 11、十进制数27对应的二进制数为( D )。 A.1011 B. 1100 C. 10111 D. 11011 12、Windows的目录结构采用的是（A）。 A、树形结构 B、线形结构 C、层次结构 D、网状结构 13、将回收站中的文件还原时，被还原的文件将回到（D）。 A、桌面上 B、“我的文档”中 C、内存中 D、被删除的位置
考试性质 计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。 II考查目标 计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。III考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 二、答题方式 答题方式为闭卷、笔试。 三、试卷内容结构 数据结构45分 计算机组成原理45分 操作系统35分 计算机网络25分 四、试卷题型结构 单项选择题80分(40小题，每小题2分)
综合应用题70分 IV考查内容 数据结构 【考查目标】 1.掌握数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、栈、队列和数组 (一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 三、树与二叉树
833“计算机学科专业基础综合”复习参考提纲 一、考察目标 计算机学科专业基础综合考试涵盖数据结构、计算机组织与体系结构、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 二、考试形式和试卷结构 1、试卷满分及考试时间：本试卷满分为150，考试时间为180分钟 2、答题方式：闭卷，笔试 3、试卷内容结构：数据结构45分、计算机组织与体系结构45分、操 作系统35分、计算机网络25分 三、考察范围 数据结构： 【总体要求】 “数据结构”要求学生掌握数据结构的基本理论和基本方法，使学生具备基本的数据结构分析、设计、求解实际问题的能力。要求掌握数据结构的基本概念、基本原理和基本方法；掌握线性表、树与二叉树、图的逻辑结构、物理结构、基本操作，以及基本操作在不同的物理结构上的实现，并能够对操作算法进行基本的时间复杂度和空间复杂度进行分析；掌握基本的查找和排序方法，并能够利用这些方法对实际问题进行分析和求解，具备采用C或C++或JA V A 语言设计与实现算法的能力。 （一）数据结构基本概念 1.复习内容 数据结构、算法的基本定义，数据结构的逻辑结构和物理结构，算法的性能评价方法。 2.具体要求 数据结构的定义
数据结构的逻辑结构 数据结构的物理结构 算法的概念和算法的性能评价(时间复杂度) （二）线性表（大题考点） 1.复习内容 线性表的概念和基本运算，线性表的顺序存储和链式存储，线性表的基本运算在顺序存储和链式存储结构上的实现。 2.具体要求 线性表的概念和基本运算 线性表的顺序存储 线性表的链式存储 线性表的应用 （三）栈和队列（选择题考点） 1.复习内容 栈和队列的基本概念、基本操作和存储结构。 2.具体要求 栈和队列的基本概念和基本操作 栈和队列的顺序存储结构 栈和队列的链式存储结构 栈和队列的应用 （四）串 1.复习内容 串的基本概念、存储结构和模式匹配算法 2.具体要求 串的基本概念和基本操作 串的顺序存储结构 串的链式存储结构 模式匹配算法 （五）数组和广义表
1．计算机的应用领域可大致分为三个方面，下列答案中正确的是（）。C （A）计算机辅助教学、专家系统、人工智能 （B）工程计算、数据结构、文字处理 （C）实时控制、科学计算、数据处理 （D）数值计算、人工智能、操作系统 2．操作系统的主要作用不包括（）。B （A）管理系统中的各种软硬件资源 （B）播放多媒体计算机系统中各种数字音频和视频文件 （C）为用户提供友善的人机界面 （D）为应用程序的开发和运行提供一个高效率的平台 3．下列不属于（）通信三要素。D （A）信源（B）信宿（C）信道（D）电信 4．操作系统是现代计算机必不可少的系统软件之一，在下列有关操作系统的叙述中，错误的是（）。A （A）计算机只有安装了操作系统之后，CPU才能执行数据的存取和处理操作 （B）最早的计算机并无操作系统 （C）通常称已经运行了操作系统的计算机为“虚计算机” （D）操作系统可以为用户提供友善的人机界面 5．计算机中组成二进制信息的最小单位是（）。A （A）比特（B）字节（C）字（D）位组 6．能将高级语言源程序转换成目标程序的是（）。A （A）编译程序 （B）解释程序 （C）调试程序 （D）编辑程序 7．设一个数值311，与十六进制C9相等，则该数值是（）数。B （A）二进制（B）八进制（C）五进制（D）十六进制 8．高级程序设计语言的基本组成成分有（）。A （A）数据、运算、控制、传输 （B）外部、内部、转移、返回 （C）子程序、函数、执行、注解 （D）基本、派生、定义、执行 9．计算机的存储单元中存储的内容（）。A （A）只能是数据 （B）只能是程序 （C）可以是数据和指令 （D）只能是指令 10．下列几种高级语言中，被称为第一个结构化程序设计语言的是（）。B （A）C语言（B）PASCAL （C）LISP （D）Fortran 11．RAM具有的特点是（）。C （A）海量存储 （B）存储在其中的信息可以永久保存 （C）一旦断电，存储在其上的信息全部消失且无法恢复 （D）存储在其中的数据不能改写
第1章计算机基础知识 1.1 计算机与信息社会 电子计算机是20 世纪人类最伟大的发明之一，随着计算机科学的发展与应用的普及， 计算机已经融入人们的生活，成为人们日常生活、工作、学习中不可缺少的一个基本工具。“21 世纪是以计算机为基础的信息时代”，掌握以计算机为核心的信息技术基础知识和 应用能力是现代大学生必备的基本素质。 1.1.1 计算机的发展 一般认为，世界上第一台数字式电子计算机诞生于1946 年2 月，它是由美国宾夕法尼 亚大学物理学家莫克利(J.Mauchly)和工程师埃克特(J.P.Eckert)等人共同开发的电子数值积 分 计算机(Electronic Numerical Integrator And Calculator，简称ENIAC)。 ENIAC 体积非常庞大，其占地面积为170 平方米，总重量达30 吨，如图1-1 所示。机 器中约有18 800 只电子管、1 500 个继电器、70 000 只电阻以及其他各种电气元件，每小时耗电量约为140 千瓦。这样一台“巨大”的计算机每秒钟可以进行5 000 次加减运算，相当于手工计算的20 万倍、机电式计算机的1000 倍。这台计算机的功能虽然无法与今天的计算机相比，但它的诞生却是科学技术发展史上一次意义重大的事件，展现出新技术革命的曙光。图1-1 ENIAC(电子数值积分计算机) ENIAC 虽是第一台正式投入运行的电子计算机，但它却并不具备现代计算机“存储程序”?2 ?大学计算机基础 的思想。由于其结构设计不够弹性化，导致对它的每一次再编程都意味着电气物理线路的再连接。ENIAC 的开发小组针对其缺陷又进一步完善了设计。1946 年6 月，冯·诺依曼博士发表了“电子计算机装置逻辑结构初探”论文，并设计出第一台“存储程序”的离散变量自动电子计算机(The Electronic Discrete Variable Automatic Computer，简称EDVAC)，于1952 年正式投入运行，其运算速度是ENIAC 的240 倍。冯·诺依曼提出的EDVAC 计算机结构为人们普遍接受，并成为当今所有计算机的基础结构。 1. 计算机的发展历程 ENIAC 诞生至今半个多世纪以来，计算机获得了突飞猛进的发展。人们依据计算机性能 和当时的软硬件技术，将计算机的发展划分成以下四个阶段，如表1-1 所示。 表1-1 计算机发展的四个阶段 年代 第一代 1946~1957 第二代 1958~1964 第三代 1965~1970 第四代 1971~现在 电子器件电子管晶体管集成电路大规模集成电路 存储器 延迟线、磁芯、
大学计算机基础试题及答案（完整版） 一、单选题 1、完整的计算机系统由（C）组成。 A、运算器、控制器、存储器、输入设备和输出设备 B、主机和外部设备 C、硬件系统和软件系统 D、主机箱、显示器、键盘、鼠标、打印机 2、以下软件中，（D）不是操作系统软件。 A、Windowsxp B、unix C、linux D、microsoft office 3、用一个字节最多能编出（D）不同的码。 A. 8个 B. 16个 C. 128个 D. 256个 4、任何程序都必须加载到（C）中才能被CPU执行。 A. 磁盘 B. 硬盘 C. 内存 D. 外存 5、下列设备中，属于输出设备的是（A）。 A、显示器 B、键盘 C、鼠标 D、手字板 6、计算机信息计量单位中的K代表（B）。 A. 102 B. 210
C. 103 D. 28 7、RAM代表的是（C）。 A. 只读存储器 B. 高速缓存器 C. 随机存储器 D. 软盘存储器 8、组成计算机的CPU的两大部件是（A）。 A、运算器和控制器 B. 控制器和寄存器 C、运算器和内存 D. 控制器和内存 9、在描述信息传输中bps表示的是（D）。 A、每秒传输的字节数 B、每秒传输的指令数 C、每秒传输的字数 D、每秒传输的位数 10、微型计算机的内存容量主要指（A）的容量。 A.RAM B.ROM C.CMOS D.Cache 11、十进制数27对应的二进制数为( D)。 A.1011 B. 1100 C. 10111 D. 11011 12、Windows的目录结构采用的是（A）。 A、树形结构 B、线形结构 C、层次结构 D、网状结构 13、将回收站中的文件还原时，被还原的文件将回到（D）。 A、桌面上 B、“我的文档”中 C、内存中 D、被删除的位置
计算机应用基础 计算机基础 第一章计算机概述第二章 WINDOWS操作系统 第三章 WORD20 第四章 EXCLE2000 第五章 PowerPoint2000 第六章计算机网络基础 第七章网页第八章信息安全 第一章计算机概述 §1.1 计算机的诞生和发展§1.2 计算机的组成 - 硬件 §1.3计算机的数据处理方式§1.4 计算机软件§1.5 计算机安装与维护 1.1 计算机的诞生和发展 一、ABOUT COMPUTER … 二、计算机的发展 三、多媒体计算机 1.1 计算机的诞生和发展 ABOUT COMPUTER … ●计算机是一种按程序高速、自动处理信息的现代化电子设备 ●自1946年2月世界第一台计算机诞生至今已有50多年的历史。 ●随着计算机的诞生和发展，信息的交流和传播起了质的变化，产生了相对于人类传 统文化（哲学、自然科学、数学等）的第二文化—计算机文化。 ●计算机能干什么？ §1.1 计算机的诞生和发展 ABOUT COMPUTER … 学习、办公、娱乐、设计、排版、金融、炒股、医疗、购物、通讯…… 信息社会的主要特征 1. 信息处理能力倍增 2. 信息网络成为社会活动中心 3. 信息的速传使人类互相间时空“缩短” 4. 信息产业称为重要的支柱产业 5. 科技人员成为重要的社会阶层，而对科技的投入相对增加 第一台计算机ENIAC 1946年2月，诞生在美国宾夕法尼亚大学。 ENIAC（Electronic Numerical Integrator And Calculator 电子数字积分计算机）, 1900个电子管，重30t，占地约167m2 运算速度5000次/秒，只能存储20个字长为10位的十进制数，不能存储程序 第一台计算机不具备现代计算机的主要原理特征：存储程序和程序控制 §1.1 计算机的诞生和发展 计算机的发展 B 最早的有存储功能的计算机： 1946～1950 EDVAC 美国冯· 诺依曼 ★1947～1949 EDSAC 英国剑桥大学维尔克斯 (EDSAC是第一台存储程序式计算机） 1946年，冯·诺依曼首次提出了电子计算机中存储程序的概念（存储程序和程序控制），并提出了计算机的基本构造—存储器、计算器、控制器、输入设备和输出设备。 计算机的发展 C
2020年硕士研究生统一入学考试 《计算机专业基础》 第一部分考试说明 一、考试性质 计算机专业基础是计算机科学与技术学科（一级学科）、计算机技术工程领域硕士生入学考试的专业基础课。考试对象为参加东北大学计算机科学与工程学院2020年全国硕士研究生入学考试的准考考生。 二、考试形式与试卷结构 （一）答卷方式：闭卷，笔试 （二）答题时间：180分钟 （三）考试题型及比例 简答题20% 综合题80% （四）参考书目 《数据结构》，严蔚敏，清华大学出版社，2001年。 《C语言程序设计》（第3版），谭浩强,清华大学出版社,2010年。 第二部分考查要点 （一）数据结构考查要点 1 绪论 1.1 数据结构的基本概念和术语 1.2 抽象数据类型的表示与实现 1.3 算法和算法分析 2 线性表 2.1 线性表类型定义
2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 3 栈和队列 3.1 栈的类型定义、表示和实现 3.2 栈的应用 3.3队列的类型定义、表示和实现 3.4 队列的应用 4 串 4.1 串的类型定义、表示和实现 4.2串操作应用 5 数组和广义表 5.1数组的定义、顺序表示和实现 5.2特殊矩阵的压缩存储 5.3广义表的定义和存储结构 6 树和二叉树 6.1 树的定义和基本术语 6.2二叉树的定义、基本性质和存储结构 6.3遍历二叉树和线索二叉树
6.4树和森林 6.5哈夫曼树及哈夫曼编码 7 图 7.1 图的定义、基本术语和存储结构 7.2图的遍历 7.3图的连通性和最小生成树 7.4有向无环图、拓扑排序和关键路径。 9 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 10 排序 10.1 插入排序 10.2 快速排序 10.3 选择排序 10.4 归并排序 10.5 基数排序 10.6排序方法的比较 （二）C语言考查要点
计算机基本理论基础知识总汇 1、计算机按照数据处理规模大小可以分为（巨型计算机）（大型计算机）（小 型计算机）（微型计算机）（工作站）等 2、计算机的硬件主要由（控制器）（运算器）（存储器）（输入输出设备）以及 电源等硬件组成。 3、计算机主机是（控制器）（运算器）（存储器）的总称，主要包括(CPU）(内 存)（主板）等部件。 4、控制器和运算器集成在一起，合称为（中央处理器） 5、CPU是(Central Processing Unit)的缩写。 6、计算机硬件系统可以分为两大部分，即（主机）和（外部设备） 7、外部设备存储器包括（硬盘）（光盘）（U盘） 8、1971年，每个Intel成功的把（算术运算器）和（逻辑运算器）集成在一起， 发明了世界上第一块微处理器 9、计算机可以分为（硬件）和（软件）两大部分 10、运算器是信息的加工和处理部件，它的主要功能是完成（算术）运算和 （逻辑）运算。 11、运算器除了能进行各种加、减、乘、除运算外，还可以进行（逻辑运算） 12、运算器主要由（算术运算单元）（寄存器）（累加器）等组成 13、控制器主要由（指令译码器）（指令寄存器）（控制逻辑部件）等组成 14、（运算器）和（控制器）集成在一起就是通常所讲的CPU 15、（中央处理器）和（内存储器）一起被称为主机 16、存储器是计算机汇总记忆设备，用来存放（数据）和（程序） 17、CPU内部（缓存）的大小以及（速度）对CPU的性能影响很大。 18、存储器一般可以分为（内部存储器）和（外部存储器）两大类 19、一般把计算机的输入输出设备称为（外部设备） 20、计算机软件是指为了（运行）（管理）和（维护）计算机系统所编制的各 种程序的总和。 21、计算机软件可分为（系统软件）和一般（应用软件） 22、一般把计算机数据总线包含的二进制位数称为（字长） 23、计算机的（运算速度）是衡量计算机性能的主要指标，它主要取决于指 令的（执行时间） 24、CPU的总线包括(数据)（地址）和（控制） 25、CPU一般由（逻辑运算）单元、（控制）单元和（存储）单元组成。 26、衡量CPU性能的技术指标有（主频）（外频）（倍频系数）（Cache容量） （生产工艺技术）（封装类型）（CPU附加指令） 27、主频=（外频）*（倍数系数） 28、附加指令可以提高CPU处理（多媒体）（3D图形）等数据的能力 29、主板一般包括（CPU插槽）（控制芯片）（键盘和面板控制开关接口）（指 示灯插接件）（扩充插槽）等元件。 30、主板按照接口可分为（AT结构）和（ATX结构）的主板 31、主板可以按三种方法进行分类，即按（主板上使用的CPU）（主板结构） 或（主板采用的芯片组）来分类。
安徽工业大学2008年招收攻读硕士学位研究生专业基础课试卷（A）科目名称：计算机专业基础代码：874 考生注意：所有答题务必书写在考场提供的答题纸上，在本试题单上的答题一律无效（本题单不参与阅卷） 一、解释下列名词（共20分，每小题2分） 1、SCM 2、IT 3、BI 4、MRP 5、API 6、INTRANET 7、SQL 8、UML 9、 DSS 10、TCP/IP 二、先判断下列的说法正确与否，如错误，请修改，使之成为正确的论断（每小题2 分，共20分） 1、原型法是软件开发的一种方法，此种方法仅在需求阶段使用，设计阶段不能使用。 2、ERP系统开发过程中，做好代码设计工作，有利于系统的实施，代码设计通常在系 统总体设计阶段完成。 3、软件需求规格说明书在软件开发中具有重要的作用，它是软件验收的重要依据之一。 4、模型是对现实的简化，建模是为了更好地理解所开发的系统。 5、UML支持面向对象的主要概念，它是一种开发方法。 6、在面向对象开发方法中，采用OMT技术仅需要建立对象模型与功能模型即可。 7、软件调试的任务就是发现软件的错误。 8、在软件模块设计中，强调高耦合，低内聚。 9、当软件开发项目的进度有可能拖延时，增加开发人员可能延缓进度。 10、从应用软件系统开发来说，面向对象开发方法适合需求比较稳定的系统。 三、选择题。从A、B、C、D中选择一个正确的答案（本题共20分，其中第3小题4分，第4小题6分，其它每小题各2分） 1、IT规划是企业战略规划的一部分，在规划过程中常采用三种方法进行，这三种方法为： A．CSF方法、SST方法、CASE方法 B．OOD方法、OMT方法、SSA方法 C．BPR方法、OOA方法、SST方法 D．CSF方法、SST方法、BSP方法 2、在软件设计过程，模块间的联系，通常要考虑各自独立性，块间保持 A．高内聚、低耦合 B．高耦合、低内聚 C．控制域依从作用域 D．作用域依从控制域 3、关系模式SC(Sno，Cno，Score)，S（SNO，SNAME，SSEX）中，Sno是学生的学号，Cno是课程号，Score为成绩。SNAME为学生姓名，SSEX为性别。若要查询每个女同学的所学课程的平均成绩和最高成绩，且要求查询结果按平均成绩升序排列。可用SQL 语言写为＿(1)＿。若要求查询结果仅显示平均分数超过60分，则应＿(2)＿。 (1) A．SELECT S.SNO，Cno，AVG(SCORE) ，MAX（SCORE）M FROM SC，S WHERE S.SNO=SC.SNO AND SSEX=’女’GROUP BY S.SNO ORDER BY AVG(SCORE)，ASC ;
06 /07 学年第一学期《大学计算机基础》试卷卷一 课程编号：1401011110 使用班级：06级本科上机试卷 答题时间：100 分钟 一.单选(每题2分，共54分) 1：（2分） 将十进制数0．40625转化为二进制数应是B 。 A) 0．001101 B) 0．01101 C) 0．0011011 D) 0．00111 【所在章节】第一部分：计算机概述； 【知识点】数制和编码系统。 2：（2分） 常采用T来表示 B 。 A) 1024M B) 1024G C) 1024K D) 1024 2 【所在章节】第一部分：计算机概述； 【知识点】各类二进制信息（数据、控制、地址）在计算机内部的处理过程。 3：（2分） 未来计算机的发展方向是 D 。 A) 数字化、网络化、巨型化、智能化 B) 网络化、智能化、微型化、通用化 C) 集成化、网络化、数字化、智能化 D) 网络化、智能化、微型化、巨型化 【所在章节】第一部分：计算机概述； 【知识点】计算机未来 4：（2分） 如果按字长来划分，微型机可分为8位机、16位机、32位机、64位机和128位机等。所谓32位机
是指该计算机所用的CPU( A ) 。 A、一次能处理32位二进制数 B、具有32位的寄存器 C、只能处理32位浮点数 D、有32个寄存器 【所在章节】第二部分：微型计算机系统 【知识点】了解计算机的基本原理 5：（2分） 微型计算机的性能主要取决于( B )的性能。 A、RAM B、CPU C、显示器 D、硬盘 【所在章节】第二部分：微型计算机系统 【知识点】计算机系统的组成 6：（2分） 个人计算机(PC)是除了主机外,还包括外部设备的微型计算机、而其必备的外部设备是( B ) 。 A、键盘和软驱 B、显示器和键盘 C、键盘和打印机 D、显示器和扫描仪 【所在章节】第二部分：微型计算机系统 【知识点】了解常用外设的功能和基本工作原理。 7：（2分） 冯·诺依曼计算机的主要特点是（ A ）。 A.以运算器为核心，存储程序原理为基础 B.以存储器为核心，存储程序原理为基础 C.以运算器为核心，指令的逻辑顺序和在存储器中存放的物理顺序是一致的。 D.以存储器为核心，指令的逻辑顺序和在存储器中存放的物理顺序是一致的。 【所在章节】第二部分：微型计算机系统 【知识点】知识点：了解微机的组成及发展过程；理解微机各基本部件的功能与主要技术指标；了解计算机基本指令系统的概念；深入掌握微机的各级存储系统；了解常用外设的功能和基本工作原理。 8：（2分） 文件系统的目录结构采用（ A ）。 A．树形结构 B. 层次结构 C. 链表结构 D. 图表结构 【所在章节】第三部分：操作系统 【知识点】文件系统功能 9：（2分） 以下各个操作中，不属于系统优化的是（C ）。 A)磁盘清理B) 碎片整理C) 禁用注册表D) 调整虚拟内存
一、数据结构 【考查目标】 1.掌握数据结构的基本概念、基本原理和基本方法。 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、栈、队列和数组 (一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 三、树与二叉树 (一)树的基本概念 (二)二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 (三)树、森林 1.树的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树与二叉树的应用 1.二叉排序树 2.平衡二叉树 3.哈夫曼(Huffman)树和哈夫曼编码 四、图 (一)图的基本概念 (二)图的存储及基本操作
1.邻接矩阵法 2.邻接表法 3.邻接多重表、十字链表 (三)图的遍历 1.深度优先搜索 2.广度优先搜索 (四)图的基本应用 1.最小(代价)生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 (一)查找的基本概念 (二)顺序查找法 (三)分块查找法 (四)折半查找法 (五)B树及其基本操作、B+树的基本概念 (六)散列(Hash)表 (七)字符串模式匹配 (八)查找算法的分析及应用 六、排序 (一)排序的基本概念 (二)插入排序 1.直接插入排序 2.折半插入排序 (三)气泡排序(bubble sort) (四)简单选择排序 (五)希尔排序(shell sort) (六)快速排序 (七)堆排序 (八)二路归并排序(merge sort) (九)基数排序 (十)外部排序 (十一)各种内部排序算法的比较 (十二)排序算法的应用 二、计算机组成原理 【考查目标】 1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具
[模拟] 计算机学科专业基础综合模拟30 单项选择题 第1题： 存储管理中地址重定位必须在CPU中设置专门寄存器，而______不是此类寄存器。 A.基址寄存器 B.界限寄存器 C.页表控制寄存器 D.程序计数器 参考答案：D 在单一分区中，操作系统存放在低址部分，为了防止用户破坏，都设置了界限寄存器，其包括两部分：基址寄存器的内容是操作系统常驻内存部分以后的首地址，长度寄存器的内容便是用户可用区域的长度。其地址变换也是：绝对地址=基址寄存器+逻辑地址。但现在大部分单用户操作系统都不再使用界限寄存器，由于操作系统不会发生变化将基址和长度用两个常量来代替。不再使用硬件寄存器。在动态分区中，进行动态重定位需要基址寄存器：绝对地址=基址寄存器+逻辑地址。在分页系统中，页表控制寄存器中存放页表起始位置和页表长度，在地址变换时先用页号与页表控制寄存器中的页表长度比较，判断是否越界，如没有则根据页表控制寄存器中页表起始位置找到页表查找到相应的块号进行地址转换：绝对地址=块号*块长+页内地址。 第2题： 一个完整的计算机系统包括______。 A.主机、键盘、显示器 B.主机及其外部设备 C.主机与实用程序 D.硬件系统与软件系统 参考答案：D 计算机硬件是由主机和外围设备组成，主机是指CPU和内存储器。通常，把不装备任何软件的计算机称为硬件计算机或裸机，裸机是不能使用的，必须配备一定的软件，构成计算机系统才能使用。 第3题： 随着计算机技术的不断发展和对指令系统的合理性研究，精简指令系统RISC逐步取代CISC的重要位置。下面所述不是CISC主要缺点的是______。 A.软硬件功能分配的问题 B.VLSI技术的不断发展引起的一系列问题
第一章计算机基础 1.计算机中一条指令的组成是什么？ 操作数和操作码 2.简述计算机的工作过程 ●输入原始数据，程序等并进行存储于内存 ●控制器从内存取出指令经译码器译码分析处理 ●将运算的结果输出，程序和数据存入外存 3.简述计算机在信息社会的主要作用 科学计算，信息处理，过程控制，计算机辅助功能，办公自动化，人工智能，电子商务，娱乐休闲 4.计算机为什么采用二进制数而不用十进制数 ●电路简单 ●工作可靠 ●简化运算 ●逻辑性强 ●编码简单 5.简述计算机的特点 运算速度快，精度高，记忆功能，具有逻辑判断能力，具有自动执行程序的功能6.国际上按什么原则将计算机分成六大类，哪六大类？ 按工作性能分：巨型机，大型机，小型机，微型机，服务器，工作站 7.操作系统的五大基本功能 作业管理，文件管理，微处理器管理，存储管理，设备管理 8.外存和内存的区别是什么 ●内存又称主存，暂时存放操作系统，正在使用的其他软件和数据 外存又称辅存，一般存放长时间需要保存的软件和数据 ●内存容量小，存取周期短 外存容量大，存取速度慢 ●断电后，内存中的RAM和cache中的信息全部丢失 断电后，外存中信息不丢失 ●内存可以之间和CPU交换数据 外存只能通过接口电路与内存打交道，不能与CPU之间进行交换数据 9.内存中，RAM ,ROM各有什么特点 ●ROM，只读存储器，只能读不能写，掉电后，信息不丢失 ●RAM ,随机存取存储器，既能读也能写，掉电后信息全部丢失 10.执行一条指令的分成哪几步骤 ●取指令，CPU从内存取出指令，存放在控制器的指令寄存器中 ●分析指令，通过控制器的指令译码器，对指令进行译码分析 ●执行指令，按时序向某部件发出指令要求的控制信号 11.一块显卡的质量取决于哪些方面 显示分辨率显存容量显存位宽刷新频率色彩位数 12.PC机硬件的主要性能指标有哪些 字长主频运算速度内存容量系统总线的传输速率 13.微机中衡量微处理器的性能指标有哪些