软件开发技术基础复习资料(南航版)

考试题型分布：填空题（30分：30*1分），简答题（30分：6*5分），计算题（30分：3*10分），编程题（10分：1*10分）1.软件工程的三个基本要素2.算法的概念3.算法的基本特征4.算法描述方式5.算法设计基本方法6.递归设计7.算法评价标准8.制约算法效率的要素9.时间复杂度10.空间复杂度11.数据12.阐述数据、数据元素、数据项和数据结构的含义和联系。13.数据类型的概念；举例常见数据类型14.数据逻辑结构包含15.数据结构主要包括数据的逻辑结构和存储结构。两者的关系16.数据存储结构两种常见类型：顺序存储结构，链式存储结构。分别的特点：17.数据结构基本操作有哪些18.线性表（LinearList19.线性表的顺序存储结构的特点：20.顺序表中数据元素的存储地址计算21.顺序表插入，删除算法的时间和空间复杂度：22.栈的基本概念：栈、栈顶、栈底、栈的修改（后进先出，先进后出）、入栈、退栈。23.栈的顺序存储结构（大概了解）24.栈的溢出类型：上溢，下溢。25.基于栈的表达式计算：算术运算符的优先级，给定一个表达式，构建栈。26.波兰表示法（Polishnotation）27.队列的术语：排头，队尾，队列规则（先进先出，后劲后出）。28.队列的假溢出及其避免方法。（了解）29.循环队列30.线性链表31.线性链表插入，删除后指针的变化。32.单链表33.双向链表34.索引存储的概念：35.索引存储的方式36.数组37.树结构概念具有分支和层次关系的非线性结构（一对多）对于结构中的一个节点，可能有一个前趋和多个后继（线性表中是有且仅有一个前趋和一个后继。38.树的基本术语树是n(n≥0)个结点的有限集。若n=0，称为空树。1）结点－包含一个数据元素及若干指向子树的分支；根结点：没有前驱，仅有后继叶结点：没有后继，仅有前驱分支结点：有且仅有一个前驱，可以有多个后继（2）度与深度结点的度：该结点拥有的子树数目。树的度：最大的结点度深度：最大的层次数（3）结点之间的关系：双亲：孩子的父结点；孩子：结点的子树的根称为该结点的孩子；兄弟：同一双亲的孩子结点；堂兄弟：同一层上不同双亲的结点；（4）路径（树枝，分支）：从K1出发自上而下到K2所经历的所有结点序列（5）有序树－子树有序的树如：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。（6）森林－不相交的树的集合39.二叉树定义：二叉树是结点的有序集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。定义是递归结构可为空树每结点的度=2。子树有序。40.二叉树的形态：满、完全、一般、单支41.用有序树表示一个表达式。将一个表达式表示成有序树的规则如下：表达式中的运算符为有序树的根结点或内部结点：每一运算符的所有运算对象为该运算符结点的子树所有参数变量为叶子结点。42.二叉树的基本性质。性质1在二叉树的第i层上最多有2i-1个结点。例如：对于右图，第1层上最多有1≤20个结点，第2层上最有2≤21个结点，第3层上有3≤22个结点，…性质2深度为h的二叉树最多有2h-1个结点。性质3设二叉树叶结点数为n0，度为2的结点数为n2，则n0=n2+1性质4具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。性质5：具有n个结点的完全二叉树的深度为log2n+1性质6：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1,则其双i/2；(2)如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i；(3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。43.满二叉树，完全二叉树满二叉树：深度为k且有2k–1个结点的二叉树完全二叉树：对于深度为k的完全二叉树，则1)前k-1层为满二叉树；2)第k层结点依次占据最左边的位置；3)一个结点有右孩子，则它必有左孩子；4)度为1的结点个数为0或15)叶子结点只可能在层次最大的两层上出现；6)对任一结点，若其右分支下的子孙的最大层次为L,则其左分支下的子孙的最大层次必为L或L+1。44.二叉树遍历方案。掌握具体的遍历过程。先序，中序，后序。二叉树由根、左子树、右子树三部分组成以根的访问顺序来划分,子树的访问顺序以左子树优先遍历分解为：访问根D，遍历左子树L，遍历右子树R三种遍历方案：先序遍历:DLR若二叉树非空：（1）访问根结点A（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树中序遍历:LDR若二叉树非空：1)找到根结点A，但不访问A2)根据A找到B，中序遍历左子树3)再回到A、访问根结点A；4)根据A找到C，中序遍历右子树后序遍历:LRD若二叉树非空：（1）后序遍历左子树：即按LRD的顺序遍历左子树（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A45.从遍历序列恢复到二叉树由先序遍历序列和中序遍历序列可唯一地确定一棵二叉树。由中序遍历序列和后序遍历序列可唯一地确定一棵二叉树。算法思路：1）在先(后)序序列中确定根结点2）在中序序列中搜索根结点，并将中序序列拆分为左右两个子树中序序列3）递归执行1），2）确定左右子树的根结点，直到确定二叉树的所有结点。46.二叉树的顺序存储结构，完全二叉树，一般二叉树需要补齐所缺少的那些结点。空间利用率问题对一般二叉树造成空间浪费。在最坏情况下，一个深度为k且只有k个结点的单支树(不存在度为2的结点)，则需要长度为2k-1的数组。根据完全二叉树特性，结点在向量中的相对位置隐含了结点之间的关系。★考虑到数组下标是从0开始，因此；bt[i]的双亲是bt[(i-1)/2]，其左、右孩子是bt[2i+1]和bt[2i+2]（如果存在的话）。47.有序树向二叉树转化规则。具体过程。（1）T中的结点与T’中的结点为一一对应；（2）T中某个结点N的第一个子结点N1在T’中为对应结点N的左儿子结点；（3）T中某个结点N的第一个子结点以后的其它子结点，在T’中被依次链接成一串开始于N1的右儿子结点。48.表达式的线性化将一般表达式化为波兰表达式（后缀）步骤:将表达式用有序树表示;将有序树转化为二叉树;对二叉树进行中序遍历，遍历序列即为表达式的波兰表达式49.哈夫曼树的概念（最优二叉树）路径：从树中一个结点到另一个结点所经过的分支路径长度：路径上的分支数目树的路径长度：根到每一结点的路径长度(L)之和结点的权：根据应用需要给树的结点赋权值（W）；结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积树的带权路径长度：树中所有n个叶子结点的带权路径长度之和最优二叉树或哈夫曼树：树的带权路径长度最小的二叉树50.哈夫曼树的构造过程。根据给定的n个权值构成n棵二叉树的集合F，其中每棵二叉树中只有一个带权值的结点；在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；在F中删除这两棵树，同时将新得到的二叉树加入到F中；重复2)和3)，直到F中只含一棵树为止。51.图的基本概念了解。图--更为复杂的非线性数据结构抽象的图--仅代表数据信息以及它们之间的关系。数据节点间的关系是任意的。线性表--一对一：一个前趋，一个后继。树--一对多：一个前趋，多个后继，层次。图--多对多：可以有多个前趋，多个后继。图的描述要素：数据；关系图由两个集合构成，记作G=V,E，其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。52.图的存储方法53.图的遍历指从图中某一个顶点出发访问(Visit)图中每一个顶点一次且仅一次。横向优先遍历(BFS),纵向优先遍历(DFS)54.查找技术分类查找技术主要分为：静态查找、动态查找、散列查找静态查找静态查找在数据的检索过程中不进行插入和删除操作，提供如下两种查找：(1)查询某个“特定”元素是否在表中；(2)检索某个“特定”元素的各种属性；静态查找表的存储结构：顺序结构，链式结构静态查找表的组织方法：顺序表，有序表动态查找在查找过程中需要进行插入不存在的数据元素和删除已有的数据元素。散列查找利用HASH函数计算数据的存储地址。55.顺序查找：适用于顺序存储结构（顺序表、有序表）和链式存储结构的静态查找。对分查找法仅适用于顺序存储结构的有序表。分块查找又称索引顺序查找，它是顺序查找的一种改进方法，用于在“分块有序”表中进行查找。三种查找的比较56.二叉排序树的构造：（给定一数据元素序列，进行二叉排序树构造）57.构造过程：58.依次读人序列中的每一个数据元素，分别为之建立新结点，按如下方式插入到二叉排序树中：59.若二叉排序树为空，则新结点为二叉排序树的根结点；60.若二叉排序树不空，则将新结点与根结点的值比较，若小于根结点值，则插入到左子树中去，否则插入到右子树中去。61.二叉排序树的平衡化处理：概念，分类，应用。62.B-树的插入、删除应用。B-插入在2m＋1阶B一树中插入一个新元素（关键字为x)(1)在找到插入位置的叶结点中其关键字个数小于2m，则直接插入即可。(2)在找到插入位置的叶结点中其关键字个数已满（等于2m），此时需要分裂，即将原结点中的2m个关键字与要插入的关键字x一起按序排列后再对分，即将原来的结点分裂成两个结点（这时需要申请一个新的结点）。结点分裂后，将中间的关键字升到其父结点中。如果父结点中的关键字个数也已满，则又要进行分裂。这种分裂过程有可能一直进行到根，在这种情况下，B一树的深度就增加了1。B-删除在B一树中删除关键字x，首先要进行查找，找到关键字x在B一树中的位置。如果x在叶子结点上，则进行删除如果x在非叶子结点上，则要用一个比x大、而又最接近x的关键字K代替x，这个K就是x右边指针所指的路径上最左边叶子结点上的第一个关键字然后在叶子结点中删除K。63.散列（又称杂凑、哈希）的基本思想。以结点的值k为自变量，通过一定的函数关系h计算出对应的函数值h(k)，把这个值解释为结点的存储地址（散列地址），将结点存入该地址中去。64.散列（Hash）函数。用来定义记录的关键字与记录的存储位置的对应关系的函数。其自变量是记录的关键字，函数值是记录存储位置。例如：H(key)=key-194865.散列函数的构造方法1.数字选择法（截段法）2.平方取中法3.分段叠加法4.除法（余数法）66.冲突的概念。解决冲突的方法。67.线性探查法，二次探查法，随机探查法的具体的探查过程和算法。68.排序的方法分类，及各算法的时间复杂度。互换排序（冒泡排序和快速排序），插入排序（直接插入法和shell排序），选择排序，归并排序，基数排序。69.数据与信息的联系70.数据库71.数据库管理系统(DataBaseManagementSystem，DBMS)。DBMS的主要功能。72.数据库技术发展三阶段：人工管理，文件系统，数据库系统。简述三者的优缺点。73.数据库系统的体系结构74.数据库系统体系结构中硬件及软件的关系75.数据库系统的三级数据模式结构，二级映像。76.用户访问数据的过程。77.数据库语言的组成。78.概念模型（E-R模型），各术语（实体，属性，码，域，实体集，实体的联系）79.数据模型（结构数据模型），各术语（字段，记录，文件，码）80.ER图的四个基本成分。81.常见数据模型：层次模型，网状模型，关系模型。82.关系模型概念。关系模型的优点。83.关系代数的运算。常规的集合运算（包括并、差、交和笛卡儿积等）和专门的关系运算（包括选择、投影、联接等）84.数据库设计85.数据库设计的过程（六阶段）86.需求分析调查方法：87.概念结构的设计方法：自顶向下，自底向上，逐步扩张，混合策略88.常见数据抽象方法：分类，聚集，概括。89.设计E-R图。90.局部E-R图