《自考数据结构导论复习资料(共19页).doc》由会员分享，可在线阅读，更多相关《自考数据结构导论复习资料(共19页).doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上数据结构导论复习第一章 概论1数据：凡能被计算机存储、加工处理的对象。2数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理3数据项：又叫字段或域，它是数据的不可分割的最小标识单位。4逻辑结构需要注意的几点：逻辑结构与数据元素本身的内容无关逻辑结构与数据元素相对位置无关逻辑结构与所有结点的个数无关5数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。6四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？答：集合中任何两个结点之间都没有逻辑关系，组织形式松散；线性结构中结点按逻辑关系依次排列形成一条“锁链”；树形结构具有分支、层次特性
2、，其形态有点像自然界中的树；图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。7运算是在逻辑结构层次上对处理功能的抽象8基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算9数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。10数据结构涉及数据表示和数据处理两个方面11存储结构的含义和四种基本存储方式的基本思想？答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。一个存储结构应包含三个主要的部分：存储结点、机内表示和附加
3、设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。13算法的概念和分类？答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被机械地求解。算法的类型有：运行终止的程序可执行部分、伪语言算法和非形式算法（根据描述算法语言不同）14算法在给定输入下的计算量的含义和估算的方法？ 答：算法在给定输入下的计算
4、量是指根据该类问题的特点合理地选择一种或几种操作作为“标准操作”，确定每个算法在给定输入下共执行多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。 估算的方法有：最坏时间复杂度和平均时间复杂度。15最坏情况时间复杂性和平均时间复杂性的概念？ 答：最坏情况时间复杂性也称为最坏时间复杂度，是指以算法在所有输入下的计算量的最大值作为算法的计算量；平均情况时间复杂性也称为平均时间复杂度，是指以算法在所有输入下的计算量的加权平均值作为算法的计算量；16空间复杂性指的是一个算法除输入数据占存储空间之外所需要的附加存储空间的大小。17算法的性质：正确性、易读性、健壮性和高效率。第二章 线性表1线性
5、结构：是n（n0）个结点的有穷序列。2线性结构的基本特征：若至少含有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋；除终端节点没有直接后继外，其他结点有且仅有一个直接后继。3线性表的逻辑结构是线性结构4线性表的六种基本运算的功能？ 答：初始化INITIATE(L)，功能是建立一个空表 求表长LENGTH(L)，功能是返回线性表L的长度 读表元GET(L，i)，功能是返回线性表L的第i个结点 定位（按值查找）LOCATE(L，X),功能是返回找到的结点集合中序号的最小值，否则返回值为0（说明没有找到） 插入INSERT（L，X，i），功能是在线性表L的地i个位置上增加一个值为
6、X的新结点（整个表长+1） 删除DELETE(L，i)，功能是撤销线性表L的第i个位置结点（整个表长-1）5顺序表表示法的基本思想、特点 答：基本思想是：按照顺序存储方式，顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素，所有存储结点按相应数据元素建的逻辑关系决定的次序依次排列。 特点：逻辑结构中相邻的结点在存储结构中仍相邻。6区别顺序表的容量与线性表的表长? 答：顺序表的容量是指定义顺序表时的maxsize的值，而线性表的表长是指其中包含的结点个数。7顺序表中ai的地址计算：ai的地址=b+（i-1）*l，b是首地址，l是每个结点占的空间7掌握顺序表上实现插入、删除和定位运算的三个
7、算法P18-208单链表表示法的基本思想用指针表示结点间逻辑关系9单链表的结点形式：答：由数据域和指针域两部分组成；这两部分各自的作用分别是数据域是用于存储线性表的一个数据元素的，指针域是用于存放一个指针的，该指针指向本结点所含数据元素的直接后继所在的结点。10头指针和头结点的作用？ 答：头指针是一个指向链表开始结点的指针，单链表由头指针唯一确定；头结点是我们人为地在链表的开始结点之前附加的一个结点，有了头结点之后，头指针指向头结点，不论链表是否为空，头指针总是非空的，而且头指针的设置使得对链表的第一位置上的操作和在其他位置上的操作一致。11单链表上实现插入、删除和定位三种运算的三个算法：P2
8、6-2812插入算法中所包含的指针操作：s=malloc(size);sdata=x;snext=pnext;pnext=s; 删除算法中所包含的指针操作：q=pnext;pnext=qnext;free(q);13Malloc（size）的作用： 生成一个结点 形式一条指针14循环链表的组织方法：将单链表中的尾结点的NULL改成指向头结点的指针，就形成了循环链表。循环链表优点：可以从表中任一结点出发都可以向后扫描整表。15双链表的结点形式： 刻画双链表结构的对称性的语句：ppriornext= pnextprior;16顺序表的主要优点和主要缺点： 优点：无需为表示结点间的逻辑关系而增加额外
9、的存储空间 可以方便地随机存取表中的任意结点 缺点：插入和删除运算不方便 分配内存空间采用静态分配方式17链表的主要优点： 插入和删除运算方便，只需要修改指针，不需要移动结点 分配内存空间采用动态分配方式18字符串：以字符为数据元素，以线性结构为逻辑结构的数据。19串的逻辑结构（是线性结构）和串的特点（是由0个或多个字符组成的有穷序列）20串的基本运算的功能：判等EQUAL(S,T)的功能是两个串的长度要相等，而且对应位置的字符都要相同。21串的顺序存储方法（紧缩格式和非紧缩格式）和链接存储方法第三章 栈、队列和数组1栈的基本运算及由此而决定的栈的基本特点栈是一种只允许在栈顶进行插入、删除的特
10、殊线性表；其基本特点是采用“后进先出”操作；2栈的基本运算：初始化InitStack（S）进栈Push（S，X）退栈Pop（S） 读栈顶元素TOP（S）判断栈空Empty（S）3顺序栈 “上溢”、“下溢”的概念 “上溢”：顺序栈在进行进栈时，超过了顺序栈的最大的容量 “下溢”：顺序栈在进行退栈时，栈中的元素少于0个元素4进栈和退栈运算在顺序栈上的实现算法：P445顺序栈上的简单算法（初始化，判栈空，取栈顶元素）6链栈的结点形式及其描述： Data用来存放该结点的数据元素 Next用来存放指向下一个数据元素7链栈上实现进栈和退栈的算法P468链栈上的简单算法（初始化，判栈空，取栈顶元素）9 队列
11、的基本运算及由此决定的队列的特点 队列是一种只允许在对头进行插入在队尾进行删除的特殊线性表；其基本特点是采用“先进先出”操作；10顺序队上的“假溢出”及其解决方法：顺序队在进行多次入队、出队后，顺序队已经满了，但顺序队中的大部分空间是空的； 解决方法：将顺序队改成循环队11循环队队满、队空的条件： 判断循环栈满的条件：（sqrear+1）%maxsize）=sqfront 判断循环栈空的条件：sqrear= sqfront12链队的结点形式及其链队的组织方法：13在链队上实现入队、出队的算法P56-5714数组的逻辑结构是线性结构的推广15二维数组的基本运算是读与写16二维数组：，其中a00是
12、首地址，k是每个数据元素存储单元。17稀疏矩阵的三元组表示法：A=（i,j,aij）A=(1,2,3),(1,6,1),(3,1,5),（3，2，-1），（4，5，4），（5，1，-3）)第四章 树1树的定义：是n（n0）个结点的有穷集合，满足： 有且仅有一个称为根的结点 其余结点分为m（m0）个互不相交的非空集合T1，T2 Tm，这些集合中的每一个都是一棵树，称为根的子树。2树形结构的有关术语及其含义根结点双亲结点和孩子结点兄弟结点和堂兄弟结点子孙结点和祖先结点树的层次、树的高度和树的度3二叉树的逻辑结构、特点和五种基本形态（1）：二叉树是n（n0）个结点的有穷集合，满足： 有且仅有一个称为
13、根的结点 其余结点分为2个互不相交的集合T1，T2，T1是左子树，T2是右子树，且T1，T2也都是一棵二叉树。（2）特点：二叉树是棵有序树 二叉树的度2（3）五种基本形态 4二叉树的基本运算和性质（1）二叉树的基本运算： 初始化 INITIATE(BT) 求根 ROOT(BT) 求双亲PARENT(BT,X) 求左孩子 LCHILD(BT,X) 求右孩子 RCHILD(BT,X) 建树CREATE(X,LBT,RBT) 剪枝DELLEFT(BT,X) 和 DELRIGHT(BT,X)（2）二叉树的性质： 第i层上，最多有个结点 深度是K，最多总有 是针对普通二叉树 n0=n2+1 具有n个结点
14、，深度 是针对完全二叉树 按照从上到下，从左到右的顺序编号， 5二叉链表的结点形式及其描述，二叉链表中各结点的联系方法及根指针的作用（1）二叉链表的结点形式data是存放该结点的数据元素，lchild是存放指向该结点的左孩子的指针，rchild是存放指向该结点的右孩子的指针。（2）根指针的作用，是用来指明根结点。6满二叉树和完全二叉树的概念（1）满二叉树是深度为K的二叉树的总共结点数为（2）完全二叉树是在满二叉树上少0个或者从最下层的最右边开始少起的二叉树7设计二叉树上基于三种遍历的简单算法8判定树和哈夫曼树的概念（1）判断树是用来描述分类过程的二叉树（2）哈夫曼树是构造带权路径长度最小的二叉
15、树9.哈夫曼树的特性:m个权值构造的哈夫曼树的结点总数为2m-1m个权值构造的哈夫曼树后权值都处在叶子结点上在哈夫曼树中，权值越大离根越近在哈夫曼树中，没有度为1的结点10.将树转化成二叉树时，得到的二叉树的右子树永远为空11.在n个结点的二叉链表中，总共有2n个指针，其中，非空指针数为n-1，空指针数为n+112. 三叉链表的好处是方便每个结点找其双亲结点13.讨论树、森林和二叉树的关系目的是想借助二叉树上的运算方法来实现对树的一些运算14.要将先序、中序和后序遍历序列中的两种还原成唯一二叉树时，必须要有中序序列15. 附录：树这章可以出的应用题1.二叉树 二叉链表图 2. 二叉链表图 二叉
16、树（是上题中的逆操作）3. 二叉树 顺序存储结构图 操作规则： 完全化 按从上到下，从左到右编号 依次存入对应的数组中的位子ABCDEFGH 1 2 3 4 5 6 7 8 9 10 11 12 134.顺序存储结构图 二叉树（是上题中的逆操作）5. 二叉树 写出先序、中序和后序遍历 先序（DLR）:ABDEGCF 中序（LDR）:DBGEACF 后序（LRD）:DGEBFCA6. 先序和中序或者先序和后序序列 二叉树（1）先序序列：ABCDEFGHIJ中序序列：CDBFEAIHGJ（2）后序序列：DECBHGFA中序序列：BDCEAGFH7.树 孩子链表表示法8.树 孩子兄弟链表表示法9.树
17、 双亲表示法10.树 二叉树 11.森林 二叉树 12.二叉树 森林 13.哈夫曼树的构造给定权值给7，18，3，32，5，26，12，8，构造哈夫曼树并计算其带权路径长度带权路径长度=298第五章 图1图状结构的定义并熟悉有关术语（1）图的定义：图由两个集合构成，记作G=(V，E)，其中V是顶点的有穷非空集合，E是边的集合，并且边是顶点集合的无序对或有序对集合。（2）图的术语：无向图：顶点点偶对是无序的 记作：（vi，vj）有向图：顶点点偶对是有序的 记作：无向完全图：任何两个顶点都有边关联的无向图（n个顶点无向完全图总有边）有向完全图：任何两个顶点都有弧关联的有向图（n个顶点有向完全图总有
18、边）无向图顶点的度：与该顶点关联的边的数目；有向图顶点的度=入度+出度（入度：以该顶点为终点的边数；出度：以该顶点为始点的边数；）权：图中边上附带的值；路径：是从一个顶点到另一个顶点的序列；简单路径：序列中顶点不重复的路径；环/回路：第一个顶点和最后一个顶点相同的路径；简单环/回路：除了第一个顶点和最后一个顶点相同外，其余顶点均不重复的回路；子图：设图G=（V，E），若，且中的边关联的顶点都在中，则称（，）是的子图；连通图：在无向图中，任何两个顶点都存在到的路径强连通图：在有向图中连通分量：无向图的一个极大的连通子图强连通分量：有向图的一个极大的强连通子图极小连通子图：将子图中任何一条边删除后
19、该子图都不再连通，则给子图是极大连通子图：向子图中再加入其他任何一个顶点及其相关联的边后该子图都不连通，则给子图是图的生成树：包含图中所有顶点的一个极小连通子图。注：n个顶点的图的生成树包含有n-1条边；若包含图的所以顶点的子图的边n-1，则说明图中一定含有环；若包含图的所以顶点的子图的边n-1，则说明图一定是非连通的；2有向图、无向图邻接矩阵表示法和邻接表表示法 无向图 邻接矩阵 邻接表 有向图 邻接矩阵 邻接表 逆邻接表注：（1）无向图的邻接矩阵是一个对称矩阵；（2）无向图的邻接矩阵中D（Vi）=第i行或者第i列“1”的个数/第i行或第i列元素之和；（3）无向图中有n个顶点、e条边则其邻接
20、表中有n个表头结点和2e个表结点；（4）无向图的邻接表中D（Vi）=第i个单链表中表结点的个数；（5）有向图的邻接矩阵中D（Vi）=ID（Vi）+OD（Vi）其中， ID（Vi）=第i列中“1”的个数OD（Vi）=第i行中“1”的个数（6）有向图中有n个顶点、e条边则其邻接表中有n个表头结点和e个表结点；（7）有向图的邻接表中D（Vi）=ID（Vi）+OD（Vi）其中， OD（Vi）=第i个单链表中表结点的个数； ID（Vi）=逆邻接表中第i个单链表中表结点的个数； 或者=邻接表中值域=Vi的表结点的个数；3网的领接矩阵表示 带权有向图（有向网） 邻接矩阵4连通图的深度优先搜索和广度优先搜索的
21、基本思想、基本步骤，并给出相应搜索的顶点序列 深度优先搜索序列：V0，V1，V3，V7，V4，V2，V5，V6 广度优先搜索序列：V0，V1，V2，V3，V4，V5，V6，V7 图的深度优先搜索相当于树的先根遍历 图的广度优先搜索相当于树的层次遍历 深度优先搜索，用栈来暂存访问过的顶点 广度优先搜索，用队列来暂存访问过的顶点（1）连通图的深度优先搜索步骤：首先访问出发点（Vi），然后任选一个与Vi的未被访问过的邻接点Vj ，再以Vj为新的出发点继续进行深度优先搜索，直到图中所有顶点均被访问过。（2）连通图的广度优先搜索步骤：首先访问出发点（Vi），然后依次访问与Vi的未被访问过的邻接点Vj，V
22、k ，再以VjVk为新的出发点继续进行广度优先搜索，直到图中所有顶点均被访问过。5非连通图的遍历方法以及图的连通分量的求法 连通分量 深度优先搜索序列：V1，V2，V3，V5，V4，V6，V8，V7广度优先搜索序列：V1，V2，V4，V3，V5，V6，V8，V76生成树和最小生成树的概念（1）图的生成树：包含图中所有顶点的一个极小连通子图；（2）树的权：指树中所有边上权之和；（3）最小生成树：是指树的权最小的生成树；7Prim算法的基本思想，并能据此用图示法表示出求给定网的一棵最小生成树的过程（1）Prim算法的基本思想： 初始化：U=Vi，TE=； 找U中顶点关联的所有边中权值最小的边（u，
23、v），如果uU，vV-U，则最小生成树包括边（u，v）,即：把v加入U中，把（u，v）加入TE中； 重复执行，直到U=V才结束；（2）构造最小生成树的过程： U=V2 TE= U=V2,V1 TE=(V2,V1) U=V2,V1,V3 TE=(V2,V1), (V1,V3), U=V2,V3,V1,V4 TE=(V2,V1), (V1,V3), (V3,V4) U=V2,V3,V1,V4,V5 TE=(V2,V1), (V1,V3), (V3,V4), (V4,V5)8 拓扑排序的基本概念及给出一个有向图的拓扑序列(1) 拓扑排序：指找一个有向图的一个拓扑序列的过程。拓扑排序只能用在有向图中；
24、拓扑排序得到的序列一般不唯一；拓扑排序不能用于含有环或者是回路的有向图中；检查有向图中是否含有环或者是回路的方法有：拓扑排序和按深度优先搜索（2）给出一个有向图的拓扑序列（找入度=0） 拓扑序列：V1，V5，V2，V4，V3第六章 查找表1集合：由任意一些可分辨的对象构成的整体确定性：元素x是否属于集合A一定是确定唯一性：同一集合的各个元素是互不相同的空集：集合中没有元素集合的逻辑结构的基本特点：任何两个元素之间都没有逻辑关系2查找表：由同一数据类型的元素构成的集合。 3查找表包括静态查找表（只提供查找、读表元）动态查找表（只提供查找、读表元、插入、删除、初始化）4静态查找表的顺序表的顺序查找
25、算法：从表的第n个位置开始，从后往前依次将各个位置上的数据元素的键值与给定值K比较，如果相等，则返回该键值的位置，否则，查找不成功5查找长度：数据元素的键值与给定值K的比较次数平均查找长度： ASL=（Pi为查找第i个元素的概率；Ci找到第i个元素所比较的次数）等概率事件的平均查找长度：ASL=6有序表：对于任何一个顺序表，若其中的所有结点按键值的某种次序排列。二分查找算法：R.itemmid.key=k，说明mid就是我们找到的位置 R.itemmid.keyk，说明我们找到的位置在low和mid之间，令mid=high-1 R.itemmid.keyk，说明我们找到的位置在mid和high
26、之间，令mid=low+17二叉排序树的概念：要么是一棵空树，要么是一棵满足下列要求的二叉树： 如果左子树不为空，则左子树上所有的结点都小于根结点； 如果右子树不为空，则右子树上所有的结点都大于根结点； 左右子树都是一个二叉排序树；二叉排序树的性质：用中序遍历二叉排序树得到的序列是递增的序列；8二叉排序树的查找算法的基本思想： 若tkey=K，查找成功，返回t指针若tkeyK，继续查找其左子树若tkeyK，继续查找其右子树若t=NULL，说明查找失败9二叉排序树插入运算的实现方法： （1）原则：必须保证插入后仍然是一棵二叉排序树 （2）方法：当查找K不成功而终止时，就是恰好找到了以K为键值的新
27、结点在二叉排序树上的插入位置。以（19，14，22，1，66，21，83，27，56，13，10）构造一棵二叉排序树。10散列函数：将键值映射为散列表中存储位置的函数散列表：按照散列存储方式构造的存储结构11散列存储和散列查找的两个主要问题：（1）如何构造“均匀的”散列函数（2）用什么方法解决冲突12同义词：设有散列函数H和键值k1、k2，若k1k2且（k1）=（k2），则称k1、k2是同义词。冲突：假设动态查找表中x1，x2，要求将x1，x2存入同一个散列表，而且它们键值是同义词，则产生冲突。13散列函数的评价（选择）原则：产生冲突越少，散列函数就越好。14各种常用的散列函数的构造方法：数字
28、分析法 除余法 平方取中法 基数转换法 随机数法15开散列表的存储组织方式：设散列函数为H，H的值域为（0，1，n -1），设置一个“地址向量”Hpn，其中的每个指针Hpi指向一个单链表，该单链表用来存储所有散列地址为i的数据元素。开散列表的处理冲突的方法：拉链表16给（13，41，15，44，6，68，12，25，38，64，19，49）序列，以H（k）=k%13为散列函数，构造一个开散列表。查找成功时：ASL（）查找失败时：ASL（）17闭散列表的存储组织方法：将所有的键值存入一个一维数组中，每个元素占用一个地址空间。18闭散列表上处理冲突的主要方法：线性探测法 二次探测法 多重散列法 公
29、共溢出区法法 19以（Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec）为关键字，散列函数为H（i）=，其中，i是每个单词的第一个字母在26个字母表中的位置，利用线性探测法构造闭散列表。查找成功：ASL（）查找失败：ASL（）第七章 文件1文件的逻辑结构：是由特性相同的记录所构成饿集合，其中每个记录由一个或多个数据项构成。2文件的两类主要的基本运算：检索：顺序存取直接存取按关键字存取修改：插入一个记录删除一个记录更新一个记录记录：每个数据元素就是一个记录（逻辑记录物理记录）3文件存储结构的含义：文件在存储介质上的实际组织形式文件存储结构种类：顺序文
30、件散列文件索引文件顺序文件：适应于磁带存储器，也适应磁盘存储器索引文件：只适应于磁盘存储器散列文件：只适应于外存储器散列文件的存储单位是桶 索引文件的两种存取方式： ：索引顺序存取方法 ：虚拟存取方法散列文件的优缺点： 优点：散列文件具有随机存放、记录不需要进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间 缺点：散列文件不能顺序存取，只能按关键字随机存取，在经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况，此时需要重新组织文件。第八章 排序1排序的定义：将一组任意排列的数据元素重新排列成一个按键值有序的序列的过程。2排序包括：内部排序（待排序的数据元素都在内存
31、中）插入排序、交换排序、选择排序和归并排序外部排序（待排序的数据元素有在外存中）3内部排序算法时间复杂度的度量方法： 通常用键值的比较和记录的移动作为标准操作：、 当键值是字符串时 采用键值比较 当记录很多时 采用记录移动4 插入排序的方法：（直接插入排序、折半插入排序、表插入排序和希尔排序）5直接插入排序的基本思想、基本步骤和算法：（1）基本思想：依次将每个记录插入到一个有序的子序列中去。（2）基本的步骤： 46，58，15，45，90，18，10，62 i=1 46 58，15，45，90，18，10，62i=2 46，58 15，45，90，18，10，62i=3 15，46，58 45
32、，90，18，10，62i=4 15，45，46，58 90，18，10，62i=5 15，45，46，58， 90 18，10，62i=6 15，18，45，46，58，90 10，62i=7 10，15，18，45，46，58，90 62i=8 10，15，18，45，46，58，90，62（3）类C算法描述：void straightsort()for(i=2;i=n; i+) r0.key=ri.key; j=i-1; while(r0.keyrj.key) rj+1.key=rj.key; j-; rj+1.key=r0.key; 6 冒泡排序：每趟是将待排序中最大排列在最大的位置上
33、7快速排序的基本思想，对给定的键值序列，能用图示法表示一趟快速排序中的交换过程以及每趟的结果1) 基本思想：在待排序的n个记录中任取一个记录，以该记录键值为标准，将所有记录分成两组，使得第一组中各个记录的键值都小于等于该键值，第二组中各个键值都大于该键值。2）对给定的键值序列，能用图示法表示一趟快速排序中的交换过程以及每趟的结果： 第一趟结果：11，18，69，23 70 93，73 第二趟结果：11 18，69，23 70 93，73 第三趟结果：11，18，23，69 70 93，73 第四趟结果：11，18，23，69 ，70 ，73 ，938直接选择排序的基本思想和具体做法（1） 基本
34、思想：首先在所有的记录中选出键值最小的记录，把它与第一个记录交换；然后在其余的记录中再选出键值最小的记录与第二个记录交换；依次类推，直到所有记录排好序。（2） 具体做法：9堆的定义，建堆的方法，堆的调整方法和“帅选”过程 (1) 堆的定义：堆是一键值序列k1,k2,，kn，对所有i=1，2，满足：kik2i，kik2i+1，即，堆可以看成是一棵以k1为根的完全二叉树，任一结点的值都不大于两个孩子，且任一子树也是堆。（2）建堆的方法： 72，73，71，23，94，16，05，68 （3）堆的调整方法和“帅选”过程： 依此类推10二路归并排序的思想：如果序列中有n个记录，可以把它看成n个子序列，
35、每个子序列中只包含一个记录（因而都是有序的），再把每相邻的两个子序列合并，得到n/2个较大的子序列，每个子序列包含2个记录，依次类推11 具体做法： 26，5，77，1，61，11，59，15，48，19 26，5，77，1，61，11，59，15，48，19 5， 26， 1，77， 11，61， 15，59，19，485， 26， 77， 1， 61，11， 59， 15，48，191，5， 26，77， 11，15，59，61，19，481，5，11，15，26，59，61，77，19，481，5，11，15，19，26，48，59，61，7712各种排序算法的平均时间和空间复杂度，最坏时间复杂度，稳定性排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O（n2）O（n2）O（1）稳定冒泡排序O（n2）O（n2）O（1）稳定快速排序O（nlog2n）O（n2）O（log2n）不稳定直接选择排序O（n2）O（n2）O（1）不稳定堆排序O（nlog2n）O（nlog2n）O（1）不稳定二路归并排序O（nlog2n）O（nlog2n）O（n）稳定专心-专注-专业