软件工程技术基础复习指南
一．数据结构1术语：1数据；2数据元素；3数据结构；4结构
2数据结构定义：就是具有结构的数据元素的集合。3算法的定义：用来解决某个特定课题的指令的集合。4算法的性质：输入、输出、有穷性、确定性、有效性5算法描述：自然语言、程序流程图、具体程序语言6算法分析：指对算法质量优劣的评价。（时间复杂度、空间复杂度、可读性、可移植性、
易测试性）7时间复杂度：依据算法编写的程序在计算机中运行时间多少的度量（关键语句之行的次
数）O（
）；（Olog2
（二分检索）O
（比较两个具有
个字符串）O
log2
O
2O
3（常规矩阵乘）O2
O
）；O（1）：访问数组中的元素是常数时间操作8空间复杂度：依据算法编写的程序在计算机中占存储空间多少的度量9频度统计法：以语句执行的次数的多少作为算法的时间量度的分析方法10语句的频度：语句被执行的次数11算法的频度：算法中所有语句的频度之和12数组：下标与值组成的偶对的有穷集合13二维数组的存储结构：行序为主序分配方式、列序为主序分配方式、14特殊矩阵的压缩存储：对称矩阵、对角矩阵、15线性表：数据元素之间具有的逻辑关系为线性关系的数据元素集合16线性表的基本操作：创建、索引、存入、插入、删除、排序、17线性表顺序存储结构：用一组地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过数据元素的存储位置直接反映18顺序存储结构优点：原理简单、元素存储地址可用简单解析式计算、存储空间开销小19顺序存储结构缺点：需事先分配连续地址、基本操作时间效率低20线性链表：用一组地址任意的存储单元连续的或不连续的依次存储表中各个数据元素数据元素之间的逻辑关系通过间接地反映出来21链式存储结构优点：存储空间动态分布、地址不连续、插入删除操作效率高（O1）22链式存储结构缺点：存储密度小、查找定位效率低O
23堆栈定义：是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由一个称为栈顶指针的变量给出。当表中没有元素时，称之为空栈。（后进先出）
f24堆栈基本操作：插入、删除、测试堆栈是否为空25堆栈存储结构：顺序、链式26队列的定义：一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线
性表。允许插入的一端称为队尾，队尾元素的位置由rear指出；允许删除的一端称为队头队头元素的位置由fro
t指出。（先进先r