二级公共基础知识(41)教材

全国计算机等级考试

二级公共基础知识约12课时青岛工学院学习方法逻辑推理运算必须理解概念性、理论性知识点要加强记忆适当记忆一些名词与所学的VF程序设计知识结合起来，以增加对知识的理解能力做大量习题青岛工学院一、数据结构与算法考点提示：1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。青岛工学院本章考点点评及考核情况考点点评：该部分属于重点考核知识点，在此7个考点中，经常会考到的知识点是1、4、6点，特别是二叉树的遍历，基本上每年必考的内容。分值情况：本部分内容所占分值在3-5分。青岛工学院1.1算法算法：

是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法；算法是解题思路，而程序是解题思路在其编译环境中的具体描述。算法的特征：（1）可行性：在具体环境中可执行和正确与否（2）确定性：每一步必须有明确的定义（3）有穷性：在有限步骤（时间）内执行完毕（4）拥有足够的情报：初始数据或初始状态必须要充足且正确。青岛工学院算法的基本要素： 一是对数据对象的运算和操作（四类） 二是算法的控制结构（各操作之间的执行顺序）。基本运算和操作包括： 算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：

顺序、选择、循环。算法设计的基本方法： 列举法、归纳法、递推、递归、减半递推技术、回溯法。青岛工学院算法复杂度(包括)：

算法时间复杂度和算法空间复杂度。算法时间复杂度： 是指执行算法所需要的计算工作量（运算的执行次数）。衡量算法时间复杂度的主要因素：

一方面依赖于问题的规模，（如N×N矩阵乘法运算，f(n)=O(n3)）另一方面，某些情况下还和问题的输入数据集有关（如冒泡排序）,此时用两种方法分析：（1）平均性态：用基本运算次数的加权平均值来衡量----A(n)=（2）最坏情况复杂性：最大执行次数

----W(n)=青岛工学院算法空间复杂度： 是指执行算法所占用的空间，包括算法程序所占用的空间、输入的初始数据所占用的空间、算法执行过程中所需要的额外空间。算法设计的要求：（1）正确性 （2）可读性 （3）健壮性（4）效率与低存储量需求青岛工学院例题算法的时间复杂度是指______。

A.执行算法程序所需要的时间

B.算法程序的长度

C.算法执行过程中所需要的基本运算次数

D.算法程序中的指令条数算法的空间复杂度是指______。

A.算法程序的长度

B.算法程序中的指令条数

C.算法程序所占的存储空间

D.执行算法所需要的空间下面叙述正确的是______。

A.算法的执行效率与数据的存储结构无关

B.算法的空间复杂度是指算法程序中指令（或语句）的条数

C.算法的有穷性是指算法必须能在执行有限个步骤之后终止

D.以上三种描述都不对(C)(D)(C)青岛工学院算法一般都可以用哪几种控制结构组合而成______。

A.循环、分支、递归

B.顺序、循环、嵌套

C.循环、递归、选择

D.顺序、选择、循环在下列选项中，哪个不是一个算法一般应该具有的基本特征______。

A.确定性 B.可行性 C.无穷性 D.拥有足够的情报算法的时间复杂度取决于_____。

A.问题的规模 B.待处理数据的初态

C.问题的难度 D.A和B在计算机中，算法是指______。

A.查询方法

B.加工方法

C.解题方案的准确而完整的描述

D.排序方法(D)(C)(D)(C)青岛工学院1.2数据结构的基本概念数据结构（两个，注意区分）： 反映数据元素之间关系的表示。数据结构研究的三个方面：（1）各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）各数据元素在计算机中的存储关系，即数据的存储结构（又叫物理结构）；（3）对各种数据结构进行的运算。数据的逻辑结构：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。 数据的逻辑结构是数据元素之间固有的，是与计算机硬件没有关系的结构青岛工学院数据逻辑结构的四种形式： 集合、线性结构、树形结构、图形结构数据存储结构： 是指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。

数据的物理结构反映的是数据的存储方法，这受到具体的物理存储介质制约(与计算机硬件有关系)。数据存储结构的三种形式：

顺序、链接、索引。数据结构中的数据元素，其逻辑结构和存储结构不一定相同。青岛工学院按逻辑（前后件）关系的复杂程度，将数据的逻辑结构简单分为线性结构和非线性结构：线性结构（什么是线性结构？线性结构有那几个？）（线性表、线性链表、栈、队列）：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。在一个线性结构中插入或删除任何一个节点后还应该是线性结构。非线性结构：不满足线性结构条件的数据结构。线性结构和非线性结构都可以是空数据结构，对于空数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。图1.5线性结构特列青岛工学院例题在数据结构中，与所使用的计算机无关的数据结构是_____。

A.逻辑

B.存储

C.逻辑和存储

D.物理在数据结构中，从逻辑上可以把数据结构分成______。

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D.内部结构和外部结构数据的存储结构是指______。

A.数据所占的存储空间量

B.数据的逻辑结构在计算机中的表示

C.数据在计算机中的顺序存储方式

D.存储在外存中的数据(A)(C)(B)青岛工学院1.3线性表及顺序存储结构线性表（是什么？是表？是线表？）：

线性表是最常用且最简单的一种线性数据结构。简言之，一个线性表是n个数据元素的有限序列。线性表有两种存储结构（顺序存储和链式存储）如26个英文字母的字母表（A,B,C,D……,Z）是一个线性表，表中的数据元素是单个字母字符。数据元素的定义在不同情况下各不相同 在复杂线性表中，一个数据元素可以由若干个数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）青岛工学院姓名学号性别年龄班级健康状况王晓林790631男18计1健康陈红790632女20计1一般……每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等6个数据项组成青岛工学院非空线性表的结构特征：（1）有且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。青岛工学院线性表的顺序存储结构(典型结构是数组存储)： 指用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点：（1）线性表顺序存储结构中所有元素所占的存储空间是连续的；（2）线性表顺序存储结构中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。可以看出，顺序存储是一种随机存取的存储结构,链式存储是一种顺序存取的存储结构。只要知道某元素地址，其他任何元素地址都可以计算出来青岛工学院顺序表的运算（时间复杂度）： 插入： 在平均情况下，要插入一个元素，需要移动表中一半的元素。 删除： 在平均情况下，要删除一个元素，需要移动表中一半的元素。

线性表顺序存储缺点：：线性表的顺序存储结构，插入和删除元素时需大量移动元素，故不便于插入和删除操作青岛工学院例题对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A.N+1 B.N C.(N+1)/2 D.N/2顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。用数组表示线性的优点是（）A．便于插入和删除操作 B．便于随机存储C．可以动态地分配存储空间D．不需要占用一片相邻的存储单元(B)相邻(B)青岛工学院1.4栈和队列（线性结构）栈：

是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素

还有初始化、置空、判断栈是否为空或满青岛工学院队列：

是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾（最后一个元素），front指针指向队头（第一个元素的前面）。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算：（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。青岛工学院例题下列关于栈的叙述中正确的是______。

A.在栈中只能插入数据

B.在栈中只能删除数据

C.栈是先进先出的线性表

D.栈是先进后出的线性表栈和队列的共同点是______。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。

A.CABED

B.DBCEA

C.CDABE

D.DCBEA(D)(C)(D)青岛工学院下列关于队列的叙述中正确的是______。

A.在队列中只能插入数据

B.在队列中只能删除数据

C.队列是先进先出的线性表

D.队列是先进后出的线性表下列不是栈的运算的是______。

A.删除栈顶元素

B.删除栈底元素

C.判断栈是否为空

D.将栈置为空栈若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是______。

A.1432 B.2341 C.3142 D.3421栈的基本运算有三种：入栈、退栈和______。在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有______个元素(C)(B)(C)读栈(3)计算公式是：：（尾指针-头指针+容量）%容量青岛工学院下列关于线性表、栈和队列的叙述，错误的是（）A．线性表是给定的n（n必须大于零）个元素组成的序列B．线性表允许在表的任何位置上进行插入和删除操作C．栈只允许在一端进行插入和删除操作D．队列允许在一端进行插入在另一端进行删除一个队列的入队序列是1，2，3，4，则队列的输出序列是（）A．4，3，2，1 B．1，2，3，4C．1，4，3，2 D．3，2，4，1设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列（）序列是不可能通过栈产生的。A．1，2，3，4，5 B．5，3，4，1，2C．4，3，2，1，5 D．3，4，5，2，1(A)(B)(B)青岛工学院设栈S的初始状态为空，6个元素入栈的顺序为e1，e2，e3，e4，e5和e6。若出栈的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（）

A．6 B．4 C．3 D．2(C)青岛工学院1.5线性链表

由于顺序存储有一些缺点，某些情况我们需采用链式存储结构。链式结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，指向前一个或后一个结点。线性链表： 在定义的链表中，若只含有一个指针域来存放下一个元素的地址，称单链表或线性链表。青岛工学院在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 线性链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表。 单链表只有一个指针域，只能顺指针向链尾扫描，为弥补这一缺点，可设置两个指针，左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。这样的线性链表称为双向链表。线性链表的基本运算：查找、插入、删除。青岛工学院查找：在线性链表中，即使知道被访问结点的序号i，也不能像顺序存储那样直接按序号i访问结点，而只能从链表的head出发，顺指针域next逐个往下搜索，直到找到第i个结点为止。因此，链表不是随机存取结构,而是顺序存取结构。插入：青岛工学院例题下列叙述中正确的是______。

A.线性表是线性结构

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

C.线性链表是非线性结构

D.二叉树是线性结构线性表的顺序存储结构和线性表的链式存储结构分别是______。

A.顺序存取的存储结构、顺序存取的存储结构

B.随机存取的存储结构、顺序存取的存储结构

C.随机存取的存储结构、随机存取的存储结构

D.任意存取的存储结构、任意存取的存储结构在循环链表中，增加头结点的目的是______。

A.方便运算的实现

B.使单链表至少有一个结点

C.标识表结点中首结点的位置

D.说明单链表是线性表的链式存储实现

(A)(B)(A)青岛工学院用链表表示线性表的优点是______。

A.便于插入和删除操作

B.数据元素的物理顺序与逻辑顺序相同

C.花费的存储空间较顺序存储少

D.便于随机存取链不具备的特点是______。

A.可以随机访问任意一个节点

B.插入和删除不需要移动任何元素

C.不必事先估计存储空间

D.所需空间与其长度成正比对线性表，下列情况下应当采用链表表示的是______。

A.经常需要随机的存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续空间

D.表中元素个数不变(A)(A)(B)青岛工学院如果最常用的操作是取第i个结点及其前驱，最省时间的存储方式是______。

A.单链表 B.双向链表 C.单循环链表D.顺序表与单链表相比，双向链表的优点之一是______。

A.插入、删除操作更加简单

B.可以随机访问

C.可以省略表头指针和表尾指针

D.顺序访问相邻结点更加灵活若已知一个栈的进栈序列是1，2，3。。。N，其输出序列是p1,p2……pn，若p1=n，则pi为______。

A.i B.n-i C.n-i+1D.不确定可以用带表头结点的链表表示线性表，也可以用不带表头结点的链表表示线性表，前者最主要的好处是（）A．可以加快对表的遍历 B．使空表和非空表的处理统一C．节省存储空间 D．可以提高存取表元素的速度(D)(D)(C)(B)青岛工学院1.6树与二叉树树是一种简单的非线性结构，元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。青岛工学院树的性质：（1）树所有结点的度之和比结点总数小1（2）树所有结点的度之和与边的条数之和相等青岛工学院二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。AΦ空树只有根节点只有左子树只有右子树两棵子树二叉树的五种形态：青岛工学院二叉树的基本性质：（1）度为0的结点（即叶子结点）总是比度为2的结点多一个；（n0=n2+1常用于求某个度的结点数）（2）在二叉树的第k层上，最多有2^(k-1)(k≥1)个结点； （求单层最多节点数）（3）深度为k的二叉树最多有2^k-1个结点； （求树的最多结点总数）（4）具有n个结点的二叉树，其深度至少为int[log2n]+1

（二叉树的最小深度）青岛工学院满二叉树

一颗深度为k且有2k-1个结点的二叉树称为满二叉树(可见，满二叉树结点总数一定是奇数)完全二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应（5）具有n个结点的完全二叉树的深度为[log2n]+1或

[log2（n+1）]；（求完全二叉树的深度）青岛工学院二叉树存储结构 常采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历（按某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次）：（1）前序（根）遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序（根）遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序（根）遍历（LRD），首先遍历左子树，然后访问遍历右子树，最后访问根结点。注意，遍历时子树也要遵循遍历规则。前：ABDIJEKCFG中：IDJBKEAFCG后：IJDKEBFGCA规律：前序遍历第一个节点是树的根，后续遍历最后一个节点是树的根。青岛工学院例题下列有关树的概念错误的是（）A．一棵树中只有一个无前驱的结点B．一棵树的度为树中各个结点的度数之和C．一棵树中，每个结点的度数之和等于结点总数减1D．一棵树中每个结点的度数之和与边的条数之和相等下面关于二叉树的叙述正确的是（）A．一棵二叉树中叶子结点的个数等于度为2的结点个数加1B．一棵二叉树中结点个数要大于0C．二叉树中任何一个结点要么是叶，要么恰有两个子女D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等B(A)青岛工学院设n，m为一棵二叉树上的两个结点，在中序遍历中，n在m前的条件是（）A．n在m右子树上 B．n是m的祖先C．n在m左子树上 D．n是m的子孙以下数据结构中不属于线性数据结构的是______。

A.队列 B.线性表 C.二叉树 D.栈在一棵二叉树上第5层的结点数最多是______。

A.8 B.16 C.32 D.15在深度为5的满二叉树中，叶子结点的个数为______。

A.32 B.31 C.16 D.15设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。

A.349 B.350 C.255 D.351树最适合用来表示______。A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据(C)(C)(B)(C)(B)(C)青岛工学院设有下列二叉树：

对此二叉树中序遍历的结果为______。

A.ABCDEF B.DBEAFC

C.ABDECF D.DEBFCA已知二叉树后序遍历序列是dacbe，中序遍历序列是deabc，它的前序遍历序列是______。

A.cedba

B.acbed

C.decab

D.edbac(B)(D)青岛工学院设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点数为______。

A.8 B.7 C.6 D.5一棵二叉树的前序遍历序列是ABDGCFK，中序遍历序列是DGBAFCK，则结点的后序遍历序列是（）A．ACFKDBG B．GDBFKCAC．KCFAGDB D．ABCDFKG一棵二叉树共有70个叶子节点和80个度为1的节点，则该二叉树的总节点数为（）

A.219 B.221 C.229 D.231(A)(B)(A)青岛工学院1.7查找技术顺序查找：

从表的一端开始，顺序扫描线性表只能使用顺序查找的情况：（1）线性表为无序表（不管是顺序存储还是链式存储）；（2）表采用链式存储结构（即使是有序存储）。最坏情况需要比较n次二分查找：

把表不断折半，和中值比较

******二分查找只适用于顺序存储的有序表 对于长度为n的有序线性表，最坏情况只需比较log2n次青岛工学院对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A.N+1 B.N C.(N+1)/2 D.N/2对长度为N的线性表进行二分查找，在最坏情况下所需要的比较次数为______。

A.N+1 B.log2n C.(N+1)/2 D.N/2对线性表进行折半查找时，要求线性表必须（）A．以顺序方式存储B．以链接方式存储C．以顺序方式存储，且结点按关键字有序排列D．以链接方式存储，且结点按关键字有序排列在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需要的比较次数是______。(B)(B)(C)(4)青岛工学院1.8排序技术交换类排序法：（1）冒泡排序法，最坏需要比较的次数为n(n-1)/2

。（2）快速排序法,最坏需要比较的次数为n2

插入类排序法：（1）简单插入排序法，最坏需要比较的次数为n(n-1)/2

。（2）希尔排序法,最坏需要比较的次数为n1.5选择类排序法：（1）简单选择排序法，最坏需要比较的次数为n(n-1)/2

。（2）堆排序法，最坏情况需要nlog2n次比较。青岛工学院例题希尔排序法属于哪一种类型的排序法______。

A.交换类排序法

B.插入类排序法

C.选择类排序法

D.建堆排序法在最坏情况下，冒泡排序的时间复杂度为______。在最坏情况下，堆排序需要比较的次数为______。(B)O（n2

）---n的平方青岛工学院二、程序设计基础1.形成良好的程序设计风格应注意的因素2.结构化程序设计的主要原则3.结构化程序的基本结构与特点4.结构化程序设计的原则和方法的应用5.面向对象程序设计的主要优点6.面向对象方法的基本概念（对象、类和实例、消息、继承和多态性）分值情况：所占分值1-2分注意区分：结构化程序设计和面向对象程序设计青岛工学院本章学习方法

这两章以概述的形式简介了规范化开发软件的方法。与数据结构不同，这两章内容主要是记忆性的知识点。程序设计基础的内容与大纲改革前添加了面向对象程序设计的内容，大家可以对本章进行几次细读后了解即可；软件工程基础这章主要考核内容为结构化分析及结构化设计方法（即SA及SD，约占50%），信息量较大，其次是软件测试（约占20%），考生需要将相关的概念及规则背诵，在以后有机会进行程序开发时这些知识可以得到深刻理解。青岛工学院2.1程序设计方法与风格

当今主导程序设计风格：“清晰第一，效率第二”良好的程序设计风格应注意的因素：1、源程序文档化；符号命名要有规则正确的注释：注释分序言性注释（一般写在程序最前面，说明程序功能）和功能性注释（语句功能、模块功能、语句状态说明等）视觉组织2、数据说明的方法；3、语句的结构；4、输入和输出。青岛工学院例题结构化程序设计主要强调的是______。

A.程序的规模 B.程序的易读性

C.程序的执行效率 D.程序的可移植性（本题不好，可不看）对建立良好的程序设计风格，下面描述正确的是______。

A.程序应简单、清晰、可读性好

B.符号名的命名只要符合语法

C.充分考虑程序的执行效率

D.程序的注释可有可无源程序文档化要求程序应加注释，注释一般分为序言性注释和______。功能性注释的主要内容不包括______。

A.程序的功能 B.语句的功能

C.模块的功能 D.数据的状态(B)(A)(功能性注释)(A)青岛工学院2.2结构化程序设计结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用goto语句。结构化程序的基本结构和特点：（1）顺序结构：按照语句的自然顺序，一条一条的执行；（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；（3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。包括直到型循环和当型循环。青岛工学院结构化程序设计原则和方法的应用（也比较重要，学有余力的同学可以看看）

虽然结构化程序设计方法有很多优点，但它仍是一种面向过程的设计方法。缺点：：：它把数据和处理数据的过程分离为相互独立的实体，当数据结构改变时，所有相关的处理过程的都要进行相应的修改，程序的可重用性差。青岛工学院例题结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、______和限制使用goto语句。结构化程序设计的三种基本逻辑结构是顺序、选择和______下面描述中，符合结构化程序设计风格的是______。

A.使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑

B.模块只有一个入口，可以有多个出口

C.注重提高程序的执行效率

D.不使用goto语句

(A)青岛工学院2.3面向对象的程序设计

传统的程序设计方法是面向过程的（也就是面向过程的结构化程序设计），其核心方法是以算法为核心。面向对象程序设计以对象为核心。对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好； （4）易于开发大型软件产品；（5）可维护性好。********面向对象的模型中，最基本的概念是对象和类。青岛工学院对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是现实世界实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的特征信息，描述对象的状态操作描述了对象执行的功能，操作也称为方法或服务。对象的基本特点：（1）标识惟一性：对象是可以互相区分的（2）分类性：将具有相同属性和操作的对象抽象成类（3）多态性：同一个操作可以是不同对象的行为（4）封装性：从外面看只能看到对象的外部特征，而不知道也无需知道数据的具体结构以及实现操作的算法。封装性实现了信息的隐蔽，保证对象不受外部的破坏和干扰。（5）模块独立性：对象是一个封装体。信息的隐蔽使模块通过有限的接口传递消息，降低了模块的耦合。青岛工学院类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括：（1）接收消息的对象的名称（谁）；（2）消息标识符，也称消息名（做）；（3）零个或多个参数（什么）。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。是类之间共享属性和操作的机制（提高可重用性，减少冗余）继承分单继承（改良）和多重继承（嫁接）。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。青岛工学院例题下面对对象概念描述错误的是______。

A.任何对象都必须有继承性

B.对象是属性和方法的封装体

C.对象间的通讯靠消息传递

D.操作是对象的动态性属性在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送______。

A.调用语句B.命令C.口令D.消息信息隐蔽的概念与下列哪个概念直接相关______。

A.软件结构定义 B.模块独立性

C.模块类型划分 D.模块耦合度面向对象的开发方法中，类与对象的关系是______。

A.具体与抽象 B.抽象与具体

C.整体与部分 D.部分与整体

(A)(D)(B)(B)青岛工学院三、软件工程基础1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。青岛工学院考点点评及考核情况考点点评：该部分内容考核不是很多。相对来说，考核比较多的是第4、5点，且有关白盒测试和黑盒测试的内容是经常考核的。分值情况：所占分值为2-3分。青岛工学院3.1软件工程的基本概念计算机软件是包括程序、数据及相关文档的完整集合。软件的特点包括：（1）软件是一种逻辑实体；（2）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行、使用期间不存在磨损、老化问题；（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵；（6）软件开发涉及诸多的社会因素。软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。青岛工学院软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。软件工程过程是把软件转化为输出的一组彼此相关的资源和活动，包含4种基本活动：（1）P(计划)——软件规格说明； （2）D（执行）——软件开发；（3）C（检查）——软件确认； （4）A（处理）——软件演进。软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。青岛工学院软件生命周期三个阶段:软件定义、软件开发、运行维护（时间最长），主要活动阶段包括：可行性研究和计划制定，需求分析，软件设计，软件实现，软件测试，运行和维护软件生命周期的主要活动阶段为：

（1）可行性研究和计划制定。确定待开发软件系统的开发目标和总的要求，给出它在功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。

（2）需求分析。对待开发软件提出的需求进行分析并给出详细定义，即准确地确定软件系统的功能。编写软件规格说明书及初步的用户手册，提交评审。

（3）软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。

（4）软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。

（5）软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。

（6）运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改。青岛工学院其中，可行性研究的目的就是用最小的代价确定在问题定义阶段确定的目标是否实现。可行性内容包括经济可行性研究、技术可行性研究、法律可行性研究、开发方案的选择性研究。软件设计阶段根据复杂程度可分为概要设计和详细设计两个阶段。整个软件生命周期中，最长的阶段就是使用维护阶段青岛工学院例题在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是______。

A.概要设计 B.详细设计

C.可行性分析 D.需求分析下面不属于软件工程的3个要素的是______。

A.工具B.过程C.方法D.环境软件开发的结构化生命周期方法将软件生命周期划分成______。

A.定义、开发、运行维护

B.设计阶段、编程阶段、测试阶段

C.总体设计、详细设计、编程调试

D.需求分析、功能定义、系统设计

(D)(D)(A)青岛工学院3.2结构化分析方法需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望，需求分析的任务是发现需求、求精、建模和定义需求的过程。需求分析将建立所需的数据模型、功能模型和控制模型需求分析阶段的4个方面工作： 需求获取、需求分析、编写需求规格说明书、需求评审常见的需求分析方法有：（1）结构化需求分析方法：主要有面向数据流的结构化分析方法、面向数据结构的jackson方法和面向数据结构的结构化数据系统开发方法（2）面向对象的分析的方法。青岛工学院结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析的常用工具（1）数据流图； （2）数据字典；（3）判定树； （4）判定表数据流图（DFD）：描述数据处理过程的工具，它以图形的方式描绘数据在系统中流动和处理的过程，它只反应系统必须完成的逻辑功能，所以是一种功能模型。青岛工学院数据字典（DD）：对DD中所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。

数据字典是结构化分析的核心。数据流图和数据字典共同组成系统的逻辑模型。软件需求规格说明书的作用：1、便于用户、开发人员进行理解和交流。2、作为软件开发工作的基础和依据。3、作为确认测试和验收的依据。青岛工学院例题需求分析阶段的任务是确定______。

A.软件开发方法 B.软件开发工具

C.软件开发费用 D.软件系统功能下列不属于结构化分析的常用工具的是______。

A.数据流图 B.数据字典

C.判定树 D.PAD图在数据流图（DFD）中，带有名字的箭头表示______。A.控制程序的执行顺序 B.模块之间的调用关系C.数据的流向 D.程序的组成成分(D)(D)(C)青岛工学院在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是______。A.可行性分析 B.需求分析C.详细设计 D.程序编码下列叙述中，不属于软件需求规格说明书的作用的是______。A.便于用户、开发人员进行理解和交流B.反映出用户问题的结构，可以作为软件开发工作的基础和依据C.作为确认测试和验收的依据D.便于开发人员进行需求分析(B)(D)青岛工学院3.3结构设计方法

软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径。软件设计是确定系统的物理模型。软件设计的基本原理：

抽象、模块化、信息隐蔽和模块独立性模块的独立程度是评价设计好坏的最重要度量标准，衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。结构化设计方法的基本要求是，在详细设计阶段，为了确保模块逻辑清晰，就应该要求所有的模块只使用单入口、单出口以及顺序、选择和循环3种基本控制结构。青岛工学院面向数据流的设计方法，主要是分析信息在系统中加工和流动的情况。典型的数据流类型有两种：变换型和事务型。详细设计：主要确定每个模块具体执行过程，也称过程设计。详细设计的结果基本上决定了最终的程序代码的质量。常见的详细设计工具有：图形工具（程序流程图（PFD）、盒图（N-S）、问题分析图（PAD）和HIPO）表格工具（判定表）语言工具（过程设计语言PDL(伪码)）。青岛工学院例题下列工具中属于需求分析常用工具的是______。A.PAD B.PFDC.N-S D.DFD在进行软件设计时应该遵守的最主要的原理是______。A.抽象 B.模块化 C.模块独立 D.信息隐蔽(D)(C)青岛工学院3.4软件测试软件测试：使用人工或自动手段来运行或测定某个系统的过程，用以检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。软件测试的目的：为发现错误而执行程序的过程。

静态测试：主要通过人工测试。(不用测试实例)

动态测试：利用计算机进行测试。软件测试白盒测试黑盒测试青岛工学院白盒测试（结构测试）：在程序内部进行，主要用于完成软件内部操作的验证，如果想用白盒测试出所有错误，则至少要把所有可能的路径都执行一次。主要方法有逻辑覆盖、基本路径测试。黑盒测试：主要诊断功能错误或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错，用于软件确认。主要方法有等价类划分法、边界值分析法、错误推测法等。软件测试过程一般按4个步骤进行：单元测试：发现各个模块内可能存在的错误，主要依据详细设计说明书和源程序集成测试：发现和接口有关的错误，主要依据概要设计说明书验收测试（确认测试）：运用黑盒测试法验证软件的功能是否满足需求规格说明书的需求，软件配置是否正确、完整。系统测试：在真实的工作环境下检验软件是否正常工作青岛工学院例题在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是______。

A.循环的集合 B.地址的集合

C.路径的集合 D.目标的集合在测试中，下列说法错误的是______。

A.测试是为了发现程序中的错误而执行程序的过程

B.测试为了表明程序的正确性

C.好的测试方案是极可能发现迄今为止尚未发现的错误的测试方案

D.成功的测试是发现了至今尚未发现的错误的测试软件测试基本方法中，下列______不用测试实例。

A.白盒测试 B.动态测试 C.黑盒测试 D.静态测试(C)(B)(D)青岛工学院3.5程序的调试软件测试主要为了发现错误，它的执行贯穿软件生命周期，而程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行；程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。青岛工学院例题

下列不属于软件调试技术的是______。A.强行排错法 B.集成测试法C.回溯法 D.原因排除法软件调试的目的是______。A.发现错误 B.改正错误C.改善软件的性能 D.挖掘软件的潜能(B)(B)青岛工学院四、数据库设计基础数据库、数据库管理系统、数据库系统数据库系统的发展，数据库系统的基本特点，数据库系统的结构体系实体联系模型及E-R图，从E-R图导出关系数据模型集合运算及选择、投影、连接运算，数据规范化理论数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略数据库管理青岛工学院考点点评及考核情况考点点评：该部分内容的重要程度仅次于第一部分，基本上每个考核点在以往考试中都会涉及到，其中，数据模型和关系运算基本上每年都考。分值情况：所占分值为3-5分。青岛工学院本章学习方法

数据库是当前软件处理的信息核心，目前大部分软件都是基于数据库的，因此学习一下数据库知识对程序开发也是很有帮助的。本章主要的考核点是关系模型、关系代数及数据库系统的基本概念，其余的知识点了解即可，其中数据库的设计和管理可以结合着软件工程来看，考生会发现这两者有很多相似之处。除了关系代数会考一些简单的计算问题外，其余的都是以概念题的形式考核，大家需要仔细的阅读。青岛工学院4.1数据库系统的基本概念数据：实际上就是描述事物的符号记录。数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合定型的值。数据库(DB)：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库管理系统(DBMS)：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库系统的核心。青岛工学院数据库管理系统功能：（1）数据模式定义：即为数据库构建其数据框架；（2）数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段；（3）数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计；（4）数据的完整性、安全性定义与检查；（5）数据库的并发控制与故障恢复；（6）数据的服务：如拷贝、转存、重组、性能监测、分析等。为完成以上六个功能，数据库管理系统提供以下的数据语言：（1）数据定义语言(DDL)：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言(DML)：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言(DCL)：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。青岛工学院数据语言按其使用方式具有两种形式：交互式命令(又称自含型或自主型语言)、嵌入式命令（宿主型语言）。数据库管理员（DBA）：对数据库进行规划、设计、维护、监视等的专业管理人员。数据库系统(DBS)：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。数据库应用系统(DBAS)：由数据库系统、应用软件及应用界面三者组成。数据库发展阶段：人工管理阶段文件系统阶段层次与网状数据库系统阶段关系数据库系统阶段数据库应用系统DBAS数据库管理系统DBMS数据库DB数据库系统DBS青岛工学院数据库系统的三级模式：（1）外模式：也称子模式与用户模式。是用户的数据视图。也就是用户所见到的数据模式；(一个数据库可以有多个外模式)(视图)（2）概念模式（逻辑模式或模式）：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图，不涉及具体的硬件和软件环境，一个数据库只有一个概念模式；（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。（索引存取）（一个数据库只有一个内模式）数据库系统的两级映射：（1）外模式到概念模式的映射。（2）概念模式到内模式的映射；青岛工学院例题数据库系统的核心是______。(B)A.数据模型 B.数据库管理系统C.软件工具 D.数据库下列叙述中正确的是______。(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致下列模式中，能够给出数据库物理存储结构与物理存取方法的是______。(A)A.内模式 B.外模式C.概念模式 D.逻辑模式青岛工学院在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是______。

(A)A.数据库系统 B.文件系统C.人工管理 D.数据项管理索引存取属于______。

(B)A.模式 B.内模式 C.外模式 D.概念模式数据处理的最小单位是______。(C)A.数据B.数据元素C.数据项D.数据结构下列有关数据库的描述，正确的是______。(C)A.数据库是一个DBF文件