数据结构与算法、基本概念：数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。包括文本类型的数据（如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。+数据元素(DataElement)：是数据的基本单位，有时也称为元素、结点、顶点、记录，可以有若干个数据项（字段、域、属性）组成。心数据结构（DataStructure）：指的是数据之间的相互关系，即数据的组织形式。其包括三部分：1、逻辑结构：数据元素之间的逻辑关系。2、存储结构：数据元素及其关系在计算机存储器内的表示。3、数据的运算（算法）：即对数据施加的操作。*数据的逻辑结构有两大类：1、线性结构：特征：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。例：一维数组、链表、栈、队列、串2、非线性结构：特征：一个结点可能有多个直接前趋和直接后继。例：多维数组、广义表、树、图数据的存储结构有以下基本存储方法：1、顺序存储方法：该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。2、链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。3、索引存储方法该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。4、散列存储方法：该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。例：除余法散列函数、相乘取整法散列函数算法的基本特征：1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。4、拥有足够的情报时间复杂度：该算法执行的时间耗费，它是该算法所求解问题规模n的函数
数据结构与算法 一、基本概念： ❖ 数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。包括文本 类型的数据(如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。 ❖ 数据元素(Data Element)：是数据的基本单位，有时也称为元素、结点、顶点、记录， 可以有若干个数据项（字段、域、属性）组成。 ❖ 数据结构（Data Structure）：指的是数据之间的相互关系，即数据的组织形式。其包括 三部分： 1、逻辑结构：数据元素之间的逻辑关系。 2、存储结构：数据元素及其关系在计算机存储器内的表示。 3、数据的运算（算法）：即对数据施加的操作。 ❖ 数据的逻辑结构有两大类： 1、线性结构： 特征：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有 一个直接前趋和一个直接后继。 例：一维数组、链表、栈、队列、串 2、非线性结构： 特征：一个结点可能有多个直接前趋和直接后继。 例：多维数组、广义表、树、图 ❖ 数据的存储结构有以下基本存储方法： 1、顺序存储方法： 该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存 储单元的邻接关系来体现，一般通过数组来实现的。 2、链接存储方法： 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字 段表示的。通过指针类型来实现的。 3、索引存储方法： 该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项， 索引项的一般形式是：关键字，地址。 4、散列存储方法： 该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。 例：除余法散列函数、相乘取整法散列函数 ❖ 算法的基本特征： 1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。 3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。 4、 拥有足够的情报 ❖ 时间复杂度：该算法执行的时间耗费，它是该算法所求解问题规模 n 的函数
空间复杂度：该算法执行时所耗费的存储空间，它也是问题规模n的函数。二、线性表：*线性表(LinearList)：是由n(n>=0)个数据元素(结点)ai,a,a3,….…,an组成的有限序列。对于非空的线性表，有且仅有一个开始结点a，它没有直接前趋；有且仅有一个终端结点an，它没有直接后继；其余的结点有且仅有一个直接前趋结点和一个直接后继结点。线性表的存储结构：1、顺序存储(SequentialList)：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。2、链式存储(LinkedList)：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的，在存储每个结点值的同时，还存储指向其后继结点的地址，用这种方法存储的线性表称为链表。常见的运算有：表的初始化、求表的长度、取表中的第1个结点、查找结点、插入新的结点、删除结点。顺序表和链表的比较：1、基于空间的考虑：A、顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。B、顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的C、顺序表存储密度为1，而链表中的每个结点，除了数据域外，还要额外的设置指针域存储密度小于12、基于时间的考虑：A、在链表中的任何位置上进行插入和删除，只需要修改指针，而顺序表中平均将要移动近一半的结点。B、顺序表是随机存取结构，它的存取时间为O(1)，而链表需从头结点顺着链扫描链表。总之，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构：当线性表的长度变化较大，难以估计其存储规模时，以采用链表作为存储结构为好。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜：对于频繁进行插入和删除的线性表，宜采用链表做存储结构。例：关于线性表的描述中，错误的是（）A、线性表是线性结构B、线性表的顺序存储结构，必须占用一片连续的存储单元C、线性表是单链表D、线性表的链式存储结构，不必占用一片连续的存储单元用数组表示线性表的优点是（）A、便于插入和删除操作B、便于随机存取C、可以动态地分配存储空间D、不需要占用一片连续的存储空间三、栈：*栈(Stack)：是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈项(Top)，另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进
❖ 空间复杂度：该算法执行时所耗费的存储空间，它也是问题规模 n 的函数。 二、线性表： ❖ 线性表(Linear List)：是由 n(n>=0)个数据元素(结点)a1,a2,a3,······,an 组成的有限序列。 对于非空的线性表，有且仅有一个开始结点 a1，它没有直接前趋；有且仅有一个终端结 点 an，它没有直接后继；其余的结点有且仅有一个直接前趋结点和一个直接后继结点。 ❖ 线性表的存储结构： 1、顺序存储(Sequential List)：将线性表的结点按逻辑次序依次存放在一组地址连续的存储 单元里，用这种方法存储的线性表称为顺序表。 2、链式存储(Linked List)：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也 可以是不连续的，在存储每个结点值的同时，还存储指向其后继结点的地址，用这种方法存 储的线性表称为链表。 ❖ 常见的运算有： 表的初始化、求表的长度、取表中的第 i 个结点、查找结点、插入新的结点、删除结点。 ❖ 顺序表和链表的比较： 1、基于空间的考虑： A、顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。 B、顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续 的 C、顺序表存储密度为 1，而链表中的每个结点，除了数据域外，还要额外的设置指针域， 存储密度小于 1 2、基于时间的考虑： A、在链表中的任何位置上进行插入和删除，只需要修改指针，而顺序表中平均将要移动近 一半的结点。 B、顺序表是随机存取结构，它的存取时间为 O(1)，而链表需从头结点顺着链扫描链表。 总之，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用 顺序表作为存储结构；当线性表的长度变化较大，难以估计其存储规模时，以采用链表作为 存储结构为好。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做 存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构。 例：关于线性表的描述中，错误的是（ ） A、线性表是线性结构 B、线性表的顺序存储结构，必须占用一片连续的存储单元 C、线性表是单链表 D、线性表的链式存储结构，不必占用一片连续的存储单元 用数组表示线性表的优点是（ ） A、便于插入和删除操作 B、便于随机存取 C、可以动态地分配存储空间 D、不需要占用一片连续的存储空间 三、栈： ❖ 栈(Stack)：是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这 一端为栈顶(Top)，另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进
先出的线性表，又称为LIFO表。栈的基本运算有：栈的初始化、判栈空、判栈满、进栈、出栈等+栈的存储：顺序存储、链式存储例：若进栈的输入序列是A、B、C、D、E，并且在它们进栈的过程中可以进行出栈操作，则不可能出现的出栈序列是（）A、EDCBAB、DECBAC、DCEABD、ABCDE四、队列：+队列(Queue)：也是一种运算受限的线性表，它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一段称为队头(Front)，允许插入的一段称为队尾(Rear)。（类似于生活中的购物排队）。是一种先进先出的线性表，又称为FIFO表。队列的基本运算：队列的初始化、判队空、判队满、入队、出队队列的存储实现：顺序存储、链式存储例：一个队列的入队序列是1，2，3，4，则队列的输出序列是（）B、1,2,3,4C、1, 4, 3, 2D、3,2,4,1A、4，3,2,1五、串：*串(String)：是零个或多个字符组成的有限序列。串中所包含的字符个数称为该串的长度。串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串注：空串是任意串的子串，任意串是其自身的子串*串有串常量、串变量之分：1、串常量在程序中只能被引用但不能改变其值，即只能读不能写。2、串变量其值是可以改变的。串的基本运算：求串长、串复制、串联接、串比较、字符定位、六、树（非线性结构)：树(Tree)：是n(n>=O)个结点的有限集T，T(n=O)为空时称为空树，否则它满足如下两个条件：1、有且仅有一个特定的称为根(Root)的结点2、其余的结点可分为m(m>=0)个互不相交的子集T1，T2，...，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆圈旁边，有时亦可写在圆圈内
先出的线性表，又称为 LIFO 表。 ❖ 栈的基本运算有： 栈的初始化、判栈空、判栈满、进栈、出栈等 ❖ 栈的存储： 顺序存储、链式存储 例：若进栈的输入序列是 A、B、C、D、E，并且在它们进栈的过程中可以进行出栈操 作，则不可能出现的出栈序列是（ ） A、EDCBA B、DECBA C、DCEAB D、ABCDE 四、队列： ❖ 队列(Queue)：也是一种运算受限的线性表，它只允许在表的一端进行插入，而在另一 端进行删除。允许删除的一段称为队头(Front)，允许插入的一段称为队尾(Rear)。（类似 于生活中的购物排队）。是一种先进先出的线性表，又称为 FIFO 表。 ❖ 队列的基本运算： 队列的初始化、判队空、判队满、入队、出队 ❖ 队列的存储实现： 顺序存储、链式存储 例：一个队列的入队序列是 1，2，3，4，则队列的输出序列是 （ ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 五、串： ❖ 串(String)：是零个或多个字符组成的有限序列。 串中所包含的字符个数称为该串的长度。 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串 注：空串是任意串的子串，任意串是其自身的子串 ❖ 串有串常量、串变量之分： 1、串常量在程序中只能被引用但不能改变其值，即只能读不能写。 2、串变量其值是可以改变的。 ❖ 串的基本运算： 求串长、串复制、串联接、串比较、字符定位、 六、树（非线性结构）： ❖ 树(Tree)：是 n(n>=0)个结点的有限集 T，T(n=0)为空时称为空树，否则它满足如下两个 条件： 1、有且仅有一个特定的称为根(Root)的结点 2、其余的结点可分为 m(m>=0)个互不相交的子集 T1，T2，.，Tm，其中每个子集 本身又是一棵树，并称其为根的子树(Subtree)。 ❖ 在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆圈旁边，有 时亦可写在圆圈内
度(Degree)：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。+叶子(Leaf)：度为零的结点称为叶子或终端结点+分支结点(Node)：度不为零的结点称为分支结点。树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点，相应的该结点称为孩子结点的双亲(Parents)结点或父结点。同一个双亲的孩子称为兄弟结点(Sibling）+结点的层数(Level)是从根起算,设根的层数为1,其余结点的层数等于其双亲结点的层数加1.4树中结点的最大层数称为树的高度(Height)或深度(Depth).森林(Forest)：是m(m>=O)棵互不相交的树的集合。删去一棵树的根，就得到一个森林，反之，加上一个结点作树根，森林就变为一棵树。二叉树(BinaryTree)：是n(n>=O)个结点的有限集，它或者是空集(n=O)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树中，每个结点最多只能有两棵子树，并且有左右之分。*二叉树的五种基本形态：例：具有3个结点的二叉树有几种形态。*满二叉树(FullBinaryTree)：一棵深度为k且有2k-1个结点的二叉树称为满二叉树完全二叉树(CompleteBinaryTree)：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。二叉树的性质：性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)性质2：深度为k的二叉树至多有2k-1个结点(k>=1)性质3：在任意一棵二叉树中，若终端结点的个数为no，度为2的结点数为n2，则no=n2+1性质4：具有n个结点的完全二叉树的深度为[lgn]+1(取下整)或[1g(n+1)](取上整)。例：一棵二叉树的结点数为18个，求它的最小高度已知度为2的结点数为15个，求叶子结点数二叉树的遍历：*遍历(Traversal)：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访间。前序遍历：（又称为先序遍历、先根遍历）若二叉树为空，则执行空操作。否则：1、访问根结点；2、前序遍历左子树；3、前序遍历右子树。中序遍历：（又称为中根遍历）若二叉树为空，则执行空操作。否则：1、中序遍历左子树：
❖ 度(Degree)：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最 大度数。 ❖ 叶子(Leaf)：度为零的结点称为叶子或终端结点 ❖ 分支结点(Node)：度不为零的结点称为分支结点。 ❖ 树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点，相应的该结点称为孩 子结点的双亲(Parents)结点或父结点。 ❖ 同一个双亲的孩子称为兄弟结点(Sibling) ❖ 结点的层数(Level)是从根起算,设根的层数为 1,其余结点的层数等于其双亲结点的层数 加 1. ❖ 树中结点的最大层数称为树的高度(Height)或深度(Depth). ❖ 森林(Forest)：是 m(m>=0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林， 反之，加上一个结点作树根，森林就变为一棵树。 ❖ 二叉树(Binary Tree)：是 n(n>=0)个结点的有限集，它或者是空集(n=0)，或者由一个根 结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。 ❖ 二叉树的五种基本形态： 例：具有 3 个结点的二叉树有几种形态。 ❖ 满二叉树(Full Binary Tree)：一棵深度为 k 且有 2 k -1 个结点的二叉树称为满二叉树 ❖ 完全二叉树(Complete Binary Tree)：若一棵二叉树至多只有最下面的两层上结点的度数 可以小于 2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称 为完全二叉树。 二叉树的性质： 性质 1：二叉树第 i 层上的结点数目最多为 2 i-1 (i>=1) 性质 2：深度为 k 的二叉树至多有 2 k -1 个结点(k>=1) 性质 3：在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1 性质 4：具有 n 个结点的完全二叉树的深度为[lgn]+1(取下整) 或 [lg(n+1)](取上整)。 例：一棵二叉树的结点数为 18 个，求它的最小高度 已知度为 2 的结点数为 15 个，求叶子结点数 二叉树的遍历： ❖ 遍历(Traversal)：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访 问。 前序遍历：（又称为先序遍历、先根遍历） 若二叉树为空，则执行空操作。否则： 1、访问根结点； 2、前序遍历左子树； 3、前序遍历右子树。 中序遍历：（又称为中根遍历） 若二叉树为空，则执行空操作。否则： 1、中序遍历左子树；
2、访问根结点；3、中序遍历右子树。后序遍历：（又称为后根遍历）若二叉树为空，则执行空操作。否则：1、后序遍历左子树；2、后序遍历右子树；3、访问根结点。例：已知一棵二叉树的中序遍历序列是：FDGBACHE，其后序遍历序列是：FGDBHECA求其前序遍历序列。一棵二叉树的前序遍历序列为ABDGCFK，中序遍历序列为DGBAFCK，则结点的后序遍历序列是（A、ACFKDBGB、GDBFKCAC、KCFAGDBD、ABCDFKG七、排序(Sort)：心所谓排序，就是指整理文件中的记录，使之按关键字递增（或递减）次序排列起来。心冒泡排序(BubbleSorting)：通过对待排序序列从后向前或从前向后（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元）。直接选择排序（SelectionSorting）：心扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。直接插入排序(InsertionSorting)：X每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。快速排序(QuickSorting)：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。各种内部排序方法的比较排序方时间复杂度空间复杂度法平均时间最坏时间最好时间直接插O(n)O(n)O(n°)0(1)入直接选O(n2)O(n?)O(n2)0(1)择冒泡O(n)0(n2)0(n2)0(1)快速O(n°)O(nlgn)O(nlgn)O(Ign)堆O(nlgn)O(nlgn)O(nlgn)0(1)例：对一个具有n个元素的序列进行冒泡排序，在最坏情况下，要进行交换的次数是（）C、n*n/2D、n(n+1)/2-1A、n(n+1)/2B、n(n-1)/2
2、访问根结点； 3、中序遍历右子树。 后序遍历：（又称为后根遍历） 若二叉树为空，则执行空操作。否则： 1、后序遍历左子树； 2、后序遍历右子树； 3、访问根结点。 例：已知一棵二叉树的中序遍历序列是：FDGBACHE，其后序遍历序列是：FGDBHECA 求其前序遍历序列。 一棵二叉树的前序遍历序列为 ABDGCFK，中序遍历序列为 DGBAFCK，则结点的后 序遍历序列是（ ） A、ACFKDBG B、GDBFKCA C、KCFAGDB D、ABCDFKG 七、排序(Sort)： ❖ 所谓排序，就是指整理文件中的记录，使之按关键字递增（或递减）次序排列起来。 ❖ 冒泡排序(Bubble Sorting)： 通过对待排序序列从后向前或从前向后(从下标较大的元素开始)，依次比较相邻元素的 排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从 后部移向前部（从下标较大的单元移向下标较小的单元）。 ❖ 直接选择排序(Selection Sorting)： 扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采 用同样的方法，直到子表空为止。 ❖ 直接插入排序(Insertion Sorting)： 每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位 置，直到全部记录插入完成为止。 ❖ 快速排序(Quick Sorting)：任取待排序序列中的某个元素作为基准(一般取第一个元素)， 通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于 基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序 列继续进行排序，直至整个序列有序。 各种内部排序方法的比较 排序方 法 时间复杂度 空间复杂度 最好时间 平均时间 最坏时间 直接插 入 O(n) O(n2 ) O(n2 ) O(1) 直接选 择 O(n2 ) O(n2 ) O(n2 ) O(1) 冒 泡 O(n) O(n2 ) O(n2 ) O(1) 快 速 O(nlgn) O(nlgn) O(n2 ) O(lgn) 堆 O(nlgn) O(nlgn) O(nlgn) O(1) 例：对一个具有 n 个元素的序列进行冒泡排序，在最坏情况下，要进行交换的次数是（ ） A、n(n+1)/2 B、n(n-1)/2 C、n*n/2 D、n(n+1)/2-1
对n个元素进行冒泡排序过程中，最好情况下的时间复杂性为（DC、O(n2)D、O(n)A、O(1)B、O(log2n)对n个元素进行快速排序的过程中，平均情况下的时间复杂性为（A、O(1)B、O(Ign)C、O(n)D、O(nlgn)查找(Searching)：八、+所谓查找是指给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置：否则查找失败，返回相关的提示信息。顺序查找(SequentialSearch)的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找即适用顺序存储结构，又适用链式存储结构。查找成功的平均查找长度为：（n为结点数目）(1+2+3+4+ :. +n) /n= (n+1)/2+二分查找(BinarySearch)又称折半查找，它是一种效率较高的查找方法，二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。另外，二分查找只适用顺序存储结构，在链式存储结构上无法实现二分查找。查找成功时的平均查找长度：(n为结点数目）n+1lg(n + 1) -1n表示当n很大时，可用近似公式：Ig(n+1)-1软件工程基础、基本概念：*软件(Software)：软件是一种产品(逻辑产品)，指的是计算机中程序及其说明程序的各种文档。“程序”是计算任务的处理对象和处理规则的描述；“文档”是有关计算机程序功能、设计、编制、使用的文字或图形资料。软件危机的表现：1、软件需求的增长得不到满足2、软件开发成本和进度无法控制3、软件质量难以保证4、软件不可维护或维护程度非常低5、软件成本不断提高6、软件开发生产效率的提高赶不上硬件的发展和应用需求的增长
对 n 个元素进行冒泡排序过程中，最好情况下的时间复杂性为（ ） A、O(1) B、O(log2n) C、O(n2 ) D、O(n) 对 n 个元素进行快速排序的过程中，平均情况下的时间复杂性为（ ） A、O(1) B、O(lgn) C、O(n2 ) D、O(nlgn) 八、查找(Searching)： ❖ 所谓查找是指给定一个值 K，在含有 n 个结点的表中找出关键字等于给定值 K 的结点。 若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回 相关的提示信息。 ❖ 顺序查找(Sequential Search)的基本思想是：从表的一端开始，顺序扫描线性表，依次将 扫描到的结点关键字和给定值 K 相比较，若当前扫描到的结点关键字与 K 相等，则查 找成功；若扫描结束后，仍未找到关键字等于 K 的结点，则查找失败。顺序查找即适 用顺序存储结构，又适用链式存储结构。 查找成功的平均查找长度为：(n 为结点数目) (1+2+3+4+···+n) / n = (n+1)/2 ❖ 二分查找(Binary Search)又称折半查找，它是一种效率较高的查找方法，二分查找要求 线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。另外， 二分查找只适用顺序存储结构，在链式存储结构上无法实现二分查找。 查找成功时的平均查找长度：(n 为结点数目) 当 n 很大时，可用近似公式： lg(n+1)-1 表示 软件工程基础 一、基本概念： ❖ 软件(Software)：软件是一种产品(逻辑产品)，指的是计算机中程序及其说明程序的各种 文档。“程序”是计算任务的处理对象和处理规则的描述；“文档”是有关计算机程序功 能、设计、编制、使用的文字或图形资料。 ❖ 软件危机的表现： 1、软件需求的增长得不到满足 2、软件开发成本和进度无法控制 3、软件质量难以保证 4、软件不可维护或维护程度非常低 5、软件成本不断提高 6、软件开发生产效率的提高赶不上硬件的发展和应用需求的增长 lg( n 1) 1 n n 1 + − +
软件工程(SoftwareEngineering)：用工程化的方法、科学知识和技术原理来定义、开发、维护软件的一门学科。软件工程的目标：付出较低的开发成本；达到要求的软件功能：取得较好的软件性能：开发的软件易于移植：需要较低的维护费用：能按时完成开发任务，及时交付使用：开发的软件可靠性高，软件工程研究的主要内容是软件开发技术和软件开发管理两个方面。+软件生存周期：是指一个软件从提出开发要求开始直到该软件报废（停止运行)为止的整个时期。软件生存周期模型：是描述软件开发过程中各种活动如何执行的模型。4、常用的模型有：瀑布模型、增量模型、螺旋模型、喷泉模型、变换模型和基于知识的模型瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型。主要包括问题定义及可行性分析、项目开发计划、需求分析、概要设计、详细设计、编码、测试和维护几个阶段。例：下列描述中正确的是（）A、程序就是软件B、软件开发不受计算机系统的限制C、软件既是逻辑实体，又是物理实体D、软件是程序、数据与相关文档的集合二、软件可行性研究与项目开发计划：软件可行性研究的目的是用最小的代价在尽可能短的时间内确定该软件项目是否能够开发，是否值得去开发。*可行性研究的任务：A、技术可行性B、经济可行性C、社会可行性（法律可行性）*可行性研究的具体步骤：1、确定项目规模和目标2、研究正在运行的系统3、建立新系统的高层逻辑模型4、导出和评价各种方案5、推荐可行的方案6、编写可行性研究报告三、软件需求分析：心需求分析是指开发人员要准确理解用户的要求，进行细致的调查分析，将用户非形式的需求陈述转化为完整的需求定义，再由需求定义转换到相应的形式功能规约（需求规格说明）的过程。需求分析的基本任务：1、问题识别A、功能需求B、性能需求C、环境需求
❖ 软件工程(Software Engineering)：用工程化的方法、科学知识和技术原理来定义、开发、 维护软件的一门学科。 ❖ 软件工程的目标： 付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移 植；需要较低的维护费用；能按时完成开发任务，及时交付使用；开发的软件可靠性高。 ❖ 软件工程研究的主要内容是软件开发技术和软件开发管理两个方面。 ❖ 软件生存周期：是指一个软件从提出开发要求开始直到该软件报废(停止运行)为止的整 个时期。 ❖ 软件生存周期模型：是描述软件开发过程中各种活动如何执行的模型。 ❖ 常用的模型有：瀑布模型、增量模型、螺旋模型、喷泉模型、变换模型和基于知识的模 型 瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型。主要包括问 题定义及可行性分析、项目开发计划、需求分析、概要设计、详细设计、编码、测试和维护 几个阶段。 例：下列描述中正确的是（ ） A、程序就是软件 B、软件开发不受计算机系统的限制 C、软件既是逻辑实体，又是物理实体 D、软件是程序、数据与相关文档的集合 二、软件可行性研究与项目开发计划： ❖ 软件可行性研究的目的是用最小的代价在尽可能短的时间内确定该软件项目是否能够 开发，是否值得去开发。 ❖ 可行性研究的任务： A、技术可行性 B、经济可行性 C、社会可行性（法律可行性） ❖ 可行性研究的具体步骤： 1、确定项目规模和目标 2、研究正在运行的系统 3、建立新系统的高层逻辑模型 4、导出和评价各种方案 5、推荐可行的方案 6、编写可行性研究报告 三、软件需求分析： ❖ 需求分析是指开发人员要准确理解用户的要求，进行细致的调查分析，将用户非形式的 需求陈述转化为完整的需求定义，再由需求定义转换到相应的形式功能规约（需求规格 说明）的过程。 ❖ 需求分析的基本任务： 1、问题识别 A、功能需求 B、性能需求 C、环境需求
D、用户界面需求2、分析与综合，导出软件的逻辑模型3、编写文档（需求规格说明书）需求分析的方法：1、结构化分析(StructuredAnalysis)：是面向数据流进行需求分析的方法。SA方法利用图形等半形式化的描述方式表达需求，主要描述工具：A、数据流图(DFD)：是SA方法中用于表示系统逻辑模型的一种工具，以图形的方式描绘数据在系统中流动和处理的过程B、数据字典(DD)：用以定义数据流图中的各个成分的具体含义，为系统的分析、设计及维护提供了有关元素的一致的定义和详细的描述。C、描述加工逻辑的结构化语言、判定表、判定树2、IDEF方法（是ICAMDefinition的缩写）：是一种用于进行复杂系统分析和设计的方法，是在结构化分析和设计技术的基础上提出来的。3、面向对象分析方法(OOP)：将客观世界的事物抽象为对象，通过属性和方法描述对象的状态和行为，具有继承、封装和多态性等特征。例：软件开发的结构化分析方法中，常用的描述软件功能需求的工具是（）A、业务流程图、处理说明B、软件流程图、模块说明C、数据流程图、数据字典D、系统流程图、程序编码四、软件概要设计：将软件需求转换为软件表示的过程。软件概要设计的基本任务：1、设计软件系统结构2、数据结构及数据库设计（概要设计、逻辑设计、物理设计）：3、编写概要设计文档：4、评审：软件设计的方法：模块化：模块在程序中是数据说明、可执行语句等程序对象的集合，或者是单独命名和编址的元素，如高级语言中的过程、函数、子程序等。模块独立性指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少目接口简单。其度量标准是：耦合性和内聚性耦合性也称块间联系，指软件系统结构中各模块间相互联系紧密程度的一种度量。模块之间联系越紧密，其耦合性就越强，模块的独立性则越差。心内聚性也称块内联系，指模块功能强度的度量，即一个模块内部各个元素（语句之间、程序段之间）彼此结合的紧密程度的度量。&将软件系统划分模块时，尽量做到高内聚低耦合。例：为了使模块尽可能独立，要求（）A、模块的内聚程序要尽量高，且各模块间的耦合程序要尽量强B、模块的内聚程序要尽量高，且各模块间的耦合程序要尽量弱C、模块的内聚程序要尽量低，且各模块间的耦合程序要尽量弱
D、用户界面需求 2、分析与综合，导出软件的逻辑模型 3、编写文档(需求规格说明书) ❖ 需求分析的方法： 1、结构化分析(Structured Analysis)：是面向数据流进行需求分析的方法。 SA 方法利用图形等半形式化的描述方式表达需求，主要描述工具： A、数据流图(DFD)：是 SA 方法中用于表示系统逻辑模型的一种工具，以图形的方式描绘 数据在系统中流动和处理的过程。 B、数据字典(DD)：用以定义数据流图中的各个成分的具体含义，为系统的分析、设计及维 护提供了有关元素的一致的定义和详细的描述。 C、描述加工逻辑的结构化语言、判定表、判定树 2、IDEF 方法(是 ICAM Definition 的缩写)： 是一种用于进行复杂系统分析和设计的方法，是在结构化分析和设计技术的基础上提出 来的。 3、面向对象分析方法(OOP)： 将客观世界的事物抽象为对象，通过属性和方法描述对象的状态和行为，具有继承、封 装和多态性等特征。 例：软件开发的结构化分析方法中，常用的描述软件功能需求的工具是（ ） A、业务流程图、处理说明 B、软件流程图、模块说明 C、数据流程图、数据字典 D、系统流程图、程序编码 四、软件概要设计： 将软件需求转换为软件表示的过程。 ❖ 软件概要设计的基本任务： 1、设计软件系统结构 2、数据结构及数据库设计（概要设计、逻辑设计、物理设计）： 3、编写概要设计文档： 4、评审： ❖ 软件设计的方法： 模块化：模块在程序中是数据说明、可执行语句等程序对象的集合，或者是单独命名和 编址的元素，如高级语言中的过程、函数、子程序等。 ❖ 模块独立性指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且 接口简单。其度量标准是：耦合性和内聚性 ❖ 耦合性也称块间联系，指软件系统结构中各模块间相互联系紧密程度的一种度量。模块 之间联系越紧密，其耦合性就越强，模块的独立性则越差。 ❖ 内聚性也称块内联系，指模块功能强度的度量，即一个模块内部各个元素(语句之间、 程序段之间)彼此结合的紧密程度的度量。 ❖ 将软件系统划分模块时，尽量做到高内聚低耦合。 例：为了使模块尽可能独立，要求（ ） A、模块的内聚程序要尽量高，且各模块间的耦合程序要尽量强 B、模块的内聚程序要尽量高，且各模块间的耦合程序要尽量弱 C、模块的内聚程序要尽量低，且各模块间的耦合程序要尽量弱
D、模块的内聚程序要尽量低，且各模块间的耦合程序要尽量强五、软件详细设计：主要确定每个模块具体执行过程软件详细设计的基本任务：1、为每个模块进行详细的算法设计：2、为模块内的数据结构进行设计：3、对数据库进行物理设计：4、输入、输出格式设计5、编写详细设计说明书：6、评审：&详细设计常用三种工具：图形(流程图、盒图、问题分析图PAD)、表格(判定表)语言（过程设计语言，又称为伪码）六、软件编码：主要是将详细设计得到的处理过程描述转换为基于某种计算机语言的程序常用的计算机语言：Pascal、C、C++、Java等七、软件测试：软件测试代表了需求分析、设计、编码的最终复审。软件测试贯穿于软件开发的全过程。软件测试的目的：1、软件测试是为了尽可能多地发现程序中的错误而执行程序的过程。2、一个好的测试用例能够发现至今尚未发现的错误。3、一个成功的测试是发现了至今尚未发现的错误的测试。软件测试的原则：1、测试用例应由输入数据和预期的输出数据两部分组成。2、测试用例不仅选用合理的输入数据，还要选择不合理的输入数据3、除了检查程序是否做了它应该做的事4、应制定测试计划并严格执行，排除随意性5、长期保留测试用例6、对发现错误较多的程序段，应进行更深入的测试7、程序员避免测试自己的程序&软件测试方法：1、静态测试：是指被测试程序不在机器上运行，而是采用人工检测和计算机辅助静态分析的手段对程序进行检测。2、动态测试：是指通过运行程序发现错误A、黑盒测试法(功能测试)：
D、模块的内聚程序要尽量低，且各模块间的耦合程序要尽量强 五、软件详细设计： 主要确定每个模块具体执行过程 ❖ 软件详细设计的基本任务： 1、为每个模块进行详细的算法设计： 2、为模块内的数据结构进行设计： 3、对数据库进行物理设计： 4、输入、输出格式设计 5、编写详细设计说明书： 6、评审： ❖ 详细设计常用三种工具： 图形(流程图、盒图、问题分析图 PAD)、 表格(判定表)、 语言(过程设计语言，又称为伪码) 六、软件编码： 主要是将详细设计得到的处理过程描述转换为基于某种计算机语言的程序 常用的计算机语言： Pascal 、C、C++、Java 等 七、软件测试： 软件测试代表了需求分析、设计、编码的最终复审。软件测试贯穿于软件开发的全过程。 ❖ 软件测试的目的： 1、软件测试是为了尽可能多地发现程序中的错误而执行程序的过程。 2、一个好的测试用例能够发现至今尚未发现的错误。 3、一个成功的测试是发现了至今尚未发现的错误的测试。 ❖ 软件测试的原则： 1、测试用例应由输入数据和预期的输出数据两部分组成。 2、测试用例不仅选用合理的输入数据，还要选择不合理的输入数据 3、除了检查程序是否做了它应该做的事 4、应制定测试计划并严格执行，排除随意性 5、长期保留测试用例 6、对发现错误较多的程序段，应进行更深入的测试 7、程序员避免测试自己的程序 ❖ 软件测试方法： 1、静态测试： 是指被测试程序不在机器上运行，而是采用人工检测和计算机辅助静态分析的手段对 程序进行检测。 2、动态测试：是指通过运行程序发现错误 A、黑盒测试法(功能测试)：
主要对软件的接口进行测试，依据需求规格说明书，检查程序是否满足功能要求。常用的技术是等价类划分法、边界值分析法、错误推测法、因果图法、综合策略法B、白盒测试法(结构测试)：主要测试程序的内部结构和处理过程。常用的技术是语句覆盖、条件覆盖、路径覆盖、判定覆盖等软件测试的实施：1、单元测试：单元测试是对软件设计的最小单位一一模块（程序单元)进行正确性检验测试，主要针对模块的以下五个基本特征进行测试：A、模块接口B、局部数据结构：C、重要的执行路径：D、错误处理测试：E、边界条件：2、集成测试：集成测试是指在单元测试的基础上，将所有模块按照设计要求组装成一个完整的系统进行的测试，故也称组装测试或联合测试。主要方法有两种：非渐增式测试：首先对每个模块分别进行单元测试，然后再把所有的模块按设计要求组装在一起进行测试。渐增式测试：逐个把未经过测试的模块组装到已经过测试的模块上去，进行集成测试每加入一个新模块进行一次集成测试，重复此过程直至程序组装完毕。3、确认测试：确认测试又称有效性测试，它的任务是检查软件的功能与性能是否与需求规格说明书中确定的指标相符合，因而需求规格说明是确认测试的基础。4、系统测试：系统测试是通过测试确认的软件作为整个计算机系统的一个元素，与计算机硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起，在实际运行环境下对计算机系统进行一系列的集成测试和确认测试。程序调试：调试是在进行了成功的测试之后才开始的工作，目的是确定错误的原因和位置，并改正错误，又称为纠错。例：软件测试的目的是（）A、证明软件的正确性B、找出软件系统中存在的所有错误C、尽可能多地发现软件系统中的错误D、证明软件系统中存在错误在软件测试方法中，黑箱测试法和白箱测试法是常用的方法，其中黑箱测试法主要是用于测试（）A、结构合理性B、软件外部功能C、程序正确性D、程序内部逻辑八、软件维护：软件投入使用后进行的阶段，是软件生存周期中时间最长的一个阶段，所花费的精力和
主要对软件的接口进行测试，依据需求规格说明书，检查程序是否满足功能要求。常用 的技术是等价类划分法、边界值分析法、错误推测法、因果图法、综合策略法 B、白盒测试法(结构测试)： 主要测试程序的内部结构和处理过程。常用的技术是语句覆盖、条件覆盖、路径覆盖、 判定覆盖等 ❖ 软件测试的实施： 1、单元测试： 单元测试是对软件设计的最小单位——模块(程序单元)进行正确性检验测试，主要针对 模块的以下五个基本特征进行测试： A、模块接口 B、局部数据结构： C、重要的执行路径： D、错误处理测试： E、边界条件： 2、集成测试： 集成测试是指在单元测试的基础上，将所有模块按照设计要求组装成一个完整的系统进 行的测试，故也称组装测试或联合测试。 主要方法有两种： 非渐增式测试：首先对每个模块分别进行单元测试，然后再把所有的模块按设计要求组 装在一起进行测试。 渐增式测试：逐个把未经过测试的模块组装到已经过测试的模块上去，进行集成测试， 每加入一个新模块进行一次集成测试，重复此过程直至程序组装完毕。 3、确认测试： 确认测试又称有效性测试，它的任务是检查软件的功能与性能是否与需求规格说明书中 确定的指标相符合，因而需求规格说明是确认测试的基础。 4、系统测试： 系统测试是通过测试确认的软件作为整个计算机系统的一个元素，与计算机硬件、外设、 支撑软件、数据和人员等其他系统元素组合在一起，在实际运行环境下对计算机系统进行一 系列的集成测试和确认测试。 ❖ 程序调试： 调试是在进行了成功的测试之后才开始的工作，目的是确定错误的原因和位置，并改正 错误，又称为纠错。 例：软件测试的目的是（ ） A、证明软件的正确性 B、找出软件系统中存在的所有错误 C、尽可能多地发现软件系统中的错误 D、证明软件系统中存在错误 在软件测试方法中，黑箱测试法和白箱测试法是常用的方法，其中黑箱测试法主要是 用于测试（ ） A、结构合理性 B、软件外部功能 C、程序正确性 D、程序内部逻辑 八、软件维护： 软件投入使用后进行的阶段，是软件生存周期中时间最长的一个阶段，所花费的精力和