2025年全国计算机二级备考公共基础知识通关要点梳理

计算机二级公共基本知识

一、数据构造与算法

数据构造指是数据之间互有关系，即数据组织形式。

数据构造用来反应一种数据内部构成，即一种数据由哪些成分构成、以什么

方式构成、展现什么样构造。数据构造有逻辑上数据构造和物

理上数据构造之分。逻辑上数据构造反应数据之间逻辑关系，而物理上

数据构造反应数据在计算机内部存储安排。数据构造是数据存在形式。

算:去是解题环节，是指令有限序列。它们规定理处理某一特定类型问题

一系列运算，是对解题方案精确与完整描述。一种问题处理方案要以算法为基本。

1.1概念简介

♦算法时间复杂度：

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

算法工作量用算法所执行基本运算次数来度量，而算法所执行基本运算次数

是问题规模函数，即

算法工作量二f(n)

其中n是问题规模。

彳列乜口，两个n阶矩阵相乘所需要基本运算(即两个实数乘法)次数为R

即计算T作量为也就是时间复杂度为n3c

♦算法空间复杂度：

算法空间复杂度一般是指执行这个算法所需要内存空间。

♦数据逻辑构造

数据元素互相之间关系，称为构造。

数据逻辑构造：是指反应数据元素之间逻辑关系数据构造。

♦数据存储构造

数据存储构造：是数据逻辑构造在计算机存储空间中存储形式。也称数据物

理构造。

各数据元素在计算机存储空间中位置关系与它们逻辑关系不一定是相似。同

一种数据逻辑构造可以根据需要体现到任意一种或儿种不一样存储构造。

数据次序存储方式：是将逻辑上相邻结点存储在物理位置上亦相邻

存储单元里。也就是将所有存储结点相继存入在一种持续相邻存储区里。

数据链式存储方式：是在存储每个结点信息同步，增长一种指针来

体现结点间逻辑关系。该方式不规定逻辑上相邻结点在物理位置上亦相邻，结点

间逻辑关系是由附加指针字段体现。因而，链式存储构造中每个结点都由两某些

构成：一某些用于存储结点自身信息，称为数据域;另一某些用于存储该结点

后继结点（或前驱结点）存储单兀地址，称为指针域。指针域可以包括一种或多

种指针，这由结点之间关系所决定。

♦线性构造和非线性构造

假如在一种线性构造中，一种数据元素都没有，则称该数据构造为空数据构

造。

线性构造逻辑特性：在一种非空数据构造中，除第一种数据元素只

有一种后继没有前驱、最终一种数据元素只有一种前驱没有后继外，其她每一种

数据元素仅有一种前驱和一种后继。线性构造也称为线性表。

注：某个元素直接相邻前一种元素称为此元素前马区、直接相邻后一种元素

称为此元素后乡能。

非线性构造逻辑特性：在一种非空数据构造中，某数据元素也许有

多于一种前驱或后继。如树型构造等。

习题：

（一）选用题（单项选择）

1.算法时间复杂度是指（D）

A）算法执行时间

B）算法所处理数据量

0算法程序中语句或指令条数

D）算法在执行过程中所需要基本运算次数

1.2线性表

线性表是由同一类型数据元素构成一种线性数据构造。是一种最基本、最常

用数据构造。线性表常用存储方式有两种：次序存储方式和链接存储方式。

线性表数学定义：

L二(ai,a2,a3,...,an)

阐明：

线性表是具有相似类型n(n20)个数据元素构成有限序列。

L：为表名称。

ai(i=l,2,为表元素，也称为线性表中一种结点。它可以是一种数、一

种字符、一种字符串，也可以是一条记录，还可以是复杂数据对象。ai是a2前

驱、az是ai后继，a2是a3前驱、a3是az后继，…，依次类推。

n：为线性表长度(元素个数)，当n=0时称线性表为空表。

线性表特点：

在非空线性表中：存在唯一一种“第一种元素”(根结点)。存在唯一一种“最

终一种元素”(终端结点)。除第一种元素外，其她元素均有唯一前驱。除最终一

种元素外，其她元素均有唯一后继。

1.3栈和队列

栈和队列本质上也是线性表，只是它们操作受到了限制。

1.3.1栈

栈是限定仅在表尾进行插入和删除操作线性表。表尾称为栈顶(top),表头

称为栈底(bonom)。

栈这种数据构造，类似于子弹夹，底端是封闭，最终压入子弹总是最先被弹出，

最先压入子弹只能最终被弹出。

栈顶元素总是最终被插入元素，从而也是最先能被删除元素；栈底元素总是

最先被插入元素，从而也是最终能被删除元素。即栈是按照“先进后出”或“后

进先出”原则组织数据。因而，栈也被称为“先进后出”表或“后

进先出”表。由此可以看出，栈具有记忆作用。

1.3.2队歹U

队列是指只容许在表一端插入元素、在另一端删除元素线性表。容许插入一端称

为队尾(rear),容许删除一端称为队头(front)。

在队列这种数据构造中，最先插入元素将最先可以被删除，反之最终插入元素将

最终才能被删除。因而，队列又称为“先进先出”或“后进后出”

线性表。

1.4树和二叉树

1.4.1树

树形构造是数据构造中一种很重要非线性构造。在树形构造中，所有数据元

素之间关系具有明显层次特性。树形构造很像自然界中树，像一棵倒长树。在现

实生活中，能用树形构造体现例子诸多。参见下面图形：

树形构造基本特性及基本术语:

如下图为例:

树根：

在树形构造中，没有前驱结点只有i种，称为树根结点，简称为树根。如:

上图中“R”。

父结点：

在树形构造中，每一种结点（除了树根结点）只有一种前驱，称为父结点C

如：上图中“R”是K、P、Q、D父结点；是X、Y父结点。

子结点:

在树形构造中，每个结点可以有多种后继，称为该结点子结点。

如：上图中K、P、Q、D是“R”子结点；X、Y是“N”子结点。

叶子结点：

在树形构造中，没有后继结点称为叶子结点，也称终端结点。

如：上图中C、M、F、E、X、G、S、L、Z、A均为叶子结点。

结点度：

在树形构造中，一种结点所拥有后继个数称为该结点度。

如：上图中根结点R度是4；结点T度是3；结点P、Q、D、O、Y、W度

都为1。叶子结点度为0。

树度：

在树形构造中，所有结点中最大度称为树度.如：上图中树度为4,由于结

点R度最大，是4。

树■深度：

在树形构造中，树最大层数称为树深度（或高度）。如：上图中树深度是5o

阐明：树形构造具有明显层次关系，即树是一种层次构造。在树形构造中一

般按如下原则分层：

1）根结点在第1层。

2）别的结点层数等于其父结点层数加1。

子树：

在树形结中，以某结点一种子结点为根构成树称为该结点一棵子树。

如：上图中，结点R有4棵子树，它们分别以K、P、Q、D为根结点；结点P

有1棵子树，其根结点为N：结点T有3棵子树，它们分别以W、Z、A为根结

点。

在树形构造中，子树间互不相交，叶子结点没有子树。

森林：

森林是M(M20)棵互不相交树集合。删去一棵树根，就得到一种森林；反

之，加上一种结点作树根，森林就变为一棵树。

1.4.2二叉树

(1)二叉树特点

①非空二叉树只有一种根结点。

②二叉树中每个结点，最多有两棵子树，分另称为该结点左子树与右子树。

当一种结点即没有左子树也没有右子树时，该结点就是叶子结点。在下面图中，

左面是只有根结点二叉树，右面是深度为4二叉树：

(2)满二叉树与完全二叉树

1)满二叉树:

满二叉树是指除最终一层外，每一层上所有结点均有两个子结点。

就是说，在满二叉树中，每一层上结点数都到达最大值，即在满二叉树第k

层上有2"1<21)个结点，且深度为k满二叉树有2k-1(k,1)个结点。

在下图中分别是深度为2、3、4满二叉树:

(a)深度为2的满二叉树(b)深度为3的满二叉树(c)深度为4的满二叉树

图1,32满二叉树

满二叉树中不存在度数为1结点，每个分支结点均有两棵深度相似子树，且叶子

结点都在最下一层。

2)完全二叉树：

若一棵二叉树最多只有最下面两层上结点度数可以不不小于2,并且最下一

层上所有结点都集中在该层最左边若干位置上，则此二又树称为完全二叉树。

在下图4棵二叉树中，分别是深度为3和4完全二叉树:

C)深度为3的完全二叉树(b)深度为4的完全二又利

图L33完全二叉归

满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

在满二叉树最下一层上，从最右边开始持续删去若干结点后得到二叉树仍然是一

棵完全二义树。

在完全二叉树中，若某个结点没有左子结点，则它一定没有右子结点，即该

结点必是叶子结点。

（3）二叉树性质

假设定义根结点层数为1（注意：有些资料中规定根结点层数为（））。

性质1：在二叉树第i层上，最多有2i7（i21）个结点。

性质2：深度为k二叉树最多有2k-1（k、1）个结点“

性质3：在任意二叉树中，若度为0结点（即叶子结点）个数为no,度为2结

点个数为m，则：n0=n2+1

（对于完全二叉树尚有如下属性）

性质4：具有n个结点完全二叉树，其深度为[Iog2n]+1。注:|log2n|

体现取log2n整数某些。性质5：假如将一棵有n个结点完全二又树自顶向下、

同一层自左向右持续给结点编号1、2、3、…、n,则对于任意结点i（l这iW

n）有如下结论：

1）假如=1,此结点为根结点，无前驱（即无父结点）；

假如>1,则该结点父结点编号为lnt（i/2）。也可体现到[i/2],都体

现取整数。

2）假如2i>n,则结点i无左子结点，显然也没有右子结点，是叶子结点。

假如2iWn,则结点i左子结点是编号为2i结点。

3）假如2i+l〉n,则结点i无右子结点。

假如2i+lWn,则结点i右子结点编号为2i+1。

(4)二叉树遍历

二叉树遍历就是遵从某种次序，访问二叉树中所有结点，使得每个结点仅被

访问一次。

一棵非空二叉树是由根结点、左子树和右子树三某些构成。因而遍历一棵非

空二叉树问题就可以分解为三项“子任条”：

①访问根结点(假设用D体现)。

②遍历左子树(假设用L体现)。

③遍历右子树(假设用R体现)。

在遍历二叉树过程中，一般先遍历左子树，然后再遍历右子树。在先左后右

原则下，根据访问根结点次序，二叉树遍历可分为三种：前序遍历(DLR)、中序

遍历(LDR)、后序遍历(LRD)。

如下图中二叉树为例：

前序遍历(DLR)：

首先访问根结点，然后遍历左子树，最终遍历右子树。在遍历左、右子树时,

仍然先访问子树根结点，然后遍历其左子树，最终遍历其右子树。即，前序遍历

是指访问所有根结点（波及子树根结点）都在遍历其左、右子树之前。

前序遍历操作：

若二叉树为空，则结束反返回。否则：

①访问根结点

②前序遍历左子树

③前序遍历右子树

如，对上图中二叉树进行前序遍历成果是：FCADBEGHP

中序遍历（LDR）:

首先遍历左子树，然后访问根结点，最终遍历右子树。在遍历

左、右子树时，仍然先遍历其左子树，然后访问子树根结点，最终遍历其右子树。

即，中序遍历是指访问所有根结点（波及子树根结点）都在遍历其左子树之后、在

遍历其右子树之前。

中序遍历操作：

若二叉树为空，则结束反返回。否则：

①中序遍历左子树

②访问根结点

③中序遍历右子树

如，对上图中二叉树进行中序遍历成果是：ACBDFEHGP

后序遍历（LRD）：

首先遍历左子树，然后遍历右子树，最终访问根结点。

在遍历左、右子树时，仍然先遍历其左子树，然后遍历其右子树，最终访问子树

根结点。即，后序遍历是指访问所有根结点（波及子树根结点）都在遍历其左、右

子树之后。

后序遍历操作:

若二叉树为空，则结束反返回。否则：

①后序遍历左子树

②后序遍历右子树

©访问根结点

如，对上图中二叉树进行后序遍历成果是：ABDCHPGEF

1.5查找

查找又称检索。查找是指在一种给定数据构造中查找某个指定元素。一般，

根据不一样数据构造，应采用不一样查找措施。

1.5.1次序查找

次序查找乂称次序搜索或线性查找。次序查找一般是指在线性表中查找指定

元素。

次序查找基本思想：

在n个结点构成线性表中，从线性表一端开始，依次将线性表中元素与被查

元素进行比较，若相等则体现找到，即查找成功；若线性表中所有元素都与被杳

元素进行了比较但都不相等，则体现线性表中没有要找元素，即查找失败。

在次序查找中，查找成功时最多需要比较n次、至少比

较1次、平均比较次数约为表长二分之一。查找失败时比较

n+1次。

次序查找时间复杂度为0（n）。

对于无序表（即表中元素排列是无序）和链式存储构造线性表（有序和无序），

只能用次序查找。

次序查找长处：

算法简朴而合用范围广。对表中元素排列次序无规定，既可以是按关键字排

列有序表，也可以是无序表；对表存储构造也无任何规定，既合用于次序存储次

序表，也合用于链接存储链表。

次序查找缺陷：

查找效率低，平均查找长度较大。当n很大时不合适采用次序查找。

1.5.2二分查找

二分查找乂称折半查找。它是一种查找效率较高查找措施。该措施只合用于

次序存储构造有序表。一般是指有序表中元素按值升序排列(非递减有序排列)。

二分查找不能用于链式存储构造线性表。

二分查找基本思想：参见“C语言程序设计”或“VB程序设计”课件对应

内容动画。

对于长度为n有序线性表，查找成功时最多需要比

较Iog2(n+1)次、至少比较1次、平均查找长度近似

Iog2no当查找失败时,比较log2n或Iog2(n+1)次。

不管二分查找成功与否，其时间复杂度均为

0(log2n)o

二分查找最坏性能和平均性能相称靠近。

1.6排序

排序就是将文献中记录进行整顿，使之按照关键字进行递增或递减次序排列

起来，成为一种有序序列过程。在本节所简介排序措施中，其排序对象一般认为

是次序存储线性表，在程序设计语言中就是一维数组。

这里排序算法，都是针对升序排序。

161互换排序

互换排序是两两比较待排序记录关键字，若发现两个记录关键字次序相反时

即进行互换，直到没有反序记录为止。下面简介两种常用互换排序。

(1)冒泡排序

冒泡排序基本思想：参见“C语言程序设计”或“VB程序设计”课件对应

内容动画。

对于长度为n线性表，在最坏状况下，冒泡排序需

要通过n/2遍扫描，比较次数为n(n-1)/2。

冒泡排序算法平均时间复杂度为0(n2),空间复

杂度为0(1)。

(2)迅速排序

迅速排序基本思想：

参见下图:

分割

WT----------

分割-----(

--------►T

一^1.分割

2T---------

快速排序示意图

从线性表中选用一种元素，设为T,将线性表背面不不小于T元素移到前面,

将线性表前面不不不小于T元素移到背面，成果就把线性表提成了两某些(称为

两个子表)，T插入到其分界线位置处，这个过程称为线性表分割。通过对线性

表一次分割，就以T为分界线，将线性表提成了先后两个子表，且前面子表中所

有元素均不不不不小于T,背面子表中所有元素均不不不小于To

假如对分割后各子表再按上述原则进行分割，并且这种分割过程可以一直做

下去，伴随对各子表不停地进行分割，划分出子表会越来越多(一次只能对一种

了表进行再分割处理)，直到所有了表中元素都排好序为止，则此时线性表就变

成了有序表。

对于长度为n线性表：

在最坏状况下，迅速排序比较次数为n(n7)/2。算法

时间复杂度为0(n2),空间复杂度为0(n)。

在最佳状况下，迅速排序算法时间复杂度为

0(nlog2n),空间复杂度为0(Iog2n)。

迅速排序算法平均时间复杂度是0(nlog2n),平均比

较次数不不不不小于(n+1)Iog2n

1.6.2插入排序

插入排序是每次将一种待排序记录按其关键字大小，插入到前面已排好序列

中恰当位置，直到所有记录插入为止。

(1)直接插入排序

迅速排序基本思想：请查看有关资料。

对于长度为n线性表：

在最坏状况下，直接插入排序比较次数为n(n-1)/2o

算法时间复杂度为0S2)。

(2)希尔排序

希尔排序基本思想：请查看有关资料。

对于长度为n线性表：

在最坏状况下希尔排序比较次数为0(n1.5)。

1.63选用排序

选用排序基本思想是：每一遍在n-i+l(i=l,2,…,n-1)个待排序记录中选用关键

字最小记录作为有序序列中第i个记录，直到所有记录排完为止。

(1)直接选用排序

选用排序基本思想：参见“C语言程序设计”或“VB程序设计”课件对应

内容动画。

在最坏状况下，直接选用排序比较次数为

n(n-1)/2o

(2)堆排序

希尔排序基本思想：请查看有关资料。

在最坏状况下，堆排序比较次数为0（nlog2n）。

习题：

（一）选用题（单项选择）

1.下列论述中对的是（D）

A）栈是“先进先出”线性表

B）队列是“先进后出”线性表

C）循环队列是非线性构造

D）有序线性表既可以采用次序存储构造，也可以采用链式存储构造

2.下列有关栈论述中对的是（A）

A）栈顶元素最先被删除B）栈顶元素最终才能被删除

C）栈底元素永远不能被删除D）以上三种说法都不对

3.下列论述中对的是（B）

A）有一种以上根结点数据构造不一定是非线性构造

B）只有一种根结点数据构造不一定是线性构造

0循环链表是非线性构造

D）双向链表是非线性构造

4.支持子程序调用数据构造是（A）

A）栈B）树C）队列D）二叉树

5.某二又树有5个度为2结点，则该二叉树中叶子结点数是（C）

A）10B）8C）6D）4

提醒：在任意二叉树中，若度为。结点（即叶子结点）个数为n0,度为2结点个数为n2,则：

n0=n2+l即n0（叶子结点数）=5+1=6

6.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树深度为（假设根结点在第一

层）（D）

A）3B）4C）6D）7

7.下列排序措施中，最坏状况下比较次数至少是（D）

A）冒泡排序B）简朴选用排序C）直接插入排序D）堆排序

8.下列论述中对的是（A）

A）对长度为n有序链表进行查找，最坏状况下需要比较次数为n

B）对长度为n有序链表进行对分查找，最坏状况下需要比较次数为（n/2）

0对长度为n有序链表进行对分查找，最坏状况下需要比较次数为（logzn）

D）对长度为n有序链表进行对分查找，最坏状况下需要比较次数为（nlogzn）

（二）填空题

I.假设用一种长度为50数组（数组元素下标从。到49）作为栈存储空间，栈底指针bottom

指向栈底元素，栈顶指针top指向栈顶元素，假如botk）m=49,top=30（数组卜标），则栈中具

有个元素。

答案：20

2.一种队列初始状态为空.现将元素A、B、C、D、E、P、5、4、3、2、1一次入队，然后

再一次退队，则元素退队次序为O

答案：A、B、C、D、E、F、5、4、3、2、1

3.设某循环队列容量为50,假如头指针front=45（指向队头元素前一种位置）,尾指针

rear=10（指向队尾元素），则该循环队列中共有个元素。

答案：15

4.设二叉树如下：

对该二叉树进行后序遍历成果为。

答案：E、D、B、G、H、F、C、A

5.一棵二叉树中序遍历成果为DBEAFC,前序遍历成果为ABDECF,则后序遍

历成果为。

答案：DEBFCA

6.有序线性表能进行二分查找前提是该线性表必要是存储。

答案：次序

二、软件工程基本

计算机软件是计算机系统中与硬件互相依存另一某些，是波及程序、数据及

有关文档完整集合.

软件由两某些构成：一是机器可执行程序和数据；二是机器不可执行，与软

件开发、运行、维护、使用等有关文档。

软件分类

软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）。

应用软件：是为处理特定领域应用而开发软件。

系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机顾客提

供多种服务软件。

支撑软件：是介于系统软件和应用软件之间，协助顾客开发软件工具性软件。

软件生命周期

一般将软件产品从提出、实现、使用维护到停止使用退伍过程称为软件生命

周期。参见下图:

构造化分析措施

构造化分析常用工具：

数据流图(DFD)：是描述数据处理过程工具，是需求理解逻辑模型图形体现,

它直接支持系统功能建模。

数据字典(DD)：是构造化分析措施关键。

鉴定树

鉴定表

构造化设计措施

常用过程设计工具：

图形工具：程序流程图，N-S图，PAD图（问题分析图），HIPO

表格工具：鉴定表。

语言工具：PDL（伪码）

软件设计基本原理

1）抽象：是一种思维工具，就是把事物本质共同特性提取出来而不考虑其

她细节。

2）模块化：是指把一种待开发软件分解成若干小简朴某些。如高档语言中

过程、函数、子程序等。每个模块可以完毕一种特定子功能，各个模块可以按一

定措施组装起来成为一种整体，从而实现整个系统功能。

3）信息隐蔽：是指在一种模块内包括信息（过程或数据），对于不需要这些信

息其她模块来说是不能访问。

4）模块独立性：是指每个模块只完毕系统规定独立子功能，并且与其她模块联

络至少且接口简朴。模块独立程度是评价设计好坏重要度量原则。衡量软件

模块独立性使月耦合性和内聚性两个定性度量原则。

内聚性：是一种模块内部各个元素间彼此结合紧密程度度量。内聚是从功能

角度来度量模块内联络。

内聚性是信息隐蔽和局部化概念自然扩展。一种模块内聚性越强则该模块模

块独立性越强。作为软件构造设计设计原则，规定每一种模块内部都具有很强内

聚性，它各个构成某些彼此都亲密有关。

耦合性：耦合性是模块间互相连接紧密程度度量。

一种模块与其她模块耦合性越强则该模块模块独立性越弱。原则上讲，模块

化设计总是但愿模块间耦合体现为非直接耦合方式。不过，由于问题所固有复杂

性和构造化设计原则，非直接耦合往往是不存在。

耦合性与内聚性是模块独立性两个定性原则，耦合性与内聚性是互相联络。

在程序构造中，各模块内聚性越强，则耦合性越弱。一般先进软件设计，应尽量

做到高内聚，低耦合，即减弱模块之间耦合性和提高模块内内聚性，有助于提高

模块独立性。

软件测试

软件测试是在软件投入运行前对软件需求、设计、编码最终审核。软件测试

是为了发现错误而执行程序过程。软件测试应当制定明确测试筹划并按筹划执

行。

软件测试目：是发现错误。

软件测试措施和技术：若从与否需要执行被测软件角度，可以分为静态测试

和动态测试措施。若按照功能划分可以分为白盒测试和黑盒测试措施。

静态测试：波及代码检查、静态构造分析、代码质量度量等。静态测试不实

际运行软件，重要通过人工进行。

动态测试：是基于计算机测试，是为了发现铛误而执行程序过程。需要精心

设计一批测试用例，并运用这些测试用例去运行程序，以发现程序错误过程。测

试用例格式为:

［（输入值集）,（输出值集）］

白盒测试：也称构造测试或逻辑驱动测试。它是根据软件产品内部工作过程,

检查内部成分，以确认每种内部操作符合设计规格规定。白盒测试把测试对象看

作一种打开盒子，容许测试人员运用程序内部逻辑构造及有关信息来设计或选用

测试用例，对程序所有逻辑途径进行测试。通过在不一样点检查程序状态来理解

实际运行状态与否与预期一致。因此，白盒测试是在程序内部进行，重要用于完

毕软件内部操作验证。

白盒测试重要措施有逻辑覆盖、基本途径测试等。

黑盒测试：也称功能测试或数据驱动测试。黑盒测试是对软件已经实现功能

与否满足需求进行测试和验证。黑盒测试完全不考虑程序内部逻辑构造和内部特

性，只根据程序需求和功能规格阐明，检查程序功能与否符合它功能阐明。因此,

黑盒测试是在软件接口处进行，完毕功能验证。黑盒测试只检查程序功能与否按

照需求规格阐明书规定正常使用，程序与否能恰当地接受输入数据而产生对的输

出信息，并且保持外部信息（如数据库或文献）完整性。

黑盒测试重要诊断功能不对或遗漏、界面错误、数据构造或外部数据库访问

错误、性能错误、初始化和终止条件错误。黑盒测试措施重要有等价类划分法、

边界值分析法、错误推测法、因果图等，重要用于软件确认测试。

程序调试

在对程序进行了成功测试之后，将进入程序调试（一般称Debug,即排错）。

程序调试任务是诊断和改正程序中错误。

它与软件测试不一样，软件测试是尽量多地发现软件中错误，

并找出软件错误详细位置。软件测试贯穿整个软件生

命期，调试重要在开发阶段。

习题：

（一）选用题（单项选择）

1.软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。下面属于应用软

件是（C）

A）编译程序B）操作系统C）教务管理系统D）汇编程序

2.软件按功能可分为：应用软件、系统软件、和支撑软件（或工具软件）。卜.面属于系统软

件是（B）

A）编辑软件B）操作系统C）教务管理系统D）浏览器、

3.软件（程序）调试任务是（A）

A）诊断和改正程序中错误B）尽量多发现程序中错误

0发现并改正程序中所有错误D）确定程序中错误性质

4.下面论述中错误是（A）

A）软件测试目是发现错误并改正错误

B）对被调试程序进行“错误定位”是程序调试必要环节

C）程序调试一般也称为Debug

D）软件测试应严格执行测试筹划，排除测试随意性

5.耦合性和内聚性是对模块独立性度量两个原则。下列论述中对的是（B）

提高耦合性、减少内聚性有助干提高模块独立?性

B）减少耦合性、提高内聚性有助于提高模块独立性

C）耦合性是指一种模块内部各个元素间彼此结合紧密程度

D）内聚性是指模块间互相连接紧密程度

6.数据流图（DFD图）是（C）

A）软件概要设计工具B）软件详细设计工具

0构造化措施需求分析工具D）面向对象措施需求分析工具

7.软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于（B）

A）定义阶段B）开发阶段C）维护阶段D）上述三个阶段

8.在软件开发中，需求分析阶段产生重要文档是（D）

A）软件集成测试筹划3）软件详细设计阐明书C；顾客手册D）软件需求规格阐

明书

9.构造化程序所规定基本构造不波及（B）

A）次序构造B）GOTO跳转C）选用（分支）构造D）反复（循环）构造

10.下面描述中错误是（A）

A）系统总体构造图支持软件系统详细设计

B）软件设计是将软件需求转换为软件体现过程

0数据构造与数据库设计是软件设计任务之•

D）PAD图是软件详细设计体现工具

（二）填空题

1.软件测试可分为白盒测试和黑盒测试。基本途径测试属于测试。

答案：白盒

2.符合构造化原则三种基本控制构造是：选用构造、循环构造和o

答案：次序构造

3.软件是、数据和文档集合。

答案：程序

4.对软件设计最小单位(模块或程序单元)进行测试一般为测试。

答案：单元或模块

三、数据库设计基本

计算机应用三大领域：科学计算、数据处理、过程控制。

数据库系统基本概念

数据(Data)：就是描述事物符号记录。

数据库(DB)：是数据集合，它具有统一构造形式并存储于统一存储介质内，

是多种应用数据集成，并可被各个应用程序所共享。数据库中数据具有“集成”、

“共享”特点。

数据库管理系统(DBMS)：是数据库机构，是一种系统软件，负责数据库中

数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是

数据库系统关键。

数据库管理系统一般提供对应数据语言(DataLanguage)来完毕对应功能：

数据定义语言(DDL)：负责数据模式定义与数据物理存取构建。

数据操纵语言(DML)：负责数据操纵，波及查询及增、册h改等操作。

数据控制语言(DCL)：负责数据完整性、安全性定义与检查以及并发控制、

故障恢复等功能，波及系统初启程序、文献读写与维护程序、存取途径管理程序、

缓冲区管理程序、安全性控制程序、完整性检查程序、并发控制程序、事务管理

程序、运行日志管理程序、数据库恢复程序等。

数据库管理员(DBA)：由于数据库共享性，因而对数据库规划、设计、维护、

监视等需要有专人管理，称她们为数据库管理员。

数据库系统(DBS)：由数据库(数据)、数据库管理系统(软件)、数据库管理员

(人员)、系统硬件平台(硬件)、系统软件平台(软件)这五某些构成，称为数据库系

统。

数据库应用系统(DBAS)：是数据库系统再加上应用软件及应用界面这三者

所构成。

E-R模型

该模型将现实世界规定转化成实体、联络、属性等几种基本概念，以及它们

间两种基本联接关系，并且可以用一种图非常直观地体现出来。下面是E-R模型

基本概念。

目前较为有名概念模型有E-R模型、扩充E-R模型、面向对象模型及谓词

模型等。

实体：现实世界中事物可以抽象成为实体。实体是概念世界中基本单位，它

们是客观存在且又互相区别事物。但凡有共性实体可构成一种集合称实体集。如

学生A和学生B,她们都是实体，她们又都是学生，从而构成一种学生实体集。

属性：现实世界中事物均有某些特性，这些特性可以用属性来体现。属性刻

画了实体特性。一种实体往往可以有若干个属性。

联络；现实世界中事物问美联称为联络。在概念世界中联络反应了实体集问

一定关系。如工人与设备间操作关系，上、下级间领导关系等。

实体集间联络有多种，就实体集个数而言有：

1)两个实体集间联络。

2)多种实体集间联络。

3)一种实体集内部联络：是一种实体集内不一样实体间联络。

实体集间联络个数可以是单个也可以是多种，波及：

一对一联络，简记为1:1

一对多或多对一联络，简记为1:M或M:1(其中M也可以小写)

多对多联络，简记为M:N或m:n

E-R模型由上面三个基本概念构成。由实体、联络、属性三者结合起来才能

体现现实世界。

E・R图：E-R模型可以用一种非常直观图形式体现，这种图称为E-R图。在

E-R图中咱们分别用下面不一样几何图形体现E-R模型中三个概念与两个联接关

系。

1)实体集体现法

用矩形体现实体集，在矩形内写上该实体集名字。如实体集学生(student)、

课程(course)可体现为:

studentcourse

实体集表示法

2)属性体现法

用椭圆形体现属性，在椭圆形内写上该属性名称。如学生有属性：学号(S#)、

姓名(Sn)及年龄(Sa),可体现为：

属性表示法

3)联络体现法

用菱形体现联络，在菱形内写上联络名。如学生与课程间联络SC,可体现

为：

上面是三个基本概念分别用三种几何图形体现。下面是它们之间联接关系图形体

现。

4)实体集或联络与属性间联接关系

属性依附于实体集，属性也依附于联络，因而它们之间分别有联接关系。参

见下图:

其中：C#（课程号）、Cn（课程名）、P#（预修课号）

5）实体集与联络间联接关系

如下图体现实体集与联络间联接关系:

实体集与联系间的联接关系

还可以在线段边上注明其对应函数关系，如等。下图体现studenl

FPU是一种三元联络（工厂、产品与顾客间联络）:

(a)图：企业职工(enployee)间上、下级管理(manage)联络。即一种实体集内

部可以有多种联络。

(b)图：教师(T)与学生(S)之间可以有教学(E)联络也可以有管理(M)联络。即

实体集间可以有多种联络。

下面是E-R图一种实例图

关系模型

关系模型采用二维表来体现，简称表。

二维表由表框架(Frame)及表元组(Tuple)构成。表框架由n个命名属性

(Attribute)构成，n称为属性元数(Arity)。每个属性有一,种取值范围，称为值域

(Domain)o表框架对应了关系模式，即类型概念。

在表框架中按行可以存储数据，每行数据称为元组，实际上，一种元组是由

n个元组分量所构成，每个元组分量是表框架中每个属性投影值。一种表框架可

以存储m个元组，m称为表基数(Cardinality)。

一种n元表框架及框架内m个元组构成了一种完整二维表。

关系框架与关系元组构成了一种关系。一种语义有关关系集合构成一种关

系数据库。关系框架称为关系模式，而语义有关美系模式集合构成了关系数据库

模式。

满足下面7个性质二维表称为关系(Relation)：

1)元组个数有限性：二维表中元组个数是有限。

2)元组惟一性：二维表中元组均不相似。

3)元组次序无关性：二维表中元组次序可以任意互换。

4)元组分量原子性：二维表中元组分量是不可分割基本数据项。

5)属性名惟一性：二维表中属性名各不相似。

6)属性次序无关性：二维表中属性与次序无关，可任意互换。

7)分量值域同一性：二维表属性分量具有与该属性相似值域。

以二维表(美系)为基本构造所建立模型称为关系模型。

在关系模型中一和重要概念是键(Key)或码。键具有标识元组、建立元组间

联络等重要作用。

键或码：在二维表中凡能惟一标识元组最小属性集称为该表键或码。

候选键或候选码：二维表中也许有若干个键，它们称为该表候选键(Candidata

Key)或候选码。

主键或主码：从二维表所有候选键中选用一种作为顾客使用键，称为主键

(PrimaryKey)或主码。一般主键也简称为键或码。

外键或外码：表A中某属性集是某表B键，则称该属性集为A外键(Foreign

Key)或外码。

表中一定要有键，由于假如表中所有属性子集均不是键，则表中属性全集必

为键(称为全键)，因而也一定有主键。

在关系元组分量中容许出现空值(NunValue)以体现信息空缺。空值用于体现

未知值或不也许出现值，一般用NULL体现。一般关系数据库系统都支持空值,

不过有两个限制：关系主键中不容许出现空值，由于如主键为空值则失去了其兀

组标识作用；需要定义有关空值运算。

关系代数

关第代数是有关关系数据库理论。

数据库设计与管理

数据库设计是数据库应用关键。

数据库设计四个阶段，参见下图:

DBMS模独

DBMS条凭

硬件、OS支屋

数据库设计的四个阶段

从E-R图向关系模式转换

参见下表:

E-R模型与关系间的比较表

E-R模型

关系E-R模型关系

属性

属性实体张关系

实体

元组联系关系

习题：

（一）选用题（单项选择）

1.数据库应用系统中关键问题是（A）

A）数据库设计B）数据废系统设计C）数据库维护D）数据库管理员培训

2.将E-R图转换为关系模式时，实体和联络都可以体现为（C）

A）属性B）键C）关系D）域

3.负责数据库中查询操作数据库语言是（C）

A）数据定义语言B）数据管理语言0数据操纵语言D）数据控制语言

4.数据库管理系统中负责数据模式定义语言是（A）

A