《数据结构》 年  月期末考试指导一、考试说明 本课程为闭卷考试，满分  分，考试时间  分钟。考试题型如下：、选择题（每题  分，共  题）、填空题（每题 分，共  题）、主观题（ 分）二、复习重点内容第一章 绪论、数据数据是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。、数据元素和数据对象数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。、数据的逻辑结构和存储结构数据之间的相互关系称为逻辑结构。通常分为集合、线性结构、树型结构、图状结构或网状结构四类基本结构数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。、数据结构的二元组表示数据结构的形式定义为，数据结构是一个二元组：，其中： 是数据元素的有限集， 是  上关系的有限集。、算法的特性算法具有以下五个特性：（）有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（）确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（）可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（）输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（）输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。第二章 线性表、线性链表基本概念结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域 ：结点中用于保存数据元素的部分；结点的指针域 ：结点中用于保存数据元素直接后继存储地址的部分；空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针。头指针：用于存放线性链表中第一个结点的存储地址。假设  为链表的头指针，它指向表中第一个结点，若  为“空”（），则所表示的线性链表为“空”表，其长度  为“零”。 、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。E8求关键路径的方法8求最短路径的方法R8广度优先遍历算法J8深度优先遍历算法、排序的方法有很多种，（ ）法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。E8堆排序 8快速排序 R8插入排序 J8起泡排序、设要将序列（，O，R，S，A，E，T，，?，J，，U）中的关键码按升序排列，（ ）是二路归并排序一趟扫描的结果。E8（，O，R，J，A，E，T，，?，，S，U）8（A，E，R，，，J，，U，?，O，T，S）R8（O，，R，S，E，A，T，，J，?，，U）J8（O，R，，A，E，T，，?，J，，U，S）、有一个按元素值排好序的顺序表（长度大于 ），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是 $ 和 7，在查找不成功的情况下，$ 和 7 的关系是（ ）。E8$78$37R8$J8不一定参考答案：//B/B//B =/>/?/*//B（二）填空题/算法分析的两个主要方面是VVVVVVVVVVVVVV和VVVVVVVVVVVVVVV。/判定一个顺序栈 .最多元素为 '为栈满的条件是CCCCCCCCCC。、二维数组 EHIHI采用列序为主方式存储，每个元素占一个存储单元%并且 EHIHI的存储地址是 ，则 EHIHI的地址是VVVVVVVVVVVVVV。、已知二叉树的前序序列为 EJ+WROX，中序序列为 JW+EOXR，写出后序序列VVVVVVVVVVVVVVVVVVVV。参考答案：8空间性能，时间性能8F〉F/=/7DB@E,*（三）主观题、简述下列术语：数据、数据元素、数据对象、逻辑结构和存储结构。 答题要点：数据是信息的载体，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总和；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是数据的子集，是具有相同性质的数据成员（数据元素）的集合。数据的逻辑结构是对数据之间关系的描述，与数据的存储无关；数据的存储结构是逻辑结构在计算机存储器中的实现。 、试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。答题要点：Y#-6 Z$6#85ZY#-6 Z--85Z, 6 !$"6 =#6[$"6 /-#[>\J+[#G "\J+/5 6=##%$%G [\J+/[5 6[C5#- ]\L=F3-#[00#[$$0F36[>G $1#[" "G [>、如果矩阵 * 中存在这样的一个元素 *565+6满足条件：*565+6是第  行中值最小的元素，且又是第 + 列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出 'F的矩阵 * 的所有马鞍点。提示：依题意，先求出每行的最小值元素，放入 '5'6之中，再求出每列的最大值元素，放入 '%56之中，若某元素既在 '56中，又在 '%5+6中，则该元素 *565+6便是马鞍点，找出所有这样的元素$即找到了所有马鞍点。答题要点：Y#-6 2$6#853Y6 4 Y6 4 G#6#^#HIHI=##%.%5G [##HI%^HI[!"#[#2[#001/计算出每行的最小值元素%放入 #HI之中/1=#H#IH#IHI[!".[.2[.00#!H#IH.I2#H#I#H#IH#IH.I[> !".[.2[.001/计算出每列的最大值元素%放入 ^HI之中/1=^H.IHIH.I[!"#[#2[#00#!H#IH.I3^H.I^H.IH#IH.I[>!"#[#2[#00!".[.2[.00#!#H#I^H.I="#!Z_6%_6<_6`Z%#%.%H#IH.I[5G [>#!]5G "#!Z没有鞍点＼Z[>、如图所示的 *D 网，求：（）每项活动  的最早开始时间 （）和最迟开始时间 （）。（）完成此工程最少需要多少天（设边上权值为天数）。（）哪些是关键活动。（）是否存某项活动，当其提高速度后能使整个工程缩短工期。答题要点：（）求所有事件的最迟发生时间如下：3 33= 3'%:3$3=<3'%:3$3< 3=3=3>3= 3?33'%:3>$3?< 3'%:3=$3<求所有事件的最迟发生时间如下：3 333?3 3>3=3=3 3':3>$3?<3':3=$3< 3':3=$3<=33 3':3$3=<求所有活动的 $和 #如下： 活动 8：3 3 #活动 8：3 3= #活动 8：3 3? #活动 8：3= 3== #活动 8：3= 3 #=活动 =8：=3 =3 #=活动 >8：>3 >3= #>活动 ?8：?3 ?3> #?活动 8：3 3? #活动 8：3== 3= #活动 8：3> 3 #活动 8：3?= 3 #活动 8：3? 3 #（）完成此工程最少需要  天。（）从以上计算得出，关键活动为 ，，=，?，， 和 。这些活动构成了两条关键路径即 ，，=，?，， 和 ，，=，，，。（）存在 ，，=， 活动，当其提高速度后能使整个工程缩短工期。说明：本考试指导只适用于 ? 学期 = 月期末考试使用，包括正考和重修内容。指导中的章节知识点涵盖考试所有内容，给出的习题为考试类型题，习题答案要点只作为参考，详见课程讲义或笔记。如果在复习中有疑难问题请到课程答疑区提问。最后祝大家考试顺利！ 头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点。、线性表的顺序存储结构把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用  个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第  个数据元素的存储位置 和第  个数据元素的存储位置 之间满足下列关系：线性表的第  个数据元素  的存储位置为：由于  语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。、线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针 !或链"。这两部分组成了链表中的结点结构：（#$%）其中：# 域是数据域，用来存放结点的值。% 是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的  个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（&"#。第三章 栈和队列、栈的定义及基本运算栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。假设栈 ，，，…，则  称为栈底元素， 为栈顶元素。栈中元素按，，，… 的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，只能在栈顶插入和删除元素。因此，栈称为后进先出表（）。、队列的定义及基本运算队列  也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头!"，允许插入的一端称为队尾" "。先进入队列的成员总是先离开队列。因此队列亦称作先进先出#"$#"$的线性表，简称  表。当队列中没有元素时称为空队列。在空队列中依次加入元素%%& 之后， 是队头元素， 是队尾元素。显然退出队列的次序也只能是%%&，也就是说队列的修改是依先进先出的原则进行的。第四章 串、串定义串"#'是零个或多个字符组成的有限序列。一般记作 (&)，其中 是串名，双引号括起来的字符序列是串值；#*#*可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串+,"#'，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串-"#'。 要注意空串和空白串的不同，例如“ ”和“”分别表示长度为  的空白串和长度为  的空串。 第五章 数组和广义表、 数组的顺序存储方式数组通常有两种顺序存储方式：⑴ 行优先顺序将数组元素按行排列，第  个行向量紧接在第  个行向量后面。以 二 维 的 ' 数 组 为 例 ， 按行 优 先 顺 序 存 储 的 线 性 序 列 为 ： $$$$($$$$$$$($$(($'$$'$$($'$在 )**、 语言中，数组就是按行优先顺序存储的。⑵ 列优先顺序将数组元素按列向量排列，第 + 个列向量紧接在第 + 个列向量之后，* 的 ' 个元素按列优先顺序存储的线性序列为：$$$$($'$$$$$$('$$(($$$$$($'$在 ,-.-* 语言中，数组就是按列优先顺序存储的。、 对称矩阵在一个  阶方阵 * 中，若元素满足下述性质：++ $+ ≦ ≦则称 * 为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。/若  +≧ ，则 + 在下三角形中。+ 之前的  行（从第  行到第  行）一共有 (0 个元素，在第  行上，+ 之前恰有 + 个元素（即 $$$($+），因此有："0+ "10≦/若 1+，则 + 是在上三角矩阵中。因为 ++，所以只要交换上述对应关系式中的  和 + 即可得到：./.010#*201第六章 树和二叉树、二叉树的定义二叉树是由 3个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。、树的存储结构/双亲表示法在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。/孩子表示法采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置。/孩子兄弟表示法所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域 4"$5#-6 和 "#'5$#7-#'，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，因此该方法也常被称为二叉树表示法。、遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。二叉树的遍历顺序包括：先序遍历、中序遍历和后序遍历。 8先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则9访问根结点；:先序遍历左子树；;先序遍历右子树。8中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则9中序遍历左子树；:访问根结点；;中序遍历右子树。8后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则9后序遍历左子树；:后序遍历右子树；;访问根结点。、线索二叉树当以二叉链表作为存储结构时%只能找到结点的左右孩子的信息%而不能在结点的任一序列的前驱与后继信息%这种信息只有在遍历的动态过程中才能得到%为了能保存所需的信息%可增加标志域：-5#-6 -' 6 "' "5#-6其中<以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。、树与二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法：、森林和二叉树的转换将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方树根结点 2 的第一个孩子结点 2 紧邻的右兄弟二叉树根结点 2 的左孩子结点 2 的右孩子&-5#-6 域指示结点的左孩子-5#-6 域指示结点的前驱&"5#-6 域指示结点的右孩子"5#-6 域指示结点的后继 法，进行森林与二叉树转换。从树的二叉链表示的定义可知%任何一棵和树对应的二叉树%其右子树必为空。所以只要将森林中所有树的根结点视为兄弟，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标树的根，就可以将森林转换为二叉树。转换规则：若 =，，，…，>是森林，则 （）="%%?>8若 为空，即 ，则 为空树。8若 非空，则 （）的根是  的根，其左子树为 ，是从  根结点的子树森林=，，…，>转换而成的二叉树；其右子树为 ?，是从除  外的森林@=，，…，>转换而成的二叉树。、哈夫曼树的概念路径：从一个结点到另一个结点之间的若干个分支路径长度：路径上的分支数目称为路径长度；结点的路径长度：从根到该结点的路径长度树的路径长度：树中所有叶子结点的路径长度之和；一般记为 A。在结点数相同的条件下，完全二叉树是路径最短的二叉树。结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度树中所有叶子结点的带权路径之和；通常记作 BAåC#D#哈夫曼树：假设有  个权值C%C%&%C，构造有  个叶子结点的严格二叉树，每个叶子结点有一个 C#作为它的权值。则带权路径长度最小的严格二叉树称为哈夫曼树。第七章 图、图的深度优先搜索遍历首先访问顶点 ，并将其访问标记置为访问过，即 34#56；然后搜索与顶点  有边相连的下一个顶点 +，若 + 未被访问过，则访问它，并将 + 的访问标记置为访问过，34#5+6，然后从 + 开始重复此过程，若 + 已访问，再看与  有边相连的其它顶点；若与  有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。、图的广度优先搜索遍历广度优先搜索遍历类似于树的按层次遍历。设图 7 的初态是所有顶点均未访问，在 7中任选一顶点  作为初始点，则广度优先搜索的基本思想是：8首先访问顶点 ，并将其访问标志置为已被访问，即 34#56；88接着依次访问与顶点  有边相连的所有顶点 9，9，…，9；8然后再按顺序访问与 9，9，…，9 有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止 。、E+F网和关键路径若在带权的有向图中%以顶点表示事件%有向边表示活动%边上的权值表示完成该活动的开销如该活动所需的时间%则称此带权的有向图为用边表示活动的网络%简称 E+ 网。E+ 网中%从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于 E+网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程 E+ 网的关键路径长度。 确定 E+ 网中关键路径的步骤：8计算事件的最早发生时间 G （）8计算事件的最迟发生时间 G-（）8计算活动 # 的最早开始时间 H#I若活动 # 有边2G.%G3表示%则活动 # 的最早开始时间 H#I可由下式计算< H#IG H.I8计算活动 # 的最迟开始时间 -H#I若活动 # 有边2G.%G3表示%则活动 # 的最迟开始时间 -H#I可由下式计算<-H#IG-HIF2G.%G38计算活动 # 的时间余量 6H#I确定关键路径令 6H#I-H#IF H#I，对于活动 #，若有 6H#I，则说明活动 # 为关键活动，由关键活动组成的路径就是关键路径。、寻找最短路径的迪杰斯特拉（J#.$"）算法（）8J#.$" 算法的基本思想按路径长度递增顺序求最短路径算法，与求最小生成树的普里姆算法类似。（8J#.$"算法的基本步骤设 K 是起始源点，L已求得最短路径终点集合。KFL未确定最短路径的顶点的集合初始时 L=K>）长度最短的最短路径是边数为  的长度最小的路径。）下一条长度最短的路径：9K#MKFL，先求出 K到 K#中间只经 L中结点的最短路径；:上述最短路径中长度最小者即为下一条长度最短的路径；;将所求最短路径的终点加入 L中；）重复 ）直到求出所有的最短路径第八章 动态存储管理、动态存储管理的定义计算机内存在刚开始工作时，空闲部分是一个整块的连续区域；随着用户进入系统，多次申请和释放内存以后，空闲部分不再是连续的了，而成了多个空闲区。动态存储管理指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。、可利用空间表及分配方法可利用空间表是将所有内存空闲块用链表连接而成，空闲块的大小可以是全相同的，也可以是分成若干固定大小的，还可以是随机大小的。可利用空间表的分配算法包括：33"'%:3+13+$3"; 上的权 <13+$3"; 为所有到达 3" 的有向边333"':3+13"$3+; 上的权 <13"$3+; 为所有从 3" 出发的有向边= /首次拟合法/最佳拟合法/最坏拟合法第九章 查找、顺序查找顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度（EG "'  "5 '5%E）。、二分查找二分查找的基本思想是：首先将待查值 N 与有序表 "",HI到 "",HFI的中点#6 上 的 关 键 字 "",H#6I8 , 进 行 比 较 ， 若 相 等 ， 则 查 找 成 功 ； 否 则 ， 若"",H#6I8 ,3   ， 则 在 "",HI 到 "",H#6FI 中 继 续 查 找 ， 若 有"",H#6I8 ,2， 则在 "",H#60I到 "",HFI中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为 N 的元素；若当前的查找区间为空表示查找失败。 查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。 个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。比较的关键字个数：为该结点在判定树上的层次数。因此，二分查找的时间复杂度为-'。、散列表和散列函数散列表也称哈希表。散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。具体说，就是选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值  计算地址，将  与地址单元中元素关键码进行比较，确定查找是否成功。散列法中使用的转换函数称为散列函数。常用的散列函数的构造方法包括：直接定址法、除留余数法、折叠法等。、处理冲突的方法通常关键码的集合比存储地址集合大得多，因而经过散列函数变换后，可能将不同的关键码映射到同一个存储地址上，这种现象称为冲突。解决冲突的常用方法是开放定址法，其思路是有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。在具体实现上，常采用线性探测法，即一旦冲突，就找附近（下一个）空地址存入。用表达式表示就是：O#O$5 ,06#6P#2其中：O$5 ,为哈希函数 为哈希表长度6#为增量序列 ，，…F，且 6##第十章 内部排序、直接插入排序> 直接插入排序（"#'5$ "#"#'）的基本思想是：把  个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 F个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。直接插入排序在空间复杂度上，只需要一个元素的辅助空间，用于元素的位置交换。时间复杂度为 （）、起泡排序起泡排序排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部（从下标较小的单元移向下标较大的单元），就象水底下的气泡一样逐渐向上冒。起泡排序算法的时间复杂度为 （）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。、快速排序快速排序（#"#'）的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。 快速排序的平均时间复杂度为 （-'）。最好的空间复杂度为 （-'），最坏的空间复杂度为 。、简单选择排序简单选择排序的基本思想是：第一次从 "",HIQ"",HFI中选取最小值，与"",HI交换，第二次从 "",HIQ"",HFI中选取最小值，与 "",HI交换，第三次从 "",HIQ"",HFI 中 选 取 最 小 值 ， 与 "",HI 交 换 ， … ， 第 # 次 从 "",H#FIQ"",HFI中选取最小值，与 "",H#FI交换，…%第 F 次从 "",HFIQ"",HFI中选取最小值，与 "",HFI交换，总共通过 F 次，得到一个按排序码从小到大排列的有序序列。简单选择排序的时间复杂度为 数量级，当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些。、二路归并排序二路归并排序的基本思想是：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从 增加到 （元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果。二路归并排序的时间复杂度为 -'，空间复杂度为 。、各种内排序方法的选择规则（）当待排序元素的个数  较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。（当待排序元素的个数  大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。（）当待排序元素的个数  大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。（当待排序元素的个数  小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。当待排序元素的个数  小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码? 不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。 第十一章 外部排序、外部排序的过程（）按可用内存大小，将外存上含  个记录的文件分成若干长度为 - 的子文件或段（$ ' ），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件（通常称这些有序子文件为归并段或顺串（"））重新写入外存。（）对归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。第十二章 文件、 直接存取文件直接存取文件指的是利用杂凑（@4A）法进行组织的文件。它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。、直接存取文件的特点优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的 插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。三、重点习题（一）选择题、在数据结构中，从逻辑上可以把数据结构分成（ ）。E8动态结构和静态结构8紧凑结构和非紧凑结构R8线性结构和非线性结构J8内部结构和外部结构、一个顺序存储的线性表第一个元素的存储地址是 ，每个元素的长度为 ，则第 个元素的地址是（ ）。E88R8J8、设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。E8顺序表 8栈 R8队列 J8链表、数组 EHIHI中%每个元素 E 的长度为  个字节%从首地址 E 开始连续存放在存储器内%该数组按行存放时%元素 EHIHI的起始地址为（ ）。E8E08E0R8E0J8E0、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。E8空或只有一个结点 8高度等于其结点数 R8任一结点无左孩子 J8任一结点无右孩子、对于一个具有  个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。E88FR8FJ8