二级公共基础知识

一、算法的基本概念算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。1．算法的基本特征可行性(effectiveness)

每一步要能实现

执行的结果达到预期的目的确定性(definiteness)---非多义性有穷性(finiteness)拥有足够的情报----输入数据结构与算法一、算法的基本概念2．算法的基本要素算法中对数据的运算和操作算术运算逻辑运算关系运算数据传输算法的控制结构顺序选择循环一、算法的基本概念3．算法设计基本方法列举法（工作量大找规律分类优化）归纳法（列举少量找出一般关系可能是错的）递推（也是归纳从初始条件逐次推出中间结果或最后结果）递归（也是归纳从算法本身到达递归边界）减半递推技术（分而治之规模减半重复减半）回溯法（试探八皇后问题）一、算法的基本概念算法的复杂度1.时间复杂度指执行算法所需要的计算工作量算法工作量=f(n)n是问题的规模与下列因素无关：书写算法的程序设计语言编译产生的机器语言，代码质量机器执行指令的速度算法工作量的分析方法：第一种情况：在同一个问题规模下，算法执行所需的基本运算次数可能与输入有关（例如顺序查找），可以用两种方法分析算法工作量(1)平均性态

当问题规模一定时，如果算法执行所需的基本运算次数取决于某一个特定的输入时，用此方法分析工作量

A(n)=

pi是某个元素(x)出现的概率,ti

是在输入某个元素(x)时所执行的基本运算次数n+1∑i=1piti(2)最坏情况复杂性

是指当问题规模为n时，算法所执行的基本运算的最大次数

W(n)=max(ti)

W(n)比A(n)更有实用价值第二种情况：算法的计算工作量也可能与输入无关（例如n阶矩阵相乘），在所有可能的输入下，算法所执行的基本运算次数是一定的，此时A(n)=W(n)2.空间复杂度是指执行这个算法所需要的内存空间内存空间包括：1）算法程序占用空间2）输入的初始数据占用空间3）算法执行中所需的额外空间二、数据结构的基本概念数据结构研究三个问题:(1)逻辑结构:数据集合中各元素之间所固有的逻辑关系(2)存储结构:各数据元素在计算机中的存储关系(3)运算:对各种数据结构进行运算数据结构研究的目的:(1)提高数据处理速度(2)节省存储空间1.什么是数据结构例如:无序表的顺序查找和有序表的对分查找3516788543293321544616212933354346547885无序表:若查找的元素正好是第一个,次数少若查找的元素是最后一个或查找的元素不在表中的情况,无序表有序表则次数多(1)数据的逻辑结构指数据元素的信息(即数据元素的集合,记为D)和各数据元素之间的前后件关系(记为R)。与它们在计算机中的存储位置无关.记B为数据结构,则

B=(D,R)例如:一年四季的数据结构表示为:

B=(D,R)

D={春,夏,秋,冬}

R={(春,夏),(夏,秋),(秋,冬)}

用二元组表示数据元素之间的前后件关系(2)数据的存储结构(物理结构)是指数据的逻辑结构在计算机存储空间中的存放形式注意:各数据在计算机中的存储位置关系与它们的逻辑关系不一定是相同的.

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有：

顺序

链接

索引

2、数据结构的图形表示例1:一年四季春夏秋冬结点

例2:家庭成员父亲

儿子女儿

有向箭头前件指向后件例3:用图形表示数据结构B=(D,R)D={d1,d2,d3,d4,d5,d6,d7}R={(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}d1d2d3d7d4d6d5

根结点(无前件)终端结点(叶子结点无后件)内部结点3.线性结构与非线性结构（1）线性结构:有且只有一个根结点每个结点最多有一个前件,也最多有一个后件注意:在一个线性结构中插入或删除任何一个结点后还应该是线性结构如:

ABCD将A删除就不满足了(2)非线性结构：不是线性结构就是非线性结构例如：家庭成员关系对非线性结构的存储与处理比线性结构复杂得多三、线性表及其顺序存储结构1、线性表的基本概念例如：一个N维向量、英文字母表、一年中的四季，一个一维数组等都是线性表，其中的每一个值都是线性表的一个数据元素（结点）。此时的数据元素是一个简单项。又如：一个学生表也是线性表，其中的每条记录就是线性表的一个数据元素（结点）。此时的数据元素是一个复杂项。2、线性表的顺序存储结构两个基本特点:（1）线性表中所有元素所占存储空间是连续的（2）线性表中所有元素在存储空间中是按逻辑顺序依次存放的2、线性表的顺序存储结构线性表中每一个数据元素的存储地址ADR(ai)由该元素在线性表中的位置序号i唯一确定ADR(ai)=ADR(a1)+(i-1)k

k表示每个元素占用的字节数3、顺序表的插入运算（元素后移、上溢）291856633524314712345678910872918566335243147123456789101429871856633524314712345678910如再插入，将上溢1234567思考：在末尾插入一个元素，在表头插入一个元素，在表中i位置处插入一个元素，表中其他元素移动情况。结论：在线性表的存储情况下，要插入一个元素，效率低；特别是在大表中，消耗的时间更多。4、顺序表的删除运算2918566335243147123456789101856633524314712345678910185663352447123456789101256734思考：在末尾删除一个元素，在表头删除一个元素，在表中i位置处删除一个元素，表中其他元素移动情况。结论：在线性表的存储情况下，要删除一个元素，效率低；特别是在大表中，消耗的时间更多。故：线性表在顺序存储结构下的插入与删除运算，比较适合小线性表或者其中元素不常变动的线性表。四、栈和队列1、栈（stack）及其基本运算它是限定在一端进行插入与删除的线性表此端称为栈顶，用指针top来指示；另一端不允许做任何操作，称为栈底，用指针bottom来指示。所谓“先进后出”表或者“后进先出”表。插入一个元素称为入栈，删除一个元素成为退栈。栈示意图an……a2a1入栈退栈栈顶top栈底bottom2、队列（queue）及其运算它是在一端（队尾）插入，用尾指针rear指示；另一端（队头）删除，用头指针front指示的线性表。所谓“先进先出”表或者“后进后出”表往队列的队尾插入一个元素称为入队运算，从队列的队头删除一个元素称为退队运算。队列示意图ABCDEFfrontrear退队入队五、线性链表一个存储单元对应一个数据结点，这个存储单元称为存储结点，简称结点。1、线性链表线性表的链式存储结构称为线性链表数据域指针域存储序号12…I…m线性链表的存储空间数据域指针域V（i）NEXT(i)存储序号i线性链表的一个存储结点数据1数据2数据nNull……head线性链表的逻辑结构例：设线性表为（a1,a2,a3,a4,a5）,存储空间有10个存储结点，则存储情况如图：a29a11a410a35a50123456789103head物理状态图a1head线性链表的逻辑状态图a2a3a4a50319510以上是线性单链表，特点是：每个结点只有一个指针域，由它只能找到后件结点，而不能找到前件结点。为弥补此缺点，每个结点设两个指针，即左指针（Llink）用来指向其前件；右指针(Rlink)用来指向其后件。此线性链表称为双向链表，其逻辑状态如图：0DRLDRLD0…………head域中值为0，表示为空Null,即不指向任何结点2、带链的栈AnAn-1A10Top…AnAn-1A10Top…An+1AnAn-1A10Top…入栈操作退栈操作3、带链的队列A1A2An0front…A1A2An…An+10A1A2An0…rearfrontrearrearfront入队操作退队操作六、树与二叉树1、树的基本概念树（tree）是一种非线性结构。RKPQDBENOTCHXYSWZAMFGL根结点叶子结点根结点、父结点、子结点、叶子结点结点的度、树的度（后件个数）树的深度（层次个数）子树重要概念2、二叉树及其基本性质特点：（1）非空的二叉树只有一个根结点（2）每个结点最多有两棵子树，且分别称为该结点的左子树与右子树；没有左右子树的结点就是叶子结点

RKDENOTBB只有根结点的二叉树二叉树的基本性质

性质1：在二叉树的第K层上，最多有2k-1(k>=1)个结点。

性质2：深度为m的二叉树最多有2m-1个结点。（等比数列求和：S=a1(1-qn)

/(1-q)）

性质3：在任意一棵二叉树中，（出）度为0的结点（即叶子结点）总是比（出）度为2的结点多一个。（所有的出度=所有入度+1）

性质4：具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。（由性质2得出）满二叉树与完全二叉树（1）满二叉树即除最后一层外，每一层上的所有结点都有两个子结点。也就是说，每一层上的结点数都达到最大值。(即：除叶子结点外的所有结点均有两个子结点)满二叉树非满（2）完全二叉树即除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。

两者关系：满二叉树也是完全二叉树，反之则不一定。完全二叉树的基本性质

性质5：具有n个结点的完全二叉树的深度为[log2n]+1（由性质4得出）

性质6：设完全二叉树共有n个结点。如果从根结点开始，按层序（每层从左到右）用自然数1，2，3，…，n给结点进行编号，则对编号为k（k=1,2,3,…,n）的结点有以下结论：（1）若k=1,则该结点为根结点，它没有父结点；若k>1,则该结点的父结点编号为int(k/2)（2）若2k<=n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）（3）若2k+1<=n,则编号为k的结点的右子结点

3、二叉树的存储结构FCEDHGPAB4F6C90E2A08D0130H010P05G110B0BT二叉树二叉链表的逻辑状态iL(i)V(i)R(i)LchildRchildValue二叉树存储结点结构10P020A0346F9513G162C87811D090E510110B012130H0BT二叉链表的物理状态4、二叉树的遍历（1）前序遍历（DLR）

根左右（2）中序遍历（LDR）

左根右（3）后序遍历（LRD）

左右根例如：表达式（a+b）*d/2用下列逻辑结构，采用前序遍历就可以实现(a*b/d2+)七、查找技术1、顺序查找从第一个元素开始，依次比较，若相等，则表示找到。这对于大表来说，效率较低。在最坏的情况下，顺序查找需要比较n次。2、二分法查找此方法只适用于顺序存储的有序表。效率比顺序查找高。对于长度为n的有序线性表，在最坏的情况下，二分法只需要比较log2n次，而顺序查找需要比较n次。八、排序技术1、交换类排序（1）冒泡排序（相邻元素比较）假设线性表的长度为n，在最坏情况下，需要比较的次数为n(n-1)/2（2）快速排序法（选取元素，不断分割）2、插入类排序（1）简单插入排序法（提取元素，插入有序表）将无序序列中的各元素（先保存到一个变量T中）依次插入到已经有序的线性表。每一次比较后最多移掉一个逆序。因此其效率与冒泡法相同，在最坏情况下，需要比较的次数为n(n-1)/2（2）希尔排序法（先分割成子序列，再插入排序）将相隔某个增量h的元素构成一个子序列。在排序的过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。增量一般取ht=n/2k

(k=1,2,…,[log2n])其中n为待排序序列的长度。希尔排序对于每个子表仍然是插入排序，但是，在子表中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善了排序性能。其效率与所选取的增量序列有关，如果选取上述增量，则在最坏情况下，需要比较次数为O（n1.5）3、选择类排序（1）简单选择类排序（选择，交换）扫描整个线性表，选取最小元素，交换到表的最前面；对剩下的子表采用同样的方法，直到子表是空为止。最坏情况下，比较次数n(n-1)/2（2）堆排序软件工程基础一、软件的生命周期指软件产品从提出、实现、使用维护到停止使用退役的过程。

可行性研究需求分析概要设计详细设计实现测试使用维护退役定义阶段开发阶段维护阶段二、结构化分析方法1、需求分析2、分析工具

a.数据流图（DFD）

b.数据字典（DD）c.判定树

d.判定表3、软件需求规格说明书（SRS）加工（转换）数据流存储文件（数据源）源，潭（系统之外的实体）三、结构化设计方法1、软件设计的基本原理（1）抽象（2）模块化（3）信息隐蔽（4）模块独立性

a.内聚性：是一个模块内部各个元素间彼此结合的紧密程度。一个模块的内聚性越强，那么其独立性就越强。

b.耦合性：是模块间互相连接的紧密程度。一个模块与其他模块的耦合性越强,则其独立性越弱。内聚与耦合的关系：内聚性越强那么耦合性就越弱。应该做到高内聚，低耦合。2、概要设计（1）基本任务：设计软件的系统结构数据结构及数据库设计编写概要设计文档概要设计文档评审（2）设计工具

a.结构图

b.数据流图（变换型、事务型）（3）设计准则（P66）3、详细设计（1）基本任务：

a.为软件结构中的每一个模块确定实现算法和局部数据结构。

b.用某种选定的表达工具表示算法和数据结构的细节。（2）设计工具

a.图形工具：程序流程图PFD，N-S，PAD，HIPOPAD:问题分析图b.表格工具：判定表

c.语言工具：PDL（伪码）HIPO图(hierarchyplusinput-process-output)是IBM公司于70年代中期在层次结构图(structurechart)的基础上推出的一种描述系统结构和模块内部处理功能的工具(技术)。HIPO图由层次结构图和IPO图两部分构成,前者描述了整个系统的设计结构以及各类模块之间的关系,后者描述了某个特定模块内部的处理过程和输入/输出关系。

HIP0图一般由一张总的层次化模块结构图和若干张具体模块内部展开的IPO图组成,如图3.13和图3.14所示。图3.13是一张有关修改库存文件部分内容模块的层次模块结构图。图3.14是图3.13中若干张模块展开图(I