第一篇：软考教材分享：程序员考试考点分析与真题详解(第4版 )
程序员
http://
程序员考试考点分析与真题详解（第4版）
第 1 章 数据结构与算法
数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点与结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。
数据结构按逻辑结构不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。
按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。
1.常用数据结构
数组（一维数组、二维数组、静态数组、动态数组）、线性表、链表（单向链表、双向链表、环形链表）、队列、栈、树（二叉树、查找树）和图（邻接矩阵、邻接表）等的定义、存储和操作。
2.常用算法
（1）排序算法、查找算法、数值计算算法、字符串处理算法、递归算法、最小生成树、拓扑排序和单源点最短路径求解算法、图的相关算法。
（2）算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性。
1.1 算法设计概述
程序员
http://
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。
（1）有穷性：一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
（3）输入：一个算法有零个或多个输入，以确定运算对象的初始情况。所谓零个输入是指算法本身定出了初始条件。这些输入取自于某个特定对象的集合。
（4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
（5）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
算法设计要求正确性、可读性、健壮性、高效率与低存储量需求。
效率指的是算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。
算法的复杂性是算法效率的度量，是算法运行所需要的计算机资源的量，是评价算法优劣的重要依据。可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素。
（1）硬件的速度。例如，使用486还是使用586.（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。
程序员
http://
（3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。
（4）问题的规模。例如，求100以内的素数与求1 000以内的素数其执行时间必然是不同的。
显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述的各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。
1.时间复杂度
一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。
一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该操作重复执行的次数作为算法的时间度量。在一般情况下，算法中原操作重复执行的次数是规模n的某个函数T（n）。
许多时候要精确地计算T（n）是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。
定义（大Ο记号）：如果存在两个正常数c和n0,对于所有的n,当n≥n0时有：
f（n）≤ cg（n）
则有：
f（n）= Ο（g（n））
也就是说，随着n的增大，f（n）渐近的不大于g（n）。例如，一个程序的实际执行
程序员
http://
时间为T（n）=2n3+n2+5,则T（n）=Ο（n3）。T（n）和n3的值随n的增大渐近地靠拢。
使用大Ο记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。
通常用Ο（1）表示常数计算时间。常见的渐近时间复杂度有：
Ο（1）<Ο（log2n）<Ο（n）<Ο（nlog2n）<Ο（n2）<Ο（n3）<Ο（2n）
2.空间复杂度
一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。
程序运行所需的存储空间包括以下两部分。
（1）固定部分：这部分空间与所处理数据的大小和个数无关。主要包括程序代码、常量、简单变量和定长成分的结构变量所占的空间。
（2）可变部分：这部分空间大小与算法在某次执行中处理特定数据的大小和规模有关。例如，100个数据元素的排序算法与1 000个数据元素的排序算法所需的存储空间显然是不同的。
算法由数据结构来体现，所以看一个程序首先要搞懂程序实现中所使用的数据结构，如解决装箱问题就使用链表这种数据结构。数据结构是算法的基础，数据结构支持算法，如果数据结构是递归的，算法也可以用递归来实现，如二叉树的遍历。经常采用的算法有迭代法、递推法、递归法、穷举法、贪婪法、分治法和回溯法等，根据考试大纲的要求，对程序员级别的考试，需要考生掌握递归法。
1.2 线性表
线性表是最简单和最常用的一种数据结构，线性表是由相同类型的结点组成的有限序
程序员
http://
列。一个由n个结点a0,a1,…，an-1组成的线性表可记为（a0,a1,…，an-1）。线性表的结点个数为线性表的长度，长度为0的线性表称为空表。对于非空线性表，a0是线性表的第一个结点，an-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两相邻结点ai和ai+1,称ai是ai+1的前驱结点，ai+1是ai的后继结点。其中a0没有前驱结点，an-1没有后继结点。
线性表中结点之间的关系可由结点在线性表中的位置所确定，通常用（ai,ai+1）（0≤i≤n–2）表示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。
线性表的结点可由若干个成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了讨论方便，往往只考虑结点的关键字，而忽略其他成分。
1.线性表的基本运算
线性表包含的结点个数可以动态地增加或减少，可以在任何位置上插入或删除结点。线性表常用的运算可分成几类，每类有若干种运算，如下所示。
1）查找运算
在线性表中查找具有给定键值的结点。
2）插入运算
在线性表的第i（0≤i≤n–1）个结点的前面或后面插入一个新结点。
3）删除运算
删除线性表的第i（0≤i≤n–1）个结点。
4）其他运算
统计线性表中结点的个数；
程序员
http://
输出线性表各结点的值；
复制线性表；
线性表分拆；
线性表合并；
线性表排序；
按某种规则整理线性表。
2.线性表的存储
线性表常用的存储方式有顺序存储和链接存储。
1）顺序存储
顺序存储是最简单的存储方式，通常用一个数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中，即线性表的第i个结点存储在数组的第i（0≤i≤n–1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。
顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点。缺点主要有两个：一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。
2）链接存储
链接存储是用链表存储线性表（链表），最简单的是用单向链表，即从链表的第一个结点开始，将线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息，还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结点的先后次序关系。
链表存储线性表的优点是线性表的每个结点的实际存储位置是任意的，这给线性表的插
程序员
http://
入和删除操作带来方便，只要改变链表有关结点的后继指针就能完成插入或删除的操作，不需移动任何表元。链表存储方式的缺点主要有两个：一是每个结点增加了一个后继指针成分，要花费更多的存储空间；二是不方便随机访问线性表的任一结点。
3.线性表上的查找
线性表上的查找运算是指在线性表中找某个键值的结点。根据线性表中的存储形式和线性表本身的性质差异，有多种查找算法，例如顺序查找、二分法查找、分块查找、散列查找等。其中二分法查找需要线性表是一个有序序列。
4.在线性表中插入新结点
1）顺序存储
设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。完成插入主要有以下步骤。
检查插入要求的有关参数的合理性；
把原来的第n–1个结点至第i个结点依次往后移一个数组元素的位置；
把新结点放在第i个位置上；
修改线性表的结点个数。
在具有n个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，则在顺序存储线性表中插入一个新结点，平均移动次数为n/2.2）链接存储
在链接存储线性表中插入一个键值为x的新结点，分以下4种情况。
在某指针p所指结点之后插入；
插在首结点之前，使待插入结点成为新的首结点；
程序员
http://
接在线性表的末尾；
在有序链表中插入，使新的线性表仍然有序。
5.删除线性表的结点
1）顺序存储
在有n个结点的线性表中，删除第i（0≤i≤n–1）个结点。删除时应将第i+1个表元至第n–1个结点依次向前移一个数组元素的位置，共移动n–i–1 个结点。完成删除主要有以下几个步骤。
检查删除要求的有关参数的合理性；
把原来第i+1个表元至第n–1个结点依次向前移一个数组元素的位置；
修改线性表表元个数。
在具有n个结点的线性表上删除结点，其时间主要花费在移动表元的循环上。若删除任一表元的概率相等，则在顺序存储线性表中删除一个结点，平均移动次数为n/2.2）链接存储
对于链表上删除指定值结点的删除运算，需考虑几种情况：一是链表为空链表，不执行删除操作；二是要删除的结点恰为链表的首结点，应将链表头指针改为指向原首结点的后继结点；其他情况，先要在链表中寻找要删除的结点，从链表首结点开始顺序寻找。若找到，执行删除操作，若直至链表末尾没有指定值的结点，则不执行删除操作。完成删除由以下几个步骤组成。
如链表为空链表，则不执行删除操作；
若链表的首结点的值为指定值，更改链表的头指针为原首结点的后继结点；
在链表中找指定值的结点；
程序员
http://
将找到的结点删除。
1.2.1 栈
栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。
1.顺序存储
可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。
2.链接存储
栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为NULL的链表是空栈。
1.2.2 队列
队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。
1.顺序存储
可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量head（称为头指针），为了指明当前执行进队运算的队尾位置，也需要一个指针变量tail（称为尾指针）。
若用有N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法
程序员
http://
是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。
循环队列就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N–1]连接起来。一般地，用tail指向队尾元素的下一个位置（注意，并不是指向最后一个元素本身），用head指向队头元素。队空的初态为 head=tail=0.在循环队列中，当tail 赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail,这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满，用这种简单办法来区别队空和队满。即对空的判别条件是head=tail,队满的判别条件是head=（tail+1）%N.2.链接存储
队列也可以用链接存储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为NULL.队列的头指针head 指向链表的首结点，队列的尾指针tail指向链表的尾结点。当队列的头指针head值为NULL时，队列为空。
1.2.3 数组
在计算机中存储一个矩阵时，可使用二维数组。例如，M×N阶矩阵可用一个数组a[M][N]来存储（可按照行优先或列优先的顺序）。如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵。若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。因此，通常采用三元组数组或十字链表两种方法来存储稀疏矩阵。
1.三元组数组
稀疏矩阵的每个非零元素用一个三元组来表示，即非零元素的行号、列号和它的值。然
程序员
http://
后按某种顺序将全部非零元素的三元组存于一个数组中。
如果只对稀疏矩阵的某些单个元素进行处理，则宜用三元组表示。
2.十字链表
在十字链表中，矩阵的非零元素是一个结点，同一行的结点和同一列的结点分别顺序循环链接，每个结点既在它所在行的循环链表中，又在它所在列的循环链表中。每个结点含5个域，分别为结点对应的矩阵元素的行号、列号、值，以及该结点所在行链表后继结点指针、所在列链表后继结点指针。
为了处理方便，通常对每个行链表和列链表分别设置一个表头结点，并使它们构成带表头结点的循环链表。为了方便引用某行某列，全部行链表的表头结点和全部列链表的表头结点分别组成数组，这两个数组的首结点指针存于一个十字链表的头结点中，最后由一个指针指向该头结点，如图1-1所示。
图1-1 十字链表
如果对稀疏矩阵某行或某列整体进行某种处理，可能会使原来为零的元素变为非零，而原来为非零的元素可能变成零。对于这种场合，稀疏矩阵宜用十字链表来表示。
1.2.4 字符串
程序员
http://
字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含有效字符的个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。
字符串通常存于足够大的字符数组中，每个字符串的最后一个有效字符之后有一个字符串结束标志，记为' '.通常，由系统提供的库函数形成的字符串末尾会自动添加' ',但当由用户的应用程序来形成字符串时，必须由程序自行负责在最后一个有效字符之后添加' ',以形成字符串。
对字符串的操作通常有：
统计字符串中有效字符的个数；
把一个字符串的内容复制到另一个字符串中；
把一个字符串的内容连接到另一个足够大的字符串的末尾；
在一个字符串中查找另一个字符串或字符；
按字典顺序比较两个字符串的大小。
1.3 树
1.3.1 二叉树
1.二叉树的基本概念
二叉树是一个有限的结点集合，该集合或者为空，或者是由一个根结点及其两棵互不相交的左、右叉子树所组成的。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（或右子结点），也可能同时有左右两个子结点。如图1-3所示的是二叉树的4种可能形态（如
程序员
http://
果把空树计算在内，则共有5种形态）。
图1-3 二叉树的4种不同形态
与树相比，二叉树可以为空，空的二叉树没有结点（树至少有一个结点）；在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树常采用类似树的标准存储结构来存储，其结点类型可以用C语言定义如下：
typedef struct Btnode{
char data;/*数据*/
strucrt Btnode *lchild;/*左孩子*/
struct Btnode *rchild;/*右孩子*/
}BTNODE;
2.二叉树的性质
二叉树具有下列重要性质（此处省略了推导过程，有兴趣的读者可自行推导）。
性质1:在二叉树的第i层上最多有2i–1个结点（i≥1）。
性质2:深度为k的二叉树最多有2k–1个结点（k≥1）。
性质3:对任何一棵二叉树，如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1.一棵深度为k且有2k–1个结点的二叉树称为满二叉树。如图1-4就是一棵满二叉树，对结点进行了顺序编号。
如果深度为k，有n个结点的二叉树中的结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。例如图1-5（a）是一棵完全二叉树，而（b）、（c）是两棵非完全二叉树。显然，满二叉树是完全二叉树的特例。
程序员
http://
图1-4 满二叉树的例子
图1-5 完全二叉树、非完全二叉树的例子
根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第k层或k-1层（最后两层）。
性质4:具有n个结点的完全二叉树的深度为[log2n]+1（注：[m]表示不大于m的最大整数，如[4]=
4、[4.1]=
4、[4.9]=4,下同）。
性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点i（1≤i≤n），有：
（1）如果i=1，则结点i无双亲，是二叉树的根；如果i>1,则其双亲是结点[i/2]。
（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
（3）如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1。
3.二叉树的遍历
树的所有遍历方法也同样适用于二叉树，此外，由于二叉树自身的特点，还有中序遍历方法。
（1）前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。
（2）中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。
程序员
http://
（3）后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。
例如，图1-6所示的二叉树，其前序遍历、中序遍历和后序遍历结果分别如下。
（1）前序遍历：1,2,4,5,7,8,3,6。
（2）中序遍历：4,2,7,8,5,1,3,6。
（3）后序遍历：4,8,7,5,2,6,3,1。
以上3种遍历方法都是递归定义的，可通过递归函数分别给以实现。
性质6：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树。
根据性质6，给定一棵二叉树的前序遍历序列和中序遍历序列，我们可以写出该二叉树的后序遍历序列。例如，某二叉树的前序遍历序列为ABHFDECKG、中序遍历序列为HBDFAEKCG，则构造二叉树的过程如图1-7所示。
程序员
http://
图1-7 已知前序遍历序列和中序序列，求二叉树的过程
1.3.2 二叉排序树
二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质（BST性质）的二叉树。
（1）若它的左子树非空，则左子树上所有结点的值均小于根结点；
（2）若它的右子树非空，则右子树上所有结点的值均大于根结点；
（3）左、右子树本身又各是一棵二叉排序树。
例如，图1-8就是一棵二叉排序树。
根据二叉排序树的定义可知，如果中序遍历二叉排序树，就能得到一个排好序的结点序列。二叉排序树上有查找、插入和删除3种操作。下面，我们假设二叉排序树的结点只存储结点的键值，其类型与前面的二叉树的结点类型相同。
1.静态查找
程序员
http://
静态查找是在二叉排序树上查找键值为key的结点是否存在，可按以下步骤在二叉排序树ST上找值为key的结点：
（1）如果二叉排序树ST为空二叉树，则查找失败，结束查找；
（2）如果二叉排序树根结点的键值等于key,则查找成功，结束查找；
（3）如果key小于根结点的键值，则沿着根结点的左子树查找，即根结点的左子树作为新的二叉排序树ST继续查找；
（4）如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的二叉排序树ST继续查找。
2.动态查找
在二叉排序树上，为插入和删除操作而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为此，查找函数可设4个参数：查找树的根结点指针root、待查找值key、存储键值为key结点的父结点的指针pre,存储键值为key以及结点的指针p.但函数要考虑以下几种不同的情况：
（1）二叉排序树为空，查找失败，函数使*p=NULL,*pre=NULL;
（2）二叉排序树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点，*pre指向该结点，*p=NULL,如果插入键值为key的结点，就插在该结点下；
（3）查找成功，*p指向键值为key的结点，*per指向它的父结点。
3.插入结点
首先利用动态查找函数确定新结点的插入位置，然后分以下几种情况作为相应的处理：
（1）如果相同键值的结点已在二叉排序中，则不再插入；
（2）如果二叉排序为空树，则以新结点为二叉排序树；
程序员
http://
（3）根据要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并进行相应的插入。
4.删除结点
删除二叉排序树上键值为key的结点的操作可按以下步骤进行。
（1）调用查找函数确定被删结点的位置；
（2）如果被删除结点不在二叉排序树上，则函数返回。否则，按以下情况分别处理。
①如果被删除的结点是根结点，又可分以下两种情况。
l被删除结点无左子树，则以被删除结点的右子树作为删除后的二叉排序树；
l被删除结点有左子树，则用被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树。
②如果被删除结点不是根结点，且被删除结点无左子结点，则，l被删除结点是它父结点的左子结点，则把被删除结点的右子树作为被删除结点父结点的左子树；
l被删除结点是它父结点的右子结点，则把被删除结点的右子树作为被删除结点父结点的右子树；
③如果被删除结点不是根结点，且被删除结点无左子结点，则被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树，同时进行以下操作：
l被删除结点是它父结点的左子结点，则把被删除结点的左子树作为被删除结点父结点的左子树；
被删除结点是它父结点的右子结点，则把被删除结点的左子树作为被删除结点父结点的右子树。
程序员
http://
1.3.3 最优二叉树
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。在一些应用中，赋予树中结点的一个有某种意义的实数，这些数字称为结点的权。结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和，称为树的带权路径长度（树的代价），通常记为：
其中n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和根到结点ki之间的路径长度。
在权为wl,w2,…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为 w1,w2,…，wn,则哈夫曼树的构造规则如下：
（1）将w1,w2,…，wn看成是有n 棵树的森林（每棵树仅有一个结点）；
（2）在森林中选出两个根结点权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
（3）从森林中删除选取的两棵树，并将新树加入森林。
重复第（2）步和第（3）步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。
例如，如果叶子结点的权值分别为1、2、3、4、5、6,则构造哈夫曼树的过程如图1-9所示。
程序员
http://
图1-9 哈夫曼树的构造过程
在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。
给定结点序列
（1）用字符ci作为叶子，pi作为ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1;
（2）将从根到叶子路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码。
给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子结点c[i]（0≤i≤n–1）为出发点，向上回溯至根为止。向上时走左分支则生成代码0,走右分支则生成代码1.需要注意以下几个问题：
（1）由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时串中，并设一个指针start指示编码在该串中的起始位置（start初始时指示串的结束位置）；
程序员
http://
（2）当某字符编码完成时，从临时串的start处将编码复制到该字符相应的位串bits中即可；
（3）因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符“ ”,bits的大小应为n+1.给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
平均码长 =
式中pi为第i个字符的概率，li为码长。
利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%~90%,其压缩效率取决于被压缩文件的特征。
1.4 图
在线性结构（例如队列和栈）中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的一个前驱和后继。在树形结构（如树和二叉树）中，除根结点没有前驱外，一个结点只有一个前驱，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数都是任意的。
1.4.1 图的基础知识
程序员
http://
1.图的基本概念
图G由两个集合V和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集。若E（G）为空，则图G只有顶点而没有边。
图分为有向图和无向图两种。如图1-10（a）所示是一个有向图，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。
如图1-10（b）所示是一个无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图G中，如果i≠j,i、j∈V,（i,j）∈E,即i和j是G的两个不同的顶点，（i,j）是G中一条边，顶点i和顶点j是相邻的顶点，边（i,j）是与顶点i和j相关联的边。
如果限定任何一条边或弧的两个顶点都不相同，则有n个顶点的无向图最多有n（n–1）/2条边，这样的无向图称为无向完全图。一个有向图最多有n（n–1）条弧，这样的有向图称为有向完全图。
如果同为无向图或同为有向图的两个图G1=（V1,E1）和G2=（V2,E2），满足V2V1且 E2E1,则称图G2是图G1的子图。
在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度
程序员
http://
等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。
在图G=（V,E）中，如果存在顶点序列（V0,V1,…，Vk），其中V0=P,Vk=Q,且（V0,V1），（V1,V2），…，（Vk-1,Vk）都在E中，则称顶点P到顶点Q有一条路径，并用（V0,V1,…，Vk）表示这条路径，路径的长度是路径的边数，这条路径的长度为k.若G是有向图，则路径也是有向的。
在有向图G中，若对于V（G）中任意两个不同的顶点Vi和Vj,都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。
有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即其自身。非强连通的有向图有多个强连通分量。
2.图的存储结构
最常用的图的存储结构有邻接矩阵和邻接表。
1）邻接矩阵
邻接矩阵反映顶点间的邻接关系，设G=（V,E）是具有n（n≥1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i,j）或
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第i行元素的和即为顶点i的度。对于有向图，其邻接矩阵第i行元素之和为顶点i的出度，而邻接矩阵第j列元素之和为顶点j的入度。
程序员
http://
若将图的每条边都赋上一个权，则称这种带权图为网（络）。如果图G=（V,E）是一个网，若（i,j）或
2）邻接表
在图的邻接表表示中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。例如，图1-10（a）和图1-10（b）的邻接表分别如图1-11（a）和图1-11（b）所示。
图1-11 图的邻接表表示
在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。
3.图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
1）深度优先遍历
在G中任选择一顶点V为初始出发点（源点），则深度优先遍历可以定义如下：首先，访问出发点V,并将其标记为已访问过；然后，依次从V出发搜索V的每个邻接点W.若W
程序员
http://
未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。
2）广度优先遍历
广度优先遍历的过程是：首先访问出发顶点V;然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,…，Wk-1;接着再依次访问与顶点W0,W1,…，Wk-1邻接的全部未被访问过的顶点。依此类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。
从广度优先搜索遍历过程知，若顶点V在顶点W之前被访问，则对V相邻顶点的访问就先于只与W相邻的那些顶点的访问。因此，需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问这些顶点相邻接的其他还未被访问过的顶点。
1.4.2 最小生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。
含有n个顶点的连通图的生成树有n个顶点和n–1条边。对一个带权的图（网），在一棵生成树中，各条边的权植之和称为这棵生成树的代价。其中代价最小的生成树称为最小
程序员
http://
代价生成树（简称最小生成树）。
MST性质：设G=（V,E）是一个连通网络，U是顶点集V的一个真子集。若（u,v）是G中所有的一个端点在U（u∈U）里、另一个端点不在U（即v∈V–U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边（u,v）。
求连通的带权无向图的最小代价生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
1.普里姆算法
设已知G=（V,E）是一个带权连通无向图，顶点V={0,1,2,…，n–1}.设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时，U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合，初始时T为空。如果边（i,j）具有最小代价，且i∈U,j∈V–U,那么最小代价生成树应包含边（i,j）。把j加到U中，把（i,j）加到T中。重复上述过程，直到U等于V为止。这时，T即为要求的最小代价生成树的边的集合。
普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为O（n2），与图中的边数无关，所以适合于稠密图。
2.克鲁斯卡尔算法
设T的初始状态只有n个顶点，而无边的森林T=（V,φ），按边长递增的顺序选择E中的n–1安全边（u,v）并加入T,生成最小生成树。所谓安全边，是指两个端点分别是森林T里两棵树中顶点的边。加入安全边，可以将森林中的两棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。
程序员
http://
克鲁斯卡尔算法的特点，是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O（elog2e），与图中的顶点数无关，所以较适合于稀疏图。
1.4.3 最短路径
带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边权值的总和。路径长度的具体含义取决于边上权值所代表的意义。
1.单源最短路径
已知有向带权图（简称有向网）G=（V,E），找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。
目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看成是已生成的源点到其自身的长度为0的路径）。
迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集（看成红点集），V-S是最短距离尚未确定的顶点集（看成蓝点集）。
（1）初始化：初始化时，只有源点s的最短距离是已知的（SD（s）=0），故红点集S={s},蓝点集为空。
（2）重复以下工作，按路径长度递增的次序产生各顶点的最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有的蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
程序员
http://
需要注意的是：
（1）若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
（2）从源点s到终点v的最短路径简称为v的最短路径；从s到v的最短路径长度简称为v的最短距离，并记为SD（v）。
根据按长度递增的次序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1,红点2,……，红点n,蓝点k
距离为：
源点到红点n最短距离 + <红点n,蓝点k>的边长。
为求解方便，可设置一个向量D[0…n–1],对于每个蓝点v∈V–S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V–S},则D[k]=SD（k）。
初始时，每个蓝点v的D[c]值应为权w
程序员
http://
2.每一对顶点之间的最短路径
对图中每对顶点u和v,找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。
但更常用的是弗洛伊德（Folyd）提出的求每一对顶点之间的最短路径的算法。设G=（V,E）是有n个顶点的有向图，顶点集合V={0,1,…，n–1}.图用邻接矩阵M表示。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2,…，Cn,其中C0是已知的带权邻接矩阵a,Ck（i,j）（0≤i,j 设在第k次递推之前已求得Ck-1（i,j）（0≤i,j （1）如果从顶点i到顶点j的最短路径不经过顶点k,则由Ck（i,j）定义知，从i到j中间的顶点序号不大于k的最短路径长度还是Ck-1（i,j）即Ck（i,j）=Ck-1（i,j）。 （2）如果从顶点i到顶点j的最短路径要经过顶点k,则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于Ck-1（i,k）和Ck-1（k,j）分别表示i到k和从k到j的中间顶点序号不大于k-1的最短路径长度，若Ck-1（i,k）+Ck-1（k,j） 程序员 http:// 1.5 排序与查找 所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）的次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不是唯一的。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。 要注意的是，排序算法的稳定性是针对所有的输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 1.5.1 插入排序 插入排序的基本思想是，每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 1.直接插入排序 直接插入排序的过程是，在插入第i个记录时，R1,R2,…，Ri-1已经排好序，将第i个记录的排序码ki依次和R1,R2,…，Ri-1的排序码逐个进行比较，找到适当的位置。 使用直接插入排序，对于具有n个记录的文件，要进行n–1趟排序。各种状态下的时间复杂度如表1-1所示。 表1-1 直接插入排序有关数据 程序员 http:// 说明：初始文件按关键字递增排序，简称“正序”,初始文件按关键字递减排序，简称“反序”.2.希尔排序 希尔（Shell）排序的基本思想是，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 一般取d1=n/2,di+1=di/2.如果结果为偶数，则加1,保证di为奇数。 例如，要对关键码{72,28,51,17,96,62,87,33,45,24}进行排序，这里n=10,首先取d1=n/2=5.则排序过程如图1-12所示。 图1-12 希尔排序的过程 希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，有人在大量实验的基础上指出，当n在某个特定范围内时，希尔排序的平均时间复杂度为O（n1.3）。 1.5.2 选择排序 选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。 程序员 http:// 直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换……，依次类推，直到所有记录排完为止。 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需进行n–i次比较，因此，总的比较次数为n（n–1）/2=O（n2）。当初始文件为正序时，移动次数为0;文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3（n–1）。直接选择排序的平均时间复杂度为O（n2）。直接选择排序是不稳定的。 1.5.3 交换排序 交换排序的基本思想是，两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。 1.冒泡排序 冒泡排序将被排序的记录数组R[1…n]垂直排列，每个记录R[i]看成是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上“飘浮”.如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 冒泡排序的具体过程如下。 第一步，先比较k1和k2,若k1>k2,则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn.这时最大的排序码记录转到了最后位置，称第一次起泡。共执行n–1次比较。 与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n–2次比较。称第二次起泡。 依此类推，共进行n–1次起泡，完成整个排序过程。 程序员 http:// 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数为n–1次，记录移动次数为0.因此，冒泡排序最好的时间复杂度为O（n）。 若初始文件是反序的，需要进行n–1趟排序。每趟排序要进行n–i次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录3次来达到交换记录位置的目的。在这种情况下，比较次数达到最大值n（n–1）/2=O（n2），移动次数也达到最大值3n（n–1）/2=O（n2）。因此，冒泡排序的最坏时间复杂度为O（n2）。 虽然冒泡排序不一定要进行n–1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。 2.快速排序 快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下。 第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这两组中间。 第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。 例如，要对关键码{7,2,5,1,9,6,8,3}进行排序，选择第一个元素为基准。第一趟排序的过程如图1-13所示。 要注意的是，在快速排序中，选定了第一个元素为基准，接着就拿最后一个元素和第一 程序员 http:// 个元素比较，如果大于第一个元素，则保持不变，再拿倒数第二个元素和基准比较；如果小于基准，则进行交换。交换之后，再从前面的元素开始与基准比较，如果小于基准，则保持不变；如果大于基准，则交换。交换之后，再从后面开始比较，依此类推，前后交叉进行。 然后，再采取同样的办法对{3,2,5,1,6}和{8,9}分别进行排序，具体过程如图1-14所示。 图1-13 第一趟排序过程 图1-14 各趟排序过程 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k–1次关键字的比较。 最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须进行n-1次划分，第i次划分开始时区间长度为n–i+1,所需的比较次数为n–i（1≤i≤n-1），故总的比较次数达到最大值n（n-1）/2=O（n2）。如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增次序（或递减次序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。 在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准 程序员 http:// 的左、右两个无序子区间的长度大致相等。总的关键字比较次数为O（nlog2n）。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为O（n2），最好时间复杂度为O（nlog2n）。 尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O（nlog2n）。快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O（log2n），故递归后需栈空间为O（log2n）。在最坏的情况下，递归树的高度为O（n），所需的栈空间为O（n）。快速排序是不稳定的。 1.5.4 归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看为有n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们进行两两合并。直到得到长度为n的有序表，排序结束。 例如，需要对关键码{72,28,51,17,96,62,87,33}进行排序，其归并过程如图1-15所示。 归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O（n），故其时间复杂度无论是在最好情况下还是在最坏情况下均是O（nlog2n）。归并排序需要一个辅助向量来暂存两个 程序员 http:// 有序子文件归并的结果，故其辅助空间复杂度为O（n），显然它不是就地排序。 1.5.5 基数排序 设单关键字的每个分量的取值范围均是C0≤kj≤Crd–1（0≤j （1）若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数。 （2）若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为字符串的最大长度。 基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。 基数排序的具体实现过程如下：设有r个队列，队列的编号分别为0,1,2,…，r–1.首先按最低有效位的值把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述收集过程，直至最高有效位，这样便得到一个从小到大的有序序列。为减少记录移动的次数，队列可以采用链式存储分配，称为链式基数排序。每个队列设有两个指针，分别指向队头和队尾。 例如，需要对{288,371,260,531,287,235,56,299,18,23}进行排序，因为这些数据最高位为百位，所以需要3趟分配和收集。第1趟分配和收集（按个位数）的过程如图1-16所示；第2趟分配与收集（按十位数）的过程如图1-17所示；第3趟分配与收集（按百位数）的过程如图1-18所示。 程序员 http:// 图1-16 第1趟分配与收集 图1-17 第2趟分配与收集 图1-18 第3趟分配与收集 基数排序的时间复杂度为O（d（r+n）），所需的辅助存储空间为O（n+rd），基数排序是稳定的。 1.5.6 顺序查找 顺序查找的基本思想是，从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，程序员 http:// 也适用于线性表的链式存储结构。 成功时顺序查找的平均查找长度如下： 在等概率的情况下，pi=1/n（1≤i≤n），故成功的平均查找长度为（n+…+2+1）/n=（n+1）/2，即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确定查找失败。 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中的结点按查找概率由小到大地存放，以便提高顺序查找的效率。 顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字排序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。 1.5.7 二分法查找 二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中的结点按关键字排序，并且要用向量作为表的存储结构。 二分法查找的基本思想如下（设R[low,…，high]是当前的查找区间）。 （1）确定该区间的中点位置：mid=[（low+high）/2]; （2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若R[mid].key>k,则由表的有序性可知R[mid,…，n].key均大于k,因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…，mid-1]中。因此，程序员 http:// 新的查找区间是左子表R[low,…，high],其中high=mid-1.若R[mid].key （3）下一次查找时针对新的查找区间进行，重复步骤（1）和（2）。 （4）在查找过程中，low逐步增加，而high逐步减少。如果high 因此，从初始的查找区间R[1,…，n]开始，每经过一次与当前查找区间中点位置上的结点关键字比较，就可以确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为k的结点，或者直至当前的查找区间为空（即查找失败）时为止。 例如，我们要在{11,13,17,23,31,36,40,47,52,58,66,73,77,82,96,99}中查找58的过程如图1-19所示（粗体表示mid位置）。在上述序列中查找35的过程如图1-20所示。 图1-19 二分法查找58 图1-20 二分法查找35 二分法查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。要注意的是，判定树的形态只与表结点的个数n相关，而与输入实例中R[1,…，n].key的取值无关。 设内部结点的总数为n=2h–1,则判定树是深度为h=log2（n+1）的满二叉树。树中第k层上的结点个数为2k–1,查找它们所需的比较次数是k.因此在等概率假设下，二分法查 程序员 http:// 找成功时的平均查找长度约为log2（n+1）–1.二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度，即为[log2 n]+1.二分法查找的最坏性能和平均性能相当接近。 虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费o（nlog2n）的时间。二分法查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。 1.5.8 分块查找 分块查找（Blocking Search）又称索引顺序查找。它是一种性能介于顺序查找和二分法查找之间的查找方法。二分法查找表由分块有序的线性表和索引表组成。表R[1,…，n]均分为b块，前b–1块中结点个数为s=[n/b],第b块的结点数允许小于等于s;每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。 抽取各块中的最大关键字及其起始位置构成一个索引表ID[l,…，b],即ID[i]（1≤i≤b）中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。 分块查找的基本思想是：索引表是有序表，可采用二分法查找或顺序查找，以确定待查的结点在哪一块。 由于块内无序，只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找 程序员 http:// 长度是两次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1 = log2（b+1）–1+（s+1）/2≈log2（n/s+1）+s/2;如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2 =（b+1）/2+（s+1）/2=（s2+2s+n）/（2s）。 注意，当块中的结点数选定为时ASL2取极小值。，即当采用顺序查找确定块时，应将各 分块查找的优点是：在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。 分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。 1.6 递归法 递归是一种特别有用的工具，不仅在数学中广泛应用，在日常生活中也常常遇到。例如一个画家所制作的如图1-21所示的一幅画便是一种递归的图形。 递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解中构造出规 程序员 http:// 模较大问题的解。特别地，当规模N=1时，能直接得解。 递归算法包括“递推”和“回归”两部分。递推就是为得到问题的解，将它推到比原问题简单的问题的求解。如f（n）=n!,为计算f（n），将它推到f（n-1），即f（n）=nf（n-1），这就是说，为计算f（n），将问题推到计算f（n–1），而计算f（n–1）比计算f（n）简单，因为f（n–1）比f（n）更接近于已知解0!=1.使用递推时应注意： （1）递推有终止的条件。所谓“终止条件”就是在此条件下问题的解是明确的，缺少终止条件便会使算法失效。例如n!,当n=0时，0!=1为递推的终止条件。 （2）“简单问题”表示离递推终止条件更为接近的问题。简单问题与原问题解的算法是一致的，其差别主要反映在参数上。例如，f（n–1）与f（n）其参数相差1.参数变化，使问题递推到有明确解的问题。 回归是指当“简单问题”得到解后，回归到原问题的解上来。例如，当计算完f（n–1）后，回归计算nf（n–1），即得n!的值。使用回归应注意： （1）递归到原问题的解时，算法中所涉及的处理对象应是关于当前问题的，即递归算法所涉及的参数与局部处理对象是有层次的。当解一问题时，有它的一套参数与局部处理对象。当递推进入一“简单问题”时，这套参数与局部对象便隐蔽起来，在解“简单问题”时，又有它自己的一套。但当回归时，原问题的一套参数与局部处理对象又活跃起来了。 （2）回归到原问题以得到问题的解，回归并不引起其他操作，如下例所示。 计算n!.其公式为： 程序员 http:// 程序片段如下： 【程序1-1】 int factorial（int n） { if（！n）return（1）； else return（n*factorial（n-1））； } 图的深度优先搜索、二叉树的前序、中序和后序遍历等可采用递归实现。 1.6.1 斐波纳契数列 问题描述：编写计算斐波纳契（Fibonacci）数列，数列大小为n。 无穷数列1,1,2,3,5,8,13,21,35,…称为斐波纳契数列，其递归定义如下： 由斐波纳契数列的递归定义可知，当n大于1时，这个数列第n项的数值是它前面两项之和。由于递归算法的执行过程分递推和回归两个阶段，在递推阶段，程序把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解，在回归阶段，程序由在规模很小时求得的解得到较复杂问题的解。因此，对于斐波纳契数列的求解，要得到数列第n项的值，就必须求得数列第n–1项的值。同理，要求得数列第n–1项的值，就必须求得数列第n–2项的值，依次递推下去，最后需要求得数列第1项和第0项的值，递推部分结束。又当n等于0和1时，其数值为1,根据这些值可求出数列第2项的值，再根据数列第2项的值可得到第3项的值，依次回归，最后可依次得到数列第n– 2、n–1和n 程序员 http:// 项的值。由这个例子，我们可以很清楚地了解递归的形式和过程。该问题程序实现如下： 【程序1-2】 # include< stdio.h > int F（int n） {if（n==0）return 1; if（n==1）return 1; if（n>1）return F（n-1）+F（n-2）； /*递归*/ } main（）{ int i,n,m; printf（“please input n: n”）； scanf（“%d”,&n）； printf（“the Fibonacci is : ”）； for（i=0;i<=n;i++）{ m=F（i）； printf（“%d,”,m）； } } 1.6.2 斐波纳契数列 问题描述：编写计算斐波纳契（Fibonacci）数列，数列大小为n。 无穷数列1,1,2,3,5,8,13,21,35,…称为斐波纳契数列，其递归定义如下： 程序员 http:// 由斐波纳契数列的递归定义可知，当n大于1时，这个数列第n项的数值是它前面两项之和。由于递归算法的执行过程分递推和回归两个阶段，在递推阶段，程序把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解，在回归阶段，程序由在规模很小时求得的解得到较复杂问题的解。因此，对于斐波纳契数列的求解，要得到数列第n项的值，就必须求得数列第n–1项的值。同理，要求得数列第n–1项的值，就必须求得数列第n–2项的值，依次递推下去，最后需要求得数列第1项和第0项的值，递推部分结束。又当n等于0和1时，其数值为1,根据这些值可求出数列第2项的值，再根据数列第2项的值可得到第3项的值，依次回归，最后可依次得到数列第n– 2、n–1和n项的值。由这个例子，我们可以很清楚地了解递归的形式和过程。该问题程序实现如下： 【程序1-2】 # include< stdio.h > int F（int n） {if（n==0）return 1; if（n==1）return 1; if（n>1）return F（n-1）+F（n-2）； /*递归*/ } main（）{ int i,n,m; printf（“please input n: n”）； 程序员 http:// scanf（“%d”,&n）； printf（“the Fibonacci is : ”）； for（i=0;i<=n;i++）{ m=F（i）； printf（“%d,”,m）； } } 1.7 本章例题分析 例题1（2011年5月试题36） 若二维数组arr[18,16]的首地址为base,数组元素按列存储，且每个元素占用4个存储单元，则元素arr[5,5]在该数组空间的地址为（36）。 （36）A.base+（4*8+4）*4 B.base+（5*8+5）*4 C.base+（4*6+4）*4 D.base+（5*6+5）*4 例题分析 在本题中，题目告诉我们二维数组arr是一个8行6列的数组，那么每一列有8个元素，而按列存储的意思就是先将第一列的元素全部存放完后，再开始存放第二列的元素，一次类推。 另外从题目给出的二维数组arr[18,16]我们可以看出，下标是从1开始的，因此元素arr[5,5]描述的是第5行第5列的元素，那么在存储该元素前，应该先存储完前4列的所有元素，并且第5列的前4个元素也都已经存放，所有元素arr[5,5]在该数组空间的地址为 程序员 http:// base+（4*8+4）*4.例题答案：（36）A 例题2（2011年5月试题37） 设线性表（59,53,46,48,37,31,25）采用散列（Hash）法进行存储和查找，散列函数为H（Key）=Key MOD 7（MOD表示整除取余运算）。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址 （37） 对应的单链表最长。 （37）A.2 B.3 C.4 D.6 例题分析 根据题目给出的散列函数我们可以分别计算出关键字（59,53,46,48,37,31,25）对应的散列地址分别为（3,4,4,6,2,3,4）。 在链地址方法中，散列表地址域的每个元素都是一个指针，指向一个单链表表，这个单链表存储所有该散列地址上的同义词，比如本题中的59和31就是同义词，因为他们的散列地址都是3.那么很显然，对应散列地址为4的元素有3个，而对应其它散列地址的元素个数都小于3,因此最长的单链表对应散列地址4.所以本题答案选C.例题答案：（37）C 例题3（2011年5月试题38） 设递增序列A为a1,a2,…，an,递增序列B为b1,b2,…，bm,且m>n,则将这两个序列合并为一个长度为m+n的递增序列时，当（38）时，归并过程中元素的比较次数最少。 （38）A.an >bm B.an C.a1>b1 D.a1 例题分析 程序员 http:// 题目告诉我们两个序列都是递增序列，那么如果一个序列的最小值大于另一个序列的最大值时，归并过程的比较次数最少，所以本题答案选B.例题答案：（38）B 例题4（2011年5月试题39） 已知某带权有向图G（顶点数为6,顶点编号为1至6）的邻接表如下所示，其中表结点的结构为： 则图G中含有的弧数为（36）。 （39）A.9 B.11 C.15 D.18 例题分析 根据题目给出的表结点的结构我们可以知道，其中各结点中最左边的是邻接顶点编号，而最中间是边上的权值，右边是指向下一个邻接顶点的指针。根据题目给出的邻接表，我们可以得到如图1-22所示的有向图，所以图G中含有9条弧。 程序员 http:// 图1-22 有向图 例题答案：（39）A 例题5（2011年5月试题40） 当二叉树的结构形如 （40） 时，其后序遍历序列和中序遍历序列相同。 （40） 例题分析 本题主要考查二叉树的遍历。 中序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按中序遍历根结点的左子树，然后访问根结点，最后再按中序遍历根结点的右子树。 后序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，最后再访问根结点。 对于选项A的中序遍历，首先应该遍历根结点的左子树，因此其中序遍历序列为从下至上，而其后续遍历也同样先遍历根结点的左子树，因此其后序遍历序列也为从下至上。 例题答案：（40）A 例题6（2011年5月试题41） 对长度为n的有序表进行二分（折半）查找时，无论查找指定的一个元素是否成功，最多只与表中的（41） 个元素进行比较即可。 程序员 http:// （41） 例题分析 二分（折半）查找的基本思想为：在有序表中，先确定待查元素所在的区域，再逐步缩小这个区域，直到在区域中找到该元素（查找成功）或者区域缩小为0也没有找到该元素（查找失败）为止。通常采用如下递归步骤： （1）将区域分为左、中、右三个部分，其中区域中间的元素单独处于中间区域，该元素左、右两边的元素分别属于左、右区域，则左、右区域所包含的元素相等（或相差1个），数量为原区域元素的一半； （2）比较给定关键字与中央区域元素的关键字，如果相等则查找成功，该元素即为所求； （3）如果给定关键字较大，那么待查元素只可能出现在中间元素右边，则继续对右区域执行步骤1~4; （4）否则给定关键字较小，则待查元素只可能出现在中间元素左边，继续查找左区域即可。 在二分（折半）查找时，无论查找成功与否，最多只与表中的个元素进行比较，例如对含有12个元素的有序表{1,4,10,16,17,18,23,29,33,40,50,51}进行折半查找，如果要查找17,那么首先应该与第6个元素比较，由于17小于18,那么应该在前半部分查找，那么接着应该与第3个元素比较，由于大于10,那么应该接着与16比较，最后与17比较，然后查找成功，一共比较了4次。如果要查找19,那么首先应该与第6个元素比较，由于19大于18,那么应该在后半部分查找，那么接着应该与第9个元素比较，由于大于33,那么应该接着与29比较，最后与23比较，然后查找失败，一共也比较了4次，即 2012年上半年软考程序员考试 历年真题重点题总结及答案 一、单选题 1、计算机中数据的表示形式是(c) A)八进制 B)十进制 C)二进制 D)十六进制 2、硬盘工作时应特别注意避免(B) A)噪声 B)震动 C)潮湿 D)日光 3、针式打印机术语中，24针是指(D) A)24x24点阵 B)信号线插头有24针 C)打印头内有24x24根针 D)打印头内有24根针 4、下面列出的四种存储器中，易失性存储器是(A)A)RAM B)ROM C)PROM D)CD-ROM 5、办公自动化是计算机的一项应用，按计算机应用的分类，它属于(c)A)科学计算 B)实时控制 C)数据处理 D)辅助设计 6、I/O接口位于(A) A)总线和设备之间 B)CPU和I/O设备之间C)主机和总线之间 D)CPU和主存储器之间 7、计算机硬件能直接识别和执行的只有(D) A)高级语言 B)符号语言 C)汇编语言 D)机器语言 8、具有多媒体功能的微型计算机系统中，常用的CD-ROM是(B) A)只读型大容量软盘 B)只读型光盘 C)只读型硬盘 D)半导体只读存储器 9、微机中1K字节表示的二进制位数是(D) A)1000 B)8x1000 C)1024 D)8x1024 10、下列字符中，ASCII码值最小的是(B) A)a B)A C)x D)Y 11、Windows 98操作系统是一个(A) A)单用户多任务操作系统 B)单用户单任务操作系统C)多用户单任务操作系统 D)多用户多任务操作系统 12、把Windows 98的窗口和对话框作一比较，窗口可以移动和改变大小，而对话框(B) A)既不能移动，也不能改变大小 B)仅可以移动，不能改变大小 C)仅可以改变大小，不能移动 D)既能移动，也能改变大小 13、在Windows 98中，“任务栏”的作用是(D) A)显示系统的所有功能 B)只显示当前活动窗口名C)只显示正在后台工作的窗口名 D)实现窗口之间的切换 14、在Word的编辑状态，执行编辑菜单中“复制”命令后(B) A)被选择的内容被复制到插入点处 B)被选择的内容被复制到剪贴板 C)插入点所在的段落内容被复制到剪贴板 D)光标所在的段落内容被复制到剪贴板 15、在Word中“打开”文档的作用是(C) A)将指定的文档从内存中读入，并显示出来 B)为指走的文档打开一个空白窗口 C)将指定的文档从外存中读入，并显示出来 D)显示并打印指走文档的内容 16、Word的“文件”命令菜单底部显示的文件名所对应的文件是(C) A)当前被操作的文件 B)当前已经打开的所有文件 C)最近被操作过的文件 D)扩展名是.doc的所有文件 17、在Word的编辑状态，执行编辑命令“粘贴”后(D) A)将文档中被选择的内容复制到当前插入点处 B)将文档中被选择的内容移到剪贴板 C)将剪贴板中的内容移到当前插入点处 D)将剪贴板中的内容拷贝到当前插入点处 18、在Word的编辑状态，进行字体设置操作后，按新设置的字体显示的文字是(B)A)插入点所在段落中的文字 B)文档中被选择的文字C)插入点所在行中的文字 D)文档的全部文字 19、OSI(开放系统互联)参考模型的最低层是(C) A)传输层 B)网络层 C)物理层 D)应用层 20、存储400个24x24点阵汉字字形所需的存储容量是(D) A)255KB B)75KB C)37.5KB D)28.125KB 21、下面是关于解释程序和编译程序的论述，其中正确的一条是(C) A)编译程序和解释程序均能产生目标程序 B)编译程序和解释程序均不能产生目标程序 C)编译程序能产生目标程序而解释程序则不能 D)编译程序不能产生目标程序而解释程序能 22、下面是与地址有关的四条论述，其中有错的一条是(C) A)地址寄存器是用来存储地址的寄存器 B)地址码是指令中给出源操作数地址或运算结果的目的地址的有关信息部分 C)地址总线上既可传送地址信息，也可传送控制信息和其他信息 D)地址总线上除传送地址信息外，不可以用于传输控制信息和其它信息 23、下列四个不同数制表示的数中，数值最大的是(B) A)二进制数11011101 B)八进制数334 C)十进制数219 D)十六进制数DA 24、设WlndowS 98桌面上已经有某应用程序的图标，要运行该程序，可以(C) A)用鼠标左键单击该图标 B)用鼠标右键单击该图标 C)用鼠标左键双击该图标 D)用鼠标右键双击该图标 25、Windows 98中的“剪贴板”是 (D) A)硬盘中的一块区域 B)软盘中的一块区域 C)高速缓存中的一块区域 D)内存中的一块区域 26、下面是关于Windows 98文件名的叙述，错误的是(D) A)文件名中允许使用汉字 B)文件名中允许使用多个圆点分隔符 C)文件名中允许使用空格 D)文件名中允许使用竖线(“|”) 27、当选定文件或文件夹后，不将文件或文件夹放到“回收站”中，而直接删除的操作是(C) A)按Delete(Del)键 B)用鼠标直接将文件或文件夹拖放到“回收站”中 C)按Shift+Delete(Del)键 D)用“我的电脑”或“资源管理器”窗口中“文件”菜单中的删除命令 28、在Windows98中，不能进行打开“资源管理器”窗口的操作是(B) A)用鼠标右键单击“开始”按钮 B)用鼠标左键单击“任务栏”空白处 C)用鼠标左键单击“开始”菜单中“程序”下的“Win dows资源管理器”项 D)用鼠标右键单击“我的电脑”图标 29、在使用Windows98的过程中，若出现鼠标故障。在不能使用鼠标的情况下，可以打开“开始”菜单的操作是(C) A)按Shift+Tab键 B)按Ctrl十Shift键 C)按Ctrl+Esc键 D)按空格键 30、在Windows98的“我的电脑”窗口中，若已选定了文件或文件夹，为了设置其属性，可以打开属性对话框的操作是 A)用鼠标右键单击“文件”菜单中的“属性”命令(B)B)用鼠标右键单击该文件或文件夹名，然后从弹出的快捷菜单中选“属性”项 C)用鼠标右键单击“任务栏”中的空白处，然后从弹出的快捷菜单中选择“属性”项 D)用鼠标右键单击“查看”菜单中“工具栏”下的“属性”图标 31、在Windows98的“资源管理器”窗口中，如果想一次选定多个分散的文件或文件夹，正确的操作是(B) A)按住Ctrl键，用鼠标右键逐个选取 B)按住Ctrl键，用鼠标左键逐个选取 C)按住Shift键，用鼠标右键逐个选取 D)按住Shift键，用鼠标左键逐个选取 32、在Windows98中，若己选定某文件，不能将该文件复制到同一文件夹下的操作是 A)用鼠标右键将该文件拖动到同一文件夹下 B)先执行“编辑”菜单中的复制命令，再执行粘贴命令(C) C)用鼠标左键将该文件拖动到同一文件夹下 D)按注Ctrl键，再用鼠标右键将该文件拖动到同一文件夹下 33、在中文Windows98中，为了实现全角与半角状态之间的切换，应按的键是(A) A)Shift+空格 B)Ctrl十空格 C)Shift十Ctrl D)Ctrl十F9 34、在word的编辑状态，设置了一个由多个行和列组成的空表格，将插入点定在某个单元格内，用鼠标单击“表格”命令菜单中的“选定行”命令，再用鼠标单击“表格”命令菜单中的“选定列”命令，则表格中被“选择”的部分是(D) A)插入点所在的行 B)插入点所在的列 C)一个单元洛 D)整个表格 35、在Word的编辑状态，设置了标尺，可以同时显示水平标尺和垂直标尺的视图方式是(B) A)普通方式 B)页面方式 C)大纲方式 D)全屏显示方式 36、设定打印纸张大小时，应当使用的命令是(B) A)文件菜单中的“打印预览”命令 B)文件菜单中的“页面设置”命令 C)视图菜单中的“工具栏”命令 D)视图菜单中的“页面”命令 37、如果想在Word7.0主窗口中显示常用工具按扭，应当使用的菜单是(B) A)“工具”菜单 B)“视图”菜单 C)“格式”菜单 D)“窗口”菜单 38、当前活动窗口是文档d1.doc的窗口，单击该窗口的“最小化”按扭后 A)不显示d1.doc文档内容，但d1.doc文档 并未关闭 B)该窗口和d1.doc文档都被关闭 C)d1.doc文档未关闭，且继续显示其内容 D)关闭了d1.doc文档但该窗口并未关闭 39、当个人计算机以拨号方式接入1nternet网时，必须使用的设备是 A)网卡 B)调制解调器(Modem)C)电话机 D)浏览器软 40、微型计算机中，控制器的基本功能是 A)进行算术运算和逻辑运算 B)存储各种控制信息 C)保持各种控制状态 D)控制机器各个部件协调一致地工作 41、下列设备中，既能向主机输入数据又能接收主机输出数据的设备是 A)CD-ROM B)显示器 C)软磁盘驱动器 D)光笔 42、在计算机领域中，通常用英文单词“BYTE”来表示 A)字 B)字长 C)二进制位 D)字节 43、某工厂的仓库管理软件属于 A)应用软件 B)系统软件 C)工具软件 D)字处理软件 44、微型计算机的主机包括 A)运算器和显示器 B)CPU和内存储器 C)CPU和UPS D)UPS和内存储器 45、下面四条常用术语的叙述中，有错误的一条是 A)光标是显示屏上指示位置的标志 B)汇编语言是一种面向机器的低级程序设计语言，用汇编语言编写的源程序计算机能直接执行 C)总线是计算机系统中各部件之间传输信息的公共通路 D)读写磁头是既能从磁表面存储器读出信息又能把信息写入磁表面存储器的装置 46、下列字符中，其ASCII码值最大的是 A)9 B)D C)a D)y 47、下列四个无字符十进制整数中，能用八个二进制位表示的是 A)257 B)20C)31 3D)296 48、计算机病毒是指 A)编制有错误的计算机程序 B)设计不完善的计算机程序 C)计算机的程序已被破坏 D)以危害系统为目的的特殊的计算机程序 49、在计算机应用中，“计算机辅助设计”的英文缩写为 A)CAD B)CAM C)CAE D)CAT 50、WINDOW98系统安装并启动后，由系统安排在桌面上的图标是 A)资源管理器 B)回收站 C)MICROSOFT WORD D)MICROSOFT FOXPRO 51、在WINDOW98中，有两个对系统资源进行管理的程序组，它们“资源管理器”和 A)“回收站” B)“剪贴板” C)“我的电脑” D)“我的文档” 52、在WINDOW98中，下列正确的文件名是 A)MY PRKGRAM GROUP.TXT B)FILE1|FILE2 C)A<>B.C D)A?B.DOC 53、WINDOW98中，不能在“任务栏”内进行的操作是 A) 设置系统日期的时间 B)排列桌面图标 C)排列和切换窗口 D)启动“开始”菜单 54、word 主窗口的标题栏右边显示的按钮是 A)最小化按钮 B)还原按钮 C)关闭按钮 D)最大化按钮 55、在word 的编辑状态，单击按钮后可以 A)将指定的文档打开 B)为指定的文档打开一个空白窗口 C)使当前窗口还原 D)使当前窗口极大化 56、在word的哪种视图方式下，可以显示分页效果 A)普通 B)大纲 C)页面 D)主控文档 57、在word的编辑状态，执行“文件”菜单中的“保存”命令后将所有打开的文档存盘 A)将所有打开的文档存盘 B)只能将当前文档存储在原文件夹内 C)可以将当前文档存储在已有的任意文件内 D)可以先建立一个新文件夹，再将文档存储在该文件夹内 58、在word的编辑状态，连续进行了两次“插入”操作，当单击一次“撤消”按钮后 A)将两次插入的内容全部取消 B)将第一次插入的内容全部取消 C)将第二次插入的内容全部取消 D)两次插入的内容都不被取消 59、下列属于微机网络所特有的设备是 A)显示器 B)UPS电源 C)服务器 D)鼠标器 60、CPU中有一个程序计数器(又称指令计数器)，它用于存放 A)正在执行的指令的内容 B)下一条要执行的指令的内容 C)正在执行的指令的内存地址 D)下一条要执行的指令的内存地址 61、与十六进制数值CD等值的十进制数是 A)20 4B)20 5C)206 D)203 62、在微型计算机内存储器中，不能用指令修改其存储内容的部分是 A)RAM B)DRAM C)ROM D)SRAM 63、下列四条叙述中，正确的一条是 A)假若CPU向外输出20位地址，则它能直接访问的存储空间可达1MB B)PC机在使用过程中突然断电，SRAM中存储的信息不会丢失 C)PC机在使用过程中突然断电，DRAM中存储的信息不会丢失 D)外存储器中的信息可以直接被CPU处理 64、在WINDOW98中为了重新排列桌面上的图标，首先应进行的操作是 A)用鼠标右键单击桌面空白处 B)用鼠标右键单击“任务栏”空白处 C)用鼠标右键单击已打开窗口空白处 D)用鼠标右键单击“开始”空白处 65、在WINDOW98中，若在某一文档中连续进行了多次剪切操作，当关闭该文档后，“剪贴板”中存放的是 A)空白 B)所有剪切过的内容 C)最后一次剪切的内容 D)第一次剪切的内容 66、在WINDOW98的“资源管理器”窗口中，其左部窗口中显示的是 A)当前打开的文件夹的内容 B)系统的文件夹树 C)当前打开的文件夹名称及其内容 D)当前打开的文件夹名称 67、在WINDOW98的“我的电脑”窗口中，若已选定硬盘上的文件或文件夹，并按了DEL键和“确定”按钮，则该文件或文件夹将 A)被删除并放入“回收站” B)不被删除也不放入“回收站” C)被删除但不放入回收站 D)不被删除但放入“回收站” 68、在WINDOW98的资源管理器窗口中，为了将选定的硬盘上的文件或文件夹复制到软盘，应进行的操作是 A)先将它们删除并放入“回收站”，再从“回收站”中恢复 B)用鼠标左键将它们从硬盘拖动到软盘 C)先用执行“编辑”菜单下的“剪切”命令，再执行“编辑”菜单下的“粘贴”命令 D)用鼠标右键将它们从硬盘拖动到软盘，并从弹出的快捷菜单中选择“移动到当前位置” 69、在WINDOW98中，要安装一个应用程序，正确的操作应该是 A)打开“资源管理器”窗口，使用鼠标拖动 B)打开“控制面板”窗口，双击“添加/删除程序”图标 C)打开MS-DOS窗口，使用copy命令 D)打开“开始”菜单，选中“运行”项，在弹出的“运行”对话框中copy命令 70、在WINDOW98中，用“创建快捷方式”创建的图标 A)可以是任何文件或文件夹 B)只能是可执行程序或程序组 C)只能是单个文件 D)只能是程序文件和文档文件 71、在Window98的“资源管理器”左部窗口中，若显示的文件夹图标前带有加号(+)，意味着该文件夹 A)含有下级文件夹 B)仅含有文件 C)是空文件夹 D)不含下级文件夹 72、在Window98的窗口中，选中末尾带有省略号(…)的菜单意味着 A)将弹出下一级菜单 B)将执行该菜单命令 C)表明该菜单项已被选用 D)将弹出一个对话框 73、在中文Window98中，为了实现中文与西文输入方式的切换，应按的键是 A)Shift+空格 B)Shift+Tab C)Ctrl+空格 D)Alt+F6 74、在WORD的编辑状态，利用下列哪个菜单中的命令可以选定单元格? A)“表格”菜单 B)“工具”菜单 C)“格式”菜单 D)“插入”菜单 75、)在WORD的编辑状态,可以显示页面四角的视图方式是 A)普通视图方式 B)页面视图方式 C)大纲视图方式 D)各种视图方式 76、在WORD的编辑状态,要在文档中添加符号“☆”，应该使用哪个菜单中命令? A)“文件”菜单 B)“编辑”菜单 C)“格式”菜单 D)“插入”菜单 77、在WORD的编辑状态，进行“替换”操作时，应当使用哪个菜单中的命令 A)“工具”菜单中的命令 B)“视图”菜单中的命令 C)“格式”菜单中的命令 D)“编辑”菜单中的命令 78、在WORD的编辑状态，按先后顺序依次打开了d1.doc、d2.doc、d3.doc、d4.doc四个文档，当前的活动窗口是哪个文档的窗口? A)d1.doc的窗口 B)d2.doc的窗口 C)d3.doc的窗口 D)d4.doc的窗口 79、进入WORD的编辑状态后，进行中文标点符号与英文标点符号之间切换的快捷键是 A)Shift+空格 B)Shift+Ctrl C)Shift+.D)Ctrl+.80、OSI参考模型中的第二层是 A)网络层 B)数据链路层 C)传输层 D)物理层 81、微机计算机硬件系统中最核心的部件是 A)主板 B)CPU C)内存储器 D)I/O设备 82、为解决某一特定问题而设计的指令序列称为 A)文档 B)语言 C)程序 D)系统 83、下列关于系统软件的四条叙述中，正确的一条是 A)系统软件与具体应用领域无关 B)系统软件与具体硬件逻辑功能无关 C)系统软件是在应用软件基础上开发的 D)系统软件并不具体提供人机界面 84、下列几种存储器中,存取周期最短的是 A)内存储器 B)光盘存储器 C)硬盘存储器 D)软件盘存储器 85、微型计算机键盘上的Shift键称为 A)回车换行键 B)退格键 C)换档键 D)空格键 86、计算机能直接识别和执行的语言是 A)机器语言 B)高级语言 C)汇编语言 D)数据库语言 87、与十进制数254等值的二进制数是 A)11111110 B)11101111 C)11111011 D)11101110 88、下列术语中,属于显示器性能指标的是 A)速度 B)可靠性 C)分辨率 D)精度 89、在计算机领域中通常用MIPS来描述 A)计算机的运算速度 B)计算机的可靠性 C)计算机的可运行性 D)计算机的可扩充性 90、在下列四项中,不属于OSI(开放系统互连)参考模型七个层次的是 A)会话层 B)数据链路层 C)用户层 D)应用层 91、计算机系统由 A、主机和系统软件组成 B、硬件系统和应用软件组成 C、硬件系统和软件系统组成 D、微处理器和软件系统组成 92、运算器的主要功能是 A、实现算术运算和逻辑运算 B、保存各种指令信息供系统其他部件使用 C、分析指令并进行译码 D、按主频指标规定发出时钟脉冲 93、列四条叙述中，正确的一条是 A、字节通常用英文单词“bit”来表示 B、目前广泛使用的Pentium机其字长为5个字节 C、计算机存储器中将8个相邻的二进制位作为一个单位，这种单位称为字节 D、微型计算机的字长并不一定是字节的倍数 94、下列四种设备中，属于计算机输入设备的是 A、UPS B、服务器 C、绘图仪 D、鼠标器 95、与十进制数291等值的十六进制数为 A、123 B、213 C、231 D、132 96、Pentium Ⅲ/500微型计算机，其CPU的时钟频率是 A、500KHZ B、500MHZ C、250KHZ D、250MHZ 97、在操作系统中，文件管理的主要功能是 A、实现文件的虚拟存取 B、实现文件的高速存取 C、实现文件的按内容存取 D、实现文件的按名存取 98、下列WINDOW 98桌面上图标的叙述中，错误的是 A、所有的图标都可以重命名” B、图标可以重新排列 C、图标可以复制 D、所有的图标都可以移动 99、下列关于Window 98对话框的叙述中，错误的是 A、对话框是提供给用户与计算机对话的界面 B、对话框的位置可以移动，但大小不能改变 C、对话框的位置和大小都不能改变 D、对话框中可能会出现滚动条 100、下列关于Window 98“开始”菜单的叙述中，错误的是 A、“开始”菜单中包含了Windows 95的全部功能 B、用户可以自己定义“开始”菜单 C、“开始”菜单的位置不能改变 D、“开始”按钮可以不显示在桌面上 101、在Word 的编辑状态打开了一个文档，对文档没作任何修改，随后单击Word主窗口标题栏右侧的“关闭”按钮或者单击“文件”菜单中的“退出”命令，则 A、仅文档窗口被关闭 B、文档和Word主窗口全被关闭 C、仅Word主窗口被关闭 D、文档和Word主窗口全未被关闭 102、在Word的编辑状态，文档窗口显示出水平标尺，拖动水平标尺上沿的“首行缩进”滑块，则 A、文档中各段落的首行起始位置都重新确定 B、文档中被选择的各段落首行起始位置都重新确定 C、文档中各行的起始位置都重新确定 D、插入点所在行的起始位置被重新确定 103、在Word的编辑状态，打开了“wl.doc”文档，若要将经过编辑后的文档以“w2.doc”为名存盘，应当执行“文件”菜单中的命令是 A、保存 B、另存为HTML C、另存为 D、版本 104、在word的编辑状态，被编辑文档中的文字有“四号”、“五号”、“16”磅、“18”磅 四种，下列关于所设定字号大小的比较中，正确的是 A、“四号”大于“五号” B、“四号”小于“五号”C、“16”磅大于“18”磅 D、字的大小一样，字体不同 105、OSI(开放系统互连)参考模型的最高层是 A、表示层 B、网络层 C、应用层 D、会话层 106、微型计算机中使用最普遍的字符编码是 A、EBCDIC码 B、国标码 C、BCD码 D、ASCII码 107、微型计算机中的内存储器，通常采用 A、光存储器 B、磁表面存储器 C、半导体存储器 D、磁芯存储器 108、微型计算机键盘上的Tab键是 A、退格键 B、控制键 C、交替换档键 D、制表定位键 109、下列四种软件中，属于系统软件的是 A、WPS B、Word C、DOS D、Excel 110、“计算机辅助制造”的常用英文缩写是 A、CAD B、CAI C、CAT D、CAM 111、Window 98具有“复制软盘”功能，复制软盘要求 A、源盘和目的盘必须规格相同 B、系统必须具有两个软盘驱动器 C、目的盘必须先经过格式化 D、目的盘上的全部内容必须先清除 112、在Window 98中，对同时打开的多个窗口进行层叠式排列，这些窗口的显著特点是 A、每个窗口的内容全部可见 B、每个窗口的标题栏全部可见 C、部分窗口的标题栏不可见 D、每个窗口的部分标题栏可见 113、在Window 98的“资源管理器”窗口左部，单击文件夹图标左侧的加号(+)后，屏幕上显示结果的变化是 A、窗口左部显示的该文件夹的下级文件夹消失 B、该文件夹的下级文件夹显示在窗口右部 C、该文件夹的下级文件夹显示在窗口左部 D、窗口右部显示的该文件夹的下级文件夹消失 114、在Window 98中，当一个窗口已经最大化后，下列叙述中错误的是 A、该窗口可以被关闭 B、该窗口可以移动 C、该窗口可以最小化 D、该窗口可以还原 115、下列关于Window 98“回收站”的叙述中，错误的是 A、“回收站”可以暂时或永久存放硬盘上被删除的信息 B、放入“回收站”的信息可以恢复 C、“回收站”所占据的空间是可以调整的 D、“回收站”可以存放软盘上被删除的信息 116、在Window 98中，可以由用户设置的文件属性为 A、存档、系统和隐藏 B、只读、系统和隐藏 C、只读、存档和隐藏 D、系统、只读和存档 117、在Window 98中，为了将软盘上选定的文件移动到硬盘上，正确的操作是 A、用鼠标左键拖动后，再选择“移动到当前位置” B、用鼠标右键拖动后，再选择“移动到当前位置” C、按住Ctrl键，再用鼠标左键拖动 D、按住Alt键，再用鼠标右键拖动 118、在Window98的“资源管理器”窗口右部，若已单击了第一个文件，又按住Ctrl键并单击了第五个文件，则 A、有0个文件被选中 B、有5个文件被选中 C、有1个文件被选中 D、有2个文件被选中 119、在中文Window98的输入中文标点符号状态下，按下列哪个键可以输入中文标点符号顿号(、)? A、~ B、& C、D、/ 120、在Word编辑状态，可以使插入点快速移到文档首部的组合键是 A、Ctrl+Home B、Alt+Home C、Home D、PageUp 121、在Word的编辑状态，打开了一个文档，进行“保存”操作后，该文档 A、被保存在原文件夹下 B、可以保存在已有的其他文件夹下 C、可以保存在新建文件夹下 D、保存后文档被关闭 122、在Word的编辑状态，对当前文档中的文字进行替换操作，应当使用的菜单是 A、“工具”菜单 B、“文件”菜单 C、“视图”菜单 D、“编辑”菜单 123、在Word的编辑状态，先打开了d1.doc文档，又打开了d2.doc文档，则 A、d1.doc文档的窗口，遮蔽d2.doc文档的窗口 B、打开了d2.doc文档的窗口，d1.doc文档的窗口被关闭 C、打开的d2.doc文档窗口遮蔽了d1.doc文档的窗口 D、两个窗口并列显示 124、在Word编辑状态，包括能设定文档行间距命令的菜单是 A、“文件”菜单 B、“窗口”菜单 C、“格式”菜单 D、“工具”菜单 125、在计算机网络中，通常把提供并管理共享资源的计算机称为 A、服务器 B、工作站 C、网关 D、网桥 126、计算机中对数据进行加工与处理的部件，通常称为 A)运算器 B)控制器 C)显示器 D)存储器 127、微型计算机中内存储器比外存储器 A)读写速度快 B)存储容量大 C)运算速度慢 D)以上三种都可以 128、目前微型计算机中CPU进行算术运算和逻辑运算时，可以处理的二进制信息长度是 A)32位 B)16位 C)8位 D)以上三种都可以 129、微型计算机存储器系统中的Cache是 A)只读存储器 B)高速缓冲存储器 C)可编程只读存储器 D)可擦除可再编程只读存储器 130、存储容量1GB等于 A)1024B B)1024KB C)1024MB D)128MB 131、第一台电子计算机使用的逻辑部件是 A)集成电路 B)大规模集成电路 C)晶体管 D)电子管 132、微型计算机使用的键盘上的Alt键称为 A)控制键 B)上档键 C)退格键 D)交替换档键 133、与十六进制数(BC)等值的二进制数是 A)10111011 B)10111100 C)11001100 D)11001011 134、下列字符中ASCII码值最小的是 A)A B)a C)k D)M 135、存储一个32×32点阵汉字字型信息的字节数是 A)64B B)128B C)256B D)512B 136、在操作系统中，存储管理主要是对 A)外存的管理 B)内存的管理 C)辅助存储器的管理 D)内存和外存的统一管理 137、删除Windows 98桌面上某个应用程序的图标，意味着 A)该应用程序连同其图标一起被删除 B)只删除了该应用程序，对应的图标被隐藏 C)只删除了图标，对应的应用程序被保留 D)该应用程序连同其图标一起被隐藏 138、下列关于Windows 98窗口的叙述中，错误的是 A)窗口是应用程序运行后的工作区 B)同时打开的多个窗口可以重叠排列 C)窗口的位置和大小都改变 D)窗口的位置可以移动，但大小不能改变 139、在Windows 98中，为保护文件不被修改，可将它的属性设置为 A)只读 B)存档 C)隐藏 D)系统 140、在Word的编辑状态打开了一个文档，对文档作了修改，进行“关闭”文档操作后 A)文档被关闭，并自动保存修改后的内容 B)文档不能关闭，并提示出错 C)文档被关闭，修改后的内容不能保存 D)弹出对话框，并询问是否保存对文档的修改 141、在Word的编辑状态，选择了一个段落并设置段落的“首行缩进”设置为1厘米，则 A)该段落的首行起始位置距页面的左边距1厘米 B)文档中各段落的首行只由“首行缩进”确定位置 C)该段落的首行起始位置距段落的“左缩进”位置的右边1厘米 D)该段落的首行起始位置在段落“左缩进”位置的左边1厘米 142、在Word的编辑状态，打开了“w1.doc”文档，把当前文档以“w2.doc”为名进行“另存为”操作，则 A)当前文档是w1.doc B)当前文档是w2.doc C)当前文档是w1.doc与w2.doc D)w1.doc与w2.doc全被关闭 143、在Word的编辑状态，选择了文档全文，若在“段落”对话框中设置行距为20磅的格式，应当选择“行距”列表框中的 A)单倍行距 B)1.5倍行距 C)固定值 D)多倍行距 144、下列设备中，多媒体计算机所特有的设备是 A)打印机 B)视频卡 C)鼠标器 D)键盘 145、下列四项中不属于微型计算机主要性能指标的是 A)字长 B)内存容量 C)重量 D)时钟脉冲 146、目前各部门广泛使用的人事档案管理、财务管理等软件，按计算机应用分类，应属于 A)实时控制 B)科学计算 C)计算机辅助工程 D)数据处理 147、下列关于计算机病毒的四条叙述中，有错误的一条是 A)计算机病毒是一个标记或一个命令 B)计算机病毒是人为制造的一种程序 C)计算机病毒是一种通过磁盘、网络等媒介传播、扩散，并能传染其它程序的程序 D)计算机病毒是能够实现自身复制，并借助一定的媒体存的具有潜伏性、传染性和破坏性 148、计算机硬件能直接识别并执行的语言是 A)高级语言 B)算法语言 C)机器语言 D)符号语言 149、按照操作方式，Windows 98系统相当于 A)实时系统 B)批处理系统 C)分布式系统 D)分时系统 150、在Windows 98中，不能设置磁盘卷标的操作为 A)“快速”格式化 B)“完全”格式化 C)“只复制系统文件”格式化 D)磁盘“属性”对话框 151、在Windows 98中，对同时打开的多个窗口进行平铺式排列后，参加排列的窗口为 A)所有已打开的窗口 B)用户指定的窗口 C)当前窗口 D)除已最小化以外的所有打开的窗口 152、在Windows 98的“资源管理器”窗口左部，单击文件夹图标左侧的减号(—)后，屏幕上显示结果的变化是 A)该文件夹的下级文件夹显示在窗口右部 B)窗口左部显示的该文件夹的下级文件夹消失 C)该文件夹的下级文件显示在窗口左部 D)窗口右部显示的该文件夹的下级文件夹消失 153、在Windows 98中，下列不能用在文件名中的字符是 A)，B)^ C)? D)+ 154、下列关于Windows 98“回收站”的叙述中，错误的是 A)“回收站”中的信息可以清除，也可以还原 B)每个逻辑硬盘上“回收站”的大小可以分别设置 C)当硬盘空间不够使用时，系统自动使用“回收站”所占据的空间 D)“回收站“中存放的是所有逻辑硬盘上被删除的信息 155、在Windows 98中，呈灰色显示的菜单意味着 A)该菜单当前不能选用 B)选中该菜单后将弹出对话框 C)选中该菜单后将弹出下级子菜单 D)该菜单正在使用 156、在Windows 98中，若系统长时间不响应用户的要求，为了结束该任务，应使用的组合键是 A)Shift+Esc+Tab B)Crtl+Shift+Enter C)Alt+Shift+Enter D)Alt+Ctrl+Del 157、在Windows 98的“资源管理器”窗口中，若希望显示文件的名称、类型、大小等信息，则应该选择“查看”菜单中的 A)列表 B)详细资料 C)大图标 D)小图标 158、在Windows 98的中文标点符号输入状态，为了输入省略号(……)，应按的键是 A)~ B)— C)^ D)@ 159、在Word的编辑状态，选择了当前文档中的一个段落，进行“清除”操作(或按Del键)，则 A)该段落被删除且不能恢复 B)该段落被删除，但能恢复 C)能利用“回收站”恢复被删除的该段落 D)该段落被移到“回收站”内 160、进入Word后，打开了一个已有文档w1.doc，又进行了“新建”操作，则 A)w1.doc被关闭 B)w1.doc和新建文档均处于打开状态 C)“新建”操作失败 D)新建文档被打开但w1.doc被关闭 161、在Word编辑状态，进行“打印”操作，可以单击格式工具栏中的 A)B)C)D) 162、在Word的编辑状态，对当前文档中的文字进行“字数统计”操作，应当使用的菜单是 A)“编辑”菜单 B)“文件”菜单 C)“视图”菜单 D)“工具”菜单 163、在Word编辑状态，先后打开了d1.doc文档和d2.doc文档，则 A)可以使两个文档的窗口都显现出来 B)只能显现d2.doc文档的窗口 C)只能显现d1.doc文档的窗口 D)打开d2.doc后两个窗口自动并列显示 164、在Word的编辑状态，建立了4行4列的表格，除第4行与第4列相交的单元格以外各单元格内均有数字，当插入点移到该单元格内后进行“公式”操作，则 A)可以计算出列或行中数字的和 B)仅能计算出第4列中数字的和 C)仅能计算出第4行中数字的和 D)不能计算数字的和 165、下列四项内容中，不属于Internet(因特网)基本功能是 A)电子邮件 B)文件传输 C)远程登录 D)实时监测控制 166、完整的计算机硬件系统一般包括外部设备和 A)运算器和控制器 B)存贮器 C)主机 D)中央处理器 167、计算机能够自动工作，主要是因为采用了 A)二进制数制 B)高速电子元件 C)存储程序控制 D)程序设计语言 168、下面哪一组是系统软件 A)DOS和MIS B)WPS和UNIX C)DOS和UNIX D)UNIX和Word 169、下列各组设备中，全部属于输入设备的一组是 A)键盘、磁盘和打印机 B)键盘、扫描仪和鼠标 C)键盘、鼠标和显示器 D)硬盘、打印机和键盘 170、6位无符号二进制数能表示的最大十进制整数是 A)64 B)63 C)32 D)31 171、)在计算机中采用二进制，是因为 A)可降低硬件成本 B)两个状态的系统具有稳定性 C)二进制的运算法则简单 D)上述三个原因 172、下列叙述中，正确的一条是 A)存储在任何存储器中的信息，断电后都不会丢失 B)操作系统是只对硬盘进行管理的程序 C)硬盘装在主机箱内，因此硬盘属于主存 D)磁盘驱动器属于外部设备 173、将高级语言编写的程序翻译成机器语言程序，采用的两种翻译方式是 A)编译和解释 B)编译和汇编 C)编译和链接 D)解释和汇编 174、为了避免混淆，十六进制数在书写时常在后面加字母 A)H B)O C)D D)B 175、在WINDOWS 98中，下列关于“任务栏”的叙述，哪一种是错误的 A)可以将任务栏设置为自动隐藏 B)任务栏可以移动 C)通过任务栏上的按钮，可实现窗口之间的切换 D)在任务栏上，只显示当前活动窗口名 176、在WINDOWS98默认环境中，下列哪个组合键能将选定的文档放入剪贴板中 A)Ctrl+V B)Ctrl+Z C)Ctrl+X D)Ctrl+A 177、在WINDOWS98默认环境中，下列哪个是中英文输入切换键 A)Ctrl+Alt B)Ctrl+空格 C)Shift+空格 D)Ctrl+Shift 178、WINDOWS98的整个显示屏幕称为 A)窗口 B)操作台 C)工作台 D)桌面 179、在Word 97的编辑状态，打开文档ABC，修改后另存为ABD，则文档ABC A)被文档ABC覆盖 B)被修改未关闭 C)被修改并关闭 D)未修改被关闭 180、在Word 97的编辑状态中，编辑文档中的A2，应使用“格式”菜单中的命令是 A)字体 B)段落 C)文字方向 D)组合字符 181、在Word 97的编辑状态中，“粘贴”操作的组合键是 A)Ctrl+A B)Ctrl+C C)Ctrl+V D)Ctrl+X 182、在Word 97的表格操作中，计算求和的函数是 A)Count B)Sum C)Total D)Average 183、在Word 97的编辑状态中，对已经输入的文档进行分栏操作，需要使用的菜单是 A)编辑 B)视图 C)格式 D)工具 184、调制解调器(Modem)的作用是 A)将计算机的数字信号转换成模拟信号，以便发送 B)将模拟信号转换成计算机的数字信号，以便接收 C)将计算机数字信号与模拟信号互相转换，以便传输 D)为了上网与接电话两不误 185、计算机软件系统是由哪两部分组成 A)网络软件、应用软件 B)操作系统、网络软件 C)系统软件、应用软件 D)服务器端系统软件、客户端应用软件 186、下列叙述中，哪一条是正确的 A)反病毒软件通常滞后于计算机新病毒的出现 B)反病毒软件总是超前于病毒的出现，它可以查、杀任何种类的病毒 C)感染过计算机病毒的计算机具有对该病毒的免疫性 D)计算机病毒会危害计算机用户的健康 187、下列叙述中错误的一条是 A)内存容量是指微型计算机硬盘所能容纳信息的字节数 B)微处理器的主要性能指标是字长和主频 C)微型计算机应避免强磁场的干扰 D)微型计算机机房湿度不宜过大 188、用户使用计算机高级语言编写的程序，通常称为 A)源程序 B)汇编程序 C)二进制代码程序 D)目标程序 189、CAD软件可用来绘制 A)机械零件图 B)建筑设计图 C)服装设计图 D)以上都对 190、在WINDOWS 98中，一般不使用下列哪一种来管理“打印机” A)资源管理器 B)控制面板 C)我的电脑 D)附件 191、在WINDOWS 98中，若要将当前窗口存入剪贴板中，可以按 A)Alt+PrintScreen键 B)Ctrl+PrintScreen键 C)PrintScreen键 D)Shift+PrintScreen键 192、在WINDOWS 98默认环境中，下列哪种方法不能使用“查找”命令 A)用“开始”菜单中的“查找”命令 B)在“资源管理器”窗口中按“查找”按钮 C)用鼠标右键单击“开始”按钮，然后在弹出的菜单中选“查找”命令 D)用鼠标右键单击“我的电脑”图标，然后在弹出的菜单中选“查找”命令 193、在WINDOWS 98中，文件夹名不能是 A)12%+3% B)12$-3$ C)12*3!D)1&2=0 194、在WINDOWS 98中，拖动鼠标执行复制操作时，鼠标光标的箭头尾部 A)带有“!”号 B)带有“+”号 C)带有“%”号 D)不带任何符号 195、在WINDOWS 98中，若要同时运行两个程序，则 A)两个程序可以同一时刻占用同一处理器 B)只有在一个程序放弃处理器控制权后，另一个程序才能占用该处理器 C)一个程序占用处理器运行时，另一个程序可以抢占该处理器运行 D)一个程序一直占用处理器并运行完成后，另一个程序才能占用该处理器 196、在Word 97的编辑状态中，使插入点快速移动到文档尾的操作是 A)PgUp B)Alt+End C)Ctrl+End D)PgDn 197、在Word 97的编辑状态中，如果要输入希腊字母Ω，则需要使用的菜单是 A)编辑 B)插入 C)格式 D)工具 198、在Word 97的文档中插入数学公式，在“插入”菜单中应选的命令是 A)符号 B)图片 C)文件 D)对象 199、需要在Word 97的文档中设置页码，应使用的菜单是 A)文件 B)插入 C)格式 D)工具 200、在Word 97中，如果要使文档内容横向打印，在“页面设置”中应选择的标签是 A)纸张大小 B)纸张来源 C)版面 D)页边距 201、最大的10位无符号二进制整数转换成十进数是 A、511 B、512 C、1023 D、1024 202、下面有关计算机操作系统的叙述中，不正确的是 A、操作系统属于系统软件 B、操作系统只负责管理内存储器，而不管理外存储器 C、UNIX是一种操作系统 D、计算机的处理器、内存等硬件资源也由操作系统管理 203、大写字母“A”的ASCII码为十进制数65，ASCII码为十进制数68的字母是 A、B B、C C、D D、E 204、微机上操作系统的作用是 A、解释执行源程序 B、编译源程序 C、进行编码转换 D、控制和管理系统资源 205、下列存储器中存取速度最快的是 A、内存 B、硬盘 C、光盘 D、软盘 206、软盘不能写入只能读出的原因是 A、新盘未格式化 B、已使用过的软盘片 C、写保护 D、以上均不正确 207、在计算机中，一个字节是由多少个二进制位组成的 A、4 B、8 C、16 D、24 208、在16×16点阵字库中，存储一个汉字的字模信息需用的字节数是 A、8 B、16 C、32 D、64 209、下列选项中，不属于计算机病毒特征的是 A、破坏性 B、潜伏性 C、传染性 D、免疫性 210、以下操作系统中，不是网络操作系统的是 A、MS-DOS B、Windows 2000 C、Windows NT D、Novell 211、Windows98中是多少位的操作系统 A、16位 B、32位 C、64位 D、128位 212、Windows98中，欲选定当前文件夹中的全部文件和文件夹对象，可使用的组合键是 A、Ctrl+V B、Ctrl+A C、Ctrl+X D、Ctrl+D 213、在Windows98的“写字板”中，“打印预览”菜单项所在的下拉菜单是 A、文件 B、编辑 C、视图 D、工具 214、在Windows98的“资源管理器”窗口中，为了改变隐藏文件的显示情况，应首先选用的菜单是 A、文件 B、编辑 C、查看 D、帮助 215、在Word97中,按钮“”的作用是: A、打开 B、贴粘 C、保存 D、复制 216、在Word 97的编辑状态，打开文档ABC，修改后另存为ABD，则 A、ABC是当前文档 B、ABD是当前文档 C、ABC和ABD均是当前文档 D、ABC和ABD均不是当前文档 217、在Word97的编辑状态中，若设置一个文字格式为下标形式，应使用“格式”菜单中的菜单项为 A、字体 B、段落 C、文字方向 D、组合字符 218、在Word97的编辑状态中，对已经输入的文档设置首字下沉，需要使用的菜单是 A、编辑 B、视图 C、格式 D、工具 219、TCP/IP协议的含义是 A、局域网传输协议 B、拨号入网传输协议 C、传输控制协议和网际协议 D、OSI协议集 220、早期的计算机是用来进行 A、科学计算 B、系统仿真 C、自动控制 D、动画设计 221、下面有关计算机的叙述中,正确的是 A、计算机的主机只包括CPU B、计算机程序必须装载到内存中才能执行 C、计算机必须具有硬盘才能工作 D、计算机键盘上字母键的排列方式是随机的 222、显示器显示图象的清晰程度,主要取决于显示器的 A、对比度 B、亮度 C、尺寸 D、分辨率 223、下列各项中,不属于多媒体硬件的是 A、光盘驱动器 B、视频卡 C、音频卡 D、加密卡 224、在Windows98中，剪贴板是程序和文件间用来传递信息的临时存储区，此存储区是 A、回收站的一部分 B、硬盘的一部分 C、内存的一部分 D、软盘的一部分 225、在Windows98默认环境中，要把窗口中的图标直接复制到桌面上，正确的操作是 A、先按住Ctrl键不放，然后用鼠标左键将窗口中的图标拖动到桌面的指定位置，再释放Ctrl键和鼠标 B、先按住Shift键不放，然后用鼠标左键将窗口中的图标拖动到桌面的指定位置，再释放Shift键和鼠标 C、先按住Ctrl键不放，然后用鼠标右键将窗口中的图标拖动到桌面的指定位置，再释放Ctrl键和鼠标 D、先按住Shift键不放，然后用鼠标右键将窗口中的图标拖动到桌面的指定位置，再释放Shift键和鼠标 226、Windows98中，如果选中名字前带有“√”记号的菜单选项，则 A、弹出子菜单元 B、弹出对话框 C、“√”变为“×” D、名字前记号消失 227、Windows98中,文件名中不能包括的符号是 A、# B、> C、~ D、; 228、Windows98中“磁盘碎片整理程序”的主要作用是 A、修复损坏的磁盘 B、缩小磁盘空间 C、提高文件访问速度 D、扩大磁盘空间 229、Windows98中，下列关于“任务”的说法，错误的是 A、只有一个前台任务 B、可以有多个后台任务 C、如果不将后台任务变为前台任务，则它不可能完成 D、可以将前台任务变成后台任务 230、Windows98中，回收站实际上是 A、内存区域 B、硬盘上的文件夹 C、文档 D、文件的快捷方式 231、Word97中，若要计算表格中某列数值的总和，可使用的统计函数是 A、Sum()B、Total()C、Count()D、Average() 232、在Word97的文档中，选定文档某行内容后，使用鼠标拖动方法将其移动时，配合的键盘操作是 A、按住Esc键 B、按住Ctrl键 C、按住Alt键 D、不做操作 233、在Word97的编辑状态中，如果要输入罗马数字“Ⅸ”，那么需要使用的菜单是 A、编辑 B、插入 C、格式 D、工具 234、在Word97的文档中插入声音文件，应选择插入“菜单”中的菜单项是 A、对象 B、图片 C、图文框 D、文本框 235、在Word97的编辑状态下，原对齐方式是左对齐，如果连续两次单击工具栏中的“”按钮得到的对齐方式是 A、两端对齐 B、居中 C、右对齐 D、分散对齐 236、在Word97的表格操作中，当前插入点在表格中某行的最后一个单元格内，按回车键后，则 A、插入点所在的行加高 B、插入点所在的列加宽 C、在插入点下一行增加一空表格行 D、对表格不起作用 二、填空题 1、可以将各种数据转换成为计算机能处理的形式并输送到计算机中去的设备统称为()。 2、一个非零的无符号二进制整数，若在其右边末尾加上两个“0”形成一个新的无符号二进制整数，则新的数是原来数的()倍。 3、以国标码为基础的汉字机内码是两个字节的编码，每个字节的最高位为()。 4、磁盘驱动器属于()设备 5、在Windows98中，要弹出某文件夹的快捷菜单，可以将鼠标指向该文件夹，然后按()键 6、在Windows98中，“回收站”是()中的一块区域。 7、在Windows98中，要想将当前窗口的内容存入剪贴板中，可以按()键。 8、Word的“窗口”命令菜单被打开后，该菜单的下半部显示出已经打开的所有文档名，其中当前活动窗口所对应的文档名前有()符号 9、计算机网络是由负责信息处理并向全网提供可用资源的资源子网和负责信息传输的()子网组成。 10、为解决某一问题而设计的指令序列称为______。 11、在16*16点阵的汉字字库中，存储每个汉字的点阵信息所需的字节数是______ 12、微处理器(CPU)主时钟在每秒钟内发出的时钟脉冲数称为______。 13、在WINDOW98中，为了弹出“显示属性”对话框，应用鼠标右键单击桌面空白处，然后在弹出的快捷菜单中选择______项。 14、在WINDOW98的“资源管理器”窗口中，为了显示文件或文件夹的详细资料，应使用窗口中菜单栏的______菜单。 15、在WINDOW98中，通过“开始”菜单中的“程序”项进入MS-DOS方式，欲重新返回WINDOW95，可使用______命令。 16、在WORD的编辑状态，要取消WORD主窗口显示“常用工具栏”，应使用______菜单中的命令 17、提供网络通讯和网络资源共享功能的操作系统称为______。 18、将汇编语言源程序转换成等价的目标程序的过程称为()19、4个二进制位可表示()种状态。 20、微型计算机系统可靠性可以用平均()工作时间来衡量。 21、目前微型计算机中常用的鼠标器有光电式和()式两类。 22、在Windows 98的“资源管理器”窗口中,为了使具有系统和隐藏属性的文件或文件夹不显示出来,首先应进行的操作是选择()菜单中的“选项”。 23、在启动计算机系统时,当内存检查结束后,立即按()键,可以直接进入MS-DOS系统。 24、在Windows 98的“回收站”窗口中,要想恢复选定的文件或文件夹,可以使用“文件”菜单中的()命令。 25、在Word的编辑状态下,若要退出“全屏显示”视图方式,应当按的功能键是() 26、Internet(因特网)上最基本的通信协议是() 27、两位二进制可表示 [ ] 种状态。 28、在CPU中，用来暂存放数据，指令等各种信息的部件是 [ ] 29、CPU中，执行一条指令所需的时间称 [ ] 周期 30、在中文Windows98中，为了添加某个中文输入法，应选择 [ ] 窗口中的“输入法”选项。 31、在Windows 98系统中，为了在系统启动成功后自动执行某个程序，应将该程序文件添加到 [ ] 文件夹中 32、若使用Windows98“写字板”创建一个文档，当用户没有指定该文档的存放位置，则系统将该文档默认存放在 [ ] 文件夹中。 33、在Word中，可以显示水平标尺的两种视图模式是 [ ] 34、在传输数字信号时，为了便于传输、减少干扰和易于放大，在发送端需要将发送的数字信号变换成为模拟信号，这种变换过程称为[ ] 35、用屏幕水平方向上显示的点数乘垂直方向上显示的点数来表示显示器清晰度的指标，通常称为【 】。 36、计算机执行一条指令需要的时间称为【 】。 37、把一个十进制数26转换成二进制数是【 】。 38、将用高级语言编写的源程序转换成等价的目标程序的过程，称为【 】。 39、在Windows 98中，为了清除“开始”菜单下“文档”菜单中的内容，应打开【 】对话框。 40、在Windows 98中，当用鼠标左键在不同驱动器之间拖动对象时，系统默认的操作是【 】。 41、在Windows 98中，对用户新建的文档，系统默认的属性为【 】。 42、在Word的编辑状态，可以设定表格宽度的命令在【 】菜单内。 43、在计算机网络中，通信双方必须共同遵守的规则或约定，称为【 】。 44、典型的电子邮件地址一般由【 】@主机域名组成。 45、一个二进制整数从右向左数第10位上的1相当于2的【 】 次方。 46、用WINDOWS 98的“记事本”所创建文件的缺省扩展名是【 】。 47、如果WINDOWS 98的文件夹设置了【 】属性，则可以备份，否则不能备份 48、在WINDOWS 98默认环境中，进行整张软盘的复制，可通过鼠标右键单击要复制的源驱动器，在弹出的快捷菜单中单击【 】实现。 49、在Word 97的表格中，保存有不同部门的人员数据，现需要把全体人员按部门分类集中，在“表格”菜单中，对部门名称使用【 】命令可以实现。 50、微型计算机的内存是由RAM(随机存取存储器)和【 】组成的 51、将汇编语言程序翻译成与之等价的机器语言程序的程序是【 】 52、典型的微型计算机系统总线是由数据总线，【 】和控制总线三部分组成的。 53、计算机中用来表示存储空间大小的最基本容量单位是【 】 54、Windows98中，选定多个不相邻文件的操作是：单击第一个文件，然后按住【 】键的同时，单击其它待选定的文件 55、在Windows98默认环境中，要改变“屏幕保护程序”的设置，应首先双击【 】窗口中的“显示器”图标。 56、在Windows98中，若要删除选定的文件，可直接按【 】键。 57、在Word97中，要在页面上插入页眉、页脚，应使用【 】菜单下的“页眉和页脚”命令 58、为了实现网络互联，需要相就的网络连接器，主要由中继器、网桥、【 】和网关组成。答案 选择： 1、C 2、B 3、D 4、A 5、C 6、A 7、D 8、B 9、D 10、B 11、A 12、B 13、D 14、B 15、C 16、C 17、D 18、B 19、C 20、D 21、C 22、C 23、A 24、C 25、D 26、D 27、C 28、B 29、C 30、B 31、B 32、C 33、A 34、D 35、B 36、B 37、B 38、A 39、B 40、D 41、C 42、D 43、A 44、B 45、B 46、D 47、B 48、D 49、A 50、B 51、C 52、A 53、B 54、B 55、A 56、C 57、B 58、C 59、C 60、D 61、B 62、C 63、A 64、A 65、C 66、B 67、A 68、B 69、B 70、A 71、A 72、D 73、C 74、A 75、B 76、D 77、D 78、D 79、D 80、B 81、B 82、C 83、A 84、A 85、C 86、A 87、A 88、C 89、A 90、C 91、C 92、A 93、C 94、D 95、A 96、B 97、D 98、A 99、C 100、C 101、B 102、B 103、C 104、A 105、C 106、D 107、C 108、D 109、C 110、D 111、A 112、B 113、C 114、B 115、D 116、C 117、B 118、D 119、C 120、A 121、A 122、D 123、C 124、C 125、A 126、A 127、A 128、D 129、B 130、C 131、D 132、D 133、B 134、A 135、B 136、B 137、C 138、D 139、A 140、D 141、C 142、B 143、C 144、B 145、C 146、D 147、A 148、C 149、B 150、C 151、D 152、B 153、C 154、C 155、A 156、D 157、B 158、C 159、B 160、B 161、C 162、D 163、A 164、A 165、D 166、C 167、C 168、C 169、B 170、B 171、D 172、D 173、A 174、A 175、D 176、C 177、B 178、D 179、D 180、A 181、C 182、B 183、C 184、C 185、C 186、A 187、A 188、A 189、D 190、D 191、A 192、B 193、C 194、B 195、C 196、C 197、B 198、D 199、B 200、A 201、C 202、B 203、C 204、D 205、A 206、C 207、B 208、C 209、D 210、A 211、C 212、B 213、A 214、C 215、D 216、B 217、A 218、C 219、C 220、A 221、B 222、D 223、D224、C 225、A 226、D 227、B 228、C 229、C 230、B 231、A 232、D 233、B 234、A 235、A 236、A 填空： 1、输入设备 2、4 3、1 4、输入/输出 5、右 6、硬盘 7、Alt+Print Screen 8、√ 9、通信 10、程序 11、32 12、主频 13、属性 14、查看 15、exit 16、视图 17、网络操作系统 18、汇编过程 19、16 20、无故障 21、机械 22、查看 23、F8 24、还原 25、Esc 26、TCP/IP 27、4 28、寄存器 29、指令 30、控制面板 31、启动 32、我的文档 33、普通和页面视图 34、调制 35、分辨率 36、指令周期 37、11010 38、编译 39、任务栏属性 40、复制 41、存档 42、表格 43、协议 44、用户名 45、9 46、.TXT 47、存档 48、复制磁盘 49、排序 50、ROM 51、汇编程序 52、地址 53、字节 54、Ctrl 55、控制面板 56、Delete(Del) 57、视图 58、路由器 2018软考程序员最新教材变化解读教材对比 2018年软考程序员最新改版教程已经上市，与旧版相比有哪些变动呢？会不会影响18年的备考？改动大不大就以上问题，掌握行业内第一手资讯的希赛网将一一为您解答。 程序员教材第五版调整了以下部分章节内容 计算机系统基础知识：加入了多媒体基础知识。 多媒体基础知识：取消本章，内容移到第一章，且有删减。 网络基础知识：改为网络与信息安全基础知识，加入信息安全知识，其余内容一致，稍作结构上的调整。 软件工程基础知识：加入软件项目管理，包括管理范围，成本估算、风险分析和进度管理。 数据结构与算法：加入树和森林及最优二叉树，哈希查找讲解更加细致，各项内容讲解更完善，删除索引查找。 标准化与知识产权基础知识：标准化内容有删减，突出各项具体标准。 安全性基础知识：取消本章，内容移到第7章，且有删减。 软考教材最新变化解读：http://www.xiexiebang.com/rk/zt/jiaocaibianhua/# C/C++程序设计：新增章节C程序设计，突出C的主要内容。C++程序设计章节内容调整，具体内容无太大变化。 JAVA程序设计：内容稍作调整，具体内容无太大变化。 以上为2018年软考程序教材改版内容，各位有计划备考的考生应及时阅读学习新教材备考，也可以关注希赛网，我们将更新行业内最新资讯动态。 软考教材最新变化解读：http://www.xiexiebang.com/rk/zt/jiaocaibianhua/# 软考程序员资讯 http:// 软考程序员考试练习题及答案 （三）下面是希赛小编为大家整理的软考程序员考试练习题及答案,希望能帮助学友们，祝所有考生们复习顺利，安然通过考试。 练习题 21.如果你被要求写一段代码读取一个图片文档，那么一般使用哪种Stream(A)。 A、FileInputStream B、FileReader C、DataInputStream D、ObjectInputStream 22.下面关于缺省构造方法的描述中正确的是（D）。A、缺省构造方法可以初始化其它方法中定义的变量 B、java编译器会为所有的类创建缺省构造方法 C、如果在一个类中定义的构造方法都声明了参数，java编译器将为这个类创建一个缺省构造方法 D、当类中没有定义任何构造方法时，java编译器将为这个类创建缺省构造方法 23.消息类型web服务适合下面哪些情况（BD）。A、调用web服务的客户机要求立即响应 B、web服务功能在异步环境中 软考程序员资讯 http:// C、web服务是面向过程的 D、web服务是数据驱动的 24.给出下面的不完整的方法 {success=connect();If(success==-1){ Throw new TimedOutException();} } TimedOutException不是一个RuntimeException。下面的哪些声明可以被加入第一行完成此方法的声明（BC）。 A、public void method()B、public void method()throws Exception C、public void method()throws TimedOutException D、public void method()throw TimedOutException 25.以下说法错误的是（ABD）。 Ａ、类及其属性、方法可以同时有一个以上的修饰符来修饰 Ｂ、一个java类可以由多个父类 Ｃ、一个java类可以有多个子类 Ｄ、如果p是父类parent的对象，而c是子类child的对象，则语句c=p是正确的 软考程序员资讯 http:// 26.一个正在执行的线程在遇到下列情况会暂时停止执行（ABD）。A、休眠 B、执行suspend被挂起 C、执行输入输出操作 D、执行wait()方法 27.下列关于线程的说法正确的是（AB）.A、java支持多线程机制。 B、一个线程创建并启动后，它将执行自己的run()方法，如果通过派生Thread类实行多线程，则需要在子类中重新定义run()方法。把需要执行的代码写入run()方法中。如果实行Runnable接口实现多线程，则要编写接口中的抽象方法run()方法的方法体 C、要在程序中实现多线程，必须倒入Thread类import java.lang.Thread.D、一个程序中的主类不是Thread的子类，该类也没有实现Runnable接口，则这个主类运行不能控制主线程的休眠。 28.对于java.util.TreeSet类，下面哪些描述是正确的（AC）。A、这个集合中的元素是有序的 Ｂ、这个集合是保证不可变的 Ｃ、集合中的元素保证是唯一的 Ｄ、集合中元素使用唯一的key访问 软考程序员资讯 http:// Ｅ、集合中的元素保证是同步的 29.关于版本控制以下描述不正确的是（D）。A、自动跟踪每个文件和目录的变更情况 B、支持并行开发 C、ClearCase提供版本管理功能 D、能够提高软件可移植性 30.ClearCase用户通过（C）的方式获取VOB中存储的数据。A、资源管理器 B、视图（VIEW） C、版本树（Version tree） 如需了解更多习题资讯请到希赛网进行查看。 软考程序员资讯 http:// 软考程序员考试练习题及答案 （六）下面是希赛小编为大家整理的软考程序员考试练习题及答案,希望能帮助学友们，祝所有考生们复习顺利，安然通过考试。 练习题 51.下面哪一个是有效的命令？（E） A、SELECT*FROM books FOR UPDATE USING book_profit_idx WHERE(retail-cost)>10； B、CREATE INDEX book_profit_idx ON(retail-cost)WHERE(retail-cost)>10 C、CREATE FUNCTION INDEX book_profit_idx ON books WHERE(retail-cost)>10； D、a和c E、以上命令都不是 52.下面哪一项表示一个表中的一行？（D）A、一个属性 B、一个特征 C、一个字段 D、一个记录 53.下面哪一项“不是”有效的SELECT语句？（D） 软考程序员资讯 http:// A、SELECT Cost-Retail FROM books;B、SELECT Retail+Cost FROM books;C、SELECT retail*retail*retail FROM books;D、SELECT retail^3 from books;^操作不支持 54.使用UPDATE命令最多可以修改多少个记录？（D）A、1 B、2 C、3 D、无限制 55.当一个用户修改了表的数据，那么（D）A、第二个用户立即能够看到数据的变化 B、第二个用户必须执行ROLLBACK命令后才能看到数据的变化 C、第二个用户必须执行COMMIT命令后才能看到数据的变化 D、第二个用户因为会话不同，暂时不能看到数据的变化 56.表的主键特点中，说法错误的是：（B）A、一个表只能定义一个主键 B、主键可以定义在表级或列级 C、主键的每一列都必须非空 D、主键的每一列都必须惟一 软考程序员资讯 http:// 57.删除emp表的全部数据，但不提交，以下正确的语句是：（B）A、DELETE*FROM.EMP B、DELETE FROM EMP C、TRUNCATE TABLE EMP D、DELETE TABLE EMP 58.下面哪一个运算符与在一个多行子查询中使用IN运算符是等价的？（A）A、=ANY B、=ALL C、>ANY D、ANY 59.关于索引，说法错误的是：（A）A、索引总是可以提高检索的效率 B、索引由系统自动管理和使用 C、创建表的主键会自创建索引 D、删除索引对拥有索引的表的数据没有影响 60.下面哪一个SQL语句将删除DEPT表中的所有数据，并永久删除DEPT表的整个结构？（A） A、DROP TABLE dept;B、DELETE TABLE dept; 软考程序员资讯 http:// C、TRUNCATE TABLE dept;D、)DELETE*.*FROM dept;[END CODE] 如需了解更多习题资讯请到希赛网进行查看。第二篇：2012年软考程序员考试历年真题重点题总结及答案
第三篇：2018软考程序员最新教材变化解读教材对比
第四篇：软考程序员考试练习题及答案(三)
第五篇：软考程序员考试练习题及答案(六)
点击咨询 