国二公共基础知识

公共基础知识算法与数据结构程序设计基础软件工程数据库基础1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．查找6．排序第一章算法与数据结构一、算法的基本概念

1、算法：解题方案的准确而完整的描述，包括解决问题的方法和步骤

。

算法≠程序≠计算方法

2、算法的基本特征：⑴可行性：算法中描述的操作都是可以通过已经实现的基本运算的有限次数来实现

⑵确定性：算法的每个步骤必须明确定义，不允许有多义性。⑶有穷性：指算法必须能在有限的时间内做完(即算法的运行时间有限)。⑷拥有足够的情报：指运算对象的初始输入要完备且正确1.1算法二、算法复杂度1、时间复杂度：执行算法所需要的计算工作量2、空间复杂度：执行算法所需要的内存空间（存储空间）。注意：1）时间复杂度通过算法所执行的基本运算次数来度量

2）空间复杂度的内存空间主要用于：内存空间算法程序初始数据运行过程中所需的额外空间执行过程的工作单元附加空间3）时间复杂度和空间复杂度不相关4）算法的效率与问题的规模和数据的存储结构都是息息相关的。算法习题(1)算法是指（）A.查询方法B.交工方法C.解题方案的准确而完整的描述D.排序方法(2)算法的有穷性是指：A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法程序只能被有限的用户使用(3)算法的时间复杂度是指（）A.算法的执行时间

B.算法所处理的数据量C.算法程序中的语句或指令数

D.算法在执行过程中所需要的基本运算次数(4)下列叙述中正确的是（）A.一个算法的空间复杂度大，则其时间复杂度也必定大B.一个算法的空间复杂度大，则其时间复杂度也必定小C.一个算法的时间复杂度大，则其空间复杂度也必定大D.上述三种说法都不对1.2数据结构一、数据结构的基本概念1、数据结构：是抽象地研究数据的组织形式及其相互关系的一门学科。

数据的结构分为：

（1）物理结构：也被称为“存储结构”，是指数据在计算机存储介质中真正存储的结构。

（2）逻辑结构：反映数据元素之间逻辑关系的数据结构2、数据结构研究的主要内容：逻辑结构、物理结构（即存储结构）和算法。注意：逻辑结构和物理结构没有必然的联系，也不一定是一一对应的。二、数据的逻辑结构：

反映数据元素之间逻辑关系的数据结构。1、线性结构：⑴有且仅有一个根结点⑵每个结点最多只有一个前件，也最多只有一个后件。例如：主要有线性表、栈、队列、串等。

前后件关系2、非线性结构：该结构中一个结点可能有多个前件或后件。主要有树和图等。FCEGDABPH三、数据的存储结构指数据的逻辑结构在计算机存储空间中的存放形式（逻辑结构在计算机中的表示）1、顺序存储：逻辑上相邻的数据元素，在物理存储位置上也相邻。2、链式存储：逻辑上相邻的元素其物理位置不一定相邻，元素间的逻辑关系由附加的指针字段表示。注意：1）一种逻辑结构可以表示成多种存储结构

2）存储结构影响数据处理的效率例题：下列叙述中正确的是：A、程序执行效率与数据的存储结构密切相关B、程序执行效率只取决于程序的控制结构C、程序执行效率只取决于所处理的数据量D、以上三种说法都不对1.3、线性表1、线性表的定义线性表是n（n≥0）个数据元素a1，a2，……，an

的有序集合。线性表是一种线性结构，每个元素在表中的位置仅取决于元素本身的序号。n为线性表的长度，n为0的表称为空表。学号姓名语文数学计算机980001张三708069980002吴军897698980003王平878776980004李帆768689无后件无前件a1a2a3…aiai+1…an…特点：⑴线性表中所有元素所占的存储空间是连续的⑵线性表中各数据元素在存储空间中是按照逻辑顺序依次存放的⑶可以随机访问

缺点：插入和删除运算不方便；由于要求占用连续的存储空间，存储分配只能预先进行2、线性表的存储结构（1）线性表的顺序存储结构：当线性表采用顺序存储结构时，称之为顺序表。即用一组地址连续的存储单元依次存放线性表的数据元素。在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。⑴顺序表的插入：要在第i(1≤i≤n)个元素之前插入一个新元素时，需要移动n-i+1个元素⑵顺序表的删除：要删除第i(1≤i≤n)个元素时，需要移动n-i个元素真题：下列有关顺序存储结构的叙述中，不正确的是：

A、存储密度大

B、逻辑上相邻的结点物理上不必邻接

C、可以通过计算机直接确定第i个结点的存储地址

D、插入、删除操作不方便

用一组任意的存储单元（可以是连续的，也可以不连续）来存储线性表的各个数据元素。数据元素（称为结点）的存储结构由两部分组成：一部分用于存储数据元素本身的信息（称为数据域），另一部分用于存储直接后继的存储位置（称为指针域）,如下图所示：3、线性表的链式存储结构特点：①元素的存储空间可以连续，也可以不连续②元素的逻辑关系通过链结点的指针反映。③顺序访问

ABC…

…NULLhead注：分单向、双向和循环链表ABC…

…headABC…

…NULLhead循环链表：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。双向链表特点：在双向链表的结点中有两个指针域，其一指向前件，另一指向后件。真题：1、下列叙述中正确的是：

A、线性表的链式存储结构与顺序存储结构所需存储空间相同

B、线性表的链式存储结构所需存储空间一般多于顺序存储结构

C、线性表的链式存储结构所需存储空间一般少于顺序存储结构

D、以上三种说法都不对2、下列叙述中正确的是：A、有一个以上根结点的数据结构不一定是非线性结构B、只有一个根结点的数据结构不一定是线性结构C、循环链表是非线性结构D、双向链表是非线性结构3、在一个长度为n的顺序表中，在第i个元素的位置插入一个新元素，需要向后移动

个元素。4、在长度为n的顺序表中插入一个元素，最坏情况下要移动表中

个元素。5、下列叙述中正确的是A)结点中有多个指针域的所有链表一定是非线性结构B)带链的栈与队列是线性结构C)能顺序存储的数据结构一定是线性结构D)存储空间不连续的所有链表一定是非线性结构1.4栈与队列1、栈的定义栈是一种特殊的线性表，是限定在一端进行插入和删除运算的线性表。允许插入与删除的一端称为栈顶（top)，另一端称为栈底(bottom）。

2、特点最先进入栈的元素一定在栈底，最后进入栈的元素一定在栈顶。所以堆栈又称为“后进先出”表或“先进后出”表提示：程序设计语言中的递归调用采用的“栈”这种数据结构同样有顺序和链式两种。（1）、入栈PUSH（S，X）

栈顶指针TOP加1，插入新元素X；若堆栈已满，再做入栈运算时会产生溢出（通常称为上溢）。（2）、出栈POP（S）取出栈顶元素赋给变量、栈顶指针TOP减1；若堆栈为空，再做出栈运算时会产生溢出（通常称为下溢）。

（3）、读栈顶元素GETTOP（S）将栈顶元素赋给变量但不改变TOP指针。3、存储结构及运算真题：1、下列关于栈叙述正确的是A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除C)栈底元素永远不能被删除 D)以上三种说法都不对2、下列叙述中正确的是A)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B)在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C)在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D)上述三种说法都不对3、假设用一个长度为50的数组(数组元素的下标从0～49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom＝49，top＝30(数组下标)，则栈中具有__

__个元素。4、若进栈序列为1，2，3，4，且进栈过程中可以出栈，则不可能的出栈序列是（A）1，4，3，2（B）2，3，4，1

（C）3，1，4，2（D）3，4，2，15、在程序设计语言中的递归调用的存储分配通常用（）A)栈B)堆C)数组D)链表队列1、定义是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。2、特点允许插入的一端称为队尾（rear),允许删除的一端称为队头(front)。新来的元素总是加入到队尾，每次离队的总是对头的元素。因此，也将队列称为“先进先出”FIFO（FirstInFirstOut）3、存储结构同样有顺序存储结构和链式存储结构。4、基本运算①入队:插入运算称为入队，rear=rear+1,rear指示了实际的队尾位置②出队:删除运算称为出队,front=front+1，front指示的是对头的前一个位置假溢出(a)图是空队列，表示该队列最大长度maxnum=6(d）图中rear=maxnum，如果这时有J7要入队，则会产生假溢出5、循环队列(顺序存储)注意：rear=front则表示可能队满，也可能队空循环队列的基本运算①入队：插入运算称为，rear=rear+1；当rear=m+1时(m为队列的总容量)，则重置rear=1。②出队：删除运算称为出队，front=front+1；当front=m+1时(m为队列的总容量)，则重置front=1。1、一个队列的入队序列是1、2、3、4，则队列的输出序列是

A)4321B)1234

C)1432D)3

2

4

1

2、在一个容量为24的循环队列中，若头指针front=8，尾指针rear=3，则该循环队列中共有__________个元素3、对于循环队列，下列叙述中正确的是A)队头指针是固定不变的B)队头指针一定大于队尾指针C)队头指针一定小于队尾指针D)队头指针可以大于队尾指针，也可以小于队尾指针4、在一个容量为24的循环队列中，经过一系列入队和出队运算，若头指针front=8，尾指针rear=8，则该循环队列中共有__________个元素重要考点：已知循环队列容量m，队头指针front和队尾指针rear，求队列元素个数n①当front<rear时：n=rear-front②当front>rear时：n=m+(rear-front)1、树的基本概念⑴定义

树是n（n≥0）个结点（数据元素）的有穷集合，是一种非线性结构。N=0时称为空树。⑵特点①有且仅有一个结点没有前驱结点，即树的根结点。②除根结点以外，其余所有结点有且仅有一个直接前驱。③包括根结点在内，每个结点可以有多个后继结点⑶基本概念①结点的度：一个结点的子树数目称为该结点的度②树的度：结点中最大的度即为树的度。③树的深度：树的最大层次。④叶子结点：没有子数，该结点的度为0.FCEGDABPH1.5树与二叉树2、二叉树⑴特点只有一个根结点，每个结点最多有左、右两棵子树组成。若集合为空，则为空二叉树。二叉树的结点有三种：度为0的叶子结点、度为1的结点和度为2的结点⑵基本性质①二叉树的第K层上最多有2k-1个结点。②深度为m的二叉树最多有2m-1个结点。③任意二叉树中，度为0的结点（叶子结点）总是比度为2的结点多1个。或者表述为：二叉树中度为2的结点有n个，则该二叉树中有n+1个叶子结点。④具有n个结点的二叉树，深度至少为[log2n]+1ABCFEDJn0=n2+1二叉树中结点总数：n0+n1+n23、满二叉树与完全二叉树⑴满二叉树：除最后一层外，每一层上的所有结点都有两个子结点，即每一层上的结点数都达到最大值。⑵完全二叉树：除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。

(a)深度为3的满二叉树(b)深度为3的完全二叉树的几种形态说明：满二叉树一定是完全二叉树，完全二叉树未必是满二叉树。前（根）序遍历：访问根结点——左子树——右子树

ABDEHJCFG中（根）序遍历：左子树——访问根结点——右子树

DBHEJAFCG后（根）序遍历：左子树——右子树——访问根结点

DHJEBFGCAABCFEGDHJ(3)二叉树的存储结构：链式存储(4)二叉树的操作：遍历真题：1、一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为

。2、

①

有下列二叉树，对此二叉树中序遍历的结果为（）

A）BDYEACFXZB）DYBEAFCZXC）ABCDEFXYZD）ABDYECFXZ

②某二叉树共有60个叶子结点与50个度为1的结点，则该二叉树中的总结点数为（）。

A）148B）169C）182D）198

③在深度为5的满二叉树中，叶子结点的个数为

A)32B)31C)16D)15④某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为()(假设根结点在第1层)

A)3 B)4 C)6 D)7n0=60推出n2=n0-1=59共有:n0+n1+n2=60+50+59=16925-11.6查找1、顺序查找（1）基本思想：从第一个数据元素开始，逐个把数据元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功；否则，若全部比较完都不等，则查找失败。（2）在下列两种情况下只能采用顺序查找：①如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2、二分查找前提：顺序存储的有序表。基本思想：待查元素与表的“中间位置”元素的关键值进行比较，若大于关键字，则在查找表的后半部分继续二分查找，否则在前半部分进行二分查找。在最坏情况下，顺序查找需要比较n次，二分查找需要比较log2n次。

排序冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序最坏情况下比较次数O(nlog2n)次n(n-1)/2次O(n1.5)次1.7排序下列排序方法中，最坏情况下比较次数最少的是

A)

冒泡排序

B)

简单选择排序

C)

直接插入排序

D)

堆排序1、交换类排序①冒泡排序基本思想：⑴首先，从前往后扫描线性表,逐次比较相邻两个元素的大小,若前者大于后者，则两两交换位置，最后将最大的元素放到了表的末尾；⑵然后，从后往前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，最后将最小者放到表的最前面。⑶再对剩余元素进行第二趟比较…，直到n个元素按递增顺序排列好为止。其特点是：第一趟排序后，最小元素被交换到第一位，最大元素被交换到最后一位。②快速排序基本思想：从序列中选取一个元素，设为T，将序列中小于T的元素移到T前面，大于T的元素移到T后面，T插入到序列分界线的位置，这个过程叫分割。然后对分割的两部分做再次分割，直至使序列变成有序的。2、插入类排序①简单插入排序基本思想：把n个数据元素的序列分成两部分，{R1，…，Ri-1}为已排好序的有序部分，{Ri,Ri+1,….,Rn}为未排序部分，这时，把未排序部分的元素逐个插入到有序部分的合适位置上。②希尔排序基本思想：把整个无序序列按某个增量H分割成若干小的子序列分别进行插入排序，在排序过程中逐次缩小这个增量，直至H为13、选择类排序(1)简单选择排序基本思想：第一趟排序是在无序的{R1，…，Rn}中按排序码选出最小的元素，将它与R1交换；第二趟排序是在无序的{R2，…，Rn}中按排序码选出最小的元素，将它与R2交换，…，最终得到递增有序的序列。89215648851619471621564885891947第1遍第2遍1619564885892147第3遍1619214885895647其特点是：第一趟排序后，最小元素被交换到第一位。(2)堆排序第二章程序设计基础1．结构化程序设计方法的四个原则2．对象、类、消息、继承的概念、类与实例的区别程序设计的方法与风格

一、程序设计方法与风格1、符号名的命名应具有一定含义2、必要的程序注释：分为序言性注释和功能性注释(可读性)

3、程序编写清晰第一、效率第二（易读性）4、避免不必要的语句转移5、程序设计要采用模块化二、结构化程序设计1、设计原则①自顶向下②逐步求精③模块化④限制使用GOTO语句最关键的是“以提高程序清晰性为目标”

2、程序基本结构①顺序结构②选择结构③循环结构三、面向对象的程序设计1、对象⑴定义：对象是由数据和允许的操作组成的封装体，可以用来表示客观世界中的任何实体。⑵属性：对象所包含的信息（静态）⑶方法：即对象的操作，描述了对象执行的功能（动态）⑷特征：⑴标识唯一性：对象是可以区分的。⑵分类性：可以将具有相同属性和操作的对象抽象成类。⑶多态性：同一个操作可以是不同对象的行为。⑷封装性：实现信息屏蔽。⑸模块独立性：内聚性强、耦合度弱。2、类类是具有共同属性、共同方法的对象的集合、对象是类的实例。可以由基类（父类）产生子类，子类可以继承其父类的全部方法和属性。3、消息对象间相互合作的机制称为消息，对象间通过传递消息相互联系4、继承继承是一种类之间共享属性和操作的机制。子类可以继承其父类的全部方法和属性，继承具有传递性5、多态性同样的消息被不同的对象接受时可导致完全不同的行为真题：1、下列不属于结构化程序设计原则的是()A）可封装B）自顶向下C）模块化D）逐步求精2、结构化程序所要求的基本结构不包括（）A）顺序结构B）GOTO跳转C）选择结构D）循环结构3、面向对象方法中，继承是指（）A）一组对象所具有的相似性质B）一个对象具有另一个对象的性质C）各对象之间的共同性质D）类之间共享属性和操作的机制4、在面向对象方法中，实现信息隐蔽是依靠（）A）对象的继承B）对象的多态C）对象的封装D）对象的分类5、以下不属于对象的基本特点的是（）A)分类性B)多态性C)一致性D)封装性6、对象实现了数据和操作的结合，是指对数据和数据的操作进行（）A)结合B)隐藏C)封装D)抽象7、在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（）A)调用语句B)命令C)口令D）消息第三章软件工程基础一、软件的定义1、软件：包括程序、数据和相关文档的完整集合。2、软件按功能划分：应用软件、系统软件与支撑软件（或工具软件）。应用软件：QQ、Office(word、excel等）、Wps系统软件：Windows、OS/2、Linux、Unix二、软件危机与软件工程1、软件危机⑴概念：出现于20世纪60年代末，泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。⑵软件危机的主要表现：①用户对交付使用的软件系统不满意。②软件开发成本和进度无法控制。③软件的质量无法保证。④现有软件维护困难。⑤软件的成本不断提高。⑥软件开发的速度跟不上硬件的发展和应用需求的增长。总的来说，归结为成本、质量、生产率等问题。下面描述中，不属于软件危机表现的是A)

软件过程不规范B)

软件开发生产率低C)

软件质量难以控制

D)

软件成本不断提高2、软件工程为了摆脱软件危机，提出了软件工程的概念。所谓软件工程，是指采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科。⑴软件工程三要素①方法：是完成软件工程项目的技术手段②工具：支持软件的开发、管理、文档生成③过程：支持软件开发的各个环节的控制、管理⑵软件工程核心思想：把软件产品看作是一个工程产品来处理。(3)、软件工程研究的内容与原则软件工程研究的主要内容：软件开发技术和软件工程管理软件工程的原则：抽象、信息屏蔽、模块化等(4)软件开发环境软件开发环境是全面支持软件开发全过程的软件工具集合。三、软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的全过程。划分为如下三个阶段：①软件定义②软件开发③软件维护3、软件生命周期各阶段的主要任务是：阶段任务描述软件定义阶段可行性研究与计划制定确定开发目标，制定实施计划。需求分析对待开发软件提出需求进行分析，确定软件系统的功能需求并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。需求分析的成果：需求规格说明书软件开发阶段软件设计分为概要设计和详细设计两个阶段，给出软件的结构、模块的划分、功能的分配以及处理流程。这阶段提交评审的文档有概要设计说明书、详细设计说明书和测试计划初稿。软件实现在软件设计的基础上编写程序。软件测试在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。软件维护运行维护将已交付的软件投入运行，同时不断的维护，进行必要而且可行的扩充和删改。结构化分析方法（软件定义阶段）一、需求分析1、需求分析的成果：需求规格说明书2、需求分析方法⑴结构化分析方法①面向数据流的结构化分析方法SA②面向数据结构的Jackson方法（JSD）③面向数据结构的结构化数据系统开发方法DSSD⑵面向对象的分析方法：OOA二、结构化分析方法

1、分析手段：分解和抽象2、分析工具⑴数据流图DFD（注意主要图形元素说明）

加工（转换）：输入数据经加工变换输出。数据流：沿箭头放心传送数据的通道。存储文件（数据源）：表示处理过程中存放各种数据的文件。源，潭：表示系统和环境的接口。⑵数据字典DD：作用是对DFD中出现的被命名的图形元素的确切解释，（

数据字典（DD)

所定义的对象都包含于数据流图中）是结构化分析的核心。⑶判定树⑷判定表三、软件需求规格说明书软件需求规格说明书是需求分析阶段的最后成果。软件需求规格说明书的作用包括

：A)

软件验收的依据

B)

用户与开发人员对软件要做什么的共同理解C)

软件设计的依据

结构化设计方法

（开发阶段）一、软件设计的基本概念1、软件设计：把软件需求转换为软件表示的过程，分概要设计和详细设计两步完成。2、设计原则⑴抽象：把事物本质的共同特性提取出来而不考虑其他细节。⑵模块化：模块是指把一个待开发的软件分解成若干小的简单的部分。模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。⑶信息隐蔽：信息隐蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。⑷模块独立性：模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。划分模块的原则要尽量做到“高内聚，低耦合”。二、总体设计（概要设计）：1、基本任务⑴设计软件系统结构⑵数据结构及数据库设计⑶编写概要设计文档⑷概要设计文档评审2、设计工具：结构图SC(StructureChart)3、面向数据流的设计方法典型的数据流类型：变换型和事务型扇入：是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程序高。扇出：是指该模块直接调用的下级模块的个数一个模块的扇入是指有多少个上级模块调用它。扇人越大，表示该模块被更多的上级模块共享。这当然是我们所希望的。但是不能为了获得高扇人而不惜代价，例如把彼此无关的功能凑在一起构成一个模块，虽然扇人数高了，但这样的模块内聚程度必然低。这是我们应避免的。设计得好的系统，上层模块有较高的扇出，下层模块有较高的扇人。其结构图像清真寺的塔，上面尖，中间宽，下面小。例题：某系统结构图如下图所示，该系统结构图的最大扇出数是（）A)4B)1C)3D)n某系统结构图如下图所示

，该系统结构图的最大扇入数：A）n

B）

1

C）

2

D）3

某系统结构图如下图所示，该系统结构图中最大扇入是

A）0

B）1

C）2

D）3

三、详细设计：1、基本任务：为每个模块确定算法和局部数据结构2、设计工具⑴图形工具：①程序流程图：构成程序流程图的基本图符及含义：→或↓表示控制流；□表示加工步骤；

表示逻辑条件。

②N-S图：③PAD图：④HIPO⑵表格工具：判定表⑶语言工具：PDL(伪码），是一种混合语言，采用英语的词汇和结构化程序设计语言的语法，类似编程语言。软件工程阶段用到的方法用到的工具生成的文档需求分析结构化分析SA数据流图DFD数据字典DD判定表判定树软件需求规格说明书概要设计结构化设计SD软件结构图SC概要设计说明书数据库设计说明书集成测试计划详细设计结构化编程SP程序流程图N-S图问题分析图PAD伪码PDL软件测试一、定义：软件测试是为了发现错误而执行程序的过程。软件测试是保证软件质量的重要手段。

二、目标：测试是为了发现软件中的错误而运行软件的过程好的测试方案是尽可能地发现至今尚未发现的错误的测试方案成功的测试则是发现出了至今尚未发现的错误的测试。软件测试的目的是A)

评估软件可靠性

B)

发现并改正程序中的错误C)

改正程序中的错误

D)

发现程序中的错误三、原则：不要抱有“软件不会有错或认为查不出错的“幻想”设计测试用例时，应同时确定输出结果设计测试用例时，应包括合理的数据和不合理的数据软件设计者应当避免测试自己的程序严格全面地执行测试计划妥善保存测试计划、测试用例、出错统计和最终分析报告四、软件测试技术与方法按照是否需要执行软件划分：静态测试、动态测试。按照功能划分：白盒测试、黑盒测试1、静态测试与动态测试⑴静态测试：由人工或借助工具对软件进行阅读和检查。静态测试包括代码检查、静态结构分析、代码质量度量等。⑵动态测试：是基于计算机的测试，是为了发现错误而执行程序的过程。动态测试的关键是设计高效、合理的测试用例。2、白盒测试与黑盒测试⑴白盒测试：又称为结构测试或逻辑测试。利用程序内部的逻辑结构和特性来设计测试用例，检查程序中的逻辑通路是否都按预定的要求正确地工作。测试的基本原则：保证每一条独立路径至少执行一次。测试的主要方法包括逻辑覆盖、基本路径测试⑵黑盒测试：又称功能测试或数据驱动测试，是对软件的功能进行测试和验证。黑盒测试不考虑程序内部的逻辑结构和特性，只根据程序的需求和功能设计测试用例。测试的常用方法有等价分类法、边界值分析法、错误推测法和因果图。使用白盒测试方法时，设计测试用例应根据

A）程序的内部逻辑B）程序的复杂结构C）程序的功能

D）使用说明书五、软件测试的实施软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试。1、单元测试：对模块进行测试，目的是发现模块内部可能存在的错误。2、集成测试：测试和组装软件，目的是发现和接口有关的错误。3、确认测试：验证软件的功能和性能是否符合需求。4、系统测试：将通过测试的软件与硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起进行测试。

下面不属于软件测试实施步骤的是

A)

集成测试

B)

回归测试

C)

确认测试

D)

单元测试程序的调试在对程序进行了成功的测试之后将进入程序调试（通常称Debug，即排错）。注：软件调试与软件测试是不同的概念，软件调试的目的是为了改正程序中的错误。一、基本概念1、程序调试的任务：诊断和改正程序中的错误。软件测试贯穿整个软件生命期，调试则主要在开发阶段进行。2、程序调试的步骤⑴错误定位⑵修改设计和代码，以排除错误；⑶进行回归测试，防止引进新的错误。二、软件调试的方法调试的关键在于推断程序内部的错误位置及原因。软件调试可分为静态调试和动态调试。主要的调试方法有：强行排错法、回溯法、原因排除法1、程序测试的目的是（）A）发现程序中的错误

B）发现并改正程序中的错误C）诊断并改正程序中的错误

D）执行测试用例2、下面不属于软件开发阶段任务的是（）

A）测试

B）设计

C）可行性研究D)实现3、下面可以作为软件设计工具的是

DA）数据字典（DD）

B）甘特图C）数据流程图（DED图）D）系统结构图4、下面对软件测试和软件调试有关概念叙述错误的是A）程序调试通常也称为Debug

B）设计正确的测试用例C）软件测试的目的是发现错误和改正错误D）严格执行测试计划，排除测试的随意性5、下面属于白盒测试方法的是A)

等价类划分法B)

边界值分析法

C)

基本路径测试D)

错误推测法6、软件设计中模块划分应遵循的准则是

A)

低内聚低耦合

B)

高耦合高内聚C)

高内聚低耦合7、软件生命周期是指A)

软件产品从提出、实现、使用维护到停止使用退役的过程B)

软件从需求分析、设计、实现到测试完成的过程C)

软件的开发过程

D)

软件的运行维护过程8、下面描述中错误的是A)

系统总体结构图支持软件系统的详细设计B)

软件设计是将软件需求转换为软件表示的过程C)

数据结构与数据库设计是软件设计的任务之一D)

PAD图是软件详细设计的表示工具9、软件按功能可以分为应用软件、系统软件和支撑软件（或工具软件）。下面属于应用

软件的是A)

学生成绩管理系统

B)

C语言编译程序C)

UNIX

操作系统

D)

数据库管理系统10、构成计算机软件的是A)

源代码

B)

程序和数据C)

程序和文档

D)

程序、数据及相关文档11、数据流图中带有箭头的线段表示的是

A)

控制流

B)

事件驱动

C)

模块调用

D)

数据流12、在软件开发中，需求分析阶段可以使用的工具是A)

N-S图

B)

DFD图

C)

PAD图

D)

程序流程图第四章数据库设计基础一、数据、数据库、数据库管理系统1、数据(Data)：描述事物的符号记录。2、数据库(DB)：数据的集合。3、数据库管理系统(DBMS)：是在操作系统支持下管理数据库的系统软件，是数据库系统的核心。

⑴数据库管理系统的功能：①数据模式定义②数据存取的物理构建③数据操纵：数据查询、数据的删除、数据插入、数据修改④数据的完整性、安全性定义与检查⑤数据库的并发控制与故障恢复⑥数据的服务⑵数据库管理系统提供的数据语言：①数据定义语言：负责数据的模式定义与数据的物理存取构建。②数据操纵语言：负责数据的操纵，包括数据的增、删、改和查询。③数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。4、数据库应用系统(DBAS)：利用数据库系统开发的应用软件。5、数据库管理员(DBA):负责定义书库内容、决定存储结构和存取策略及安全授权等工作。6、数据库系统(DBS)：包含硬件系统、软件系统、数据库、数据库管理员和用户。二、数据库系统的发展1、人工管理阶段：数据无法共享，冗余度大，不独立，完全依赖于程序。2、文件系统阶段：数据共享性差，独立性也较差。3、数据库系统阶段：数据独立性最高。三、数据库系统的特点1、数据的集成性2、数据的高共享性和低冗余性：数据共享可以减少数据集冗余，并且避免数据的不一致性。

数据的一致性是指在系统中同一数据在不同地方出现应保持相同的值。3、数据独立性：数据与程序独立存放⑴物理独立性：当数据的物理结构改变时，如存储结构改变、存储设备的更换、存取方式改变等都不影响数据库的逻辑结构，应用程序不用改变。⑵逻辑独立性：当数据的逻辑结构改变时，如修改数据模式、增加新的数据类型、改变数据间联系等，不需要改变应用程序。4、数据统一管理与控制四、数据库系统的内部结构体系1、三级模式⑴概念模式：是对数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。一个数据库只有一个概念模式。⑵外模式：是数据库用户的数据视图，也就是用户所见到的数据模式，由概念模式推导而出。一个概念模式可以有若干个外模式。⑶内模式：给出了数据库物理存储结构与物理存取方法。内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。2、两级映射：概念模式到内模式的映射、外模式到概念模式的映射。保证了数据库系统中的数据能够具有较高的逻辑独立性和物理独立性。1、数据库管理系统是________。A)一种编译系统B)一种操作系统C)操作系统的一部分D)在操作系统支持下的系统软件2、数据库系统的核心是

系统3、在数据管理技术发展的三个阶段中，数据共享最好的是________。A)数据库系统阶段B)三个阶段相同C)人工管理阶段D)文件系统阶段4、在数据库管理系统提供的数据定义语言、数据操纵语言和数据控制语言中，

语言负责数据的模式定义与数据的物理存取构建。5、数据库DB、数据库系统DBS、数据库管理系统DBMS之间的关系是________。A)DBS包含DB和DBMSB)没有任何关系C)DB包含DBS和DBMSD)DBMS包含DB和DBS

6、数据库管理系统中负责数据模式定义的语言是

。7、数据独立性是数据库技术的重要特点之一。所谓数据独立性是指________。A)不同的数据只能被对应的应用程序所使用B)三种说法都不对C)数据与程序独立存放D)不同的数据被存放在不同的文件中

一、数据模型是对现实世界数据特征的抽象。是指反映客观事物及客观事物间联系的数据组织的结构和形式。现实世界人的抽象认识信息世界：概念模型机器世界：具体的数据模型数据模型

1、概念数据模型：对客观事物抽象化，实体-联系数据模型即E-R模型2、逻辑数据模型：把概念数据逻辑化，依赖某种数据库系统数据模型通常由数据结构、数据操作及数据约束三部分组成。层次模型、网状模型和关系模型二、E-R模型1、实体：现实世界中客观存在且可以相互区别的事物。2、属性：描述实体的特征3、实体间联系：一对一1∶1；一对多1∶m；多对多m∶n4、实体型：实体属性的集合5、实体集：相同类型实体的集合实体集属性联系6、图示法：矩形-实体集；椭圆-属性；菱形-联系学生1(学号、姓名、性别、出生日期、系别、籍贯)实体属性实体集实体型学生2(学号、姓名、性别、出生日期、系别、籍贯)学生n(学号、姓名、性别、出生日期、系别、籍贯)三、数据库管理系统所支持的数据模型分为3种：层次模型、网状模型和关系模型。层次模型：描述数据之间的从属层次关系。网状模型：描述数据之间的多种从属的网状关系。关系模型：主要描述那种具有相关性而非从属性的平行的数据之间按照某种序列排列的集合关系。格式为：关系名（属性名1，属性名2，…

，属性名n）1、元组——记录——行；属性——字段——列四、关系模型：二维表结构2、域：属性的取值范围3、码（键）：二维表中唯一标识元组的最小属性值。一个表可能有若干键，它们称为该表的候选码（或候选键），从候选键中选取一个作为用户使用的键称为主键（或主码）。如表A中的某属性是某表B的键，则称该属性为A的外键（或外码）例：1、在关系A(S，SN，D)和关系B(D，CN，NM)中，A的主关键字是S，B的主关键字是D，则称

是关系A的外码。2、图书馆数据库系统中有下列模式书（书号，类别，书名，出版社，年份，作者，价格，总藏书量，现有库存）借书卡（卡号，姓名，单位，类别）

借书记录（卡号，书号，借期，还期）其中关系书和关系借书卡的主键分别为书号和卡号，关系借书记录的主键为A）卡号，书号B）书号，借期C）卡号，书号，借期D）卡号，借期

二维表的性质：⑴二维表中元组个数是有限的——元组个数有限性；⑵二维表中元组均不相同——元组的唯一性；⑶二维表中元组的次序可以任意交换——元组的次序无关性；⑷二维表中元组的分量是不可分割的基本数据项——元组分量的原子性；⑸二维表中属性名各不相同——属性名唯一性；⑹二维表中属性与次序无关，可任意交换——属性的次序无关性；⑺二维表属性的分量具有与该属性相同的值域——分量值域的统一性。4、关系操纵：数据查询、数据的删除、数据插入、数据修改。5、关系中的数据约束：实体完整性约束、参照完整性约束、用户定义的完整性约束实体完整性约束：关系中每一个元组的主码（主键）属性不能重复，并且不能取空值，关系表中至少有一个字段满足没有重复值（即至少有一个候选索引)参照完整性：父表关键字更改，子表是否作相应的变化

例题：有三个关系表R、S和T如下，其中三个关系对应的关键字分别为A,B和符合关键字（A,B）。表T的记录项(b,q,4)违反了用户定义的完整性约束参照完整性约束实体完整性约束AA1a1bnBB1B2fghlxynpxABCaf3bq4RST一、专门的关系模型的基本运算1、选择()：从一个关系R中找出满足给定条件F的元组(记录)的操作成为选择。记为：σF(R)关系运算2023/2/220:50选择运算–例子关系RABCDA=B^D>5

(R)ABCD123710∧∨非与(and)或(or)有关系R如下：ABCDaa22be12cc114ee61则运算A<>B^D>=2R的结果为：空(a,a,2,2)