计算机等级二级公共基础知识

计算机等级二级公共基础知识第一页，共一百四十四页，编辑于2023年，星期五公共基础知识一、基本数据结构与算法。二、程序设计基础。三、软件工程基础。四、数据库设计基础。第二页，共一百四十四页，编辑于2023年，星期五第一部分数据结构与算法

5-7个题（10-14分）考试大纲:一.基本要求:1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法第三页，共一百四十四页，编辑于2023年，星期五二.考试内容:1.算法的基本概念;算法复杂度的概念和意义(时间复杂度和空间复杂度)2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念3.线性表的定义;线性表的顺序存储结构及其插入与删除运算4.栈和队列的定义;栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）第四页，共一百四十四页，编辑于2023年，星期五考点一、算法（P1）一.算法的基本概念▲所谓算法是指解题方案的准确而完善的描述。1.算法的基本特征①可行性：是否可行。②确定性：指算法中的每一个步骤必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。③有穷性：指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。④拥有足够的情报：收集的输入信息等。第五页，共一百四十四页，编辑于2023年，星期五2.算法的基本要素一个算法通常由两种要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作（指令）（P2）算术运算：加、减、乘、除逻辑运算：与、或、非关系运算：大于、小于、等于、不等于数据传输：赋值、输入、输出（2）算法的控制结构（P3）一个算法一般都可以用顺序、选择、循环三种基本控制结构组成。描述算法的工具有：传统流程图、N-S结构化流程图、算法描述语言。第六页，共一百四十四页，编辑于2023年，星期五传统流程图、N-S结构化流程图、算法描述语言。条件语句序列1语句序列2ENDIF后面的语句真假条件语句序列1ENDIF后面的语句a=0?yesno输入a,b,c

b^2-4acdelta

b<>0?

delta>0?YesNo方程有一个根方程无意义方程有二个实根方程有二个虚根输出方程的根noyes3.算法设计的基本方法①列举法②归纳法③递推法④递归法⑤减半递推技术第七页，共一百四十四页，编辑于2023年，星期五二.算法的复杂度▲（P5）算法的复杂度主要包括:时间复杂度和空间复杂度.1.算法的时间复杂度:指执行算法所需要的计算工作量.工作量可以用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数．即算法的工作量=f(n)其中n是问题的规模.

可以用平均性态和最坏情况复杂性两种方法.第八页，共一百四十四页，编辑于2023年，星期五2.算法的空间复杂度:指执行这个算法所需要的内存空间.包括算法程序所占的空间、输入的初始数据所占的存储空以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及基本种数据结构所需要的附加存储空间（例如，在链式结构中，除了存储数据本身外，还需要存储链接信息）。第九页，共一百四十四页，编辑于2023年，星期五考点二、数据结构的基本概念（P7）数据结构学科主要研究如下三个方面的内容:①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.③对各种数据结构进行的运算.数据结构学科的研究目的:提高数据处理的效率.主要包括:①数据处理速度.②尽量节省在数据处理过程中所占用的计算机存储空间.第十页，共一百四十四页，编辑于2023年，星期五一.数据结构的定义:指相互关联的数据元素的集合.1.数据处理:指对数据集合中的各元素以各种方式进行运算.(插入,删除,查找,更改等)2.数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素.3.数据结构:是指反映数据元素之间关系的数据元素集合的表示.

一个数据结构应包括两方面的信息:一是表示数据元素的信息,二是表示各数据元素之间的前后件关系.第十一页，共一百四十四页，编辑于2023年，星期五①数据的逻辑结构（P11）:指反映数据元素之间逻辑关系的数据结构.

它包含两个要素:一是数据元素的集合,通常记为D,二是D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R,形式表示为:B=(D,R)其中B表示数据结构为了反映D中各数据元素之间的前后件关系,一般用二元组来表示.例如,假设a与b是D中的两个数据,则二元组(a,b)表示a是b的前件,b是a的后件.这样,在D中的每两个元素之间的关系都可以用这种二元组来表示.第十二页，共一百四十四页，编辑于2023年，星期五例:一年四季的数据结构可以表示成:B=(D,R)D={春，夏，秋，冬}R={（春,夏）,（夏,秋）,（秋,冬）}②数据的存储结构（P12）:指数据的逻辑结构在计算机存储空间中的存放形式.也称为物理结构.

一般来说,一种数据的逻辑结构根据需要表示成多种存储结构,常用存储结构有顺序,链接,索引等.

各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,而且一般也不可能相同.

（P13）第十三页，共一百四十四页，编辑于2023年，星期五二.数据结构的图形表示一个数据结构除了用二元关系表示外,还可以直观的用图形表示.图形表示方法:对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,简称为结点;对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点,以表示数据元素之间的前后件关系.春夏秋冬女儿儿子父亲第十四页，共一百四十四页，编辑于2023年，星期五例:用图形表示数据结构B=(D,R),其中

D={di|1≤i≤6}={d1,d2,d3,d4,d5,d6}R={(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)}这个数据结构的图形表示为:d1d2d3d5d4d6第十五页，共一百四十四页，编辑于2023年，星期五三.线性结构和非线性结构（概念）（P14）数据结构一般分为线性结构和非线性结构两大类.一个非空的线性结构满足如下条件:①有且仅有一个根结点;②每一个结点最多有一个前件,也最多有一个后件;③在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.ACBABCABCD第十六页，共一百四十四页，编辑于2023年，星期五1.线性表的基本概念线性表定义:线性表是由n(n>=0)个数据元素a1,a2,…an组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件.即线性表或是一个空表,或是可以表示为:(a1,a2,…,an)

其中ai(i=1,2,…,n)是属于数据对象的元素,通常也称为线性表中的一个结点.非空线性表的基本特征:①有且只有一个根结点a1，它无前件；②有且只有一个终端结点an，它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。考点三、线性表及其顺序存储结构第十七页，共一百四十四页，编辑于2023年，星期五2.线性表的顺序存储结构（P16）具有两个基本特点：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件一定存储在后件元素的前面。第十八页，共一百四十四页，编辑于2023年，星期五线性表的随机存取地址的计算公式：ADR（ai）=ADR(a1)+(i-1)kk指每个元素所占的字节：：a1a2aian：：：：ADR(a1)占k个字节占k个字节占k个字节占k个字节：：：：：：：：ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)k线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转第十九页，共一百四十四页，编辑于2023年，星期五3.线性表的插入运算一个长度为n的线性表，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始向后移动一个位置，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1，变为n+1.其时间复杂度，在平均情况下，需要移动一半的元素，最坏情况下要移动所有元素。第二十页，共一百四十四页，编辑于2023年，星期五4731243536561829473124353656182947312435365618872912345678910123456789101234567891087线性表顺序存储结构的适用场合：对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单，对于元素需要变动的大线性表就不太合适了，因为插入和删除的效率比较低。第二十一页，共一百四十四页，编辑于2023年，星期五4.线性表的删除运算要删除第i（1≤i≤n）个元素时，首先要从第i+1个元素开始，直到最后一个（即n个）元素之间的n-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。变为n-1。删除操作的时间复杂度：在平均情况下，需要移动表中一半的元素，最坏情况下要移动表中的所有元素。第二十二页，共一百四十四页，编辑于2023年，星期五考点四、栈和队列(重点)（P19）1、栈及其基本运算(1)栈的定义:栈是限定在一端进行插入和删除操作的线性表.它按照”后进先出”(或”先进后出”)的原则组织数据.(2)栈的顺序存储:在程序设计语言中一般是用一维数据S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量.(3)栈的基本运算①入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置.当栈顶指针已经指向存储空间的最后一个位置时说明本栈空间已满,不可能再进行入栈操作.②退栈操作:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1.当栈顶指针为0时,说明栈空,不可能再进行退栈操作.③读栈顶元素:将栈顶元素赋给一个指定的变量,栈指针(top)不变.当栈顶指针为0时,说明栈空,读栈顶元素操作失败.第二十三页，共一百四十四页，编辑于2023年，星期五ABCDEF10987654321topbottomABCD10987654321topbottom入栈退栈第二十四页，共一百四十四页，编辑于2023年，星期五2、队列及其基本运算（P21）（1）队列的定义：队列是指允许在一端进行插入、而在另一端进行删除的线性表。它按照“先进先出”的原则组织数据。FEDCBA退队入队frontrear（2）循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。（3）循环队列的基本运算①入队运算：首先将队尾指针加1（real=real+1），并当real=m+1时，置real=1，然后将新元素插入到指针指向的位置。②退队运算：首先将排头指针加1（front=front+1），并当front=m+1时置front=1，然后将排头指针指向的元素赋给指定的变量。第二十五页，共一百四十四页，编辑于2023年，星期五ABCDEF87654321realfront具有6个元素的循环队列加入X和Y后的循环队列realABCDEF87654321frontXYBCDEF87654321frontXYreal退出一个元素后的循环队列栈和队列都是顺序存储的。第二十六页，共一百四十四页，编辑于2023年，星期五考点五、线性链表（P24）1、线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。双向链表的存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前件结点的存放地址。带链的栈，带链的队列HEADA0B…H0HEAD0……第二十七页，共一百四十四页，编辑于2023年，星期五2、线性链表的基本运算（P27）：插入、删除、合并、分解、逆转、复制、排序、查找。①线性链表的插入：先从栈中为新元素分配一个新的结点q，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针p。先将q指向p的后件，然后将q挂在p结点的后面。xpxpqxpq第二十八页，共一百四十四页，编辑于2023年，星期五②线性链表的删除：先找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接在p的后面。最后归还q结点所分配的栈空间。xpqxpq第二十九页，共一百四十四页，编辑于2023年，星期五3、循环链表（P30）：循环链表的几个特点：①在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。②循环链表中最后一个结点的指针域不是空，而是指向表头结点。③判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。④在循环链表中，从任何一个结点出发都可以访问到表中其它所有的结点。xYHEADz…第三十页，共一百四十四页，编辑于2023年，星期五考点六、树与二叉树(重点)（P31）1、树的基本概念树是一种非线性结构，在树的这种数据结构中，所有数据元素之间的关系具有明显的层次特性。①父结点：在树结构中，每一个结点只有一个前件结点，称为父结点。②根结点：没有前件的结点只有一个，称为树的根结点。③子结点：每一个结点可以有多个后件，它们都称为该结点的子结点。④叶子结点：没有后件的结点称为叶子结点。IKGFHEDCBAR第三十一页，共一百四十四页，编辑于2023年，星期五⑤结点的度：一个结点所拥的后件个数称为该结点的度。⑥树的度：在树中，所有结点中的最大的度称为树的度。⑦树的深度：树的最大层次称为树的深度，树的深度也可以称为树的高度，根结点在第1层。⑧子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。叶子结点没有子树。IKGFHEDCBAR第三十二页，共一百四十四页，编辑于2023年，星期五IKGFHECBR2、二叉树及其基本性质（P34）二叉树的两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：①在二叉树的第k层上，最多有2k-1(k>=1)个结点。②深度为m的二叉树最多有2m-1个结点。③在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。④具有n个结点的二叉树，其深度至少为[㏒2n]+1。第三十三页，共一百四十四页，编辑于2023年，星期五FGEHDCBAIJKMLPNFGEHDCBAIJK3、满二叉树和完全二叉树（P35）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。基本性质：①满二叉树的第k层上有2k-1(k>=1)个结点，且深度为m的二叉树有2m-1个结点。②具有n个结点的完全二叉树的深度为[㏒2n]+1。③设完全二叉树共有n个结点，如果从根结点开始，按层序（第一层从左到右）用自然数1、2、…、n给结点进行编号，则对于编号为k的结点有以下结论：若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(K/2)。第三十四页，共一百四十四页，编辑于2023年，星期五若2k<=n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（显然也没有右子结点）若2k+1<=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。FGEHDCBAIJK4、二叉树的存储结构（P36）L(i)：左指针域，指向该结点的左子结点（存放左子结点的存储地址）。R(i)：右指针域，指向该结点的右子结点（存放右子结点的存储地址）。V(i)：存放结点的值。L(i)V(i)R(i)第三十五页，共一百四十四页，编辑于2023年，星期五5、二叉树的遍历▲（P38）①前序遍历：先访问根结点，后前序遍历左子树，再前序遍历右子树。②中序遍历：先中序遍历左子树，后访问根结点，再中序遍历右子树。③后序遍历：先后序遍历左子树，后后序遍历右子树，再访问根结点。对下图进行前序遍历的结果是：ABDECF；中序遍历的结果是：DBEACF；后序遍历的结果是：DEBFCA。FEDCBA第三十六页，共一百四十四页，编辑于2023年，星期五考点七、查找技术（P39）1、顺序查找：适用于无序表或采用链式存储的表（不管有序还是无序）。查找方法：从表头到表尾逐个查找，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下要进行n次比较。2、二分查找：适用于顺序存储的有序表。▲每次把特查找值与表中间元素比较，以减半的方式缩小搜索范围。对于长度为n的线性表，在最坏情况下要进行㏒2n次比较。例题分析：请写出用二分查找法在有序顺序表（1、2、3、4、6、8、9、11）中查找3的比较序列：4、2、3123468911第三十七页，共一百四十四页，编辑于2023年，星期五考点八、排序技术(比较次数)（P40）交换类排序：冒泡排序法，快速排序法。插入类排序：简单插入排序法，希尔排序法。选择类排序：简单选择排序法，堆排序法。1、冒泡排序法：通过相邻元素的比较、交换，逐步将线性表变成有序。首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两个元素的大小，若前者大于后者则交换它们的位置。这样就将线性表中的最大者换到了表的最后。然后，从后往前扫描剩下的线性表，同样，在扫描过程中依次比较相邻的两个元素的大小，若后者小于前者则交换位置，这样就将线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止。以时已变为有序。假设线性表的长度为n，则在最坏情况下，需经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。第三十八页，共一百四十四页，编辑于2023年，星期五例题分析：请写出用冒泡排序法对序列（5，1，7，3，6，9，3，2，7，6）进行第一遍扫描后的中间结果是：

5173693276原序列：第1遍第三十九页，共一百四十四页，编辑于2023年，星期五2、快速排序：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处。如此再对两个子表进行分割，直到分割成的子表为空时。对线性表分割的步骤：首先，在表的第一个、中间一个、最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中第一个元素移到P(k)的位置上。然后，设置两个指针i和j分别指向表的起始与最后的位置，反复操作以下两步：①将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)<T，将P(j)移到P(i)的位置上。②将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)>T，将P(i)移到P(j)的位置上。第四十页，共一百四十四页，编辑于2023年，星期五例题分析：用快速排序法对序列（5，1，7，3，6，9，3，2，7，6）进行第一次排序后的中间结果是：

5173693276原序列：T：ij第四十一页，共一百四十四页，编辑于2023年，星期五3、简单插入排序：指将无序序列中的各元素依次插入到已经有序的线性表中。一般来说，假设线性表中前j-1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：首先将第j个元素放到一个变是T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。在最坏情况下需要比较n(n-1)/2次。例题分析：用简单插入排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。原序列：T：5136732769第四十二页，共一百四十四页，编辑于2023年，星期五4、希尔排序：将整个无序序列分割成若干个小的子序列分别进行插入排序（插入排序：开始线性表中只有第1个元素，然后从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插到前面已经有序的子表中）。子序列的分割方法：将相隔某个增量h（ht=n/2k(k=1,2,3,…,[㏒2n]，n为待排序的线性表的长度））的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时进行一次插入排序，排序完成。第四十三页，共一百四十四页，编辑于2023年，星期五例题分析：用希尔排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。5173693276原序列：Hk=n/2k(k=1、2、…)H1=10/21=55173693276H2=[10/22]=25173693276H3=[10/23]四十四页，共一百四十四页，编辑于2023年，星期五5、简单选择排序：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下需要比较n(n-1)/2次。例题分析：用简单选择排序法对序列（5，1，7，3，6，9，3，2，7，6）进行排序。5173693276原序列：第四十五页，共一百四十四页，编辑于2023年，星期五6、堆排序：堆的定义如下：具有n个元素的序列（h1、h2、…、hn），当且仅当满足

hi>=h2ihi<=h2ihi>=h2i+1hi<=h2i+1（i=1,2,…,n/2）时称之为堆。或堆可以用完全二叉树来直观的表示堆的结构。以大根椎为例，堆顶（完全二叉树的根结点）元素必为序列的n个元素中最大项。9185533612473024第四十六页，共一百四十四页，编辑于2023年，星期五47915385363012244791538536301224根据堆的定义，可以得到堆排序的方法：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左右子树仍为堆，可以将该子序列调整为堆，反复做第②步，直到剩下的子序列为空为止。在最坏情况下堆排序需要比较的次数为O(n㏒2n)。第四十七页，共一百四十四页，编辑于2023年，星期五查找技术的比较次数：对于长度为n的线性表，1.顺序查找：平均要进行n/2次比较，在最坏情况下要进行n次比较。2.二分查找：在最坏情况下要进行㏒2n次比较。各类排序的时间复杂度：对于长度为n的线性表，在最坏情况下，需要比较的次数：1.冒泡排序：n(n-1)/22.快速排序：n(n-1)/23.简单插入排序：n(n-1)/24.希尔排序：O(n1.5)5.简单选择排序：n(n-1)/26.堆排序：O(n㏒2n)。第四十八页，共一百四十四页，编辑于2023年，星期五例年考题分析【2008年9月】一、选择题1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是：

A、12345ABCDE。B、EDCBA54321。

C、ABCDE12345。D、54321EDCBA。2、下列叙述中正确的是：

A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D、循环队列中元素的个数是由队头指针和队尾指针共同决定3、在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是：

A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)BDC第四十九页，共一百四十四页，编辑于2023年，星期五第五十页，共一百四十四页，编辑于2023年，星期五【2008年9月】二、填空题1、对下列二叉树进行中序遍历的结果是______

DBXEACYFZABCDEFXYZ第五十一页，共一百四十四页，编辑于2023年，星期五【2008年4月】一、选择题1、算法的有穷性是指（）

A)算法程序的运行时间是有限的B)算法程序所处理的数据量是有限的C)算法程序的长度是有限的D)算法只能被有限的用户使用2、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是A)快速排序B)冒泡排序C)直线插入排序D)堆排序3、下列关于栈的叙述正确的是A)栈按“先进先出”组织数据B)栈按“先进后出”组织数据C)只能在栈底插入数据D)不能删除数据ADB第五十二页，共一百四十四页，编辑于2023年，星期五【2008年4月】二、填空题1、深度为5的满二叉树有__个叶子结点。2、设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有__个元素。1624方法一：满二叉树的第k层上有2k-1(k>=1)个结点方法二：特例法3………9frontrear第五十三页，共一百四十四页，编辑于2023年，星期五【2007年9月】一、选择题1、下列叙述中正确的是：（）

A、数据的逻辑结构与存储结构必定是一一对应的。B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构。C、程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构。D、上述三种说法都不对。2、冒泡排序在最坏情况下比较的次数为A)n(n+1)/2B)nlog2nC)n(n-1)/2D)n/23、一棵二叉树中共有70个叶子结点与80个度为1的结点：由该二叉树中的总结点数为A、219B、221C、229D、231CCA方法一：①在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法第五十四页，共一百四十四页，编辑于2023年，星期五二、填空题1、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的________存储结构。2、对下列二叉树进行中序遍历的结果为__________。顺序HPGFBCEADACBDFEHGP第五十五页，共一百四十四页，编辑于2023年，星期五【2007年4月】一、选择题1.下列叙述中正确的是：

A、算法的效率只与问题的规模有关,而与数据的存储结构无关。

B、算法的时间复杂度是指执行算法所需要的计算工作量。

C、数据的逻辑结构与存储结构是一一对应的。

D、算法的时间复杂度与闪间复杂度一定相关。2.下列对队列的叙述正确的是：

A、队列属于非线性表

B、队列按“先进后出”原则组织数据

C、队列在队尾删除数据

D、队列按“先进先出”原则组织数据BD第五十六页，共一百四十四页，编辑于2023年，星期五3.对下列二叉树进行前序遍历的结果为：

A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ4.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为：

A、n+1B、n-1C、2nD、n/2二、填空题1.在深度为7的满二叉树中,度为2的结点个数为()ZFXAYBCDECA方法一：①在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法方法一：①满二叉树的第k层上有2k-1(k>=1)个结点②在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。方法二：特例法63第五十七页，共一百四十四页，编辑于2023年，星期五【2006年9月】一.选择题1.下列叙述中正确的是：

A、一个算法的空间复杂度大，则其时间复杂度也必定大。

B、一个算法的空间复杂度大，则其时间复杂度必定小。

C、一个算法的时间复杂度大，则其空间处长杂度必定小。

D、上述三种说法都不对。2.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为：

A、63B、64C、6D、73.对右图二叉树进行中序遍历的结果是：

A、ACBDFEGB、ACBDEGEC、ABDCGEFD、FCADBEGFCEADGB二.填空题1.按“先进后出”原则组织数据的数据结构是（）。

2.数据结构分为线性结构和非线性结构，带链的队列属于（）。DBA栈线性结构一个非空的线性结构满足如下条件:①有且仅有一个根结点;②每一个结点最多有一个前件,也最多有一个后件;③在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.第五十八页，共一百四十四页，编辑于2023年，星期五【2006年4月】一.选择题1.按照“后进先出”原则组织数据的数据结构是：

A、队列B、栈C、双向链表D、二叉树2.下列叙述中正确的是：

A、线性链表是线性表的链式存储结构

B、栈与队列是非线性结构

C、双向链表是非线性结构

D、只有根结点的二叉树是线性结构3.对右图二叉树进行后序遍历的结果是：

A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA4.在深度为7的满二叉树中，叶子结点个数为：A、32B、31C、64D、63二.填空题1.对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（）。ABCDEFBAD方法一：满二叉树的第k层上有2k-1(k>=1)个结点方法二：特例法C假设线性表的长度为n，则在最坏情况下，需经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较的次数为n(n-1)/2。45第五十九页，共一百四十四页，编辑于2023年，星期五【2005年9月】一.选择题1.下列数据结构中，能用二分法进行查找的是：

A、顺序存储的有序线性表B、线性链表

C、二叉链表D、有序线性链表2.下列关于栈的描述中正确的是：

A、在栈中只能插入元素而不能删除元素

B、在栈中只能删除元素而不能插入元素

C、栈是特殊的线性表，只能在一端插入或删除元素

D、栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素3.下列叙述正确的是：

A、一个逻辑数据结构只能有一种存储结构

B、数据的逻辑结构属于线性结构，存储结构属于非线性结构

C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响处理的效率ACD第六十页，共一百四十四页，编辑于2023年，星期五【2005年9月】二.填空题1.算法复杂度主要包括时间复杂度和（）复杂度。2.一棵二叉树第六层（根结点为每一层）的结点数最多为（）个。3.数据结构分为逻辑结构和存储结构，循环队列属于（）结构。空间复杂度满二叉树最多第k层上的结点数为2k-1个32存储结构常用的存储结构有顺序、链式和索引存储结构。逻辑结构对应的存储结构线性表顺序表（线性表的顺序存储结构）线性链表（链式存储结构）循环链表（链式存储结构）栈栈的顺序存储结构带链的栈（链式存储结构）队列循环队列（顺序存储结构）带链的队列（链式存储结构）树树的链式存储结构二叉树二叉树的链式存储结构第六十一页，共一百四十四页，编辑于2023年，星期五【2005年4月】一.选择题1.数据的存储结构是指：

A、存储在外存中的数据B、数据所占的存储空间量

C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示2.下列关于栈的描述中错误的是：

A、栈是先进后出的线性表

B、栈只能顺序存储

C、栈具有记忆作用

D、对栈插入与删除操作，不需要改变栈底指针3.对于长度为n的线性表，在最坏情况下，下列各排序所对应的比较次数中正确的是：

A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-1)/2D栈可以用来保护断点信息BD第六十二页，共一百四十四页，编辑于2023年，星期五4.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为：A、[㏒2n]B、n/2C、nD、n+15.下列对于线性链表的描述中正确的是：A、存储空间不一定是连续，且各元素的存储顺序是任意的B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的二、填空题1.某二叉树中度为2的结点有18个，则该二叉树中有（）个叶子结点。2.问题处理方案的正确而完整的描述称为（）。CA19算法第六十三页，共一百四十四页，编辑于2023年，星期五第二部分程序设计基础

1-2题（2-4分）考试大纲:一、基本要求:1.掌握逐步求精的结构化程序设计方法。二、考试内容1.程序设计方法与风格2.结构化程序设计3.面向对象的程序设计方法、对象、方法、属性及继承与多态性。第六十四页，共一百四十四页，编辑于2023年，星期五考点一、程序设计方法与风格（P48）1、程序设计方法和技术的发展主要经过了结构化程序设计和面向对象程序设计两个阶段。2、程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思想。程序设计风格会深刻影响软件的质量和可维护性。著名的“清晰第一，效率第二”的论点已经成为当今主要的程序设计风格。3、要形成良好的程序设计风格，主要应注意和考虑下述一些因素：第六十五页，共一百四十四页，编辑于2023年，星期五（1）源程序的文档结构组织对源程序的文档结构的组织要注意以下三点：①符号的命名：符号的命名应具有一定的实际含义。②程序注释：一般分为序言性注释和功能性注释。③视觉组织：在程序中利用空格、空行、缩进等技巧使程序层次清晰。（2）数据说明的方法对数据的说明要注意三点：第一，数据说明的次序规范化；第二，说明语句中变量安排有序化；第三，使用注释来说明复杂数据结构。第六十六页，共一百四十四页，编辑于2023年，星期五（3）语句的结构对语句的结构安排要遵循以下一些原则：①在一行内只写一条语句；程序编写应优先考虑清晰性。②除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。③首先要保证程序正确，然后才要求是提高速度；④避免使用临时变量而使程序的可读性下降；⑤避免不必要的转移；尽可能使用库函数；避免复杂的条件语句；⑥尽量少使用“否定”条件的条件语句；数据结构要有利于程序的简化；⑦要模块化，使模块的功能尽可能单一化；利用信息隐蔽，确保每一个模块的独立性；⑧从数据出发去构造程序；不要修补不好的程序，要重新编写。第六十七页，共一百四十四页，编辑于2023年，星期五（4）输入和输出对输入和输出用户界面要注意以下几点：①对所有的输入数据都要检验数据的合法性；检查输入项的各种重要组合的合理性；②输入格式要简单，以使得输入的步骤和操作尽可能简单；③输入数据时，应允许使用自由格式；应允许缺省值；④输入一批数据时，最好使用输入结束标志；⑤在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应屏幕上给出状态信息；⑥当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。第六十八页，共一百四十四页，编辑于2023年，星期五考点二、结构化程序设计（P50）（1）结构化程序设计的原则在结构化程序中要遵循以下四个基本原则：①自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标②逐步求精：对复杂问题，先设计一些子目标作过渡，然后逐步细化。③模块化：把程序要解决的总目标分解为一个一个的模块。④限制使用GOTO语句：程序的质量与GOTO语句的数据成反比。第六十九页，共一百四十四页，编辑于2023年，星期五（2）结构化程序的基本结构与特点①结构化程序设计中常采用顺序、选择和循环三种基本结构。②结构化程序设计的优点第一：程序易于理解、使用和维护；第二：提高了编程的效率，降低了软件开发成本。③结构化程序设计原则和方法的应用应该做到以下几个方面：◆使用程序设计语言中的顺序、选择、循环等有限的控制结构表示控制逻辑；◆选用的控制结构只准许有一个入口和一个出口；◆程序语句组成容易识别的块，每块只有一个入口和一个出口；◆复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；◆语言所没有的控制结构，应该采用前后一致的方法来模拟；◆严格控制GOTO语句的使用。第七十页，共一百四十四页，编辑于2023年，星期五考点三、面向对象程序设计（P52）（1）面向对象方法的本质（2）面向对象方法的优点（3）面向对象方法的基本概念（P54）①对象：指描述该对象属性的数据以及对这些数据施加的所有操作封装在一起构成的统一体。对象是对问题域中某个实体的抽象。②对象的属性和方法：属性是对象所包含的信息，它在设计对象时确定，一般只能通过执行对象操作来改变。方法描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。③对象的基本特点：◆标志唯一性：对象可由其内在本质来区分，而不是通过描述来区分。◆分类性：可以将具有相同属性和操作的对象抽象成类。◆多态性：同一操作可以是不同对象的行为。◆封装性：从外面看不到对象的内部，只能看到对象的外部特性。◆模块独立性好：一个对象就相当于一个模块。第七十一页，共一百四十四页，编辑于2023年，星期五④类和实例：类是具有共同属性、共同方法的对象的集合，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。⑤消息：指对象间的相互协助机制，是一个对象与另一个对象之间传递的消息。消息的组成：消息是由接收消息的对象名称、消息标识符、零个或多个参数组成。⑥继承：指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承中一个类只允许有一个父类，多继承中一个类允许有多个父类。⑦多态性：是指同样的消息被不同的对象接受时可导致完全不同的动作的现象。第七十二页，共一百四十四页，编辑于2023年，星期五例年考题分析【2008年9月】一、选择题1.数据流图中带有箭头的线段表示的是：A、控制流B、事件驱动C、模快调用D、数据流2.在面向对象的方法中，不属于“对象”基本特点的是：A、一致性B、分类性C、多态性D、标识唯一性AD第七十三页，共一百四十四页，编辑于2023年，星期五【2008年4月】一、选择题1.程序流程图中带有箭头的线段表示的是：A、图元关系B、数据流C、控制流D、调用关系2.结构化程序设计的基本原则不包括：A、多态性B、自顶向下C、模块化D、逐步求精AC第七十四页，共一百四十四页，编辑于2023年，星期五【2007年9月】一、选择题1.在面向对象方法中，实现信息隐蔽是依靠：A、对象的继承B、对象的多态C、对象的封装D、对象的分类2.下列叙述中，不符合良好程序设计风格要求的是：A、程序的效率第一，清晰第二B、程序的可读性好C、程序中有必要的注释D、输入数据前要有提示信息3.下列叙述中正确的是：A、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据理D、以上三种说法都不对ACA第七十五页，共一百四十四页，编辑于2023年，星期五【2007年4月】一、选择题1.在结构化程序设计中,模块划分的原则是：A、各模块应包括尽量多的功能B、各模块的规模应尽量大C、各模快之间的联系应尽量紧密D、模块内具有高内聚度、模块间具有低耦合度2.下面选项中不属于面向对象程序设计特征的是：A、继承性B、多态性C、类比性D、封装性CD第七十六页，共一百四十四页，编辑于2023年，星期五【2006年9月】1.下列选项中不符合良好程序设计风格的是：A、源程序要文档化B、数据说明的次序要规范化C、避免滥用goto语句D、模块设计要保证高耦合、高内聚【2006年4月】1.下列选项中不属于结构化程序设计方法的是：A、自顶向下B、逐步求精C、模块化D、可复用2.在面向对象方法中（）描述的是具有相似属性与操作的一组对象。【2005年4月】1.在面向对象方法中，类的实例称为（）。DD类对象第七十七页，共一百四十四页，编辑于2023年，星期五第三部分软件工程基础

3-5个题（6-10分）一、基本要求掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。二、考试内容1、软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。3、结构化设计方法，总体设计与详细设计。4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5、程序的调试，静态调试与动态调试。第七十八页，共一百四十四页，编辑于2023年，星期五(一)软件工程基本概念（P60）1、软件定义与软件特点①软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。②软件的三个要素：程序、数据和文档。③软件的特点：软件作为一种特殊的信息产品，具有以下特点：软件是一种逻辑实体，具有抽象性；软件没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导制了软件的移植性；软件复杂性高，成本昂贵；软件开发涉及诸多的社会因素。第七十九页，共一百四十四页，编辑于2023年，星期五④软件分类:软件按功能可分为应用软件、系统软件和支撑软件(或工具软件)三大类。支撑软件是介于系统软件和应用软件之间，协调用户开发软件的工具性软件。2、软件危机与软件工程（P61）①软件危机的含义：软件危机泛指在计算机软件的开发和维护中所遇到的一系列严重问题。②软件危机主要表现为：软件需求的增长得不到满足；软件开发的成本和进度无法控制；软件质量难以保证；软件不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高跟不上硬件的发展和应用需要的增长。③软件危机产生的原因：宏观方面是由于软件日益深入社会生活的各个层面，对软件需求的增长速度大大超过了技术进步所能带来的软件生产率的提高。而就每一项具体的工程任务来看，软件危机许多困难来源于软件工程所面临的任务和其它工程之间的差异以及软件和其他工业产品的不同。第八十页，共一百四十四页，编辑于2023年，星期五④软件工程的定义（P62）◆软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。◆软件工程的三个要素：方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。◆软件工程的核心思想是软件当作一个工程产品来处理。第八十一页，共一百四十四页，编辑于2023年，星期五（3）软件工程过程与软件生命周期（P63）①软件工程过程◆定义：软件工程过程是把输入转化为输出的一组相关的资源和活动。◆内涵：软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件过程活动。从软件开发的观点来看，它就是使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。◆软件工程过程包含的4个基本活动：软件规格说明（P）、软件开发（D）、软件确认（C）和软件演进（A）。第八十二页，共一百四十四页，编辑于2023年，星期五②软件生命周期▲（P63）◆定义：软件生命周期就是软件产品从提出、实现、使用维护到停止使用退役的全过程。◆三个阶段：软件生命周期包括软件定义、软件开发及软件维护三个阶段（每个阶段的任务）。◆软件定义阶段的任务包括可行性研究与计划制定、需求分析；软件开发阶段的任务包括概要设计、详细设计、软件实现、软件测试；软件维护的任务包括软件的运行、维护和退役。第八十三页，共一百四十四页，编辑于2023年，星期五可行性研究初步项目计划需求分析概要设计详细设计实现测试使用维护退役定义阶段开发阶段维护阶段软件生命周期第八十四页，共一百四十四页，编辑于2023年，星期五4、软件工程的目标与原则（P64）①软件工程的目标软件工程的目标是，以给定成本、进度的前提下，开发出具有时效性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程的理论和技术性研究的内容：◆软件开发技术：软件开发技术包括软件开发方法学、开发过程、开发工具、软件工程环境等内容。◆软件工程管理：软件工程管理包括软件管理学、软件工程经济学、软件心理学等内容。②软件工程的原则包括：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。第八十五页，共一百四十四页，编辑于2023年，星期五5、软件开发工具与软件开发环境（P65）①软件开发工具：软件工具的发展是从单项工具的开发逐步向集成工具发展的，软件工具为软件工程的方法提供了自动的或半自动的软件支撑环境。②软件开发环境：软件开发环境是全面支持软件开发过程的软件工具集合。计算机辅助软件工程是当前软件开发环境中富有特色研究工作和发展方向。第八十六页，共一百四十四页，编辑于2023年，星期五(二)结构化分析方法软件开发方法包括分析方法、设计方法和程序设计方法。结构化方法包括结构化分析方法、结构化设计方法和结构化编程方法。1、需求分析与需求分析方法①需求分析：软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析阶段的工作是需求获取、需求分析、编写需求规格说明书和需求评审。②需求分析方法：常见的有结构化分析方法和面向对象分析方法两种。结构化分析方法主要包括面向数据流的结构化分析方法（SA）、面向数据结构的Jackson方法（JSD）、面向数据结构的结构化数据系统开发方法（DSSD）。从需求分析建立的模型的特性来分，需求分析方法又分为静态分析方法和动态分析方法。第八十七页，共一百四十四页，编辑于2023年，星期五2、结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用。它是基于功能分解的分析方法，其目的是帮助弄清用户对软件的需求。结构化分析的常用工具有数据流图（DFD）、数据字典（DD）、判定树和判定表。其中最重要的工具是数据流图。数据流图中的主要图形元素有加工（用○表示）、数据流（用→表示）、存储文件（又叫数据源，用—表示）以及源（又叫潭，用□表示）。①建立数据流图的步骤是：第1步：由外向里：先画系统的输入和输出，然后画系统内部；第2步：自顶向下：顺序完成顶层、中间层、底层数据流图；第3步：逐层分解。②数据字典：是对DFD中出现的被命名的图形元素的确切解释。第八十八页，共一百四十四页，编辑于2023年，星期五3、软件需求规格说明书软件需求规格说明书（SRS）是需求分析阶段的最后结果，是软件开发中的重要文档之一。①软件需求规格说明书有以下几个作用：◆便于用户、开发人员进行理解和交流。◆反映出用户问题的结构，可以作为软件开发工作的基础和依据。◆作为确认测试和验收的依据。②软件需求规格说明书的内容：包括概述、数据描述、功能描述、参考文献目录和附录。③软件需求规格说明书的特点：软件需求规格说明书具有正确性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等特点。第八十九页，共一百四十四页，编辑于2023年，星期五（三）结构化设计方法（P73）1、软件设计概念软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。①软件设计的重要性和地位：a.软件开发阶段（设计、编码、测试）占软件项目开发总成本绝大部分，是在软件开发中形成质量的关键环节；b.软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统唯一途径；c.软件设计作出的决策，最终影响软件实现的成败；d.设计是软件工程和软件维护的基础。第九十页，共一百四十四页，编辑于2023年，星期五②软件设计的内容：从技术观点看，软件设计包括结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软件系统各主要部件之间的关系。数据设计是将分析时创建的模型转化为数据结构的定义。接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信。过程设计是把系统结构部件换成软件的过程性描述。从工程管理角度看，软件设计包括概要设计和详细设计。概要设计的任务是将软件需求转化为软件体系统结构、确定系统级接口、全局数据结构或数据库模式。详细设计的任务是确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。第九十一页，共一百四十四页，编辑于2023年，星期五③软件设计的基本原理:软件设计的基本原理就是抽象、模块化、信息隐蔽和模块独立性。其中度量模块独立性的两个定性的标准是模块内部的内聚性和模块间的耦合性。模块的内聚性是指一个模块内部各个元素之间彼些结合的紧密程度的度量。内聚有如下种类，它们之间的内聚性由弱到强的排列为：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚。模块的偶合性是指模块间相连接的紧密程度的度量。模块间的耦合有以下几种，它们由强到弱排列为：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合。④结构化设计方法的基本思想：将软件设计成由相对独立、单一功能的模块组成的结构。为了提高模块的独立性，应该尽量提高模块的内聚性，降低模块间的耦合性。第九十二页，共一百四十四页，编辑于2023年，星期五2、概要设计（P75）在需求分析阶段，已经将系统分解成层次结构，而在概要设计阶段，需要进一步分解，划分为模块以及模块的层次结构。①概要设计的基本任务：设计软件系统结构、确定数据结构及数据库设计、编写概要设计文档、进行概要设计文档评审。②软件结构设计工具：结构图（SC），也称为程序结构图。结构图的有关术语：◆深度：表示控制的层数。◆宽度：整体控制跨度（最大模块数的层）的表示。◆扇入、扇出：扇入是指调用一个给定模块的模块数；扇出指一个模块直接调用其他模块数。◆原子模块：树中位于叶子结点的模块。③面向数据流的设计方法：数据流类型：典型的数据流类型有两种，变换型和事务型。变换型是指信息沿输入通路进入系统，同时由外部形式变换成内部形式，进入系统的信息通过变换中心，经过加工处理后再沿输出通路变换成外部形式离开软件系统。在很多软件应用中，存在某种作业数据流，它可以引发一个或多个处理，这些处理能够完成作业要求的功能，这种数据流叫做事务型数据流。第九十三页，共一百四十四页，编辑于2023年，星期五3、详细设计①详细设计的任务：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。②过程设计的任务：对每相模块规定的功能以及算法的设计，给出适当的算法描述。③过程设计的工具：常用工具有图形工具（程序流程图、N-S图、PAD图（问题分析图）、HIPO）、表格工具（判定表）和语言工具（PDL（过程设计语言））。条件语句序列1ENDIF后面的语句控制流加工步骤逻辑条件第九十四页，共一百四十四页，编辑于2023年，星期五（四）软件测试（P85）软件测试是保证软件质量的重要手段，其主要过程涵盖了整个软件生命周期的过程，包括需求定义阶段的需求测试，编码阶段的单元测试、集成测试以及后期的确认测试、系统测试，验证软件是否合格、能否交给用户使用等。1、软件测试的目的软件测试是为了发现错误而执行程序的过程。第九十五页，共一百四十四页，编辑于2023年，星期五2、软件测试的准则软件测试过程中应遵循以下准则：①所有测试都应追溯到需求②严格执行测试计划，排除测试的随意性③充分注意测试中的群集现象④程序员应避免检查自己的程序⑤穷举测试不可能⑥妥善保存测试计划、测试用例、出错统计和最终分析报告。3、软件测试技术与方法综述（P86）①软件测试从是否要执行被测试软件的角度可以分为静态测试和动态测试。◆静态测试：静态测试包括代码检查、静态结构分析、代码质量度量等。◆动态测试：动态测试是基于计算机的测试，是为了发现错误而执行程序的过程。第九十六页，共一百四十四页，编辑于2023年，星期五②软件测试按照功能划分可以分为白盒测试和黑盒测试方法。◆白盒测试：是根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规范要求。白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。白盒测试的主要方法：1）逻辑覆盖法—泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。逻辑覆盖法有语句覆盖、路径覆盖、判定覆盖、条件覆盖以及判断-条件覆盖。2）基本路径测试法—基本路径测试的思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试。第九十七页，共一百四十四页，编辑于2023年，星期五◆黑盒测试法（P90）：是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试的方法：1）等价类划分法：将程序的所有可能的输入数据划分成若干部分（即若干等价类），然后从每个等价类中选取数据作为测试用例。2）边界值分析法：边界分析法是对各种输入、输出范围的边界情况设计测试用例的方法。3）错误推测法：靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的例子的方法。第九十八页，共一百四十四页，编辑于2023年，星期五4、软件测试的实施（P93）软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试。①单元测试：是对软件设计的最小单位—模块进行正确性检验的测试。主要目的是发现各模块内部可能存在的各种错误。②集成测试：是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。③确认测试：其任务是验证软件的功能和性及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否安全、正确。④系统测试：是将通过测试确认的软件，作为整个基于计算机系统的一个元素，与计算机硬件、外高、支持软件、数据和人员等其他系统元素组合在一起，在实际运行环境下对计算机系统进行一系列的集成测试和确认测