二级公共基础知识(教师版)

全国计算机等级考试二级公共基础知识热烈欢迎你们来共同学习，有问题随时联系！2011年3月二级公共基础知识点分布

第一章数据结构与算法(30%)考试大纲

1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。一.算法的基本概念*1.所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：有穷性确定性可行性输入输出输出或输出可说成：拥有足够的情报2.算法的组成要素算法中对数据的运算和操作算法的控制结构一.算法的基本概念3.算法设计的要求通常设计一个“好”的算法，应考虑达到以下目标。正确性：算法应当满足具体问题的需求。可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。效率与低存储量需求。效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。

一.算法的基本概念4.算法设计基本方法列举法归纳法递推递归减半递推回溯法一.算法的基本概念*5.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法的时间复杂度为算法中的基本操作重复执行的次数。是问题规模n的某个函数f(n)。一.算法的基本概念何估算算法的时间复杂度？

任何一个算法都是由一个“控制结构”和若干“原操作”组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和

∑(原操作(i)的执行次数×原操作(i)的执行时间)

Fori=1to100forj=1to100s=i*j。算法时间复杂度为：O（n2)一.算法的基本概念AQ21（2）算法的空间复杂度算法的空间负杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度，记作：S(n)=O(g(n))，其中n为问题的规模，表示随问题规模的增大，算法运行所需存储量的增长率与g(n)的增长率相同。一般不估计空间复杂度典型例题

1.一个算法是对某类给定的问题求解过程的精确描述，算法中的操作都可能通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有什么特性？

A有穷性B可行性C确定性D健壮性2.算法的时间复杂度是指（）

A）执行算法程序所需要的时间B）算法程序的长度

C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数3.下面叙述正确的是（）

A）算法的执行效率与数据的存储结构无关B）算法得空间复杂度是指算法程序中指令（或语句）的条数C）算法得有穷性是指算法必须能在执行有限个步骤之后终止D）以上三种描述都不对4.算法能正确地实现预定功能的特性称为算法的（）。

A．正确性B．易读性C．健壮性D．高效率5.

算法的计算量的大小称为计算的（）。

A．效率B.复杂性C.现实性D.难度二.数据结构1.数据结构的定义：是指相互有关联的数据元素的集合。

备注：1）数据元素：是数据的基本单位，由数据项组成。通俗的说：数据元素就是现实世界中的一个实体的抽象。

2）数据项：数据的最小单位。*2.数据结构主要研究三个方面的问题：

1)数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构。2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。3)对各种数据结构进行的运算。数据结构简单实例StudentStudent

zhangsanStudentlisi{name;{zhangsan;{lisi;

Sno;s20081001;s20081001;class;计算机1班；计算机1班；

Rscore;515；501；

}}}数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述（本身固有的），它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关，是独立于计算机的。

数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素，在存储空间中建立各存储结点之间的关联，来表示数据元素之间的逻辑关系。常见的存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构典型例题（1）数据结构中，与所使用的计算机无关的是数据的A）存储结构B）物理结构C）逻辑结构D）物理和存储结构（2）数据在计算机中的存储位置改变了，（）不变。A.数据的存储地址B.数据间的逻辑关系C.数据的物理存储结构D.逻辑结构和物理结构线性结构和非线性结构线性结构在数据元素的非空有限集合中，线性结构的逻辑特征如下：存在一个唯一的被称为“第一个”的数据元素存在一个唯一的被称为“最后一个”的数据元素除第一个之外，集合中的每个数据元素均有且只有一个直接前驱除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。线性表 通常以下列n个数据元素的序列”表示线性表：

(a1,a2,...,ai,...,an)序列中数据元素的个数n定义为线性表的表长；n=0时的线性表被称为空表。称i为ai在线性表中的位序。线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。

所有数据元素的存储位置均可由第一个数据元素的存储位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑

基地址一个数据元素所占存储量

线性表的插入和删除运算插入运算是指在线性表的某个指定位置增加一个新结点。一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。删除运算是指撤销结构中的某个结点。一般情况，要删除第i(1≤i≤n)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。栈栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的顺序存储及运算用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。top=0表示栈为空，top=m表示栈满。栈的操作入栈：在栈顶位置插入一个新元素，栈顶指针top加1。退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。栈如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（）A、DCEFBAB、ABCDEFC、EDFCABD、CBAEDF队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。循环队列初始状态为空，即front=rear=0.Front总是指示队头元素，rear指示队尾元素加1的位置。入队操作时，rear加1，若rear+1>容量，则置rear=0；退队操作时，front加1，若front+1>容量，则置front=0。**当rear>front时，元素个数＝rear－front；当rear<front时（只有循环队列才会出现队尾指针小于队头指针），元素个数＝总容量－（front－rear）。例:容量为25的循环队列中，若front=16，rear=9，有__个元素单链表线性表的链式存储结构的特点是用一组任意的存储单元(可以连续，也可以不连续)存储线性表的数据元素，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息(数据域)之外，还需要存储其后继元素的存储位置信息(指针域)。指针域中存储的信息称为指针或链，N个结点链接成一个链表，即为线性表的链式存储结构。由于结点中只包含一个指针域，故称为单链表。单链表通常以单链表中第一个数据元素的存储地址作为作为单链表的地址，称为头指针。整个链表的存储必须从头指针开始(顺序存取)，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，其指针域为空。单链表的插入和删除双向链表和循环链表在双向链表中的结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。HEAD…∧…∧HEAD…HEAD回顾：例：已知一组数据原先采用顺序存储，现改为散列存储，则（）不变。

A.存储结构B.逻辑结构C.数据间的顺序D.不确定例：常见的线性结构有___,____,_____例：在线性表中删除第5个节点，则原第6个节点的位置（），如果单链表则（）

A.6B.5C.不变D.不确定例：已知栈的头指针front当前位置为5，从栈中读取一个数据，则front指向（）

A.5B.6C.不变D.不确定例：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（）

A、435621B.123456C、546312D、654321树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。树是(n≥0)个结点的有限集合，在任意一棵非空树中：

(1)有且仅有一个特定的结点称为根结点。

(2)当n>1时，其余的结点可分为m个互不相交的子集T1,T2,…Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。集合为空的树简称为空树；树中的元素称为结点。树的主要术语结点的度：结点拥有的子树数。叶节点(终端结点)：度为0的结点。双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。同一个双亲结点的孩子互称为兄弟。层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。深度：树中结点的最大层次称为树的深度或高度。二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。二叉树的基本性质性质1

在二叉树的第i层上至多有2i-1个结点（i≥1）性质2

深度为k的二叉树至多有2k-1个结点（k≥1）性质3

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2

，则：n0=n2+1性质4

具有n个结点的二叉树，其深度至少为[log2n]+1例：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

A）221B）219C）231D）229例：一棵含18个结点的二叉树的高度至少为

A）3B）4C）5D）6满二叉树和完全二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为[log2n]+1。从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树

最大层的结点均向左靠齐

完全二叉树

ADCBEF二叉树的基本性质性质5

如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序（从第1层到第[log2n]+1层，每层从左到右）从1起开始编号，则对任一编号为i的结点(1≤i≤n)，则:

(1)如果i=1，则编号为i的结点是二叉树的根，无双亲；如果i>1，则其双亲结点parent(i)的编号是[i/2]。

(2)如果2i>n，则编号为i的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)的编号是2i。

(3)如果2i+1>n，则编号为i的结点无右孩子；否则其右孩子结点rChild(i)的编号是结点2i+1。

例：在一棵二叉树上第5层的结点数最多是A）8B）16C）32D）15例：在深度为5的满二叉树中，叶子结点的个数为

A）32B）31C）16D）15例：深度为4的二叉树中，编号为7的节点，它的右孩子节点为（）该树为满二叉树；如果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为（）

A）14B）8C）9D）15例：设树T的度为4，其中度为1，2，3，4的结点个数分别人4，2，1，1.则T中的叶子结点数为

A)8B)7C)6Ｄ）５二叉树的链式存储结构在二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。L(i)V(i)R(i)LchildvalueRchild二叉树的链式存储结构二叉树的遍历二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树"和"遍历右子树"三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。

先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；

否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。若二叉树为空，则空操作；

否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。若二叉树为空，则空操作；

否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。二叉树的遍历先序遍历：ABDEGHCFIJ中序遍历：DBGEHACIJF后序遍历：DGHEBJIFCA二叉树的遍历已知前序和中序遍历时，判断出根，分出左右子树；再根据前序分别判断出左右子树的根，然后再分出左右子树，以此类推下去……例：某二叉树的前序遍历结点访问顺序是A

B

D

G

C

E

F

H，中序遍历的结点访问顺序是D

G

B

A

E

C

H

F，则后序遍历的结点访问顺序是：已知前序和中序遍历时，判断出根，分出左右子树；再根据后序分别判断出左右子树的根，然后再分出左右子树，以此类推下去……例：已知一棵二叉树的中根序列和后根序列分别为B

D

C

E

A

F

H

G和D

E

C

B

H

G

F

A，试画出这棵二叉树。

二叉树的遍历例：例：某二叉树的前序遍历结点访问顺序是ABEFGHMN，中序遍历的结点访问顺序是EFBGAMHN，则后序遍历的结点访问顺序是：例：已知一棵二叉树的中根序列和后根序列分别为6739158和6793851，试画出这棵二叉树。(节点为0到9的数字）查找顺序查找:是指在一个给定的数据结构中查找某个指定的元素。顺序查找一般是指在线性表中查找指定元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中的所有元素与被查找元素都不相等，则查找失败。如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。平均查找长度为（n+1)/2，最坏为n.二分查找(折半查找)二分查找法只适用于顺序存储的有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到0也没有找到目标元素为止。查找过程中，给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间”或“后半个区间”之后继续进行查找。在等概率状态下查找成功时的平均查找长度为：

ASL≈log2（n＋1）-1（当n>50时）

折半查找二分查找例题：1.以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为(n+1)/2,时间复杂度为O(n)

。

2.以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于

┍log2(n+1)┑

，时间复杂度为O(log2n)。排序 排序是指将一个无序序列整理成按值递增或递减(本章均采用递增规则)的有序序列。排序可以在各种不同的存储结构上实现，本章所介绍的算法以顺序存储的线性表为排序对象，在程序设计语言中就是一维数组。常见的排序方法有插入排序(包括简单插入排序法和希尔排序法等)、交换排序(包括冒泡排序和快速排序法等)和选择排序(包括简单选择排序和堆排序等)。交换类排序冒泡排序基本思想：从表头开始扫描线性表，在扫描的过程中依次比较相邻两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置。显然，在扫描过程中，不断地将将相邻元素间较大的向后移动，最后将线性表中最大的元素移到表尾。然后，从后向前扫描剩下的线性表，同样在扫描的过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则交换位置。在扫描过程中，不断地将将相邻元素间较小的向前移动，最后将线性表中最小的元素移到表头。对剩下的线性表重复上述过程，直到剩余线性表为空为止，此时线性表变为有序。最坏情况下运算的次数为：n*(n-1)/2（即时间复杂度）。最好情况下为：n-1.冒泡排序示例第一遍(从前向后)第一遍(从后向前)第二遍(从前向后)第二遍(从后向前)快速排序基本思想：从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，将前面大于T的元素移动到后面，将线性表分为两个部分(子表)，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)的位置上。上述两步操作交替进行，直到i和j指向同一个位置，再将T移动到P(i)的位置上，完成一次分割。3168459023395412877631暂存枢轴记录T：lowhighhighhigh1212low6868highhighhigh2323low4545highhigh3131快速排序的一次分割过程31插入类排序简单插入排序基本思想：将待排序列表分成两部分：已排序部分和未排序部分。每次扫描将未排序列表中的第一个元素取出并插入到已排序列表中的合适位置。包含n个元素的列表最多需要n-1次扫描。简单插入排序示例原始序列第1趟第2趟第3趟第4趟第5趟希尔排序基本思想：将整个无序序列分割成若干个小的子序列分别进行插入排序。子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。增量序列一般取ht=n/2k(k=1,2…[log2n])希尔排序h=6h=1h=3完成选择类排序简单选择排序基本思想：将待排序列表分成两部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一个元素进行交换。经过一次选择和交换，列表中已排序部分增加一个元素，未排序部分减少一个元素。每次把一个元素从未排序部分移动到已排序部分称为完成一次分类扫描或称为一趟排序。一个包含n个元素的列表需要进行n-1次扫描完成排序。简单选择排序示例原始序列第1趟第2趟第3趟第4趟第5趟排序时间复杂度汇总（基数空间为O（rd)**从上表应当看出：1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(n)。（也就是最好情况下）。如果选择快速排序则相反，达到最坏时间复杂度。2.空间复杂度最坏的是归并排序O（n)，其次是基数排序O（rd)。3.平均时间最好的是快速、堆、归并排序O（nlgn)。4.稳定排序和不稳定排序（希尔、堆、直接选择，快速）。5.最坏情况下，时间复杂度最小的是：堆和归并排序。第二章程序设计基础(15%)考试大纲1.程序设计方法与风格。

2.结构化程序设计。

3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。

知识点归纳程序设计是一门技术，需要相应的理论、方法和工具来支持。就程序设计方法和技术的发展而言，主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中，通常采用“自顶向下，逐步求精”的方法，即把一个模块的功能逐步分解，细化为一系列具体的步骤，进而转换成一系列用某种程序设计语言编写的程序。程序设计风格除了程序设计设计方法和技术之外，程序风格也是非常重要的。良好的程序设计风格概括起来包括以下及格方面：源程序文档化数据说明的方法语句的结构输入和输出程序设计风格（4个方面）源程序文档化标识符的命名:要有一定的实际含义。程序的注释：较完善程序一般要有注视。序言性注释：通常置于每个程序模块的开头部分,一般给出程序的整体说明。功能性注释：一般是对某条语句的功能性说明。程序的视觉组织：一定要层次清晰数据的说明数据说明的次序应该规范化：比如先说明变量，其次是简单类型（如数组），接着是构造类型（如自己定义的数据结构）。说明语句中变量的安排有序化：例如多个变量出现在同一个说明语句中，要按顺序排列。使用注释说明复杂的数据结构程序设计风格语句结构在一行内只写一条语句程序编写应优先考虑清晰性除非对效率有特殊要求，程序编写要做到清晰第一，效率第二首先要保证程序正确，然后才要求提高速度避免使用临时变量而使程序的可读性下降避免不必要的转移尽可能使用库函数避免使用复杂的条件语句尽量减少使用“否定”条件的条件语句数据结构要有利于程序的简化要模块化，使模块功能尽可能单一化利用信息隐蔽，确保每一个模块的独立性从数据出发构造程序不要修补不好的程序，要重写编写程序设计风格输入和输出对所有输入数据检验合法性检查输入项的各种重要组合的合法性输入格式要简单，以使输入的步骤和操作尽可能简单输入数据时，应允许使用自由格式应允许缺省值输入一批数据时，最好使用输入结束标志在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。结构化程序设计结构化程序设计的原则自顶向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。逐步求精。对复杂的问题，应设计一些子目标过渡，逐步细化。模块化。一个复杂问题肯定是有若干简单问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标成为一个模块。严格限制GOTO语句的使用。（不是不能使用）结构化程序设计的基本结构和特点程序由一些基本结构组成，任何一个程序都可以用三种基本控制结构组成：

顺序结构、选择结构和循环结构程序结构的特点：单入口、单出口、结构中无死循环（也称有限的控制结构），程序中三种基本控制结构之间形成顺序执行关系。一个大型程序应按功能分割成一些模块，并把这些模块按层次关系进行组织。在程序设计时应采用自顶向下、逐步细化的实施方法。例：结构化程序设计的基本思想是采用"自顶向下，逐步求精"的程序设计方法和"单入口单出口"的控制结构。面向对象程序设计

面向对象方法的基本概念1.对象、类和属性

(1)对象的定义：在面向对象程序设计中，对象是程序的基本单位。对象可以表示客观世界中的任何实体，是对问题域中某个实体的抽象。

(2)对象通常由对象名、属性和操作三部分组成。

(3)类是对一组具有共同属性和相似行为的对象的一种抽象，类是对象的抽象，而对象是类的具体实例。类是抽象的，不占用内存，而对象是具体的，占用存储空间。对象的特点标识唯一性：对象名是唯一的分类性：每个对象都有属于自己的类。封装性：将对象的属性和操作封装成一个整体，也实现了数据的隐藏。模块独立性：例题：信息隐蔽的概念与下述哪一种概念直接相关______。A.软件结构定义B.模块独立性C.模块类型划分D.模拟耦合度

对象的特点继承：指一个类(子类)直接使用另一个类(父类)的所有属性和方法。

单重继承：一个类从另一个类继承属性和操作多重继承：一个类有几个父类多态性：多态性可以用“一个对外界面，多个内部实现”来表示。可以通过方法重载和方法重写来实现多态。举一个例子，计算机中的堆栈可以存储各种格式的数据，包括整型，浮点或字符。不管存储的是何种数据，堆栈的算法实现是一样的。例：有三个栈（对象），分别放数值型、字符型、日期型数据，队列（对象）向三个栈发送同样的“读取”消息，则产生的结果不一样。2.方法方法也可称为操作或服务，它描述了对象执行的功能，若通过消息传递，还可为其他对象使用。3.消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的。消息由三部分组成：消息标识符、零个或多个参数、接受消息对象的对象名面向对象程序设计的特点按照人的思维方式对客观世界进行抽象稳定性好可重用性好易于开发大型软件可维护性好1、程序设计语言的基本成分是数据成分、运算成分、控制成分和（D）

A）对象成分B）变量成分C）语句成分D）传输成分2、结构化程序设计主要强调的是（D）

A）程序的规模B）程序的效率C）程序设计语言的先进性D）程序易读性3、对建立良好的程序设计风格，下面描述正确的是（A）

A）程序应简单、清晰、可读性好B）符号名的命名只要符合语法

C）充分考虑程序的执行效率D）程序的注释可有可无4、NULL是指（C）

A）0B）空格C）未知的值或无任何值D）空字符串5、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（C）A）安全性B）一致性C）可理解性D）合理性6、子程序通常分为两类：【过程】和函数，前者是命令的抽象，后者是为了求值。7、.在面向对象方法中，类之间共享属性和操作的机制称为【继承】。8、一个类可以从直接或间接的祖先中继承所有属性和方法，提高了软件的【可重用性】第三章软件工程基础考试大纲1.软件工程基本概念，软件危机，软件工程的三要素、目标与原则。

2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。

3.结构化设计方法，总体设计与详细设计。

4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。

5.程序的调试，静态调试与动态调试。

软件定义和特点计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。计算机软件具有如下特点：软件是一种逻辑实体，具有抽象性软件生产没有明显的制造过程软件在运行、使用期间不存在磨损、老化问题软件的开发、运行对计算机系统具有依赖性软件复杂性高，成本昂贵软件开发涉及诸多社会因素软件危机所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题，包括：软件需求的增长得不到满足软件开发成本和进度无法控制软件质量难以保证软件不可维护或可维护性低软件成本不断提高软件开发生产率的提高赶不上硬件的发展和应用需求的增长。软件工程为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程的三要素方法：软件开发提供了“如何做”的技术。它包括了多方面的任务，如项目计划、软件系统需求分析、系统总体结构的设计、编码、测试及维护等。

工具：提供了自动的或半自动的软件支撑环境，即通常所说的软件工具。过程：软件工程过程软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。它包括两方面含义：1.软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动。通常包括四种基本活动：P(Plan)：软件规格说明D(Do)：软件开发C(Check)：软件确认A(Action)：软件演进2.从软件开发的观点看，软件工程过程是使用适当的资源，为开发软件进行的一组开发活动，在活动结束时将输入(用户需求)转化为输出(软件产品)。软件工程目标与原则目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。*软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。*衡量软件的指标：高内聚（模块内）、低耦合（模块间）。软件开发工具与软件开发环境计算机辅助软件工程(CASE):是一组工具和方法集合，可以辅助软件开发生命周期个阶段进行软件开发帮助进行应用程序开发的软件，包括分析、设计和代码生成.(CASE)的集成:(1)平台集成：工具运行在相同的硬件/操作系统平台。(2)数据集成：工具使用共享数据模型来操作。(3)表示集成：工具提供相同的用户界面。(4)控制集成：工具激活后能控制其他工具的操作。(5)过程集成：工具在一个过程模型和“过程机”的指导下使用。

软件生命周期软件从提出、实现、使用、维护到停止使用的过程称为软件的生命周期。一般包括以下几个阶段：可行性研究：目的就是用最小的代价在尽可能短的时间内确定该软件项目是否值得去开发。其实质是要进行一次简化、压缩了的需求分析需求分析：任务就是导出目标系统的逻辑模型，解决“做什么”的问题（即系统功能）。

需求分析的方法是：结构化分析方法和面向对象分析方法。软件设计：任务从软件需求规格说明书出发，形成软件的具体设计方案，即划分模块结构的过程.软件实现：把软件设计转换成计算机可以接受的程序代码。

软件测试:运行和维护：软件生命周期中所花费最多的阶段是软件运行维护阶段。需求分析阶段的主要工作需求获取：包括需求来源和获取需求的技术。它是软件设计的第一阶段，其本质主要是人的活动，涉及软件设计人员如何与客户建立有效的沟通(弄明白要做什么？）。也称为“需求发现”、“需求获得”。

需求分析：对沟通获得的需求或信息进行分析、汇总，并判断能否完成。编写需求规格说明书(SRS)

：是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。

需求评审：在软件生命周期中，越晚发现的错误越难修改，修改成本越昂贵的论断也已经成为了大家的共识。因此我们需要评审需求规格说明是否合理地确定了所有的性能目标，是否合理地确定了安全性方面要考虑到的问题。

软件需求软件需求包括：功能需求、性能需求、环境需求、可靠性需求、安全保密需求、用户界面需求、资源使用需求、成本消耗需求、开发进度需求等。需求分析应交付的主要文档是软件需求规格说明书。软件需求规格说明书的特点：

（1）正确性；（2）无岐义性；（3）完整性；（4）可验证性；（5）一致性；（6）可理解性；（7）可追踪性。需求分析阶段典型例题8、需求分析的任务不包括（）

A问题分析B系统设计C需求描述D需求评审。9.软件的可行性研究中不包括（D）Ａ、法律可行性Ｂ、技术可行性Ｃ、经济可行性Ｄ、政治可行性10.软件生产过程中，需求信息由（D）给出。

A、程序员B、项目管理者C、软件分析设计人员D、软件用户11．可行性研究要进行一次（）需求分析。参考答案为:C

A．详细的B．全面的C．简化的、压缩的D．彻底的**结构化分析方法（SA）结构化方法的核心和基础是结构化程序设计理论。结构化分析方法是一种建模技术（是需求分析的一种有效方法，另一种是面向对象的方法）

。其实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析常用的工具：数据流图数据字典判定树判定表（有时也用结构化语言）*数据流图1.数据流图（DFD）：就是采用图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具。2.数据流图从数据传递和加工的角度，是描述数据处理过程的工。3.数据流图的基本元素

数据源（终点)数据流处理(加工)数据存储数据流图的基本符号的意思矩形表示数据的外部实体（数据源或终点）；圆角的矩形表示变换数据的处理（加工），加工过程至少要有一个输入流和输出流。少右面的边矩形表示数据存储；箭头表示数据流，是数据的流向。例：数据流图（DFD）*处理过程至少有一个输入数据流和一个输出数据流

数据流程图上的每个元素都必须有名字。数据字典数据字典（DD）:是关于数据的信息的集合，对数据流图中的各个元素进行完整的定义和说明。数据字典是一个预留空间，一个数据库，这是用来储存信息数据库本身。

数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。

数据字典通常包含5个部分：数据项、数据结构、数据流、数据存储和处理过程。数据字典是结构化分析的核心。

结构化设计（SD）从技术角度出发软件设计包括软件结构设计、数据设计、接口设计、过程设计。（每个设计的含义一定要记住，见P6！)从结构化设计角度看，软件设计分概要设计和详细设计两步完成。1.概要设计，即总体设计。将需求分析得到的DFD转化为转化为软件系统结构和全局数据结构、确定数据库模式（即概要设计的功能）。2.概要设计的工具是结构图(SC）.结构图基本组成成分：模块、数据和调用.3.结构图基本图符由上面的数据流图转化的SC图储户模块存钱模块其他模块取钱模块验证密码确认签字详细设计即过程设计。功能是为软件结构图（SC）中的每一个模块确定采用的算法，模块内数据结构，用某种选定的表达工具（如N-S图等）给出清晰的描述。

常用工具有：程序流程图、N-S图、PAD图、过程设计语言PDL(伪码)。详细设计：由SC图中的’密码验证’得到的N-S图

（右边是N-S图，左边是根据图写的代码）验证密码输入密码返回继续输入错误正确可以取钱输入密码mIfm=‘123’

可以取钱Else

密码错误，请重新输入需求分析的工具：

（不要与方法弄混了，也不要与结构化分析工具弄混！！！）

问题分析图（PAD

）、程序流程图（PFD

）、

N-S（也是一种流程图）也称为盒图，是程序流程图的一种改进。程序流程图（PFD）中的箭头代表的是：控制流数据流图中的箭头代表：数据的流向结构图（sc):箭头代表模块的调用备注：几个易混的知识点软件设计阶段典型例题软件设计阶段典型例题1.对在数据流图中每一个命令的图形元素均给以定义是（B）Ａ、条目定义Ｂ、数据字典Ｃ、数据定义Ｄ、数据说明2.结构化程序设计理论认为，实现良好的程序结构要应用（A）的分析方法。

A、自顶向下B、自底向上C、面向对象D、基于组件3.从事物的组成部件及每个部件的属性、功能来认识事物。这种方法被称为（A）的方法。A、面向对象B、面向数据C、面向过程D、面向属性4.（D）工具在软件详细设计过程中不采用。

A．判定表B．IPO图C．PDL

D．DFD图5．程序的三种基本控制结构的共同特点是参考答案为:DA．不能嵌套使用B．只能用来写简单程序C．已经用硬件实现D．只有一个入口和一个出口6.从工程管理的角度软件设计可分为概要设计和（详细）设计两大步骤。7.流程图也称为程序框图是最常用的一种表示法，它有顺序、分支和（循环）三个基本控制构件。8.软件可靠性是指在给定的时间间隔内，程序成功运行的_概率____

9.软件工程时代的生产方式是（）化。10.结构化设计以（）为基础映射成软件结构。软件结构是以（）为基础而组成的一种控制层次结构。软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差别。软件测试是为了发现错误而执行程序的过程。（有时也解决存在的问题）一个好的测试用例是指可能找到迄今为止尚未发现的错误的用例。一个成功的测试是发现了至今尚未发现的错误的测试，一般由输入数据和预期的输出数据两部分组成。

测试用例应该包括合理的和不合理的输入条件。测试技术与方法综述从是否需要执行被测试软件的角度，可将测试分为静态测试和动态测试。

1.静态测试主要包括代码检查、静态结构分析、代码质量度量等，它可以由人工进行

。

2.动态测试：动态测试是通常意义上的测试，也就是运行和使用软件。是根据软件开发的各个阶段的规格说明和程序的内部结构而精心设计的一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。按照功能划分，可将软件测试分为黑盒测试和白盒测试。（有时也称白箱和黑箱测试）测试技术与方法综述1.黑盒测试将测试对象看作一个黑盒，不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明书，检查程序的功能是否符合它的功能说明。这种测试又称为功能测试或数据驱动测试。

黑盒测试的方法：等价类划分法、边界值分析法、错误推测法、因果图法等。2.白盒测试把测试对象看作一个透明的盒子，利用程序内部的逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试。通过在不同点检查程序的状态，确定实际的状态是否与预期的一致。这种测试又称为结构测试或逻辑驱动测试。

白盒测试的方法：逻辑覆盖、基本路径测试等。3.白盒和黑盒测试有可能是动态测试，又有可能是静态测试。软件测试的实施软件测试按四个步骤（不同阶段）进行：单元测试：对软件设计的最小单位－模块进行正确性的测试，其目的是发现各模块内部可能存在的各种错误。是在代码编写阶段可进行的测试，它是整个测试工作的基础。集成测试：是测试和组装软件的过程，它是在把模块按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。确认测试：任务是验证软件的功能和性能以及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确。系统测试：系统测试是将已经确认的软件、计算机硬件、外设、网络等其他元素结合在一起，进行信息系统的各种组装测试和确认测试，其目的是通过与系统的需求相比较，发现所开发的系统与用户需求不符或矛盾的地方，从而提出更加完善的方案。程序调试程序调试的任务是诊断和修正程序中的错误。调试的方法：强行排错法回溯法原因排除法软件维护定义：软件维护主要是指根据需求变化或硬件环境的变化对应用程序进行部分或全部的修改，修改时应充分利用源程序．修改后要填写程序改登记表，并在程序变更通知书上写明新旧程序的不同之处。分类：

1.适应性维护：为适应软件运行环境的变化而修改软件的活动。

2.改善性维护：根据用户在软件使用过程中提出的建设性意见而进行的维护活动。

3.纠错性维护：为改正软件系统中潜藏的错误而进行的维护活动。

4.预防性维护：为了改进应用软件的可靠性和可维护性，为了适应未来的软硬件环境的变化而进行的维护活动。维护的副作用维护的副作用有编码副作用、数据副作用、文档副作用三种。1.编码副作用：在使用程序设计语言修改源代码时，都可能引入错误。例如，删除或修改一个子程序、删除或修改一个标号、删除或修改一个标识符等。2.数据副作用：在修改数据结构时，可能导致软件出错。例如，在修改定义局部或全局常量、重新定义记录或文件格式、增大或减小一个数组或数据结构的大小。3.文档副作用：对相关技术文档进行相应修改而引起的错误。例如：用户对交互输入的顺序或格式进行修改。软件测试维护阶段典型例题1.下列关于软件测试的叙述中错误的是（D）。（选择一项）A、软件测试可以作为度量软件与用户需求间差距的手段B、软件测试的主要工作内容包括发现软件中存在的错误并解决存在的问题C、软件测试的根本目的是尽可能多地发现软件中存在地问题，最终把以个高质量地软件系统交给用户使用D、没有发现错误地测试也是有价值的2.在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是______。(C)

A.循环的集合B.地址的集合C.路径的集合D.目标的集合3.在设计测试用例时，应当包括（C）Ａ、合理的输入条件Ｂ、不合理的输入条件Ｃ、合理的和不合理的输入条件Ｄ、部分条件4、与设计测试数据无关的文档是（D）。

A、需求说明书B、设计说明书C、源程序D、项目开发设计5.软件测试的目的是（）A实验性运行软件B找出软件中的错误C证明软件正确D找出软件中的全部错误6.对于软件测试分类，下列各项都是按照不同阶段来进行的划分，除了（C）。

A、单元测试B、集成测试C、黑盒测试D、系统测试7.在设计测试用例时，应当包括（C）Ａ、合理的输入条件Ｂ、不合理的输入条件Ｃ、合理的和不合理的输入条件Ｄ、部分条件测试与维护阶段典型例题8.与设计测试数据无关的文档是（D）。

A、需求说明书B、设计说明书C、源程序D、项目开发设计9、为了进一步改善软件系统的可维护性和可靠性，并为以后的改进奠定基础的软件维护称为（D）。

A。纠错性维护B适应性维护C改善性维护D预防性维护10.为适应软件运行环境的变化而修改软件的活动称为（B）。

A.纠错性维护B适应性维护C改善性维护D预防性维护11、根据用户在软件使用过程中提出的建设性意见而进行的维护活动称为（C）。

A纠错性维护B适应性维护C改善性维护D预防性维护12、为改正软件系统中潜藏的错误而进行的维护活动称为（A）。

A错性维护B适应性维护C改善性维护D预防性维护

13、以下不属于白盒测试技术的是（D）

A逻辑覆盖B基本路径测试C循环覆盖测试D等价类划分14．产生软件维护的副作用，是指（C）

A．开发时的错误B．隐含的错误C．因修改软件而造成的错误D．运行时误操作15.软件测试方法中（）属于静态测试。

A黑盒法B路径覆盖C错误推测D人工检测测试与维护阶段典型例题16.黑盒测试主要是测试软件是否满足（功能）需求。17.程序设计语言的（可维护）性通常指这种语言编写的程序被理解，被修改及调整和改进的难易程度。18.软件测试是为了（）而执行程序的过程。19.软件测试的目的是尽可能的发现软件中错误，通常（）是在代码编写阶段可进行的测试，它是整个测试工作的基础。

20.若按功能划分，软件测试的方法通常分为白盒测试方法和（）测试方法。按软件是否被执行，软件测试分为（）和（）。21.测试用例应有（）和预期的输出数据两部分组成。这样便于对照检查。22.黑盒测试是（）测试，因此设计测试用例时，需要研究需求规格说明书和概要设计说明书中有关程序功能或输入、输出之间的关系等信息。23.维护的副作用有编码副作用、（）、文档副作用三种。

24.程序（）的任务是诊断和修正程序中的错误。其方法有强行排错法、（）和回溯法。第四章数据库设计基础考试大纲1.数据库的基本概念：数据库，数据库管理系统，数据库系统。

2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。

3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。知识点归纳数据库的定义1.长期存放在计算机内，有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性。数据独立性包括：物理和逻辑独立性。

物理独立性是指用户的应用程序与存储在磁盘上的数据库中数据是相互独立的。即，数据在磁盘上怎样存储由DBMS管理，用户程序不需要了解。

逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的，即，当数据的逻辑结构改变时，用户程序也可以不变。

2.数据库还可以说成：是由一个互相关联的数据的集合和一组用以访问这些数据的程序组成的。3.数据库技术的根本目标是解决数据的共享问题。计算机数据管理技术发展的三个阶段人工管理阶段:数据不具有独立性,由应用程序管理数据本身。文件系统阶段:数据独立性和共享性差,由文件管理数据本身。数据库系统阶段：有较高的数据独立性和共享性，由数据库管理系统(DBMS)管理数据。数据库管理系统(DBMS)数据库管理系统是一个帮助用户创建和管理数据库的应用程序的集合也就是一个可以帮助完成定义、构造和操纵数据库等处理目的的通用软件系统。其主要功能如下：数据模式定义：数据库存放数据的模式，即数据库中全体数据的逻辑结构和特征的描述。

数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段。数据操纵：数据的查询、修改、删除、添加四种操作。数据的完整性、安全性定义和检查：数据库的并发控制和故障恢复数据的服务为完成上述功能，DBMS提供了相应的语言：数据定义语言(DDL)数据操纵语言(DML)数据控制语言(DCL，用来设置或者更改数据库用户或角色权限的语句)数据库系统数据库系统是由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台等几个部分组成的完整的运行实体。

DBS=DB+DBMS+DBA数据库系统的特点数据的集成性数据的高共享性和低冗余性数据的独立性数据统一管理和控制数据库系统的内部体系结构三级模式外模式：又称为用户模式，是每个用户的局部数据描述，用户的数据视图.概念模式：数据库系统中全局数据逻辑结构的描述，全体用户的数据视图.内模式：又称为物理模式，是数据库物理存储结构和物理存取方法的描述.二级映射:保证了数据的物理独立性和逻辑独立性概念模式到内模式的映射(物理独立性)外模式到概念模式的映射(逻辑独立性)数据模型数据模型是数据模型（DataModel）是数据特征的抽象，它是数据及其操作的一种抽象表示。数据模型描述的内容包括三部分：数据结构：主要描述数据的类型、内容、性质以及数据间的联系等。数据操作：主要描述在相应的数据结构上的操作类型和操作方式。如选择、投影、连接等。数据约束：主要描述数据结构内数据间的语法、词义联系等。一个学生实体转换为关系模型一学生：姓名：张三；年龄：20；性别：男；班级：中文1；入学成绩：550。学生表：姓名年龄性别班级入学成绩张三20男中文1550数据模型数据模型按不同的应用层次分成三种类型：概念数据模型、逻辑数据模型和物理数据模型概念数据模型：简称概念模型，是面向现实世界的，其出发点是有效地模拟现实世界，给出数据的概念化结构。与具体的数据管理系统无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。

实体联系模型是一种广泛使用的概念模型，该模型将现实世界的要求转化为实体、联系和属性等几个基本概念，并用ER图直观地表示出来。ER模型的基本概念实体：概念世界中的基本单位，它们是客观存在且能相互区别的事物。凡具有共性的实体可以组成一个集合称为实体集。属性：属性用来描述实体的特征。一个实体可以有多个属性，每个属性可以有值，一个