二级公共基础要点-l

1、数据项是不可分割的最小数据单位。数据对象是性质相同的数据元素的集合,. 数据结构指相互有关联的数据元素的集合。域（存储元素值）和指针域（存放指针，指示前趋/后继结点）o存储空间可连续或不连续,结点的存储顺考纲基本要求1. 掌握算法的基郴念。2. 掌握基本纯结构及其操作。3. 掌握基本排序和查找算法。4. 掌握逐步求精的结构化程序设计方法。5. 掌握软件工程的基本方法,具有初步应用相关技 术进行软件开发的能力。6. 掌握数据库的基本知识，了解关系数据库的设计。1. 算法的基本概念；算法复杂度的概念和意义（时间 复杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构;数 据结构的图形

2、表示；线性结构与非线性结构的概 念。3. 线性表的定义；线性表的顺序存储结构及其插入 与删除运算。4-栈和队列的定义；栈和队列的顺序存储结构及其 基本运算。5. 线性单链表、双向链表与循环链表的结构及其基 本运算。6. 树的基本概念;二叉树的定义及其存储结构;二叉 树的前序、中序和后序遍历。7鯛查找与二分軽找算法;基本排序算法佼换 类排序，选择类排序，插入类排序）。算法舷夠唸解题方案的准确、完整描述。算法是特定问题求解方法与步骤的描述，是指 令的有限序列，其中每条指令表示一或多个操作。算 法不等于程序，程序编制不可能优于算法设计。算法的基本特征:卯管住；确定性；有穷 性；有足够的情报。 可行性

3、:算法中描述的操作都必须可以通过 已实现的基本运算执行有限次实现。 ®定性:算法中每条指令都必须含义确切，无 歧义。对相同的输入只能得出相同的输出。 有穷性:二个算法必须能在执行有穷步之后 结束,且每一步都可在有穷时间内完成。 拥有足够的情报（输）:一个算法有零或多 个输入。瞬出:无输出的算法没有意义。遽滋窿杏輕数据运算和操作；算法的 控制埶基本运算和操性:算术运算、逻辑运算、关系运 算、数据传输。基本控制鮒顺序，卿' 循环帥算法基本设计方法洌举、归纳、递扭 递归、 分治（减斗递推）、回溯法。算法复杂度:包括时间复杂度和空间复杂度。 时间复杂度.执行算法所需的计算工作量。空间

4、复杂度.执行算法所需的内存空间。常见时间复杂度：常量阶0u），对数阶o（l（）gn）, 线性阶0（n）,平方阶0（n"2）,指数阶0（2®（a） +x;s=x; / 0（1）（b）for （i=l;i<=n;卄i） 卄x;s+二x;/ 0（n）（c）for （j=l;j<=n;+i）for （k= 1;k<=n;-h-k） +x;s+=x; / 0（n2） 时间复杂度的计算:找出基本运算；计算基 本运算的执行频数；提取最高阶的执行频数。篡法的分析方袪:俯均性态（各种特定 输入下斟运算执行次数的加权平均働;最坏情 况复杂性（规模为n时基本运算的最大执行次数）

5、。篡法复杂度的意义:算法复杂度描述算法执行 时的时空开销与问题规模之间的关系设计时应尽 量选择复杂度低的算法，以节省时空开销。1.2数据结构的基本概念 1. 2. 1数据结构的定义与研究内容计算机科学中 指所有能被计算机程序处理的符号的总称。数据元素（元素、记录）是基本数据单位,常作为 一个整体处理。二:个数据元素由若干数据项组成,研究的三个方面:逻辑騒 存胳构,运算。 逻辑结构:数据元素）及其之间的逻辑 关系（r）。即：b二（d,r）逻辑钠分为线性结构与非线齢构2大类。线性结构:满足2条件:有且只有1个根结点； «个结点最多有个前件,最多有个后件。非线性结构:不满足线性结构条件的数

6、据结构。4种基本逻辑希 集合、线注结构、树结构、 图结构（网状结构）。存储结构:数据元素在计算机中的存储关系 （存储方式）。包括顺序、链接、索引等。存储结构中要存放数据元索及其关系的信息。存储元素及其关系所占用的空间称为结点。一种逻辑结构一般可用多种存储结构,不同存 储结构的数据处理效率不同。 对数据钠进 行的运算（操作）。数据结构一的图形表丞:图 l-lo无前件（前驱啲结点林 结点;无后件（后继）的结点称终 端结点（叶子结点）;其它称内部 结点仲间结点）ol2. 2顺序存储与链式存储 顺序存储的存储空间连续, 元素按逻辑关系依次存放。链存储的结点包括数据序与元素的逻辑关系无关。结点空间可方便

7、地动态 巾请和释放。可方便1 也表示线性或非线性结构。顺序在储的持点:借助元素在存储空间的相 对位置表示逻辑关系（逻辑相邻的元素存储位置也 相邻）;元素查找方便,插删繁琐（随机存取,计算 地畦接查找;插删元素时可能要移动大量数据）o链式在储的持点：用指示元素存储地址的指 针表示逻辑关系（逻辑相邻的元素存储位置可不相 邻）;元素查找不便，插删方便（顺序存取,按指针 依次查找；插删元素时修改指针即可）:指针域额 外占用存储空间。7.3线性表及其顺序存储结构1. 3. 1线性表的概念与特点元素的有限序列。n称为线性表的长度,n=0的线性表称空表。 韭空线性表的猿征:有且只有个根结点; 有且只有1个终

8、端结点;所有中间结点有且只有1 个前件箱1个启祗由若干数据项组成的数据元素又称记录，由若 干记录构成的件。线性表的主要运算:数据元素的插入，删除 査找,修改,排序;表的创建销毁清空,分解合 并，复制逆转。1. 3. 2线性表的顺序存储（顺序表）连续的存储单 元依次存储表的数据元素。线性表顺序存储结构的基圭特点:所有元素 的存储空间连续;元素在存储空间中按逻辑顺序 依次存放（元索的物理位置与逻辑关系_致）o设存储表的每个元素需k个字节,adr （ai）为ai 的存储地址，则： 皿柯甘k式中adr （al）是l的第一个数据元索al的存储 位置,称做线性表的起始位置或基地址。采用顺序存储结构的线性表

9、称为顺序表，它是 一种随机存取的存储结构。1. 3. 3顺序表的插入、删除运算插施篡：从叶子到插入点,各元素倒序咸 1个位置;貓元素插入到插入点。删除运算:从被删除元素的后继到叶子,各元素 正序前移1个顺序表操住囁:查找高效;插删低效（平均移 动n/2个元素）;易上溢，存储空间动态分配不便。1.4栈和队列钱是限定在一端（栈顶）插删元素的线性表。另 一端称栈底。指针gp指小栈顶,b必理指示栈底。栈操作魏点:按先进后出（旦q原则组织数据。栈的基圭运算:入栈（插入元素）；退栈（删 除元素）;栈顶元素（将栈顶兀素赋给指定变虽, 指针不变）o丛列是允许在一端（丛屋）插入元素，在另一端 （队头）删除元素的

10、线性表。指针矗竺指示队尾, 丄型甘旨示队头。丛列操作疫点:先进先出（e®的线性表。丛列的基本运算:入队（从队尾插入元素）； 退队（从队头删除元素）o循环队列:在逻辑上将队列空间的最后位置绕 到第一个辱形成逻辑上的环状空【耶设置一个标 志s。s=0示队空;s=l且front=rear示队满。栈写队列的异同点:同:操作受限炽能在端 点插删元素）的线性表。异:栈只能在表的一端插 删元素,；队列只能讎的一端插入元 素，另一端删除素,先进先出o上溢:顺序表/栈/循环队列满时进行插入/入栈 /入队操作。下溢:顺序表/栈/循环队列空时进行删 除/出栈/出队操作。（两个桟共亨一个存储空间可以 节绪&

11、#39;存储空间，降低上溢发生的机率）1.5线性链表采用链式存储结构的线性表/栈/队列称为线性 链表/链栈/链队列。头指针（卿指向链表首地址，亚ad二null时为 空表。单链表的结点的指针（link）指向后件结点; 双向链表的左指针（llink）指向前件结点,右指针 （rlink）|gi 后祚结点。为统一空表与非空表的运算，在链表的第一个 元素结点（首元结点）前人为设置_个头结点（头结 点属于链表，但不属于线性表）。此时,头指针指向头 结点，头结点的link指向首元结点。循环链表终端结点的link值与head相同。从 表中任一结点出发，可访问循环链表的所有结点。线性链表的突出优点是便于插入和删

12、除操作。 线性链表的基本运算:查找,插入,删除, 设p知丰处理结点,x为p的前迤y为p的后继: 查找元素:从头指针开始，按各结点的l1xk指 示依次搜索，直到找到po插入元素:屮请p空间并赋值一找到插入位置 一p.link二 x. linkx. link 二 p 的首地址删除元素：找到x一暂存x. link-x. link二 p. link-w p的空间1.6树与二叉树m （tree）是n （n二0）个结点的有限集。任意一棵 非空树中:«且仅有一个根结点；切时,其余结 点分为m（m>0）个互不相交的有限集tl, t2,tm,其 中每个集合又是一棵树，称为根的子树。韭空树的扭征:

13、有且只有1个根结点；（2w个 非根结点有且只有1个称父结点（父亲）的前件; 每个非叶子结点可有多个称子结点（孩子）的后件。树是一种简单的非线性结构，所有元素之间有 明显的层次特性。同层共父结点的结点互为兄弟; 同层不共父结点的结点互为堂兄弟。结点的后件的个数称该结点的度，所有结点中 最大的度称树的度。树的最大层次称树的深度。二叉树（binary tree）是每个结点最多有二棵子 树,且子树有左右之分,次序不能颠倒的树。韭壬乂购就:只有一个瞬点；个结点最多两棵子树,分别称为左子树与右子树。满二叉树:除最后一层外，-每层所有结点稠2 个子结点。深度为j的满二叉树有2 j -1个结点, 其第k层上有

14、2kt个结点。完全二叉树:除最后一层外,每层的结点数均达 最大值在最后一层上只缺少右边的若干结点。二翊的基本性质:（下列描述中的&1）二叉树的第k层的结点数<2 10深度为j的二叉树的结点数0刃二度为0的结点（叶子）数二度为2的结点数+1。具有n个结点的二叉树的深度之1082卫+1； （l（）g2 n表示敢log2 n的敷数前分）有n个结点的完全二叉树深度=1082 nj+1;（6）将含n个结点的完全二叉树从根结点开始, 按层序（每层从左到右）用自然数给结点编号，则有:（2淆01,则该结点为瞬点；若k>l,则该结点 的父结点编号为int（k/2） ；（绪2 k wn,则编号

15、为k的结点的左子结点编号 为2k ;否则该结点赵子结点（也无右子结点）;（3渚12k+lwn,则编号为k的结点的右子结点编 号为2k+l;否则该结点无右子结点。序表的中间位置元素的关键字比较，相等则查找成 功，不等则根据比较结果在表的前半部分或后半部 分按相同方法继续查找，直到查找成功或确定查找 不成功。牲点:查找效率高（最大比较次数二log2、n）； 只能甬于有序顺序表。1.8排序技术排底是指将一个无序序列整理成按关键字k非基本思想:借助数据元素之间的交换进行排序。 冒泡排序i下沉排帛:算法:惭舖乍序元素依次两两比较,若为妬则 交换位置。将序列照此方法处理一遍称一趟起泡, 其结果是将关键字

16、值最大的元素交换 到最后位置（即该 元索最终位置）o如 果在某趟起泡过程 中未发生交换则排 唐结束。冒泡排序最多 需要n-1泡,最493838493849384938131327659776132749初始关键字6576132749” 第一趟排序后5 3 7-9 66 12-47132749“274949132738完全!1 瞬购式存储5第六趟排序厉 第五趟排序后例第四苗排序后示序第三趟排序后映起 第一一越排序后走坏情况下比较次数 为 n （n-1）/2o快谏排序i分区交换排帛:冒泡排库的改进 篡法:在待排序序列中任取一个元素为基准，用 交换方法将所有元素分成两部分:关键字比基准小的在一个部分

17、，比它大的在另一个部分。再分别对两个部分实施上述过程,一直重复到排序完成。最坏情况下与起泡排序相当，但快速排序平均执行时间为0 （nlog2 n）,优于起泡.直接插入 直接 选择排序。实现中需大小为0（log2 n）的栈空间。髓勰魏蔦序初始关键字pivot key_4938659776132749遍历左子树，最后前序斷右子树。abcdegf中序遍历（驰）:首先虫序遍历左子树，然后 访问瞬点,最后中序斷右子树。 cbegdfa后序遍历（lrd）:首先后序遍历左子树，然后 后序朋右子树，最后访问根结点。cgefdba1次交换后2次交换后1.7查找技术3次交换后.ft1j273865977613一2

18、73897761365273813977665494949查找表是n个同类的数据元素的集合。若查找 表中的元素逻辑上按关键字大小有序（非递减或非 递增）排列则称为有序表，否则称为无序表。童找是在查找表中查找关键字等于给定值的数4次交换后27380q137697朴 j fj6549据元素。找到则称查找成功，否则称查找失败。 顺序查找（顺序搜索）:算法:将给定值与表中各 元素关键字逐个比较，'直到查找成功或找遍所有结点都不相等。犢点:对表元素的逻辑次序和存储结构 无要求（有序表,无序表，顺序表，链表均可）；效率低（最大比较次如）。适用:无序表或链表。二分查找（折半查找）:銓法:将给定值与有

19、序顺初始状态149386597761327491一次划分后12738131491769765491分别快排113127138114965176197!结束结束491651结束结東有序序列11327384949657697快速排序示例（b）排序的全过程49完成一迸快排653827（a）趟快排过程134976971. 8. 2插入类排序法基本思想:每步将一个元素按关键字插到已排 序序列的适当位置,直到全部元素插入完。简单插入排序i直触入排南:算送:将无序序列中的各元素依次取出,在有序 序列中顺序查找插入位置，将该位置及其后面所有 元素依次后移一个位覺鮭该鯉插入元素。排序效率同冒泡法，最大比较次数二

20、n(n_l)/2。初始关键字:(49)386597761327"491 = 2,(38)(3849)659776132749< = 3：(65)(384965)9776132749/=4：(97)(38496597)76132749« = 5：(76)(3849657697)132749：=6：(13)厂(1338496576972749« = 7：(27)(13厂273849657697)491(49)i=8：(1349宜接描人排序示例273849657697)依次选取作为当刖结点；若当刖结点值小3e淇某 个子结点值,则将当前结点与其最小值子结点交换; 对

21、发生交换的子结点为根的子树重复第®步, 直到所有子点值都大于其子结点值。调整堆算法:若根结点值小于其某个子结点 值则将根结点与其最小值子结点交换；对发生交 换的子结点为根的子树重复第步，道到所有子树 根结点值都大于其子结点值。堆排序:算法:将无序序列按关键字建堆; 取出堆顶元素;调整剩下的无序子序列，使其成为 堆；重复进行©步,道到无序子序列为空。堆排序的最大比较次数为nlog2 n,执行时间为 9頤2必仅需一个用于交换的附加存储结点适 合较大文件的排序,不适合规模小的线14表o各m序方法的比较：类 排序法最大比较数平均时间辅助存储交换类冒泡排序 n(n-l)/20(n2

22、)快速排序 n (n-l)/2 0 (n log2 n) 0 (log2 n)|监视哨l. r0希尔(she 11)排序(缩小增量排序):算法:先将整个待排记录序列分割成为若干子 序列分别进行简单插入排序,待整个序列的记录基 本有序时，再对全体记录进行一次简单插入排序。增量序列一般取九二n/2k (k二 1, 2, , log? n)。 排序效率与增量有关。最大比较次数为0 (25)。简单插入 n(n-l)/20(n2 )插入类希尔排序o(nrocn2 )选择类简单选择n(n-l)/20(n2 )初始关健字:h49 38 65 97 76 13 27 49 5549132738040(1)堆排

23、序 0 (n log2 n) 0 (n log2 n) 0 (log2 n) 归轴乍序 0 (n log2 n) 0 (n log2 n) 0 (n) 快速排序平均时间性能最佳，但最坏情况下 的时间性能不如堆排序和归并排序； n较大时，归并序所需时间较堆排序省，但 它所需辅助存储量最多。当序列中记录基本有序或n较小时，直接插 入排序、冒泡排序最佳。帝尔排字示例65 _ _ _97*7649i5504一趙排序结果,13132749 55 04 49 38 65 97 76§5387638270465厶7499776273s6；)9a初始状态4949 (76)(13)(273865j7b

24、调整4#结点二趙排序结果: 三趙排序结果:13 04 49 38 27 49 55 65 97 7604 13 27 38 49 49 55 65 76 971. 8. 3选择类排序法无序序列中选岀关键字最小 (最大)元素,放在已排序序列最后，直到全部排完。简单选择排序:算法:从表中选出关键字最小的 元素，与表首元素交换撚后对剩下的子表同样处理, 直至lj子證为空。最大比较次薮二n (nt )/2。堆的定叉:n个元素的序列di，d2，：dn当且 仅当 di<d21 且 di<d2i+i (或 dj>i)2i 且 dj>d2i+i) 时,称之为小顶堆(大顶堆)。(i二1,

25、2,n/2)若将此序列看成一棵完全二叉树侧堆的含义 表明，完全二叉树中所有非终端结点的值均不大于 (或不小于)其左、右孩子结点的值。即:堆顶元素(完 全二叉树的根)为序列中元素的最小值(最大值)o建堆算法:从最后一个中间结点到根结点1：>4976 (65 (2719)7c调整3#结点38349 (76)(65)(2797d 2#不需调整9:4976652749 (76 (65)(49s初始状态3s2797)7建堆算法过帝调整1#结点134976 (65) 49973821f调整3#结点2738971976 (65 (49h调整1#结点38)(4949 (76) (65) 97i调整3#结

26、点调整帥程程序设计方法和风格2程序设计基础当今主要程序设计风格:清晰第一，效率第二。要形成良好的程序设计风格,应注意5方面因 素:源程序文档化;数据说明的方法；语句的 结构；入和输出。程序注释分为序言性注释和功能性注释。2.2结构化程序设计结构化程序设计的四条原则:自顶向下；逐 步求精;块化;限制使用goto语句。软件设计四项基本原则:抽象；模块化； 信息隐蔽;独立。结构化程序的基本结构和特点： 丿®序结构:语句序列按自然顺序依次执行，是 最基本、最常用的结构。 选扌5结构（分支结构）:根据条件选择执行_ 条分支上的语句序列；包括简单选择和多分支选择o 重复结构（循坯结构）:根据条件

27、判断是否重 复执行某一段语句序列。结构化程序设计的优点:程序易理解、使用和 维护;提高编程效率,降低软件成本。2.3面向对象的程序设计面向对象方法的优点:与人类习惯的思维方 法一致;稳定性好;可重用性好;易于开发大 型软件产品；可维护性好。面向对象方法的基本概念：:是由描述该对象属性的数据及可对这 些数据施加的所有操作封装在一起构成的统一体。 对象由一组表示其静态特征的属性和它可执行的操 作组成，是构成系统的基本单位。属性即对象包含的信息，是对象的静态特性;操 作（方法漲务）描述对象的功能,是动态特性。对象的基本特点:标识惟一性;分类性; 多态性；狷装性;瞅块馳性好。（2）1:是具有共同属性和

28、方法的对象的集合。 类是对象的抽象,对象是类的实例。（3）逍息:是实例之间传递的信息。它统一了数据 流和控制流，请求对象进行某处理或回答某信息。逍息的组成:接收消息的对象的名称;消息 标识符（消息名）；零个妙个珈继承性:继承是用已有的类（辱丄父射为基 础建立新类（派生类丄壬类）的技术。即子类自动共享 父类的数据（属性）和方法（操作）o里继承指壬豹有二个父裳多重继承指壬类 有多个父类，使用多重继承时要注恿避免二义性。继承具有传递性（类自动具有其上层全部基类 定义的蝕o（5）多态性:指同样的消息被不同的对象接受时 可导致不同行动的现象。封装性:对象将内部数据及其操作的实现（方法）封装起来,使外界不

29、能直接修改它们。3软件工程基础3. 7软件工程基本概念软性是程序、数据及相关文档的集合。（与计算 机系统的操作有关的计算机程序、规程、规则,以及 可能有的文件、文档及数据）程序是针对特定任务的计算机指令的有序集 合。数据是使程序能正常操纵信息的数据结构。文 档是与程序开发、维护和使用有关的图文资料。软性的特点:逻辑实体；产没有明显的制 作过程;用期间无磨损、老化；对计算机系统 具有依赖性；复杂性高，成本昂贵；软件开发涉 及诸多的社会因素。产主要靠脑力劳动;艇产、维护成本高。软性的分类:按功能分为:系统软件;支撑 软件（工翱件）;应用软件。软件生命周期:软件产品从提出、实现、使用维 护到停止使用

30、退役的过程。命周期宜阶段:软件救、软件开发、 运行维护。主要活动阶段包括:可行性研究与计划 制定;w求分析;软件设计（概要设计、详细设 计）；软件实现；软件测试;濮行和维护o软件危机泛指软件开发和维护过程中遇到的一 系列严重问题可归结为成本、质量、生产率等。软件工程是用于计算机软件的定义、开发和维 护的一整套方法、工具、文档、实践标准和工序。软性工程要素:方法，工具,过程。方法是完成 软件项目的技术手段;工具支持软件的开发、管理、 文档生成；过程支持软件开发各环节的控制、管理。软件工程过程足把软件转化为输出的一组彼此 相关的资源和活动，包含4种基本活动:p_软件规 格说明;d-软件开发；c-软

31、件确认；a-软件演进。软件工程的汀标:在给定成本、进度的前提.卜； 开发出具有有效性、可靠性、可理解性、可维护性、 可重用性、可适应性、可移植性、可追踪性和可互 操作性且满足用户需求的产品。软性工程基本且标:付出较低的开发成本哒到 要求的软件功能；取得较好的软件性能;开发的软件 易移植且费用较低;能按时完成开发和交付使用o软件工程的基本原则:抽熟信息隐蔽、模块化、 局部化、确定性、一致虹完备性和可验证性。软件工程研究的内容:软件开发际（包括软 件开发方法学、开发鹽、开发工具和软件工程环 境）:软件工程管理（包括软件管理学、软件工程经 济学、软件心理学等）。软 tta发工具为软件工程学齢了自动或

32、半自 动的软件支撑环境。软性开发环境（软件工程环境） 是全面支持软件开发全过程的软件工具集合。符号含义例及说明定义为+与x二a+b表示x由a和b组成| 或x二a b表示x由a或b组成m* *n重复x=2 a 5表示x中出现a最少2 次,最多5次从工程勰角度看,软件耐分两步:m 舷辻（结构设辻，将软件需求转化为软件体系结构、确辻算机辅助软性工程（cas©是当前软件开发环 境中富有特色的研究工作和发展方向。3.2结构化分析方法 3. 2. 1需求分析与需求分析方法需求分析是提取和分析用户需求陈述并转化为需求分析险段的-工作概括为四个方面:需求获 取、需求分析、编写需求规格说明、需求评审。

33、需求分析方袪:结构化需求分析方法（面向数 据流的分析方法（sa）,面向数据结构的方法 （jackson方法,jsd）；面向对象的分析的方法00a。楫据建立的模型的特桂,需求分析方法乂分为 静态分析方法和动态分析方法。3. 2. 2二结构化分析方法分析（sa）、结构化设计（sd）、结构化程序设计（sp）。核心和基础是结构化 程岸设计理论。鏑化分桩方法的实质淆眼于数据流,自顶向 ie逐层分解，建立系统的处理流程,以数据流图和 数据字典为主要工具,建立系统的逻辑模型。结构化分析的13工县:册据流图；側据字 典；判定树;判定表。数据流图（d f d）:描述数据处理过程的工具,足 需求理解的逻辑模型的图

34、形表小，支持功能建模。数据流图中的主要图形元素： 二t数据流:沿箭头方向传送数据的通道o 加工（转换）:输入数据经加工变换产牛输出 = 存储文件（数据源）:处理过程中存放的数据 一i源潭:系统和环境的接口，系统之外的实休km建更的步骤:由外向里自顶向下，逐层分解。 画数据流图的注意事项： 数据流必须命名、有流向； 加工必须命名、编号、有输入流和输出流； 数据存储必须命名、有来自或流向加工的输 入流和输出流； 父图与子图必须平衡:子图与父图对应加工 必须输入流和输出流一致,编号对应；数据字典d）:关于系统元素的清晰、准确、 详细的定义。它使得用户和系统分析员对于输入、 输出、存储成分和中间计算结

35、果有共同的理解。（）可选x= （a）示a可在x中出现或不出现*注释 连附x=l9示x可取1到9中任一值数据宁典有四类条目澈据流条目、数据项条目、数据存储条ei、基本加工条ei。其中数据顶是 组成数据流和数据疗储的最小元素。dfd和dd构成需求规格说明的主要技术附件。判定树/判定表:采用树结构/二维表的加工逻 辑描述工具。判定表能清晰表示复杂条件组合与应 做动作之间的对应关系。一张判定表由四部分组成:条件定义所有条件各种取值的组合动作定义|各种条件取值组合下应执行的动作构造判定表的方法与步骤:提取条件；标出 条件取值；计算条件组合数；提取动作；制作 判定表；完善判定表（补充缺失的动作；合并冗余

36、的列）。兹件需求规格说明书（srs）是需求分析的最后 成果是软件开发的重要文档之一。它有以下作用: a腹于用户、开发人员进行理解和交流；反映用户 问题的结构，可以作为软件开发工作的基础和依据; 酚乍为确认测试和验收的依据。3.3结构化设计方法软件设计是将软件需求（功能模型）转换为软件 表示（物理趣的过程。敦徃设基圭原理:抽象；模輸；信 息隐蔽;块独立性。迪參指抽出事物本质的共同的特性而暂不考虑 其细节,是认识复杂现象的思维工具。模块化是自顶 向下逐层把软件系统划分成若干模块的过程，是解 决复杂问题的于段。信息隐蔽指使模块的内部信息 （过程或数据）不被不需要这些信息的其他模块所访 问。模块独立性

37、指每个模块只完成系统要求的独立 的子功能，并且与其他模块的联系最少且接口简单。耦合性和内聚性是衡量模块独立性的标准。耦合性是模块间互相连接的紧密程度的度量。7 种:无直接耦合,数据耦合，标记耦合，控制耦合，外 部耦合，公共耦合，内容耦合。内聚性是m内部各元素间彼此结合的紧密程 度的度量。6种:偶然内聚，逻辑内聚时间内聚通 信内聚，顺序内聚功能内聚。优秀的软件设计应力求低耦合、高内聚。从技术观点看软件设计包括:结构设计（定 义系统主要部件间的关系）；数据设计（将分析模 型转化为数据结构定义）;接口设计（描述系统内 部、软件与协作系统及人之间的通信）；a程设计 （把系统结构部件转倾软件过程性描述o

38、软住设辻的二般过程:软件设计是二个迭代的 过程;先进行高层次的结构设计;后进行低层次的过 程设计;穿插进行数据设计和接口设计。|= bb定系统级接口、全局数据结构）；谨细设辻（确立模 块的实现算法和局部数据结构）。概要设计的基本任务:设计软件系统结构; 缈据结构及数据库耐；编写蜩;确审。结构图（sc）是描述软件结构的图形工具。2种 基本元素:矩形表示模块,箭头表示调用关系。2种 信息标识:实心圆箭头表示控制信息，空心圆箭心表 示数据信息。4种基本形式:基木，顺序，重复，选择。 4种模块:传入模块，传出榄块，变换模块,协调模块。两独:变卿,騎型。变鯉特点：由输入、慈（娅）、输出 三部分组成:信息

39、沿输入通路进入系统并由外部形 式（物理输入）转换成内部形式（逻辑输入），继而经 变换中心加工处理变换得到逻辑输出，再沿输出通 路转换成外部形式（物理输出）离开软件系统。31务型、理的長点:由接受分支和发送分支组 成:接受分支接受事务，交发送分支的事务中心，根 据-条活动耐数据翩跚步骤:确定数据流趣; 确定流界；将dfd映射成sc;细化和求精scomow成鈕步骤：（1 疫换型dfd的映射:设置一个主控模块，分 別调用输入模块、变换中心和输出模块;将dfd的 输入通路、变换中心、输出通路分别映射成sc的输 入模块、变换中心、输出模块。事物型dfd的映射:设置一个主控模块，分 別调用接受分支、发送分

40、支;将dfd的接受分支、 发送分支分别映射成sc的接受分支（输入模块）、发 喲支（事物中心和辭）。详细设计的任务:为sc中的模块确定实现算法 和局部数据结塚用工具表示算法和数据结构细节。3m8.wx*:图形工具轴流程图,* pad, hipo）,表格工具（判定表），语言工具（pdl）。程序流程图特点:直观清晰，简单易学应用 普遍;容易造成非结构化的程序结构;不易反映 逐步痂过程；不易表示数据结构。丹图（盒图）特点:s个构件具有明确的功能 域（控制结构的作用域）;控制转移必定遵守结构 化设计要求；容易确定局部和全局数据的作用域； 容易表现嵌套关系和模块层次结构。pad图优点:层次结构清晰（竖线为

41、程序层次 线，最左竖线是圭线，向右层层展开,竖线条数即程 序层次数）;结构化程度高（程序从主线顶端开始, 自上而下、从古到右依次执行终于主线下端）；支 持逐步求精（左边层次的内容可以抽象，由左到右逐 步细化）;易读易写,使用方便;既可表示程序逻 辑，也可描绘数据结构；可自动生成程序。3.4软件测试软件测试是使用人工或自动手稣测试或运行 软件的过程。且的是发现软件中的错误。软件测试的准则:测试应追溯至!1用户需求; 测试前制定测试计划，严格执行；注重群集现象； 避免自己测试自己写的程序;不能穷举测试； 妥善保存测试文档（测试计划,测试用例等）o软性测时麹朋态测赫动态测试。静态测试不运行软件,主要

42、通过人工进行;包括 代码检查、静态结构分析、代码质舷量。动态测试是为了发现错误执行程序的过程,是 基于计算机的测试;包括白盒测试和黑盒测试。动态测试的关键是设计高效、合理的测试用例o 测试用例包括输入数据和预期输出结果。白盒测试（结构测试,逻辑驱动测试）:在软件内 部进行,测试程序的内部结构和处理过程。把被测对 象看作打开的盒子，测试者必须了解程序内部结构 和处理过程,检验内部控制结构和数据结构是否有 错，实际运行与预期状态是否一致o主要方法有逻辑 覆盖（语句覆盖，路径覆盖,判定覆盖,条件覆盖，判 断条件组合sm）、基本路径测试等。黑盒测试（功能测试,数据驱动测试）:在软件的 接口处进行,测试

43、程序的功能、性能。臧测核看 成黑盒子，测试者不考虑程序的内部结构和处理过 程,只依据需求规格说明书，检查程序是否满足功能 要求。主要方法有等价类划分、边界值分析、.错误 推测、因果图等，主要用于确认测试。软件测试过程一b按4个步骤进行:单元测试、 集成测试、验啊试（确认测试）和系统测试。单元测试（模块测试）:针对程序模块进行的正 确性检验；貝的是发现模块内凱的错误；依据惮细设 计说明和源程序;内容包括模块的接口，重要路径 局部数据结构，错误处理，边界等测试；方法可采用 静态和动态测试，白盒法为主，辅以黑盒祛。辅助模块:驱动模块（代替被测模块的上层模 块）;桩模（代替被测模块的下层模块）o集成测

44、试（组装测试）:将模块按要求组装并进 行测试;目的是发现与接口有关的错误;依据概要设 计说明曲容包括模块接口，全局数据结构,边界条 件和非法输入测试;方滤白葩、黑竝相结合; 组装可采用增量组装（自顶向下组装,自底向上组 装,乍明治"式鑼）或非增（二次性磔）o回归测试:使用保存的测试用例再次进行以前 实施过的测试。确认测试（有效性测试）:目的是验证软件功能、 性能等是否满足需求规格说明,软件配置是否齐全、- 正确;依据需求规格说明;方法用黑缽系统测试:将软俗乍为i+m 系统的一个元素, 与硬件、支撑软件、数据和人员等元素组合，在实际 运行环境下对计算机系统进行测试;目的是在真实 的系统

45、工作环境下检验软件能否与系统正确连接, 发现软件与需林一致之处曲容包括功能、性能、 操作、配置、外部接口、安全性测试等。3.5程序调试程序调试的任务是诊断和改正程序中的错误。 调试的基圭步骤:倔误定位 m 改设计和代 码排除错误;融行回归测试,防止引入新的错误。软件调试可分为静态调试和动态调试。静态调 试指人工分析源程序和排错，社要手段，而动态调 试是辅助静态调试。调试的关键是推断错误位置及原因。主要方法: 强行排错法（设置断点和监回溯法;原因排除法（通过演绎、归纳、二分法等实现）。4数据库设计基础数据库；以物理模式为框架的db为物理数据库。在 dbs中，只有物理数据库是真正存在的（存于外存的

46、 数据文件）。概念db是物理db的逻辑抽象;物理db 是概念db的具体实现；用户db是概念db的子集 也是物理db的子集的逻辑描述。lbs的两级映射:m念模式到内模式的映射； 外模式到概念模式的映射。4.2数据模型4.1数据库系统的基本概念数据是描述事物的符号记录。有一定的结构, 有型与值之分,如整型值15o数据库（四是存储在存储介质上、一按一定结构 集成、可共享的相关数据的集合。数据库存放数据是按数据所提供的数据模式存 放的，具有集成与共享的特点。数据库管理系统（嘶是位干用户与os之问 的一种系统软件。负责db中的数据组织,数据操纨 数据维护,控制及保护和数据服务，是db的核心。.虫鸟的功能

47、:据模式定义（为db构建数据框架）:数据存取的物理构建（为数据模式的物理 存取与构建提供存取方法与手段）;数据操纵（为 用户使用db的数据提供方便，如增、删、查、改、 算术运算、统计等）;据的完整性、安全性定义 与检查；db的并发控制与故障恢复;数据服务 （拷贝，转存,重组,性能监测，分析等）。dbms即以下媾语言:讷据定义语言（ddl, 负责数据的模式定义与物理存取构建）；数据操纵 语言（dml,负责数据的操纵，如增删查改等）:据 控制语言（dcl,负责数据完整性、安全性的定义与检 査及并发控制、故障灰复等）。数据语言按使用方式有两种结构形式:交互 式命令（自含型/自主型语言）；宿主型语言（

48、嵌入 某些宿主语言中）。数据库管理员（im：对数据库进行规划、时 维护、监视等的专业管员。数据库系统（匸旳:由db、dbms、dba、硬叶台、 软件平台五个部分构成的运行实体。数据库应用系统:dbs,应用软件,应用界面组成 数据管理技术发農的三个址段:人工管理阶 段；文件系统阶段:据库系统阶段。数据库技术发展的三个险段:文件系统阶段； （dm dbs w dbs阶段;够系dbs阶段。啓的基梯点:数据的集成性、高共享性与低 冗余性、独立性（物理独立性，逻辑独立性）、统二 理与控制（完整性检查,安锂保护,并发控制）o 三级模式:m念模式（逻辑模式）:dbs中 全局数据逻辑结构的描述，全体用户公共数

49、据视图 （全局数据视图）:外模式（子模式,用户模式）:用 户数据视图（用户见到的数据模式）;内模式（物理 模式,存储模式）:给出db物理存储结构与方法。_个dbs只有一个概念模式;以概念模式为框 架的db称概念数据库;以子模式为框架的db称用户mbararw-o缠是现实世界的符号抽象。数据模型是数据 特征的抽象，它从抽象层次上描述系统的静态特征、 动态行为和约束条件。其描述内容有数据结构、数 据操作与数据约 朽 価分。数据模型按应用层次分成三类:概念数据模 型（概念模型;面向客观世界，面向用户；与具体的 dbms及计算机平台无关;常用的有e-r模型）;飙 辑数据模型（数据模型;面向dbs,常见

50、的有层次模 型、网状模型、关系邂、面向对象模型等）物理 数据模型（物理模型；面向计算机物理表示，给出了 数据模型在计算机上物理结构的表示）o实佐是现实世界中事物的抽象;具有共性的实 体罅的集合称实体集。曲是事物（实体）或联系的特性的描述；_个属性的取值范围称该属性的值域（值集）o超是事物（实体）间关系的描述;包括一对二 （1:1）、一对多（1:n）、多对多（m:n）的联系。e-r模型二个票本概念间的联接关系:实体是概 念世界中的基本单位，属性依附于实体。属性有属性 域，每个实体可取属性域内的值;一个实休的所有属 性值叫一个元组。实休集之间可以且只能通过联系 建立联接关系；联接也可以附属有属性。

51、e-r模型由实体、.联系、一属性组成,三者结合起 来才能表示现实世界。e二r模型的图示（e-r图）:矩形表示实体集溜n； (gi®) 椭圆表示 属性（其内标 注属性名称匕 菱形表示c成绩联系（其内标注联系名称）；ci层次模型的基本结构是树形结构,具有以下特 点:每棵树有且仅有一个无双亲结点，称为根;学生e-r图课程学分mn学号修读课程名树中除根外所有结点有且仅有一个双亲。上层结点 与下层结点之间为1：n联系。网状模型是一个不加任何条件限制的无向图, 用网状结构表示实体及其之间联系，网中的结点为 m:n联系,允许结点零或有多个父结点。但在实现上 一般将网络结构分成一些基本结构(一般分为若干 棵二级树;根结点与任一叶了结点间的联系均为1:n 联系)。学号姓名 米雪性别年龄 女 173559335722袁丽女1835924欧杰17 i36338耿泽18学号35722姓名 袁丽关系模型是以二维表为基本结构建立的卿。二维表简称表，由表框架及表的元组组成。表框 架由n个属性(列)组成,n称属性元数(列数)o属性 的取值范围称值域。表框架中按行存放数据，每行称 一个元组。一个表框架可存m个元组,h称表基数。满足下列7性质的表称为遂:元组个数有限 性,元组唯一性，元组次序无关性,元组分量原了性,(4庫询操作：查询列:利用投影运算完成:在关系r(di, d2,dk)中查询取得m列(d