全国计算机等级考试二级公共基础知识总结

1、全国计算机等级考试二级公共基础知识总结 第一章数据结构与算法 1.1 算法1算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。，2确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；3算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。4归纳法：通过观察一些简单而特殊的情况，最后总结出一般性的结论的算法的设计方法。5算法时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。6算法时间复杂度取决于问题的规模和待处理的数据的初态。7如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调

2、用8工程上常用的分治法是减半递推技术9算法空间复杂度是指执行这个算法所需要的内存空间。10如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。也就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。如果已知需要查找的x有一半机会在数组中，此时q=1/2。则A(n)=(n+1)/4+n/2=3n/4。x不在数组中时，A(n)=n。. 11下面程序段的时间复杂度是 for(int i=0;i<n;i+)for(int j=1;j<=m;j+)Aij=0;语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频

3、度之和构成了该算法的运行时间。本例中语句:Aij=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n).12算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。13一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。14算法复杂度：算法时间复杂度和算法空间复杂度。1.2 数据结构的基本基本概念1数据结构研究的三个方面：数据的逻辑结构；数据的存储结构（物理结构）；数据运算。2逻辑结构是数据元素间关系的描述，与所用的计算机无关3数据的逻辑关系是指数据元素的关联。4数据的不可分割的基本单位是数据项。5数据结构是指相互有关联的

4、数据元素的集合。6一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、7。索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。8数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，与所使用的计算机密切相关9根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据结构分为两大类型：线性结构与非线性结构。10在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点或结点11插入和删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。12在数据结构中，

5、用一组地址连续的存储单元依次存储数据元素的方式是线性结构。13一个数据结构除了用二元关系表示外，还可以直观地用图形表示13 线性表及其顺序存储结构1数据元素的位置只取决于自己的序号，2线性表是由n个数据元素组成的一个有限序列。删除一个元素，平均移动的元素的个数为(n-1+n-2+.+0)/n=(n-1)/2；插入一个元素，平均移动元素个数为(n+n-1+n-2+.+1)/n=(n+1)/2，所以总体移动元素个数为n/2。3线性表是一种线性结构，数据元素之间的相对位置是线性的。4线性表可以是空表。5非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后

6、件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。6线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。7ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。例：一个矢量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是108数据元素的存储位置均取决于第一个数据元素的存储位置，即：。 ADR(ai)=ADR(a1)+(i-1

7、)k 第5个元素的地址：ADR(a5)=100+(5-1)X2=1088在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有：线性表的插入、线性表的删除、线性表的查找、线性表的排序、线性表的分解、线性表的合并、线性表的复制、线性表的逆转等9线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。10采用顺序存储的线性表，顺序存储结构必须占用一片连续的存储单元，当对其进行插入和删除操作时需要移动大量的元素，优点是存储密度大，由于数组的存储方式是采用顺序存储的，即占用连续的存储空间，所以可以用数组的下标直接存取。11查找第i-1个结点和第i

8、个结点，在顺序表中查找的时间复杂度为O(1) 速度最快。由于链表结构在空间存储上的不连续性，在查找某个结点时，需要从当前结点开始向前或者向后逐个比较查找，浪费时间，查找结果的时间复杂度均为O(n)，12链接存储不是占用一片连续的存储空间，所以便于进行插入和删除操作。13线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点，此类存储方式属于顺序存储。14 栈和队列1栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。2栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈

9、具有记忆作用。用top表示栈顶位置，用bottom表示栈底。3当一个栈ST （最多元素为MaxSize）时，ST->top= -1是判断顺序栈为空的条件。ST->top=MaxSize-1是判断顺序栈为满的条件。4栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。5通常元素出栈的顺序是先取出栈顶元素再移动栈顶指针，使之指向新的栈顶元素。6从一个循环队列中删除一个元素，通常是先取出

10、元素再移动栈顶指针7队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。8在一个容量为25的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有3个元素9队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。10队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满11当循环队列为空（S=0）时，不能进行退队运算，这种情况称为下溢12栈的基本操作。一个栈的入栈序列是1,2,3,.,n,其输出序列为P1

11、，P2，P3，。，Pn，若P1=n，则Pi为n-i+1当p1=n，即n是最先出栈的，根据栈的运算原理，n必定是最后入栈的，那么输入顺序必定是1,2,3,.,n,则出栈的序列是n,n-1,n-2,.,113设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列B序列是不可能通过栈产生的由于栈的压入和退出只能在栈顶进行，所以要使出栈的第一个数是序列的最后一个数5，只能先把序列所有元素都压入栈，但这时出栈序列只能是（A 5，4，3，2，1），所以（B 5，3，4，1，2）选项的出栈序列是错误的，应选（B）。当初始序列压入一个时，就退出一个元素，这样就得到（A）选项的出栈序列1，2，3，4，

12、5；先压入1，2，3，4四个元素，再退出所有元素，最后压入5，并退栈这时得到（C）选项的出栈序列4，3，2，1，5；压入1，2后对后面的元素3，4，5分别压入一个退出一个，这时便得到（D）选项的出栈序列3，4，5，2，1。15 线性链表1数据结构分为逻辑结构与存储结构，线性链表属于存储结构。2数据结构中的每一个结点对应于一个存储单元，这种存储单元（一个一个小块）称为存储结点，简称结点。3结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。 4在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻

13、辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。因此，链式存储结构是散列存储5带头结点的双向循环链表L为空的条件是：只有该头结点，即L->next=L 或者 L->prior=L6对于链式队列结构，插入元素是在队尾进行的，只需修改队尾指针，不需修改队头指针。向链式队列中插入一个结点就是在单链表表尾插入一个结点，同时新插入的结点成为表尾结点。例：在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是r->next=s;r=s;7向链式栈中插入一个结点，就是在单链表的表头插入一个结点，同时将新结点的位置赋予栈顶指针。例：向一个栈顶指针为HS的链式

14、栈中插入一个s所指的结点时，则执行s->next=HS;HS=s;8线性链表的基本操作：插入、删除、查找、排序。9双向链表每个结点有两个指针域，这两个指针分别指向它的前驱结点和后继结点。10单链表中，每个结点都含有一个指针域，这个指针指向它的下一个结点。因此访问单链表中的结点时，必须沿着它的指针逐个进行。11由于双向链表比单链表结构复杂，所以在插入和删除元素时，要修改更多的指针域，相对比较复杂，单向链表和双向链表在空间存储上的不连续性决定了两者都不可以随机访问，在双向链表中由于每个结点包括两个指针域，其中一个指向该结点的前驱结点，另一个指向该结点的后继结点，因此它既可以直接访问前驱结点，

15、又可以直接访问后继结点，而单链表每个结点只有一个指针域，指向它的后继结点，所以它只能直接访问它的下一个结点，而无法直接访问它的前一个结点。所以双向链表顺序访问相邻结点更加灵活。12链表的特点：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。链表结构是一些逻辑上相邻，而空间上并不一定相邻的数据元素的集合，相邻的结点之间通过指针相互联系，在插入和删除元素时，只需修改结点指针即可，不需要移动数据元素。当存储空间不足时，可以动态为其分配内存空间，所以不必事先估计存储空间的大小。所需空间与其长度成正比。13用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。

16、当往空链表插入元素时，只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。当链表只有一个元素时，删除操作只要修改指针指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。带头结点的链表并不能加快对链表的遍历，带头结点的链表反而要增加一个用于存储头结点的空间，并不能节省存储空间，用带头结点的链表跟存取元素的速度无关。14忽略了最后结点或头结点的指针，在n个结点的单向链表（无表头结点）中，每个结点都有一个指针单元（即指针域），加上头指针，至少需要n+1个指针单元。 16 树与二叉树1树是一种

17、简单的非线性结构，所有元素之间具有明显的层次特性。栈和队列都是线性结构。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。2树的结点不能为空，结点最少的树为只有一个结点的树；二叉树的结点数可以为0，结点最少的二叉树为空的二叉树。3设树T的度为4，其中度为

18、1，2，3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数为8（根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和为1。因此树的结点数为1*4+2*2+3*1+4*1+1=16。叶子结点数目等于树结点总数减去度不为0的结点数之和，即16-(4+2+1+1)=8。）4设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深和最小树深分别是99和6（要使二叉树在规定结点下有最大树深，这时二叉树退化成一个线性链表，如果对应二叉树的根结点的层次为0，那么对应二叉树的树深为结点个数减1，即99；要使二叉树有最小树深，则此二叉树为满二叉树，当满二叉树的根结点的层次为1时

19、，结点个数n和树深h之间的关系为：n=2h-1，所以当二叉树的根结点层次为0时，对应关系为n=2(h+1)-1。）二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2的m次方-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；例：深度为5的二叉树至多有2*2*2*2*2-1=31个结点。具有3个结点的二叉树有5种，8例：设深度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少2h-1为结点最少的情况，除根结点层只有1个结点外，其余h-1层均有两个结点，结点总数=2(h-1)+1=2h-1。（4）具有n个结

20、点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；（5）具有n个结点的完全二叉树的深度为log2n+1；（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论：若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。9对于深度等于其结点数的二叉树，每层只有一个结点，假设从上向下

21、分别为a1,a2,.,an,则先序遍历序列为a1,a2,.,an。后序遍历序列为an,an-1,.a1。遍历序列正好相反。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。10由满二叉树的树深和结点的关系知，对于深度为h的满二叉树，m个树叶,n个结点,则n=2h-1即 n=20+21+22+.+2(h-1)=2h-1。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。11例：设一棵叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为1312例：假定根结点的层次是0，含有1

22、5个结点的二叉树的最小树深是3（要使二叉树在规定结点数下的深度最小，这样的二叉树只能是完全二叉树。当根结点的层次为1时，二叉树的结点n和深度h之间的关系是n=2h-1，所以当二叉树的根结点的层次为0时，结点和树深的关系是n=2(h+1)-1，所以h=3，n=15）13在在深度为5的完全二叉树中，度为2的结点数最多为1514树的度是指树内各结点的度的最大值,一棵树中除根结点之外,每个结点都有一个前驱结点,结点拥有子树的个数称为结点的度,所以结点的度数之和即为除根结点外所有结点的个数,即每个结点的度数之和等于结点总数减1,结点的度即是拥有子树的个数,而结点与子树之间是以边连接的,所以一棵树中每个结

23、点的度数之和与边的条数相等,15由二叉树的性质知二叉树叶子的个数n(0)和度为2的结点个数n(2)的关系为n(0)=n(2)+1。二叉树的结点个数可以等于0，二叉树中有些不是叶子的结点只有一个子女，二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。16二叉树的遍历：前序遍历DLR先根结点，后遍历左子树，最后遍历右子树；abdgcefh EFHIGJK EDBAC DBEAFC中序遍历LDR先左子树，后访问根结点，最后遍历右子树；dgbaechf HFIEJKG DEBAC ABDECF后序遍历LRD先左子树，后遍历右子树，最后访问根结点 gdbehfca 右子树为

24、G DACBE DEBFCA17在先序、中序、后序遍历序列中叶子结点总是从左向右的。相对次序是不发生改变的。是完全相同的。（任意两种方法遍历同一棵二叉树，可以确保唯一一棵二叉树，无论是用前序遍历、中序遍历、后序遍历二叉树，其区别都在于访问根的先后次序不同，而叶子结点的顺序是一样的。）18例：对树的三大部分：树根、左子树、右子树，存在树根结点大于左子树各个结点，小于右子树各个结点，因此要得到各个结点值的递增序列，应按“左子树-根结点-右子树”的顺序进行访问，这就是中序遍历的遍历过程。 19例：设n，m为一棵二叉树上的两个结点，在中序遍历中，n在m后的条件是n在m的右子树上，如果n在m的右子树上，

25、根据中序遍历算法，先访问根结点m，然后再访问右子树上的结点，所以n必然要在m后。如果n是m的祖先，则m可能在n的左子树上，也可能在n的右子树上，如果m在n的左子树上，根据中序遍历算法，先访问n的左子树，然后访问n结点，所以n必然要在m后，对如果n是m的子孙，则n可能在m的左子树上，也可能在m的右子树上。中序遍历时，先访问左子树，再访问根结点。n在m前，则n必须在m的左子树中。 20在中序遍历序列中，根结点将左右子树分开，左边为左子树中的所有结点，右边为右子树中的所有结点。21现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这样的遍历结果22在一棵二叉树中，度为0的结点个数为

26、m，度为2的结点个数为n，则二者之间的关系是m=n+123设一棵完全二叉树共有700个结点，则在该二叉树中有350个叶子结点17 查找技术顺序查找的使用情况：（1）线性表为无序表；（2）表采用链式存储结构。1顺序查找法适合于线性表，不论采用顺序存储还是链式存储。散列存储于顺序查找无关，同样压缩存储、索引存储也与顺序查找无关2二分法查找也称折半查找，只适用于顺序存储结构的且数据元素按关键字有序的有序表，对于长度为n的有序线性表进行二分查找，最坏情况只需比较log2n次。3例：有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找为82的结点时，4次比校

27、后查找成功。（此有序表的长度为13，按比较次数log2n计算应该是4。或先找中间结点45，再找77，95，最后找到82，经过4次比较，）4例：对有18个元素的有序表用二分法查找，则查找A3的比较序列的下标为9、4、2、3第一次(1+18)/2=9,第二次(1+8)/2=4,第三次(1+3)/2=2,第四次(3+3)/2=3。5例：设有一个已按元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是s>b 。 (对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不

28、成功的关键字比较次数为log2n+1即最大比较次数。当n>=2时，显然n+1>log2n+1。)6例：在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需的关键码比较次数为4（二分查找是用要查找的关键码与线性表的中间元素比较，根据比较结果是结束查找，还是在左边或者右边子表按相同的方法继续查找。与11比较的关键码分别为15、8、10、12。比较的次数为4。）7例：在顺序表（8，12，16，20，26，27，31，34，43，49，51）中，用二分法查找关键值为21，需做的比较次数为4（首先与27比较，由于21比27小，根据二分法比较

29、的方法，所以接着与27左边的16比较，由于21比16大，所以与16右边的20比较，最后一次与26比较。所以总共比较了4次。）8例：对一个长度为10的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是3（分查找的值小于表中所有元素和大于表中所有元素两种情况进行分析），9例：在长度为n的线性表中查找一个表中不存在的元素，需要的比较次数为n10例：设线性表（a1，a2，。，a500）元素的值由小到大排列，对一个给定的k值用二分法查找线性表，在查找不成功的情况下至多需比较9次（二分法查找在查找不成功的情况下至多需要比较log2n+1=9(n=500)。）11例：已知有序表为（12，18，24，

30、35，47，50，62，83，90，115，134），当用二分法查找100时，需进行3次比较可确定成功（画出二叉树判定树，当查找100时，需要和50、90、110比较，由于110的左子树为空，查找结束，比较了3次。）12如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用分块查找方法13顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为(n+1)/2。18 排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1交换类排序法：（1）冒泡排序法，需要比较的次数（在最坏情况下的时间复杂度）为n(n-1)/2；（2）快速排序法。2插入类排序法：（1）简单插入排序法，

31、最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)次比较。3选择类排序法：（1）简单选择排序法, 最坏情况需要n(n-1)/2次比较；选择排序的思想为：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。第一个元素需要比较n-1次，第二个元素需要比较n-2次，依次类推，倒数第二个元素只须比较1次即可，所以总的比较次数为：(n-1)+(n-2)+.+2+1=n(n-1)/2。4（2）堆排序法，最坏情况需要O(nlog2n)次比较。堆排序的空间复杂度为O(1)；时间复杂度在最好情况为O(nlog2n)，平均情况为O

32、(nlog2n)，最坏情况为O(nlog2n)5在插入选择排序中，若初始数据基本正序， 则选用插入排序；若初始数据基本反序，则选用选择排序。因为插入排序在初始数据基本正序时时间复杂度为O(n)，而选择排序在初始数据基本反序时时间复杂度为O(n)6插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。7例：设关键码序列（16，9，4，25，15，2，13，18，17，5，8，24），要按关

33、键码值递增的次序排列，采用简单选择排序法，一趟扫描后的结果是2，9，4，25，15，16，13，18，17，5，8，24（简单选择排序法的思想是：以无序表的第一个元素作为比较标准，依次同后面的元素进行比较，如果有一个元素比第一个元素小则记录这个元素的下标，然后以新的最小元素继续往下比较，有更小的元素再记录该下标，再比较.，当对整个数组扫描一趟后就可以等到最小元素的下标，然后与无序表的第一个元素交换位置。本题很明显第一趟扫描结果最小元素是2，与第一个元素交换位置后得到2，9，4，25，15，16，13，18，17，5，8，24选项的结果。）8简单插入排序的过程是，每一趟将一个待排序的记录，按其关

34、键字的大小插入到已经排序的子文件中适当位置上，直到全部记录插入完成为止。当文件“局部有序”或文件长度较小的情况下，每趟的比较次数大为降低，也即n-1趟比较的时间复杂度由O(n2)降至O(n)。所以最佳内排序方法是它9在简单插入排序过程中，当待排序列中记录按关键字非递减有序排序时，所需进行关键字比较的次数最小，为n-1，即记录不需移动；反之，当待排序列中记录按关键字非递增有序排序时，总的比较次数达到最大值(n+2)(n-1)/2。由（A：94，32，40，90，80，46，21，69）、（B：21，32，46，40，80，69，90，94）、（C：32，40，21，46，69，94，90，80）

35、、（D：90，69，80，46，21，32，94，40）四个答案中知（B）选项已经基本有序，需要比较的次数最少。10例：在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次（当要插入60时，前6个元素已有序，即为：15，23，38，54，72，96，需从后向前比较到54为止，故要比较3次）11插入排序是将待排序的记录插入到前面已排好序的子文件中，即考虑已排好序的子文件。所以是在待排序的元素序列基本有序的前提下，效率最高的排序方法12在堆排序和快速排序中，当原始记录接近正序或反序时，则选用堆排序，若原始

36、记录无序，则使用快速排序。13快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。只有左子表排好序，右子表还没排好序；左子表的长度在排序过程中可能大于、等于或小于右子表的长度；14由于选择排序每趟从待排序的记录中选中关键字最小的记录，每个记录都要比较，不考虑已排好序的子文件，因此，关键字比较的次数与记录的初始排列次序无关。快速排序不考虑已排好序的子记录，15例：设有1000个无序的元素，希望用最快的

37、速度挑选出其中前10个最大的元素，由于堆排序每扫描一趟就排好一个记录，只挑选出其中的前10个最大的元素时，使用堆排序为好。16希尔排序的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。17简单选择排序每趟从n-i+1个记录中选取关键字最小的记录，其时间复杂度为O(n)。18例：已知序列，请给出采用插入排序法对该序列作升序排序时的第五趟结果是(10,32,65,70,83,100),7,9或10,32,65,70,83,100,7,919 在插入排序、希尔排序、

38、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是快速排序，需要内存容量最多的是基数排序 第二章程序设计基础21 程序设计设计方法和风格如何形成良好的程序设计风格1、源程序文档化； 2、数据说明的方法； 3、语句的结构； 4、输入和输出。1程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的2注释分序言性注释和功能性注释，语句结构清晰第一、效率第二（已成为当今主导的程序设计风格）。3编制程序在选择标识符的名字时应考虑选择含义明确的名字，以正确提示所代表的实体。4编制程序在书写功能性注解时应考虑为程序段作注解，以帮助读者理解程序。5程序设计中语句结构的要求：（1

39、）在一行内只写一条语句；（2）程序编写应优先考虑清晰性，程序编写要做到清晰第一、效率第二；（3）在保证程序正确的基础上再要求提高效率；（4）避免使用临时变量而使程序的可读性下降；避免不必要的转移；6程序的语句结构要从数据出发构造程序，利用信息隐蔽确保每一个模块的独立性。7序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描述内容可以包括：程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。不包括数据的状态8功能性注释的位置一般嵌在源程序体之中，主要描述其后的语句或者程序做什么。包括数据的状态，语句的功能，程序段的功能，不包括模

40、块的功能9源程序的文档化应考虑如下几点：（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。（2）程序注释：正确的注释能够帮助读者理解程序，注释一般分为序言性注释和功能性注释。（3）视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。不包括正确的文档格式10程序设计方法和技术的发展经过了结构化程序设计、面向对象的程序设计两个阶段 11程序文档化应注意以下几点：（1）符号名的命名。符号名的命名具有一定的实际含义，以便于对程序功能的理解；（2）程序注释。正确的注释可以帮助读者理解程序； 12输入和输出信息是用户直接关心的。输入、输出方式

41、和格式，应尽可能方便用户的使用， 在设计和编程时，对所有的输入数据都要检验数据的合法性13影响输入输出风格的因素包括通信环境，用户经验，输入/输出设备，不包括数据状态。22 结构化程序设计1结构化程序设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3.模块化；4.限制使用goto语句。2结构化程序的基本结构和特点：（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；顺序结构是顺序执行的结构，就是按照语句的自然顺序，一条一条地执行程序（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列； （3）重复结构：又称循环结构，可根

42、据给定条件，判断是否需要重复执行某一相同程序段。3在程序设计中，重复结构对应两类循环语句：（1）对先判断后执行循环体的称为当型循环结构；（2）对先执行循环体后判断的称为直到型循环语句。4结构化程序设计方法是程序设计的先进方法工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读（主要强调程序的易读性）、易理解、易维护。其中最关键的是提高程序清晰性。5结构化程序设计的主要特点是程序语句组成容易识别的模块，每块只有一个入口和一个出口。620世纪70年代提出了“结构化程序设计（structured programming）”的思想和方法。7结构化程序设计是一种面向过程的设计方法。8结构化程序设

43、计减少了程序出错的机会、提高了程序的可靠性、保证了程序的质量。9结构化程序设计具有方便理解和阅读、便于维护、便于修改等优点。没有移植性好10将现实生活中的实体抽象成类是面向对象程序设计方法考虑的问题。11结构化程序是由一些为数不多的基本结构模块组成，这些模块甚至可以由机器自动生成，从而极大地减轻了编程工作量23 面向对象的程序设计1对象是现实世界中一个实际存在的事物，它可以是有形的也可以是无形的，如狗，桌子，飞机是对象，而苹果的颜色不是对象。2属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。4类是指具有共同属性、共同方法的对象的集合（即一组具在相同的数据结构和相同的行为

44、特征的对象的集合）。包括属性和行为两部分。所以类是对象的抽象，对象是对应类的一个实例。5多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。6面向对象技术具有多态性、封装性和继承性。7在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送消息8继承是面向对象的方法的一个主要特征，但不是任何对象都必须有继承性。9在面向对象的程序设计中，各个对象之间相对独立，相互依赖性小。10继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。 是类之间共享忏悔和操作的机制。 3对象具有如下的基本特点：（1）标识唯一性。对象是可区分的，

45、并且由对象的内在本质来区分。（2）分类性。可以将具有相同属性和操作的对象抽象成类；（3）多态性。同一个操作可以是不同对象的行为。（4）封装性。只能看到对象的外部特征，无需知道数据的具体结构以及实现操作的算法。（5）模块独立性。面向对象是由数据及可以对这些数据施加的操作所组成的统一体。 第三章软件工程基础31 软件工程基本概念1计算机软件是包括程序、数据及相关文档的完整集合。2软件是一种逻辑实体（逻辑产品）；3软件按功能分为（文档）应用软件、系统软件、支撑软件（或工具软件）。4软件工程包括3个要素：方法、工具和过程。5软件工程过程包含4种基本活动：（1）P-软件规格说明；（2）D-软件开发；（3

46、）C-软件确认；（4）A-软件演进。6软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。7软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（问题定义）（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现（编码）；（5）软件测试；（6）运行和维护。8软件工程的目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。9软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。10软件开发环境是全面支持软件开发全过程的软件工具的集合11软

47、件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。12在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是需求分析13软件交付使用后，需要不断地进行维护，根据新提出的需求进行必要而且可能的扩充和删除。14需求分析主要工作包括4个方面：需求获取、需求分析、编写说明书、需求评审。15SRS是软件需求规格说明书的英文简称。32 结构化分析方法1数据字典是结构化分析方法的核心2在结构化分析方法中，用于描述系统中所用到的全部数据和文件的文档称为数据字典3结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主

48、要工具,建立系统的逻辑模型。4Jackson方法是一种面向数据流的结构化方法5结构化分析的常用工具（1）数据流图；（2）数据字典；（3）判定树；（4）判定表。6数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能建模。7数据流图由一些特定的图符构成，包括：加工（转换）、数据流、存储文件（数据源）、源和潭，不包括控制流。8程序流程图（PFD）中的箭头代表的是控制流。9常见的需求分析方法有：结构化分析方法和面向对象的分析方法（OOA）。结构化分析方法中，数据流图（DFD）是需求分析最常用的工具。在数据流图（DFD）中，带有名字的箭头表示数据的流向。10数据字典的作用

49、是对数据流图中出现的被命名的图形元素的确切解释。11判定表4部分组成：左上部是基本条件、左下部是基本动作、右上部是条件项、右下部是动作项。33 结构化设计方法1合性与内聚性是模块独立性的两个定性标准，其中内聚反映了模块内各万分之间的联系在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。依据降低耦合提高内聚的原则，通过把一些模块取消或合并来来修改程序结构2软件概要设计的基本任务是：（1）设计软件系统结构； （2）数据结构及数据库设计；（3）编写概要设计文档； （4）概要设计文档评审。模块用一个矩形表示，箭头表示模块间的调用关系。 在结构图中还可以用带注释的箭头表示模块调用过

50、程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据。3典型的数据流类型有两种：变换型和事务型。4变换型系统结构图由输入、中心变换、输出三部分组成。5在结构化设计方法中生成的结构图（SD）中，带有箭头的连线表示模块之间的调用关系6常见设计工具.N-S的重要特征是：每个构件具有明确的作用域；控制转移必须遵守结构化设计要求；易于确定局部数据和（或）全局数据的作用域；易于表达嵌套关系和模块的层次结构。7PAD有5种结构，通常把程序流程图的5种基本控制结构组合或嵌套，可以构成任何复杂的程序流程图。8常见设计工具：图形工具（程序流程图，N-S，PAD，HIPO），表格

51、工具（判定表），语言工具（PDL）。9程序流程图构成的控制结构的含义如下：（1）顺序型：几个连续的加工步骤依次排列构成；（2）选择型：由某个逻辑判断式的取值决定选择两个加工中的一个；（3）先判断重复型：先判断条件是否成立，成立则执行循环体语句；（4）后判断重复型：重复执行某些特定的加工，直到控制条件成立；（5）多分支选择型：列举多种加工情况，根据控制变量的取值，选择执行其中之一。10模块化是指把一个待开发的软件分解成若干小的简单的部分11问题分析图是继程序流程图和方框图之后，提出的又一种用于描述软件详细设计的图形表示工具34 软件测试1软件测试的目的：发现错误而执行程序的过程。（尽可能多地发现

52、软件系统中的错误和缺陷）2经验表明，程序中存在错误的概率与该程序中已发现的错误数成正比。3从功能角度划分，试软件测试方法：静态测试和动态测试。4静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行（人工检测）。5动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法（从功能角度划分）。6动态测试（动态分析）是基于计算机的测试，是为了发现错误而执行程序的过程。7白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本路径测试。8黑盒测试：用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。黑盒测试方法也称功能

53、测试或数据驱动测试，是对软件已经实现的功能是否满足需求进行测试和验证9软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。10单元测试的技术可以采用静态分析和动态测试。对动态测试通常以白盒动态测试为主，辅之以黑盒测试。11集成测试所设计的内容包括：软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试等12检查软件产品是否符合需求定义的过程称为确认测试13系统测试必须在目标环境下运行，14白盒测试主要考虑程序内部的逻辑结构，主要用于完成软件内部操作的验证。黑盒测试方法完全不考虑程序的内部结构和内部特征，只依据程序的需求和功能规格说明，检查程序的功能是否符

54、合它的功能说明。15集成测试时要进行软件单元的接口测试、全局数据结构测试、边界条件测试和非法输入的测试等16测试准则：（1）所有测试都应追溯到需求；（2）严格执行测试计划，排除测试的随意性；（3）充分注意测试中的群体现象；（4）程序员应避免检查自己的程序；（5）穷举测试不可能；（6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。17系统测试的目的是在真实的系统工作环境下，检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。包括：功能测试、性能测试、操作测试、配置测试、外部接口测试和安全测试等。18软件测试是保证软件质量的重要手段，包括需求定义阶段的需求测试、编码

55、阶段的单元测试、集成测试以及后期的确认测试和系统测试。19代码检查，包括代码审查、代码走查、桌面检查、静态分析等具体方式。35 程序的调试1程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。的关键是推断程序内部的错误位置及原因2程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。3软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；其过程可概括为设置断点、程序暂停、观察程序状态、继续运行程序。1）通过内存全部打印来排错

56、；2）在程序特定部位设置打印语句-即断点法；3）自动调试工具。（2）回溯法；（3）原因排除法。原因排除法是通过演绎和归纳，以及二分法来实现4修改错误原则：（1）在出现错误的地方，很可能有别的错误；（2）修改错误的一个常见失误是修改了这个错误的征兆或这个错误的表现，而没有修改错误本身；（3）注意修正一个错误的同时有可能会引入新的错误；（4）修改错误的过程将迫使人们暂时回到程序设计阶段；（5）修改源代码程序，不要改变目标代码。5为了修改程序中错误，往往采用“补丁程序”来实现，但这种做法会引起整体程序质量的下降。6确定错误位置占据了软件调试绝大部分的工作量。7测试的目的是暴露错误，评价程序的可靠性，而调试的目的是发现错误的位置并改正错误8经验表明，错误有群集现象，当在某一程序段发现错误时，在该程序段中还存在别的错误9程序调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位置；二是对程序进行修改，排除这个错误。目的是改正错误第四章 数据库设计基础41 数据库系统的基本概念1数据管理技术的发展过程中，