第1章? 数据结构与算法 1.1? 算法 1．算法的基本概念 *（1）定义：指为了解决某类问题而规定的一个有限长度的操作序列。或者说是一组严谨地定义运算顺序的规则。
问题处理方案的正确而完整的描述称为算法。
A(8)?? B(6) ? ? TEMP(8) *（2）算法的特征：可行性；
确定性；
有穷性；
拥有足够的情报。
（3）算法的基本要素。对数据的运算和操作；
算法的控制结构。
（4）基本运算和操作有：算术运算 (+- * / %)；
逻辑运算(与,或,非) C:?? &&? ||?? ! VF: .And. .or. .not.；
关系运算(比较)( >=，>,<, <=, ==,!=,<>)；
数据传输（a=10,a=b）。
（5）描述算法的工具：传统流程图、N-S(盒图)结构化流程图、算法描述语言等。
? ? （伪码） 定义变量T T=A A=B B=T ? 定义变量T ? T=A ? A=B ? B=T ? 输出AB ? 输入AB ? 输入A, B ? ? T ? ? A>B ? ? T ? ? F ? ? ??? ? ? ??? ? ? *（6）算法的基本控制结构3种：顺序、选择(if-else判断、分支)、循环(重复for? ,while,do while)。
（7）算法设计的基本方法：列举法，归纳法，递推法，递归法，减半递推法，回溯法。
列举法:? a+b=100 ? a=0 b=100,a=1 b=99,a=100 b=0 ? for a=0 to 100 ?? b=100-a next ?? ab+ba=100?? for a=1 to 9 for b=1 to 9 ? if? a*10+b+b*10+a=100 ? abc 递归法 S100=1+2+3+….+100 S100=100+S99 S99=99+S98 ? S1=1 ? 3? 7? 10 （8）算法设计的要求：正确性，可读性，健壮性，效率与低存储量要求。
*2．算法的复杂度 （1）算法的复杂度包括(时间复杂度)和(空间复杂度)。
? ***（2）时间复杂度是指执行算法所需要的计算工作量。（基本运算次数）。不是时间长短 （3）空间复杂度是指执行算法所需要的内存空间。（包括算法程序所占的空间，输入初始数据所占空间，算法执行过程中所需要的额外空间。
两种复杂度没有必然联系! 1.2? 数据结构的基本概念 3．数据结构的定义：是相互之间存在一种或多种特定关系的数据元素的集合。
? ? ? ? ? AA ?GG ?RR ?yy ?HH ? 101 ?ZH3 ?19 ?90 ?78 ? 102 ?LI4 ?20 ?88 ?66 ? ? **数据结构有三方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。填空 逻辑：概念? C,D,E 物理（存储）：1 ? *4．数据的逻辑结构有2种：指数据元素之间的逻辑关系。与存储无关，是独立于计算机的。有(线性结构)和(非线性结构)。春--夏--秋---冬? 行政机构，家谱，树型目录 ? **5．数据的存储结构有4种：又称物理结构，指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在存储空间的存放形式。数据的存储结构有4 种：顺序、链式、索引、散列。填空 6．数据结构的图形表示：数据结构可以用二元关系表示，也可以用图形表示（方框表示元素，称为数据结点，有向线段从前件指向后件，没有前件的结点叫根结点，没有后件的结点叫终端结点或叶子结点）。
A ? B ? C ? D ? E ? F ? 7．线性结构与非线性结构：
数据的逻辑结构分为两大类型：线性结构与非线性结构。
?? 线性结构的条件是：只有一个根结点，每个结点最多一个前件，最多一个后件。一个数据结构如不是线性结构，则为非线性结构。在线性结构中插、删结点后还应是线性结构。
1.3? 线性表及其顺序存储结构 8．线性表的定义：线性表是一种线性结构。数据元素之间的相对位置是线性的。
非空线性表的3 特征：（1）有且只有一个根，它无前件（2）有且只有一个终端结点，它无后件（3）其他结点有且只有一个前件，一个后件。
? ? 9．线性表的顺序存储结构(也叫顺序表)：特点：，存放顺序与逻辑次序相同。优点：可以随机存取。
第i元素的位置由序号确定。通常用一维数组表示（向量）。
例：学号 1? 2? 3? 4? 5??? int? a[5] 1 ? 2 ? 3 ? 4 ? 5 ? 1 ? 2 ? ?? ? ?3 ? 4 ? 5 ? 个数+1清 ? 1 ? 2 ? ?3 ? ?4 ? 5 ? 个数-1清 ? 1 ? 2 ? ?4 ? ?5 ? 5 ? a[2]=a[3]; ? 10．顺序表的插入运算：在第I位置插入元素的步骤：先判断是否上溢；
空出第I位置；
插入。元素要移动 11．顺序表的删除（第I个）运算：从第I+1位置到最后元素均向前移1个元素。平均移动一半元素(N/2)。元素要移动 1.4??????????? 栈和队列 m=8 ? 12．栈（stack）的定义：限定在一端插入与删除的线性表。允许插入、删除的一端叫栈顶，另一端叫栈底。向栈中插入的运算叫入栈，从栈中删除的运算叫退栈。栈是“先进后出”结构，FILO。
? bottom ? top ? A ? B ? 1 ? top ? C ? 2 ? 3 ? 0 ? ? ? ? ? ? 也可以说：栈是“后进先出”结构，LIFO 13．栈的存储：使用一维数组S（1：m）,m为栈的最大容量。
14．栈的运算：
（1）入栈运算：首先判断栈是否满（if top=m）(上溢),其次栈顶指针加1（top=top +1）,新元素放入( a[top]=’C’ ) （2）退栈运算：首先判断栈是否空（if top=0下溢）,将栈顶元素赋给指定变量或者输出，栈顶指针减1（top=top-1）。
3）读栈顶元素(使用)：将栈顶元素赋给指定变量( tmp=a[top]? )，当栈顶指针为top=0时，读不到栈顶元素。
练习：
（1）进栈序列是e1,e2,e3,e4,可能的出栈序列：
思考上题所有的出栈序列：
（1）e1,e2,e3,e4 （2）e4，e3,e2,e1 等 15．队列的定义及存储：队列也是一种特殊的线性表，允许在一端插入，在另一端删除，允许插入的一端叫队尾（尾指针rear ），允许删除的一端叫队头（头指针 front），是先进先出/后进后出结构。FIFO/LILO。队尾指针指向尾元素，队头指针指向头元素的前一位置。
6 ? R=3 ? ? ? 727 ? F=3 ? 8? 7? 6? 5? 4? 3? 2? 1 ? 899 ? 7 ? a[8] ? ? ? ? ? ? 16、队列的顺序存储结构一般用一维数组。入队r=r+1; a[r]=数据 ??? 出队：tmp=a[f+1]; f=f+1; 计算队中有几个元素：r-f 17．循环队列及其运算：
队列为空的条件：S=0（S为队空标志）front= rear 队满条件：S=1，front= rear。入队：首先看是否满（S=1？上溢），若不满，rear=rear+1, if rear=m+1,则rear=1),然后插入。出队：首先看是否空（S=0？下溢），若不空，将队头元素赋给指定变量，front=front+1,(如font=m+1,则front=1)。
1.5??????????? 线性链表 18．线性单链表的结构及其基本运算 q ? p ? 线性表的链式存储结构称线性链表。结点由两部分组成，数据域和指针域。指针域指向后一结点（记录它的后件的地址）。
张 ? 019 ? ? 李 ? 062 ? ? 王 ? ^ ? 011 ? 019 ? 062 ? head ? data ? Link/Next ? ? ? ? ? 在P后插入：
s ? 095 ? new(s);?? 申请一个结点 062 ? 高 ? ????? s.data=”高”; ????? s.next=p.next; ????? p.next=s; 删除q之后的：
p= q.next; q.next=q.next.next; (q.next=p) free(p ); ^或 NULL表示空。
注意：数据结构分为逻辑结构和存储结构，线性链表是一种存储结构。顺序表也是一种存储结构。
注意：存储空间比较大 注意：顺序存储可以随机存取；
????? 链式存储只能顺序存取。
19．线性链表基本运算 （1）查找运算:从头指针开始向后找（2）插入运算:先分配一个新结点，再指针操作 （3）删除运算: 优点：插入删除元素不需移动结点。
-3-第6周 20．线性双向链表的结构及其基本运算 ? 双向链表设置左指针（指向前件），右指针（指向后件）。
102 ? 101 ? 101 ? ^ ? 张 ? 102 ? head ? ^ ? 张 ? left / right ? data ? ? ? 双向链表克服了只能找到后件,不能找到前件的缺陷。
21．循环链表的结构及其基本运算 特点：（1）设置表头结点，其指针域指向第一个结点；
（2）最后一个结点的指针指向表头结点。
好处：永远至少有一个结点；
插入、删除时，空表和非空表处理方法统一；
只要指出任何一个结点，就可访问其他所有结点。与线性链表比插入删除时实现了空表和非空表的运算统一。
1.6??????????? 树与二叉树 22．树的定义 树是一种非线性结构，是一种层次结构。概念：父结点，根结点，子结点，结点的度（结点拥有的后件数），树的度（所有结点最大的度），层次：根结点为1层，依次计算，树的最大层次称树的深度、高度，叶子结点无子树、度为0。树通常用多重链表表示。
根结点没有前件,可能有0个或者1个。
23．二叉树的定义及其性质 （1）定义：非空二叉树只有一个根结点，每个结点最多有两个子树，分别称左子树和右子树。
二叉树不是一棵特殊树。
*三个结点的二叉树有5种形态。
? ? ? （2）性质：①第K层最多有2k-1个结点；
②深度为M的二叉树最多有2m-1个结点; *③度为 0的结点（叶子）总是比度为2的结点多1个；
④N个结点的二叉树，深度至少为|_log2N_|+1 ⑤完全二叉树的深度为|_log2N_|+1 （3）满二叉树：除最后一层，每层都有2个子结点，即每一层上的结点数都达到最大值，每一层都有2k-1个结点。
（4）完全二叉树：除最后一层，每层结点数都达到最大值，最后一层只缺少右边的若干个结点。
满二叉树也是完全二叉树。
? ? ? ? （5）二叉树通常采用链式存储结构，二叉链表。
*24．二叉树的遍历 即从根结点开始，访问每个结点1次。根据根结点的遍历顺序有3种遍历法（总是先左后右）。
前序（前根）（先序）遍历：（根左右） 中序遍历（中根）：（左根右）、 后序遍历（后根）：（左右根）。
? ? ? A ? B ? C ? 前:ABC 中:BAC 后:BCA ? A ? B ? C ? D ? E ? 前:A BD? CE 中:DB A CE 后: DB EC A ? 练习：
(1)已知后序为dabec，中序为debac，求前序序列。
后dabec 中debac ? (2) 已知前序为ABEGCFK，中序为EGBAFCK，求后序序列. A ? 答案：
C ? B ? 前ABEGCFK K ? F ? E ? 中EGBAFCK 后 G ? : ? GEB FKCA 1.7??????????? 查找技术 25．查找：就是在给定的数据结构中查找某个指定的元素。有两种方法：顺序查找， 和二分查找法。
26．顺序查找 方法：
大约和一半N/2元素比较、最坏情况比较N次；
适用场合：顺序查找，线性表无序，或有序线性表采用链式存储；
27．二分查找 方法：
二分查找最坏只需比较log2N次。
*适用场合：二分查找仅当有序线性表为顺序存储时才能使用。
要记住查找次数。
例：查找40，L=1? H=6? M=3 2???????? is 12，L=3? H=6? M=4 is 19 ?????? L=4? H=6?? M=5 is 40 1：5 2：10 3：12 4：19 5：40 6：90 ? 1．8排序技术 28．排序 是指将一个无序的列表整理成按值递增或递减顺序排列的有序序列。
*常用方法：交换类排序，插入类排序，选择类排序。
29．交换类排序（实例：冒泡，快速） 思想：借助数据元素之间的相互交换进行排序。
冒泡：通过相邻数据元素的交换逐步将线性表变换成有序的。
例:从小到大 6?? 10?? 8?? 14?? 2 6?? 8?? 10?? 2? 14 6?? 8?? 2?? 10? 14 6?? 2?? 8? 10? 14 2?? 6?? 8? 10? 14 快速：将原问题分解成若干个小规模的同结构的问题，递归解决每个子问题。
? 30．选择类排序（实例：简单选择排序，堆排序） 简单选择排序思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最上面，对剩下的元素采取相同的方法。直到表为空。
例:从小到大 6?? 10?? 8?? 14?? 2 1:? 5#??? 1<>5 2: 2? 10?? 8?? 14? 6 3: 2? 6??? 8?? 14? 10 4: 2? 6??? 8?? 14? 10 5: 2? 6??? 8?? 10? 14 堆排序：用于大规模有序线性表。
? 31．插入类排序（实例：简单插入，希尔Shell排序） 思想：将无序列表中的各元素依次插入到已经有序的线性表中。（当元素距它的最终位置不太远时使用） ??? 简单插入：将无序表中的各元素依次插入到已有序的线性表中。
例:从小到大 [6 ]?? [ 10? 8?? 14?? 2] [6? 10]? [ 8? 14?? 2] [6? 8? 10]? [ 14?? 2] [6? 8? 10? 14]? [ 2 ] [2? 6? 8? 10? 14] [ ] 希尔：对简单插入的改进，先选取一个增量，把增量倍数的记录放在一组中，组内进行直接插入排序，再取小增量，重复上述操作。当增量为1时，进行一次插入排序，即完成。
记住：
如线性表长度为N，各种排序方法在最坏情况下需要的比较次数：
冒泡、简单插入、快速、简单选择：n（n-1）/2 希尔：O（n1.5） 堆排序：O（nlog2n）= nlog2n+C(1)? 堆排序不是n（n-1）/2 经典题解：
1、 算法复杂度主要包括时间复杂度和（ ）复杂度。
2、 问题处理方案的正确而完整的描述称为（）。
3、 关于存储结构的描述，错误的是：
4、 数据的存储结构是指（）。数据的逻辑结构在计算机中的表示 5、 关于栈的描述错误的是：
6、 关于栈的描述正确的是：是一种特殊的线性表，只能在一端插入元素，而在另一端删除元素。X 7、 线性链表是线性表的链式存储结构。正确。
8、 线性链表的描述：存储空间不一定连续，且各元素的存储顺序是任意的。正确 9、 一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率。正确 10、????? 数据结构 分为逻辑结构和存储结构，循环队列属于（）结构。存储 11、????? 对于长度为N的线性表进行顺序查找，在平均情况下所需要的比较次数为：( ) N/2 12、????? 能用二分法查找是的数据结构是（）。
顺序存储的有序线性表 13、????? 对于长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为：( ) N 14、????? *在最坏情况下列各排序法所对应的比较次数正确的是：( ) A、??????????? 冒泡 N/2 B、??????????? 冒泡N C、??????????? 快速为N? D、??????????? 快速为N（N-1）/2 15、????? 对于长度为10的线性表进行冒泡排序，在最坏情况所需比较次数为（）N（N-1）/2 16、????? 一棵二叉树第6层（根为1）的结点数最多为（）个 17、????? 深度为7的满二叉树，叶子结点有个数为（） 18、????? 某二叉树中，度为2的结点有18个，则该 二叉树中有（）叶子结点 19、????? 下列二叉树的后序遍历序列为（） 20、????? 算法的时间复杂度是指：（） 21、????? 数据的存储结构包括顺序，（），散列和链式四种类型。
22、????? 单链表P指Ai，删除Ai之后的结点，修改指针的操作为：
? 第2章 程序设计基础 2.1? 程序设计方法与风格 1．程序设计经历的阶段。结构化程序设计，面向对象的程序设计阶段。
2．良好的编程风格应注意的因素 总体原则“清晰第一，效率第二”。注意以下4点：
（1）源程序文档化。符号名的命名；
程序注释(C注释:? /*ffffff*/)；
视觉组织。
for(i=1 ;i<10;i++ { ?? ….; } 符号名的命名；
程序注释：序言性注释（程序开头，给出程序整体说明）；
功能性注释（程序体中，描述其后的语句或程序何等什么，对语句段注释）。
视觉组织：用空格、空行、缩进等技巧使程序层次清晰。
（2）数据说明方法。易于理解和维护。
int? a; （3）语句的结构。简单直接。
（4）程序的输入输出。应尽可能方便用户的使用。
? 2.2? 结构化程序设计 3．结构化程序设计的原则 基本（主要）原则是：自顶向下、逐步求精、模块化、限制使用GOTO语句。
4．结构化程序设计的基本结构与特点 *（1）基本结构：顺序、选择、循环。
2.3? 面向对象的程序设计 5．面向对象的方法 （1）定义：是一种运用对象、类、继承、封装、聚合、关联、消息、多态性等概念来构造系统的软件开发方法。
面向对象的方法与技术开始走向实用的标志性语言是Smalltalk。
结构化程序设计方法的核心是算法，面向对象的核心是对象（类）。
（2）优点：与人类习惯的思维方法一致；
稳定性好；
可重用性好；
易于开发大型软件产品；
可维护性好。
6．面向对象方法的基本概念 （1）对象。具有属性（数据）和方法（行为方式）的实体。或说，对象是软件系统中用来描述客观事物的一个实体，它是软件系统的一个基本单位。
如：学生，书 * 对象的特征：标识惟一性；
分类性；
多态性；
封装性；
模块独立性好。
（2）类和实例。
*（类）是具有共同属性和服务的一组对象的集合。
注意：
属性=状态 服务=操作、行为、方法 对象. 属性? 对象. 方法 类是对象的抽象，类可以用来创建对象，对象是类的一个实例。
（3）*消息。指一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，统一了数据流和控制流。
面向对象方法中的消息类似于结构化程序设计方法中的“函数调用”。
S=sum(10,8); ? int? sum(int x,int y) { ? } *一个消息由3部分组成：接收消息的对象的名称；
消息（标识符）名；
零个或多个参数。
（4）继承。是使用已经定义好的类来定义一个新类。原类与新类的关系是一般类与特殊类的关系。
*继承是多个类之间共享属性和操作的机制。
继承分单继承（一个类只允许有一个父类）和多继承（一个类可以有多个父类）。
（5）多态性。指同样的消息被不同的对象接收时可导致完全不同的行为。面向对象中的多态是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象，也可以发送给子类对象。
第3章?? 软件工程基础 3.1? 软件工程基本概念 1. 软件（software） （1）定义。软件包括程序、数据和文档（或程序+文档）。软件由两部分组成，可执行的程序和数据，不可执行的文档。
（2）特点。逻辑产品；
与硬件的生产不同；
不会磨损老化；
依赖计算机系统；
开发和维护成本高；
软件开发涉及许多社会因素。
（3）分类。应用软件（为解决特定领域的应用而开发、有针对性）、系统软件（为管理计算机本身而开发,有基础性、通用性,windows,Linux,VC++,VFP）、支撑软件（是为开发软件和维护软件的软件）。
2. 软件危机 （1）产生。20世纪60年代末,1968。
（2）定义。指在计算机软件的开发和维护过程中所遇到的一系列严重问题。
（3）表现。主要是成本、质量和生产率。
（4）原因。与软件本身的特点；
软件开发和维护方法不正确（主要原因）。
3. 软件工程 （1）源自软件危机。
（2）国标定义。是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。
*（3）三要素。方法、工具和过程。方法是完成软件工程项目的技术手段；
工具用于支持软件的开发、管理、文档生成；
过程用于支持软件开发的各个环节的控制和管理。
（4）核心思想。把软件产品当作是一个工程产品来处理，即强调在软件开发中需要应用工程化原则。
4. 软件过程（了解） （1）是把输入转化为输出的一组彼此相关的资源和活动。
（2）四个基本活动Plan,DoCheck,Action即软件规格说明，软件开发，软件确认，软件演进。
5. **软件生命周期（记住名称及顺序） （1）定义。将软件产品从提出、实现、使用维护到停止使用退役的过程称为。
（2）阶段划分。1）可行性研究与计划制定，2）需求分析，3）软件设计，4）软件实现（编程），5）软件测试，6）运行和维护。
6. 软件工程的目标（简单了解） 目标：是在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可追踪性和可互操作性且满足用户需求的产品。
基本目标：较低的开发成本；
达到要求的软件功能；
取得较好的软件性能；
软件易移植；
较低的维护费用；
能按时开发完成，及时交付使用。
7. *软件工程原则（重点） （1）抽象。抽取事物最基本的特征和行为，忽略非本质细节。
（2）信息隐蔽。采用封装技术，将程序模块的实现细节隐藏起来，使模块的接口尽量简单。
（3）模块化。模块是程序中相对独立的成分。一个独立的编程单位。
（4）局部化。相关的东西放的靠近一些。
（5）确定性。软件开发过程中所有概念的表达应确定、无歧义且规范。
（6）一致性。使用的概念、符号、和术语，内外部接口应一致。
（7）完备性。软件系统不丢失任何重要成分，完全实现系统所需功能。
（8）可验证性。系统分解应遵循容易检查、测试、评审的，以确保系统的正确性。
8. 软件工程的研究内容（填空） 软件开发技术 + 软件工程管理。
9. 软件开发工具与软件开发环境 （1）软件开发工具。协助开发人员进行软件开发活动所使用的软件或环境，如需求分析工具、设计工具、编码工具、排错工具、测试工具等。
从单项开发工具逐步向集成工具发展。
（2）软件开发环境。指支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成。
（3）环境集成机制包括：数据集成、控制集成，界面集成。
**（4）CASE。计算机辅助软件工程。是软件开发环境的典型例子。
3.2 结构化分析方法 10.????? 可行性研究（了解） （1）?????????? 目的是用最小的代价在尽可能短的时间内确定问题是否能够解决。
（2）?????????? 内容：经济可行性、技术可行、法律可行性（操作/社会可行性）、评价开发方案，选出最适宜的方案。
11.????? 需求分析方法 （1）软件需求分析：是指用户对目标系统在功能、行为、性能、设计约束等方面的期望。（主要是功能需求），（解决“做什么”的问题。） （2）需求分析的任务是发现需求、求精、建模、定义需求的过程。
（3）需求分析阶段的工作：需求获取；
需求分析；
编写需求规格说明书；
需求评审。（掌握） （4）常见的需求分析方法：
主要有结构化方法和面向对象的方法。结构化方法主要包括3种：
SA，面向数据流的结构化方法。
JSD，面向数据结构的JACKSON方法。
DSSD。面向数据结构的结构化数据系统开发方法。
（5）需求分析方法又可分为静态分析方法和动态分析方法。
12.????? 结构化分析方法（SA） （1）结构化方法是比较成熟的软件开发方法。核心和基础是结构化程序设计理论。
（2）**实质。着眼于数据流，自顶向下、逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。
13.????? 数据流图（DFD）（重点） （1）定义。以图形方式描绘数据在系统中流动和处理的过程，它只反映系统必须完成的逻辑功能，所以是功能模型。
（2）主要图形元素四种。重点 数据流：箭头? →，沿箭头方向传送数据的**。
加工（处理）：圆或椭圆○，输入数据经加工变换产生输出。
存储文件：双杠〓，表示处理过程中存放各种数据文件。
源，潭：方框? □，表示系统和环境的接口。（外部实体） 学生 ? 审查 ? 申请单 ? 交费 ? ? 已批申请 ? 未批申请 ? 领书单 ? 购书文件 ? 学生 ? ? ? ? ? ? （3）画图原则。四个符号；
主图封闭在外部实体之间；
变换框（加工）至少有一个输入数据流和一个输出数据流；
每个元素要命名；
一个子图对应父图的一个加工，且两者输入流和输出流一致。
（4）画图步骤。由外向里，自顶向下，逐层分解。
14.????? 数据字典（DD） （1）DD是结构化分析方法的核心。
（2）作用，是对数据流图中出现的被命名的图形元素的确切解释。
（3）内容及主要符号。（=定义为，[ | ]或，+与/和，n{}m重复，（）可选，**注释，..连接 ） 数据字典例：
学生=要购书的学生 申请单=学号+姓名+班级+专业+1{书名+出版社+数量}5+（备注） 购书文件=日期+学号+姓名+购书信息+经办人 购书信息=书号+书名+出版社+数量+金额 ? 15.????? 判定表与判定树 都以图形方式描述数据流图中的加工逻辑（圆圈）。
（1）判定树，首先分清判定条件和判**论。
? （3）?????????? 判定表，当加工要依赖多个逻辑条件的取值，即完成该加工的一组动作是由某一组条件取值的组合引发的，适宜采用。由基本条件，条件项，基本动作，动作项。
判定表：
营业额 >=1000 ?Y ?Y ?Y ?Y ?N ?N ?N ?N ? 老客户 ?Y ?Y ?N ?N ?Y ?Y ?N ?N ? 信用好 ?Y ?N ?Y ?N ?Y ?N ?Y ?N ? 优惠 ?v ?v ?v ? ? ? ? ? ? 普通 ? ? ? ?V ?V ?V ?V ?V ? ? 16.????? 结构化方法开发过程 *** 结构化方法将软件生命周期分为计划、开发、运行（维护）3个时期。每个时期又分若干阶段。?? （1）计划期。任务是分析新系统应设定的目标，分析用户的基本需求，问题定义并分析可行性。问题定义确定软件系统的主要功能；
可行性研究对问题定义阶段所确定的问题实现的可能性和必要性进行研究。
（2）开发期。包括分析、设计和实施两类任务。分析、设计包括需求分析、总体设计和详细设计3阶段，实施包括编码和测试2阶段。
（3）运行期。主要任务是软件维护。
17.????? 软件需求规格说明书**填空 （1）它是需求分析阶段的最后成果，是软件开发的重要文档之一。
（2）作用。便于用户、开发人员进行理解和交流；
软件开发的基础和依据；
确认测试和验收的依据。
（3）主要内容。数据描述、功能描述、性能描述。
3.3? 结构化设计方法 18.????? 软件设计的基础 （1）?????????? 软件设计是把软件需求转换为软件表示和过程。
（2）?????????? **从技术上讲软件设计包括：结构设计、数据设计、接口设计、过程设计。
（3）?????????? ****从工程上讲软件设计包括：概要设计、详细设计 19.????? 软件设计的基本原理 （1）?????????? 抽象：把事物本质的共同特性提取出来而不考虑其他细节。
（2）?????????? 模块化：
模块是指把一个待开发的软件分解成若干小的简单的部分，如高级语言的过程、函数、子程序等。
模块化是指解决一个复杂问题时自顶向下逐层分解把软件系统划分成若干模块的过程。
（3）?????????? 信息隐蔽：指一个模块它包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。
（4）?????????? 模块独立性。
20.????? 模块独立性 （1）模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。
（2）模块的独立性是评价软件设计好坏的重要标准。衡量模块独立性的方法有两种，即耦合性和内聚性。希望高内聚、低耦合。** （3）耦合性是模块之间的相互联系的紧密程度的度量。耦合度从高到低如下7种：
**内容耦合（耦合度最强）；
一个模块直接访问另一模块的内容。
公共耦合；
一组模块都访问同一全局数据结构。
外部耦合；
一组模块都访问同一全局数据项。（变量）。
控制耦合；
一模块把开关量等信息送入另一模块，控制另一模块的功能。
标记耦合；
两个模块通过数据结构交换信息。
数据耦合；
两模块间传递数据参数。
非直接耦合（耦合度最弱）。两模块没有直接关系，只通过主模块控制和调用。
（4）内聚性是指从功能角度分析模块内部的联系。内聚度从弱到强如下7种：
偶然内聚；
一个模块内部各处理元素间没有任何联系。
Rrrrrr Aaaaa Bbbbb ccccc ? 5555 555555 Bbbbb Aaaaaa Cccccc ffrfrrrr ? Aaaaaaa Bbbbbbb Ccccccc 偶然 ? ? 1/0 ? If? a=1 求平均值 Else 求最大值 ? 逻辑内聚；
模块内执行几个逻辑上相关的功能，通过参数确定该模块完成哪一个功能。
? ? 时间内聚；
把需要同时或顺序执行的动作组合到一个模块。如月初始化模块。
过程内聚；
模块内的处理元素相关，且必须以特定次序执行。
例如：
? 数据排序 ? 二分查找 通信内聚；
模块内各部分均使用相同的输入或产生相同的输出。所有成分都通过使用公用数据而发生关系。
顺序内聚；
模块内各处理元素和同一个功能密切相关，而且这些处理必须顺序执行，通常一个元素的输出是另一元素的输入。
**功能内聚。模块内所有元素共同完成一个功能，缺一不可，模块不可再分。
例如：
?? 求一元二次方程的根 ?? Root( a, b, c, x1, x2) { ???? } 21.????? 结构化设计方法。
（1）?????????? 基本思想。是将软件设计成由相对独立、单一功能的模块组成的结构。
（2）?????????? 要求所有模块只使用单入口、单出口，顺序、选择、循环3种基本控制结构。
22.????? 概要设计 （1）任务4条：设计软件系统结构；
设计数据结构及数据库；
编写概要设计文档；
评审。
（2）软件结构图的基本图符号 一般模块（矩形框），数据信息（空心箭头○→），控制信息（实心箭头●→）。
主模块 ? 子模块1 ? 单价 ? 数量 ? 金额 ? 子模块3 ? 子模块2 ? （3）?????????? 结构图的形态特征：
深度：模块的层数。
宽度：一层中最大的模块数。
扇入：一个模块直接上属模块的个数。
扇出：一个模块直接调用下属模块的个数。
（4）?????????? 结构图的4种模块类型：
? 传入模块；
传出模块；
变换模块；
协调模块。
（5）?????????? **模块的作用范围和控制范围。
模块的作用范围：指受该模块内一个判定影响的所有模块集合。
控制范围：指模块本身及其下属模块的集合。
**模块的作用范围应在其控制范围之内，且判定所在的模块与受其影响的模块在层次上尽量靠近。
（6）?????????? 软件结构图优化准则。或称设计准则。
高内聚、低耦合；
模块作用范围在控制范围内；
深度、宽度、扇入、扇出应适当；
模块大小要适中。（减少接口复杂性，单入口单出口，模块功能可预测） （7）?????????? 面向数据流的设计方法。
**数据流图有两种类型：变换型和事务型。
? 查询 ? 变换型系统结构图由输入、中心变换和输出3部分组成。
? 输入 ? ? 计算 ? ? 输出 ? ? ？？ ? ? ？？ ? ? ? ? ? ? 事务型。事务中心接收数据，分析每个事务以确定它的类型，根据事务类型选取一条活动通路。
? ? ? 功能分析 ? ? 借书 ? ? 还书 ? ? 续书 ? ? 入库 ? 23.????? 详细设计 （1）?????????? 任务。是为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。
详细设计也称过程设计，主要确定每个模块具体执行过程，其结果基本上决定了最终的程序代码质量。
（2）?????????? 详细设计工具3种。
图形工具：程序流程图、N-S（方框图，盒图）、PAD，HIPO 表格工具：判定表 语言工具：PDL（伪码）。
（3）程序流程图，传统、广泛。也称程序框图。独立于任何一种程序设计语言。基本图符：方框表示加工处理步骤，菱形代表逻辑条件，箭头表示控制流。
五种控制结构是：顺序型，选择型，先判断重复型，后判断重复型，多分支选择型。
缺点：不支持逐步求精，随意转移，不易表示数据结构。
（4）N-S。五种控制结构 （5）PAD。问题分析图。五种控制结构 （6）PDL又称伪码。借助某些高级语言的控制结构和一些自然语言的嵌套。
3.4 软件测试 24.????? 软件测试 （1）?????????? 测试的目的。是查找错误而不是为了演示软件的正确功能。
（2）?????????? 测试的准则。追溯到需求；
排除随意性；
注意群集；
避免自己测试；
穷举不可能；
妥善保存测试计划和测试用例。
25.????? 静态测试与动态测试 静态测试。不实际运行软件。主要通过人工进行。包括代码审查、静态结构分析、代码质量度量等。
动态测试。基于计算机的测试。是为了发现错误而执行程序的过程。
测试用例。是指为测试设计的数据，***包括测试输入数据和与之对应的预期输出结果两部分。
动态测试设计测试用例的方法有两类：白盒（白箱）测试与黑盒（黑箱）测试。其关键是设计高效、合理的测试用例。
26.????? 白盒测试与黑盒测试 （1）白盒测试又称结构测试或逻辑驱动测试。它与程序内部结构有关，要利用程序结构的实现细节设计测试用例。常用方法有逻辑覆盖法和基本路路径测试。
（2）逻辑覆盖法有：
**语句覆盖：（最弱），选择足够的测试用例，使程序中每一个语句都执行一次。
判定覆盖：选择足够的测试用例，使程序中每一个判定至少获得“真”一次和“假”一次。
条件覆盖：使每一个判定中的每一个条件至少获得“真”一次和“假”一次。
判定、条件覆盖：使每一个判定中的每一个条件至少获得“真”一次和“假”一次，并且每一个判定至少获得“真”一次和“假”一次。
路径覆盖：使程序中所有可能的路径都至少经历一次。
（3）黑盒测试又称功能测试或数据驱动测试。不关心程序内部的逻辑，只是根据程序的功能来设计测试用例。主要用于软件确认测试。
（4）黑盒测试的常用方法有等价类划分、边界分析法、错误推测法、因果图等。
等价类划分：将程序的所有可能的输入数据划分成若干部分，然后从每个等价类中选取数据作为测试用例。等价类包括有效等价类和无效等价类。
边界分析法：对各种输入、输出范围的边界情况设计测试用例。
错误推测法：通过经验或直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的例子。
27.????? 软件测试的具体实施步骤 （1）实施步骤依次为单元测试、集成测试、验收测试、系统测试。
（2）单元测试。是对软件设计的最小单位—模块（程序单元）进行正确性测试，目的是发现各模块内部可能存在的错误。测试的依据是详细设计说明书和源程序。
（3）集成测试。是测试和组装的过程。主要目的是发现与接口有关的错误，依据是概要设计说明书。
组装方法的非增量方式和增量方式。
（4）确认测试。是验证软件的功能和性能及其它特征是否满足需求规格说明中确定的各种需求。一般以黑盒测试为主。用户为主。
（5）系统测试。
将通过确认的软件作为整个基于计算机系统的一个元素，与计算机系统的其他元素结合在一起，在实际环境下进行一系列集成测试和验收测试。目的是在真实环境下检查软件是否能与系统正确连接发现软件与系统需求不一致的地方。
3.5 程序调试（DEBUG） 28.????? 程序调试 （1）?????????? 在测试成功后开始。任务是诊断和改正程序中的错误。调试主要在开发阶段进行。
（2）?????????? 基本步骤。错误定位；
修改设计和代码，以排除错误；
进行回归测试，防止引进新的错误。关键在于推断程序内部的错误位置及原因。
（3）?????????? 调试原则。
确定错误的性质和位置的原则：分析思考与错误征兆有关的信息；
避开死胡同；
只把调试工具当辅助手段；
避免用试探法。
修改错误的原则：
在出现错误的地方，很可能有别的错误；
修改错误的一个常见失误是只修改了错误的表现，而没有修改错误本身；
修改一个错误的同时可能会引入新的错误；
修改错误的过程将迫使暂时回到程序设计阶段；
修改源代码，不要改变目标代码。
（4）?????????? 调试方法。
强行排错法：是传统的调试方法。其过程为：设置断点、程序暂停、观察程序状态、继续运行程序。涉及的调试技术主要是设置断点和监视表达式。
回溯法：（适合小程序）。从发现“症状”的位置，沿程序的控制流程，逆向跟踪源程序代码。
原因排错法：通过演译和归纳，以及二分法实现。
3.6 软件工程管理 29.????? 软件工程管理 （1）?????????? 职能。组织管理、人员管理、资源管理、计划管理。
（2）?????????? 进度安排。主要方法有甘特图法（GANTT），时间标记网络法，进度计划评审法和关键路径法。
（3）?????????? 标准化。软件工程标准化包括：如何制定软件计划；
怎样进行需求分析、设计；
编码测试要求；
维护及软件的组织管理。
（4）?????????? 软件工程标准化的作用。
提供共同遵守的规定，规范行为和有效通讯；
为软件工程成果评价验收提供统一标准；
对维护有好处。
第4章 数据库设计基础 4.1? 数据库系统基本概念 1.? 数据（Data）。是指描述事务的符号记录。是数据库中存储的基本对象。数据有临时性数据和持久性数据，数据库系统中处理持久性数据。数据有型和值之分，型给出了数据的表示类型，如整型、实型、字符型等，值给出了符合给定型的值。
**数据项是数据处理的最小单位。
2.? 数据库（DB）。是指长期存储在计算机内的、有组织的、可共享的数据集合。它有最小的冗余度，最高的独立性。
3.? **数据库管理系统（DBMS）。
（1）是数据库的机构，它是一种系统软件，负责数据库中数据的组织、数据操纵、数据维护、控制及保护和数据服务等。它是数据库系统的核心。
例如：VF，Access,Oracle等 （2）提供6大功能。数据模式定义；
数据存取的物理构建；
数据操纵；
数据的完整性、安全性定义与检查；
数据库的并发控制与故障恢复；
数据的服务。
（3）提供的数据语言。数据定义语言（DDL）；
数据操纵语言（DML）；
数据控制语言（DCL）。
数据语言还可分为交互式语言和宿主型语言。
（4）常见的DBMS。微软的SQL server；
Oracle；
IBM 公司的DB2和IMS（层次），VF，Access。
4.? 数据库管理员（DBA）。
（1）?????????? 是指对数据库规划、设计、维护、监视的人员。
（2）?????????? 主要工作是：数据库设计；
数据库维护；
改善系统性能，提高系统效率。
5.? 数据库系统（DBS）。指计算机系统引入数据库后的系统构成。包括5部分：数据库（数据）+数据库管理系统（软件）+数据库管理员（人员）+系统平台一（硬件平台）+系统平台二（软件平台）。
***DBS包括数据库和数据库管理系统 DBS>DBMS? DBS>DB? 6.? 数据库应用系统（DBAS）。是数据库加上应用软件及应用界面这三者组成，包括6部分：数据库，数据库管理系统，数据库管理员，硬件平台，应用软件，应用界面。
7.? 数据库系统的发展。3个阶段。
（1）人工管理阶段。应用程序管理数据。无共享性。不独立。
（2）文件系统阶段。文件系统管理数据。共享性差。独立性差。
（3）数据库系统阶段。DBMS管理数据，共享性高。独立性高。
8.? 数据库系统的基本特点。
（1）数据的集成性。
（2）数据的高共享性和低冗余性。
（3）数据的独立性。**分为(物理独立性)和(逻辑独立性)。前者，物理结构改变，不引起应用程序的变化，后者，数据库总体逻辑结构改变，不需修改应用程序。
（4）数据统一管理和控制。
9.? 数据库系统的内部结构体系 （1）数据库在其内部有3级模式、两级映射。3级模式是概念级模式、内部级模式、外部级模式，即内模式、模式、外模式。两级映射是模式/内模式映射、外模式/模式映射。
（2）概念模式：也称逻辑模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户的视图。与硬件环境、软件环境无关。
（3）外模式：也称子模式，它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的视图。
（4）内模式：也称物理模式，给出数据库物理存储结构与物理存取方法，内模式的物理性主要体现在操作系统及文件级上。
（5）内模式处于最底层，反映数据在计算机物理结构中的实际存储形式；
概念模式处于中间层，反映设计者的数据全局逻辑要求；
外模式处于最外层，反映用户对数据的要求。
（6）两种映射均由DBMS实现。
4.2 数据模型 10.????? 数据模型的概念。
（1）定义。数据模型是数据特征的抽象。
（2）数据模型的三要素：数据结构，数据操作，数据约束。数据结构是最关键的要素。
数据结构：主要描述数据的类型、内容、性质及数据间的联系。数据结构是数据模型的基础。
数据操作：描述在相应数据结构上的操作类型与操作方式。
数据约束：描述数据结构内数据语法、语义联系，它们之间的制约与依存关系，以及数据动态变化的规则，以保证数据的正确、有效与相容。
（3）**数据模型按应用层次分三种：概念模型，逻辑模型，物理模型。
概念模型：面向客观世界、面向用户，与DBMS无关，与计算机平台无关。是数据模型的基础。目前较有名的是E-R模型、扩充的E-R模型、面向对象的模型及谓词模型。
? 学生 ? 课程 ? 学号 ? 姓名 ? 性别 ? 年龄 ? 课号 ? 课名 ? 学分 ? 选修 ? ? N ? M ? 成绩 ? 逻辑数据模型：又称逻辑模型，是面向数据库系统的模型，着重于数据库系统一级的实现。著名的有：层次模型、网状模型、关系模型、面向对象的模型。
? 关系模式：
学生（学号，姓名，性别，年龄） 课程（课号，课名，学分） 选修（学号，课号，成绩? ） 在VF中：
“学生”表：
学号? C? 10 姓名? C? 8 性别? C? 2 年龄? N? 3? 0 Create table 学生(学生 C, …) 物理数据模型：
又称物理模型，是面向计算机物理表示的模型。它给出数据模型在计算机上物理结构的表示。
11.????? E-R模型。
（1）**E-R图即实体联系图，矩形表示实体集，椭圆表示属性，菱形表示联系。联系也可能有自己的属性。
（2）***两个实体间联系有1：1，1：M，M：N，即一对一，一对多，多对多三种。
例如：一个学校有1 个正校长 一个班级有N个学生。
????? 一个学生可以选修N门课；
一门课程可以由多个学生选修。
? ***数据的逻辑模型有3种：层次、网状、关系模型。
12.????? 层次模型。
发展最早。
实体的联系表示为树型结构。
用记录类型描述实体型，只能直接处理“一对多”联系，“多对多”联系须分解为“一对多”。
性能优于关系模型。插入删除限制多。
13.????? 网状模型。
实体的联系表示为网状。
用记录类型描述实体型，只能直接处理“一对多”联系。
性能明显优于层次模型。
14.????? 关系模型。
（1）用二维表表示，简称表。表由表框架及表的元组组成。表框架由N个命名的属性组成,每行数据叫元组。
用关系描述实体型。多对多联系直接表示。
关系模型的优点：
建立在严格的数学基础上；
实体和各类联系都用关系表示；
对数据的检索结果也是关系；
关系模型的存取路径对用户透明。
查询效率低。
二维表应满足的7条性质：
元组个数有限；
元组均不相同（元组唯一性）；
元组次序可交换；
元组的分量不可分；
属性名惟一；
属性次序可交换；
分量值域同一性。
（2）***关系中的数据约束有3种：实体完整性，参照完整性，用户定义的完整性。
（3）完整性 实体完整性：（主键中的属性值不能为空值， 这是数据库完整性的最基本要求） 学号? 姓名?? 性别? 年龄 ----------------------------------- 1011? 张三?? 男?? 20 1012? 李四?? 女?? 19 1013? 王五?? 男?? 22 参照完整性：不允许引用不存在的元组，即，在关系是的外键要么是所关联关系中实际存在的元组，要么是空值。
学号? 课号?? 成绩 ------------------------------ 1011? 05??? 80 1081? 01??? 90 用户定义的完整性：针对具体数据环境与应用环境由用户具体设置的约束。
在VF中，数据库的表可以设置字段有效性：
有效规则：性别$’男女’ 错误信息: “性别错误” ??? 默认值：”男” （4）***任何关系数据库系统都应该支持实体完整性和参照完整性。
4.3? 关系代数 （1）关系模型的基本操作。
有4 种：插入、删除、修改、查询，可分解为6种：属性指定；
元组选择；
两个关系合并；
关系的查询；
元组插入；
元组删除。
（2）关系模型的基本运算。
插入、删除、修改、查询 （1、投影π2、选择σ 3、笛卡尔积×）。
（3）关系代数的扩充运算。
交运算：∩?? 除运算：÷??? 连接与自然连接；
? ? R U S????? R-S????? R∩S A ?B ?C ? ?A ?B ?C ? ?A ?B ?C ? a1 ?b1 ?c1 ? ?a1 ?b1 ?c1 ? ?a1 ?b2 ?c2 ? a1 ?b2 ?c2 ? ? ? ? ? ?a2 ?b2 ?c1 ? a2 ?b2 ?c1 ? ? ? ? ? ? ? ? ? R???????????? S??????????????????????? A ?B ?C ? ?A ?B ?C ? a1 ?b1 ?c1 ? ? a1 ?b2 ?c2 ? a1 ?b2 ?c2 ? ?a1 ?b1 ?c2 ? a2 ?b2 ?c1 ? ?a2 ?b2 ?c1 ? ? R X S R.A ?R.B ?R.C ?S.A ?S.B ?S.C ? a1 ?b1 ?c1 ? a1 ?b2 ?c2 ? a1 ?b1 ?c1 ?a1 ?b1 ?c2 ? a1 ?b1 ?c1 ?a2 ?b2 ?c1 ? a1 ?b2 ?c2 ? a1 ?b2 ?c2 ? a1 ?b2 ?c2 ?a1 ?b1 ?c2 ? a1 ?b2 ?c2 ?a2 ?b2 ?c1 ? a2 ?b2 ?c1 ? a1 ?b2 ?c2 ? a2 ?b2 ?c1 ?a1 ?b1 ?c2 ? a2 ?b2 ?c1 ?a2 ?b2 ?c1 ? R÷S A ?B ?C ? ?A ?B ?C ? a1 ?b1 ?c1 ? ? a1 ?b2 ?c2 ? a1 ?b2 ?c2 ? ?a1 ?b1 ?c2 ? a2 ?b2 ?c1 ? ?a2 ?b2 ?c1 ? 注意：
（）笛卡尔积与除运算是逆运算；
（）T/R=S除运算条件：T中的域包含R中的所有域，T中有一些域不出现在R中。S中的域由T中那些不出现在R中的域组成。
如：T（ABC），R（BC），S=（A） （）自然连接的条件：两关系有公共域，通过公共域相同值连接。
（）连接又称θ连接，其元组一般远远少于笛卡尔积的元组。θ是比较符，为=、>、<时分别称等值连接，大于连接、小于连接。θ还可以是>=,<=,≠。
关系代数的应用实例：
S(S#,Sn,Sd,Sa)?? 学生（学号，姓名，系别，年龄 ） C(C#,Cn,P#)???? 课程（课程号，课程名，先修课号） SC(S#,C#,G)??? 选修（学号，课程号，成绩） （1）检索学生所有情况；
（2）检索年龄大于等于20岁的学生和姓名 （3）检索先修课程号为C2的课程的课程号 （4）检索课程号为C，且成绩为A的所有学生姓名 （5）检索S1所修读的所有课程名及先修课号。
（6）检索年龄为23岁的学生所修读的课程名。
（7）检索至少修读S5所修读的一门课程的学生姓名。
（8）检索修读了S5所修读全部课程的学生学号（或姓名）。
4.4? 数据库的设计与原理 1．数据库设计概述 （1）数据库设计的基本任务：根据用户对象的信息要求、处理需求和数据的支持环境（包括硬件、操作系统与DBMS）设计出数据模式。信息要求是静态要求，处理需求是动态要求。
（2）数据库设计有两种，一种是以信息需求为主，称为面向数据的方法；
另一种以处理需求为主，称为面向过程的方法。前者已是主流。
（3）数据库设计目前一般采用生命周期法。将整个数据库应用开发分成以下阶段：1）需求分析、2）概念设计、3）逻辑设计、4）物理设计、5）编码、6）测试、7）运行阶段。重点 （4）数据库设计的4个阶段 1）需求分析 2）概念设计 3）逻辑设计 4）物理设计。
2．需求分析 （1）任务：通过详细调查现实世界要处理的对象，充分了解原系统的工作概况，明确用户的各种需求，然后确定新系统的功能。
（2）需求分析的重点是调查、收集与分析用户在数据管理中的信息要求、处理要求、安全性及完整性要求。
（3）数据字典（DD）是各类数据描述的集合。通常包括：数据项，数据结构，数据流，数据存储和处理过程5部分。
（4）在需求分析时注意：重要而困难的任务是收集将来应用所涉及的数据；
必须强调用户的参与（这是数据库应用设计的特点）。
3．概念设计 （1）目的：分析数据间内在语义关联，在此基础上建立一个数据的抽象模型。
（2）概念设计的方法。有集中式模式设计法和视图集成设计法（先作局部模式设计，再集成）。
（2）概念设计的过程。选择局部应用；
视图设计；
视图集成。
（3）视图设计的三种次序：自顶向下；
由底向上；
由内向外。
（4）视图集成中的冲突：命名冲突；
概念冲突；
域冲突；
约束冲突。
4．逻辑设计。任务 （1）主要工作是：将E-R图转换成指定RDBMS中的关系模式。
（2）内容：从E-R图向关系模式转换；
逻辑模式规范化及调整、实现；
关系视图设计（又称外模式设计）。
（3）E-R模型与关系的对照：属性-属性，实体—元组，实体集—关系，联系—关系。
对照：
列，属性，字段（如张三的姓名） 行，元组，记录，实体（如张三是一个实体） 表，实体集，关系，文件 ? （4）关系视图的作用：提供数据逻辑独立性；
能适应用户对数据的不同需求；
有一定数据保密功能。
例：学生表 Open? data? xsgl Create? view xscj as select 学号，姓名，总分 from学生表 Use? xscj brow 视图是一个虚表 5．物理设计 （1）主要目标：对数据库内部物理结构作调整，并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。
（2）物理设计的内容：索引设计、聚簇设计、分区设计。
（3）另外：
数据库在物理设备上的存储结构与存取方法称为数据库的物理结构。
物理设计内容：为关系模式选择存取方法；
设计关系、索引等数据物理存储结构。
6．数据库管理。
（1）数据库是一种共享资源，需要维护与管理，这种工作称为数据库管理。
数据库管理工作由数据库管理员（DBA）负责。
（2）数据库管理包括：
1）数据库的建立 2）数据库的调整 3）数据库的重组 4）数据库的安全性控制与完整性控制 5）数据库的故障修复 6）数据库监控。
? 软件工程及程序设计基础历届考题 2002年4月 1、（02-4）编制一个好的程序，首先要保证它的正确性可靠性，还应强调良好的编程风格，在书写功能性注释时应考虑（? ）。
A. 仅为整个程序作注释????? B. 仅为每个模块作注释 C. 为程序段作注释????????? D. 为每个语句作注释 2、（02-4）需求分析最终结果是产生（? ）。
A．项目开发计划??? B．设计说明书?? C．可行性分析报告? D．需求规格说明书 3、（02-4）下列哪个是面向对象程序设计不同于其他语言的主要特点（? ）。
A. 继承性?? B. 消息传递? C. 多态性? D. 静态联编 4、（02-4）在进行单元测试时，常用的方法是（? ）。
A. 采用白盒测试，辅之以黑盒测试? B. 采用黑盒测试，辅之以白盒测试 C. 只使用白盒测试??????????? D. 只使用黑盒测试 5、（02-4）数据流的类型有（）型和事务型。
2002年9月 1、（02-9）源程序中应包含一些内部文档，以帮助阅读和理解和程序，源程序的内部文档通常包括合适的标识符、注释和（? ）。
A. 程序的视觉组织?? B. 尽量不使用或少用GOTO语句 C. 检查输入数据的有效性?? D. 设计良好的输出报表 2、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送（? ）。
A. 调用语句??? B. 命令???? C. 口令???? D. 消息 3、下面不属于软件工程的3个要素的是（? ）。
A. 工具??? B. 过程???? C. 方法??? D. 环境 4、软件调试的目的是(? )。
A. 发现错误??????? B. 改正错误 C. 改善软件的性能?? D. 挖掘软件的潜能 5、软件是程序、数据和（）的集合。文档 2003年4月 1、结构化程序设计主要强调的是（） A程序的规模? B程序的易读性 C模块类型划分 D模块耦合度 2、软件详细设计的主要任务是确定每个模块的 A算法和使用的数据结构? B外部接口 C功能D编程 3、在结构化方法中，软件功能分解属于下列软件开发中的阶段是 A详细设计? B需求分析? C总体设计? D编程调试 4、概要设计是软件系统结构的总体设计，以下选项中不属于概要设计的是 A把软件划分成模块?? B确定模块之间的调用关系 C确定各个模块的功能 D设计每个模块的伪代码 5、对于软件测试，从是否需要执行被测试软件的角度，可以分为静态测试和动态测试。代码检查属于（）测试。
2003年9月 1、（03-9）下面对对象概念的描述错误的是（ A ）。
A. 任何对象都必须有继承性 ?? B. 对象是属性和方法的封装体 C. 对象间的通讯靠消息传递 ?? D. 操作是对象的动态属性 2、对建立良好的编程风格，下面描述正确的是（A? ）。
A. 程序应简单、清晰、可读性好 ?? B. 符号名的命名只要符合语法即可 C. 充分考虑程序的执行效率??? ?? D. 程序的注释可有可无 3、检查软件产品是否符合需求定义的过程称为( A )。
A. 确认测试??? B. 集成测试 C. 验证测试???? D. 验收测试 4、在结构化方设计方法中，下面哪种内聚的内聚性最弱（ C ）。
A. 逻辑内聚???? B. 时间内聚 C. 偶然内聚???? D. 过程内聚 5、软件开发环境是全面支持软件开发全过程的（）集合。软件工具 2004年4月 1、（04-4）下面描述中，不符合结构化程序设计风格的是 A、使用顺序、选择和重复三种基本控制结构表示程序的控制逻辑?? B、注重提高程序的可读性 C、模块只有一个入口和出口???? D、使用GOTO语句 2、在面向对象设计中很多基本特点，其中“从外面看只能看到对象的外部特性，而对象的内部对外是不可见的”这一性质指的是对象的 A分类性???? B标识唯一性???? C多态性?? D封装性 3、用黑盒技术测试用例的方法之一为 A因果图? B逻辑覆盖 ?C循环覆盖 D基本路径测试 4、软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及 ( ) A. 阶段性报告? B. 需求评审? C. 总结 D．都不正确 5、按数据流的类型，结构化设计方法有两种设计策略，它们是变换分析设计和（）。事务分析设计 2004年9月 1、（04-9）结构化程序设计的一种基本方法是 A筛选法?? B递归法?? C归纳法? D逐步求精法 2、（04-9）函数重载是指 A两个或两个以上的函数取相同的函数名，但形参的个数或类型不同 B两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同 C两个以上的函数名字不同，但形参的个数或类型相同 D两个以上的函数取相同的函数名，并且函数的返回类型相同 3、（04-9）不属于软件设计原则的是 A抽象??? B模块化? C自底向上? D信息隐藏 4、（04-9）结构化程序由三种基本结构组成，三种基本结构组成的算法 ? A 可以完成任何复杂的任务 B只能完成部分复杂的任务 C只能完成符合结构化的任务? D只能完成一些简单任务 5、（04-9）若按功能划分，软件测试的方法通常分为（）测试方法和黑盒测试方法。
2005年4月 1、（05-4）下列对于软件测试的描述中正确的是(C? )。
A. 软件测试的目的是证明程序是正确的 B. 软件测试的目的是使程序运行结果正确 C. 软件测试的目的是尽可能多地发现程序中的错误 D. 软件测试的目的是使程序符合结构化原则 2、（05-4为了使模块尽可能独立，要求：B A 模块有内聚程序要尽可能高，且各模块间的耦合程序要尽量高 B模块有内聚程序要尽可能高，且各模块间的耦合程序要尽量弱 C模块有内聚程序要尽可能低，且各模块间的耦合程序要尽量弱 D模块有内聚程序要尽可能低，且各模块间的耦合程序要尽量强 3、（05-4下列描述中正确的是（? D ）。
A. 程序就是软件? B. 软件开发不受计算机系统的限制 C. 软件既是逻辑实体，又是物理实体D. 软件是程序、数据与相关的文档的集合 4、在面向对象方法中，类的实例称为（）。对象 5、诊断和改正程序中错误的工作通常称为（）。调试 2005年9月 1、（05-9）下列叙述中正确的是（?? ）。
A. 程序设计就是编制程序 B. 程序的测试必须由程序员自己去完成?? C. 程序经调试改错后还应进行再测试? D. 程序经调试改错后不必进行再测试 2、（05-9）在软件设计中，不属于过程设计工具的是（?? ）。
A. PDL（过程设计语言） B. PAD图?? C. N-S图???? D. DFD图 3、（05-9）下列描述中正确的是（?? ）。
A. 软件工程只是解决软件项目的管理问题 B. 软件工程主要解决软件产品的生产率问题?? C. 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则?? D. 软件工程只是解决软件开发中的技术问题 4、（05-9）下面叙述中正确的是（? ）。
A．软件交付使用后还需要进行维护? B．软件一旦交付使用就不需要再进行维护 C．软件交付使用后其生命周期就结束?? D．软件维护是指修复程序中被破坏的指令 5、（05-9）在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块（桩模块）。其中（ ）的作用是将测试数据传送给被测试模块，并显示被测试模块所产生的结果。
数据库基础历届考题 （05-4）在关系数据库中，将数据表示成二维表，每一个二维表称为（）。
（05-9）数据库设计的根本目标是要解决A A数据共享问题? B数据安全问题 C大量数据存储问题 D简化数据问题 （05-9） 设有如**系表：
R A ?B ?T A ?B ?C ? 1 ?1 ?2 ? 2 ?2 ?3 ? 3 ?1 ?3 ? ? ? C ? 1 ?1 ?2 ? 2 ?2 ?3 ? S A ?B ?C ? 3 ?1 ?3 ? 则下列操作中正确的是：A、T=R∩S? B、 T=R∪S??? C、 T=RXS? D 、T=R/S? （05-9）数据库系统的核心是B A数据模型? B数据库管理系统? C数据库 D数据库管理员 （05-9） 数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是（ ）数据库系统 2005年4月试题 (1)????????????? 数据的存储结构是指______。? A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 （2）下列关于栈的描述中错误的是______。? A） 栈是先进后出的线性表 B） 栈只能顺序存储 C） 栈具有记忆作用 D） 对栈的插入与删除操作中，不需要改变栈底指针 （3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是。
A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 （4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为______ A）log2n B）n/2 C）n D）n+1 （5）下列对于线性链表的描述中正确的是______。
A） 存储空间不一定是连续，且各元素的存储顺序是任意的 B） 存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C） 存储空间必须连续，且前件元素一定存储在后件元素的前面 D） 存储空间必须连续，且各元素的存储顺序是任意的 （6）下列对于软件测试的描述中正确的是______。
A） 软件测试的目的是证明程序是否正确 B） 软件测试的目的是使程序运行结果正确 C） 软件测试的目的是尽可能多地发现程序中的错误 D） 软件测试的目的是使程序符合结构化原则 （7）为了使模块尽可能独立，要求______。
A） 模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强 B） 模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱 C） 模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱 D） 模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强 （8）下列描述中正确的是______。
A）程序就是软件 B）软件开发不受计算机系统的限制 C）软件既是逻辑实体，又是物理实体 D）软件是程序、数据与相关文档的集合 （9）数据独立性是数据库技术的重要特点之一，所谓数据独立性是指______。
A）数据与程序独立存放 B）不同的数据被存放在不同的文件中 C）不同的数据只能被对应的应用程序所使用 D）以上三种说法都不对 （10）用树形结构表示实体之间联系的模型是______。
A）关系模型 B）网状模型 C）层次模型 D）以上三个都是 填空：
（1）某二叉树中度为2的结点有18个，则该二叉树中有 【1】 个叶子结点。
（2）在面向对象方法中，类的实例称为 【2】 。
（3）诊断和改正程序中错误的工作通常称为 【3】 。
（4）在关系数据库中，把数据表示成二维表，每一个二维表称为 【4】 。
（5）问题处理方案的正确而完整的描述称为 【5】 。
2005年9月试题 (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）软件工程只是解决软件开发中的技术问题 （6）在软件设计中，不属于过程设计工具的是 A）PDL(过程设计语言) B）PAD图 C）N-S图 D）DFD图? （7）下列叙述中正确的是 A）软件交付使用后还需要进行维护 B）软件一旦交付使用就不需要再进行维护 C）软件交付使用后其生命周期就结束 D）软件维护是指修复程序中被破坏的指令 （8）数据库设计的根本目标是要解决 A）数据共享问题 B）数据安全问题 C）大量数据存储问题 D）简化数据维护 （9）设有如**系表: R????????? S?????? T? A B C???? A B C??? A B C 1 1 2????? 3 1 3???? 1 1 2 2 2 3?????????????? 2 2 3 ?????????????????? 3 1 3 则下列操作中正确的是 A）T＝R∩S B）T＝R∪S C）T＝R×S D）T＝R/S （10）数据库系统的核心是 A）数据模型 B）数据库管理系统 C）数据库 D）数据库管理员 填空：
（1）?????????? 数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是 【1】 。
（2）?????????? 算法复杂度主要包括时间复杂度和 【2】 复杂度。 （3）?????????? 在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块（桩模块）。其中 【3】 的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。
（4）?????????? 一棵二叉树第六层（根结点为第一层）的结点数最多为 【4】 个。 （5）?????????? 数据结构分为逻辑结构和存储结构，循环队列属于 【5】 结构。
? ?