自考数据结构导论复习资料.docx

《自考数据结构导论复习资料.docx》由会员分享，可在线阅读，更多相关《自考数据结构导论复习资料.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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线性构造：是nn0个结点的有穷

5、序列。2线性构造的根本特征：假设至少含有一个结点，那么除起始结点没有干脆前趋外，其他结点有且仅有一个干脆前趋；除终端节点没有干脆后继外，其他结点有且仅有一个干脆后继。3线性表的逻辑构造是线性构造4线性表的六种根本运算的功能？ 答：初始化INITIATE(L)，功能是建立一个空表 求表长LENGTH(L)，功能是返回线性表L的长度 读表元GET(L，i)，功能是返回线性表L的第i个结点 定位按值查找LOCATE(L，X),功能是返回找到的结点集合中序号的最小值，否那么返回值为0说明没有找到 插入INSERTL，X，i，功能是在线性表L的地i个位置上增加一个值为X的新结点整个表长+1 删除DELE

6、TE(L，i)，功能是撤销线性表L的第i个位置结点整个表长-15依次表表示法的根本思想, 特点 答：根本思想是：依据依次存储方式，依次表的一个存储结点存储线性表的一个结点的内容，即数据元素，全部存储结点按相应数据元素建的逻辑关系确定的次序依次排列。 特点：逻辑构造中相邻的结点在存储构造中仍相邻。6区分依次表的容量及线性表的表长 答：依次表的容量是指定义依次表时的maxsize的值，而线性表的表长是指其中包含的结点个数。7依次表中ai的地址计算：ai的地址=b+i-1*l，b是首地址，l是每个结点占的空间7驾驭依次表上实现插入, 删除和定位运算的三个算法P18-208单链表表示法的根本思想用指针

7、表示结点间逻辑关系9单链表的结点形式：答：由数据域和指针域两局部组成；这两局部各自的作用分别是数据域是用于存储线性表的一个数据元素的，指针域是用于存放一个指针的，该指针指向本结点所含数据元素的干脆后继所在的结点。10头指针和头结点的作用？ 答：头指针是一个指向链表开场结点的指针，单链表由头指针唯一确定；头结点是我们人为地在链表的开场结点之前附加的一个结点，有了头结点之后，头指针指向头结点，不管链表是否为空，头指针总是非空的，而且头指针的设置使得对链表的第一位置上的操作和在其他位置上的操作一样。11单链表上实现插入, 删除和定位三种运算的三个算法：P26-2812插入算法中所包含的指针操作：s=

8、malloc(size);sdata=x;snext=pnext;pnext=s; 删除算法中所包含的指针操作：q=pnext;pnext=qnext;free(q);13Mallocsize的作用： 生成一个结点 形式一条指针14循环链表的组织方法：将单链表中的尾结点的NULL改成指向头结点的指针，就形成了循环链表。循环链表优点：可以从表中任一结点动身都可以向后扫描整表。15双链表的结点形式： 刻画双链表构造的对称性的语句：ppriornext= pnextprior;16依次表的主要优点和主要缺点： 优点：无需为表示结点间的逻辑关系而增加额外的存储空间 可以便利地随机存取表中的随意结点 缺

9、点：插入和删除运算不便利 支配内存空间接受静态支配方式17链表的主要优点： 插入和删除运算便利，只须要修改指针，不须要移动结点 支配内存空间接受动态支配方式18字符串：以字符为数据元素，以线性构造为逻辑构造的数据。19串的逻辑构造是线性构造和串的特点是由0个或多个字符组成的有穷序列20串的根本运算的功能：判等EQUAL(S,T)的功能是两个串的长度要相等，而且对应位置的字符都要一样。21串的依次存储方法紧缩格式和非紧缩格式和链接存储方法第三章 栈, 队列和数组1栈的根本运算及由此而确定的栈的根本特点栈是一种只允许在栈顶进展插入, 删除的特殊线性表；其根本特点是接受“后进先出操作；2栈的根本运算

10、：初始化InitStackS进栈PushS，X退栈PopS 读栈顶元素TOPS推断栈空EmptyS3依次栈 “上溢, “下溢的概念 “上溢：依次栈在进展进栈时，超过了依次栈的最大的容量 “下溢：依次栈在进展退栈时，栈中的元素少于0个元素4进栈和退栈运算在依次栈上的实现算法：P445依次栈上的简洁算法初始化，判栈空，取栈顶元素6链栈的结点形式及其描述： Data用来存放该结点的数据元素 Next用来存放指向下一个数据元素7链栈上实现进栈和退栈的算法P468链栈上的简洁算法初始化，判栈空，取栈顶元素9 队列的根本运算及由此确定的队列的特点 队列是一种只允许在对头进展插入在队尾进展删除的特殊线性表；

11、其根本特点是接受“先进先出操作；10依次队上的“假溢出及其解决方法：依次队在进展屡次入队, 出队后，依次队已经满了，但依次队中的大局部空间是空的； 解决方法：将依次队改成循环队11循环队队满, 队空的条件： 推断循环栈满的条件：sqrear+1%maxsize=sqfront 推断循环栈空的条件：sqrear= sqfront12链队的结点形式及其链队的组织方法：13在链队上实现入队, 出队的算法P56-5714数组的逻辑构造是线性构造的推广15二维数组的根本运算是读及写16二维数组：，其中a00是首地址，k是每个数据元素存储单元。17稀疏矩阵的三元组表示法：A=i,j,aijA=(1,2,3

12、),(1,6,1),(3,1,5),3，2，-1，4，5，4，5，1，-3)第四章 树1树的定义：是nn0个结点的有穷集合，满足： 有且仅有一个称为根的结点 其余结点分为mm0个互不相交的非空集合T1，T2 Tm，这些集合中的每一个都是一棵树，称为根的子树。2树形构造的有关术语及其含义根结点双亲结点和孩子结点兄弟结点和堂兄弟结点子孙结点和祖先结点树的层次, 树的高度和树的度3二叉树的逻辑构造, 特点和五种根本形态1：二叉树是nn0个结点的有穷集合，满足： 有且仅有一个称为根的结点 其余结点分为2个互不相交的集合T1，T2，T1是左子树，T2是右子树，且T1，T2也都是一棵二叉树。2特点：二叉树

13、是棵有序树 二叉树的度23五种根本形态 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层上，最多有 EMBED Equation.3 个结点 深度是K，最多总有 是针对一般二叉树 n0=n2+1 具有n个结点，深度 是针对完全二叉树 依据从上到下，从左到右的依次编号， 5二叉链表的结点形式及其描述，二叉链表中各

14、结点的联系方法及根指针的作用1二叉链表的结点形式data是存放该结点的数据元素，lchild是存放指向该结点的左孩子的指针，rchild是存放指向该结点的右孩子的指针。2根指针的作用，是用来指明根结点。6满二叉树和完全二叉树的概念1满二叉树是深度为K的二叉树的总共结点数为2完全二叉树是在满二叉树上少0个或者从最下层的最右边开场少起的二叉树7设计二叉树上基于三种遍历的简洁算法8判定树和哈夫曼树的概念1推断树是用来描述分类过程的二叉树2哈夫曼树是构造带权路径长度最小的二叉树9.哈夫曼树的特性:m个权值构造的哈夫曼树的结点总数为2m-1m个权值构造的哈夫曼树后权值都处在叶子结点上在哈夫曼树中，权值越

15、大离根越近在哈夫曼树中，没有度为1的结点10.将树转化成二叉树时，得到的二叉树的右子树恒久为空的二叉链表中，总共有2n个指针，其中，非空指针数为n-1，空指针数为n+112. 三叉链表的好处是便利每个结点找其双亲结点13.探讨树, 森林和二叉树的关系目的是想借助二叉树上的运算方法来实现对树的一些运算14.要将先序, 中序和后序遍历序列中的两种复原成唯一二叉树时，必需要有中序序列15. 附录：树这章可以出的应用题1.二叉树 二叉链表图 2. 二叉链表图 二叉树是上题中的逆操作3. 二叉树 依次存储构造图 操作规那么： 完全化 按从上到下，从左到右编号 依次存入对应的数组中的位子ABCDEFGH

16、1 2 3 4 5 6 7 8 9 10 11 12 134.依次存储构造图 二叉树是上题中的逆操作5. 二叉树 写出先序, 中序和后序遍历 先序DLR:ABDEGCF 中序LDR:DBGEACF 后序LRD:DGEBFCA6. 先序和中序或者先序和后序序列 二叉树1先序序列：ABCDEFGHIJ中序序列：CDBFEAIHGJ2后序序列：DECBHGFA中序序列：BDCEAGFH7.树 孩子链表表示法8.树 孩子兄弟链表表示法9.树 双亲表示法10.树 二叉树 11.森林 二叉树 12.二叉树 森林 13.哈夫曼树的构造给定权值给7，18，3，32，5，26，12，8，构造哈夫曼树并计算其带权

17、路径长度带权路径长度=298第五章 图1图状构造的定义并熟悉有关术语1图的定义：图由两个集合构成，记作G=(V，E)，其中V是顶点的有穷非空集合，E是边的集合，并且边是顶点集合的无序对或有序对集合。2图的术语：无向图：顶点点偶对是无序的 记作：vi，vj有向图：顶点点偶对是有序的 记作：无向完全图：任何两个顶点都有边关联的无向图n个顶点无向完全图总有边有向完全图：任何两个顶点都有弧关联的有向图n个顶点有向完全图总有边无向图顶点的度：及该顶点关联的边的数目；有向图顶点的度=入度+出度入度：以该顶点为终点的边数；出度：以该顶点为始点的边数；权：图中边上附带的值；路径：是从一个顶点到另一个顶点的序列

18、；简洁路径：序列中顶点不重复的路径；环/回路：第一个顶点和最终一个顶点一样的路径；简洁环/回路：除了第一个顶点和最终一个顶点一样外，其余顶点均不重复的回路；子图：设图G=V，E，假设，且中的边关联的顶点都在中，那么称，是的子图；连通图：在无向图中，任何两个顶点都存在到的路径强连通图：在有向图中连通重量：无向图的一个极大的连通子图强连通重量：有向图的一个极大的强连通子图微小连通子图：将子图中任何一条边删除后该子图都不再连通，那么给子图是极大连通子图：向子图中再参加其他任何一个顶点及其相关联的边后该子图都不连通，那么给子图是图的生成树：包含图中全部顶点的一个微小连通子图。注：n个顶点的图的生成树包

19、含有n-1条边；假设包含图的所以顶点的子图的边n-1，那么说明图中确定含有环；假设包含图的所以顶点的子图的边n-1，那么说明图确定是非连通的；2有向图, 无向图邻接矩阵表示法和邻接表表示法 无向图 邻接矩阵 邻接表 有向图 邻接矩阵 邻接表 逆邻接表注：1无向图的邻接矩阵是一个对称矩阵；2无向图的邻接矩阵中DVi=第i行或者第i列“1的个数/第i行或第i列元素之和；3无向图中有n个顶点, e条边那么其邻接表中有n个表头结点和2e个表结点；4无向图的邻接表中DVi=第i个单链表中表结点的个数；5有向图的邻接矩阵中DVi=IDVi+ODVi其中， IDVi=第i列中“1”的个数ODVi=第i行中“

20、1”的个数6有向图中有n个顶点, e条边那么其邻接表中有n个表头结点和e个表结点；7有向图的邻接表中DVi=IDVi+ODVi其中， ODVi=第i个单链表中表结点的个数； IDVi=逆邻接表中第i个单链表中表结点的个数； 或者=邻接表中值域=Vi的表结点的个数；3网的领接矩阵表示 带权有向图有向网 邻接矩阵4连通图的深度优先搜寻和广度优先搜寻的根本思想, 根本步骤，并给出相应搜寻的顶点序列 深度优先搜寻序列：V0，V1，V3，V7，V4，V2，V5，V6 广度优先搜寻序列：V0，V1，V2，V3，V4，V5，V6，V7 图的深度优先搜寻相当于树的先根遍历 图的广度优先搜寻相当于树的层次遍历

21、深度优先搜寻，用栈来暂存访问过的顶点 广度优先搜寻，用队列来暂存访问过的顶点1连通图的深度优先搜寻步骤：首先访问动身点Vi，然后任选一个及Vi的未被访问过的邻接点Vj ，再以Vj为新的动身点接着进展深度优先搜寻，直到图中全部顶点均被访问过。2连通图的广度优先搜寻步骤：首先访问动身点Vi，然后依次访问及Vi的未被访问过的邻接点Vj，Vk ，再以VjVk为新的动身点接着进展广度优先搜寻，直到图中全部顶点均被访问过。5非连通图的遍历方法以及图的连通重量的求法 连通重量 深度优先搜寻序列：V1，V2，V3，V5，V4，V6，V8，V7广度优先搜寻序列：V1，V2，V4，V3，V5，V6，V8，V76生

22、成树和最小生成树的概念1图的生成树：包含图中全部顶点的一个微小连通子图；2树的权：指树中全部边上权之和；3最小生成树：是指树的权最小的生成树；7Prim算法的根本思想，并能据此用图示法表示出求给定网的一棵最小生成树的过程1Prim算法的根本思想： 初始化：U=Vi，TE=； 找U中顶点关联的全部边中权值最小的边u，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,V

23、1,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) 拓扑排序：指找一个有向图的一个拓扑序列的过程。拓扑排序只能用在有向图中；拓扑排序得到的序列一般不唯一；拓扑排序不能用于含有环或者是回路的有向图中；检查有向图中是否含有环或者是回路的方法有：拓扑排序和按深度优先搜寻2给出一个有向图的拓扑序列找入度=0 拓扑序列：V1，V5，V2，V4，V3第六章 查找表1集合：由随意一些可辨别的对象构成的整体确定性：元素x是否属于集合

24、A确定是确定唯一性：同一集合的各个元素是互不一样的空集：集合中没有元素集合的逻辑构造的根本特点：任何两个元素之间都没有逻辑关系2查找表：由同一数据类型的元素构成的集合。 3查找表包括静态查找表只供应查找, 读表元动态查找表只供应查找, 读表元, 插入, 删除, 初始化4静态查找表的依次表的依次查找算法：从表的第n个位置开场，从后往前依次将各个位置上的数据元素的键值及给定值K比拟，假如相等，那么返回该键值的位置，否那么，查找不成功5查找长度：数据元素的键值及给定值K的比拟次数平均查找长度： ASL=Pi为查找第i个元素的概率；Ci找到第i个元素所比拟的次数等概率事务的平均查找长度：ASL=6有序

25、表：对于任何一个依次表，假设其中的全部结点按键值的某种次序排列。二分查找算法：R.itemmid.key=k，说明mid就是我们找到的位置 R.itemmid.keyk，说明我们找到的位置在low和mid之间，令mid=high-1 R.itemmid.keyk，说明我们找到的位置在mid和high之间，令mid=low+17二叉排序树的概念：要么是一棵空树，要么是一棵满足以下要求的二叉树： 假如左子树不为空，那么左子树上全部的结点都小于根结点； 假如右子树不为空，那么右子树上全部的结点都大于根结点； 左右子树都是一个二叉排序树；二叉排序树的性质：用中序遍历二叉排序树得到的序列是递增的序列；8

26、二叉排序树的查找算法的根本思想： 假设tkey=K，查找成功，返回t指针假设tkeyK，接着查找其左子树假设tkeyK，接着查找其右子树假设t=NULL，说明查找失败9二叉排序树插入运算的实现方法： 1原那么：必需保证插入后照旧是一棵二叉排序树 2方法：当查找K不成功而终止时，就是恰好找到了以K为键值的新结点在二叉排序树上的插入位置。以19，14，22，1，66，21，83，27，56，13，10构造一棵二叉排序树。10散列函数：将键值映射为散列表中存储位置的函数散列表：依据散列存储方式构造的存储构造11散列存储和散列查找的两个主要问题：1如何构造“匀整的散列函数2用什么方法解决冲突12同义词

27、：设有散列函数H和键值k1, k2，假设k1k2且k1=k2，那么称k1, k2是同义词。冲突：假设动态查找表中x1，x2，要求将x1，x2存入同一个散列表，而且它们键值是同义词，那么产生冲突。13散列函数的评价选择原那么：产生冲突越少，散列函数就越好。14各种常用的散列函数的构造方法：数字分析法 除余法 平方取中法 基数转换法 随机数法15开散列表的存储组织方式：设散列函数为H，H的值域为0，1，n -1，设置一个“地址向量Hpn，其中的每个指针Hpi指向一个单链表，该单链表用来存储全部散列地址为i的数据元素。开散列表的处理冲突的方法：拉链表16给13，41，15，44，6，68，12，25

28、，38，64，19，49序列，以Hk=k%13为散列函数，构造一个开散列表。查找成功时：ASL查找失败时：ASL17闭散列表的存储组织方法：将全部的键值存入一个一维数组中，每个元素占用一个地址空间。18闭散列表上处理冲突的主要方法：线性探测法 二次探测法 多重散列法 公共溢出区法法 19以Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec为关键字，散列函数为Hi=，其中，i是每个单词的第一个字母在26个字母表中的位置，利用线性探测法构造闭散列表。查找成功：ASL查找失败：ASL第七章 文件1文件的逻辑构造：是由特性一样的记录所构成饿集合，其中每个记录

29、由一个或多个数据项构成。2文件的两类主要的根本运算：检索：依次存取干脆存取按关键字存取修改：插入一个记录删除一个记录更新一个记录记录：每个数据元素就是一个记录逻辑记录物理记录3文件存储构造的含义：文件在存储介质上的实际组织形式文件存储构造种类：依次文件散列文件索引文件依次文件：适应于磁带存储器，也适应磁盘存储器索引文件：只适应于磁盘存储器散列文件：只适应于外存储器散列文件的存储单位是桶 索引文件的两种存取方式： ：索引依次存取方法 ：虚拟存取方法散列文件的优缺点： 优点：散列文件具有随机存放, 记录不须要进展排序, 插入删除便利, 存取速度快, 不须要索引区和节约存储空间 缺点：散列文件不能依

30、次存取，只能按关键字随机存取，在经过屡次插入, 删除后，可能出现溢出桶满而基桶内多数记录已被删除的状况，此时须要重新组织文件。第八章 排序1排序的定义：将一组随意排列的数据元素重新排列成一个按键值有序的序列的过程。2排序包括：内部排序待排序的数据元素都在内存中插入排序, 交换排序, 选择排序和归并排序外部排序待排序的数据元素有在外存中3内部排序算法时间困难度的度量方法： 通常用键值的比拟和记录的移动作为标准操作：, 当键值是字符串时 接受键值比拟 当记录很多时 接受记录移动4 插入排序的方法：干脆插入排序, 折半插入排序, 表插入排序和希尔排序5干脆插入排序的根本思想, 根本步骤和算法：1根本

31、思想：依次将每个记录插入到一个有序的子序列中去。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，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，623类C算法描述：void straightsort()

32、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 冒泡排序：每趟是将待排序中最大排列在最大的位置上7快速排序的根本思想，对给定的键值序列，能用图示法表示一趟快速排序中的交换过程以及每趟的结果1) 根本思想：在待排序的n个记录中任取一个记录，以该记录键值为标准，将全部记录分成两组，使得第一组中各个记录的键值都小于等于该键值，第二组中各个键值都大于该键值。2对给定的键值序列，能用图示法表示一趟快速排序中的交换过程以及每趟的结果： 第一趟结果：11，18

33、，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） 根本思想：首先在全部的记录中选出键值最小的记录，把它及第一个记录交换；然后在其余的记录中再选出键值最小的记录及第二个记录交换；依次类推，直到全部记录排好序。（2） 具体做法：9堆的定义，建堆的方法，堆的调整方法和“帅选过程 (1) 堆的定义：堆是一键值序列k1,k2,，kn，对全部i=1，2，满足：kik2i，kik2i+1，即，堆可以看成是一棵以k1为根的

34、完全二叉树，任一结点的值都不大于两个孩子，且任一子树也是堆。2建堆的方法： 72，73，71，23，94，16，05，68 3堆的调整方法和“帅选过程： EMBED Visio.Drawing.6 EMBED Visio.Drawing.6 依此类推10二路归并排序的思想：假如序列中有n个记录，可以把它看成n个子序列，每个子序列中只包含一个记录因而都是有序的，再把每相邻的两个子序列合并，得到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

35、， 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各种排序算法的平均时间和空间困难度，最坏时间困难度，稳定性排序算法平均时间困难度最坏时间困难度空间困难度稳定性干脆插入排序On2On2O1稳定冒泡排序On2On2O1稳定快速排序Onlog2nOn2Olog2n不稳定干脆选择排序On2On2O1不稳定堆排序Onlog2nOnlog2nO1不稳定二路归并排序Onlog2nOnlog2nOn稳定