koorio.com
海量文库 文档专家
当前位置:首页 >> >>

数据结构习题参考答案

第1章 概 论
1.数据、数据元素、数据结构、数据类型的含义分别是什么? 数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并由计算机
程序处理的符号的总称。 数据元素:数据的基本单位,在计算机程序中通常作为一个整体考虑。 数据结构:数据元素之间的关系+运算,是以数据为成员的结构,是带结构的数据元素
的集合,数据元素之间存在着一种或多种特定的关系。 数据类型:数据类型是用来区分不同的数据;由于数据在存储时所需要的容量各不相同,
不同的数据就必须要分配不同大小的内存空间来存储,所有就要将数据划分成不同的数据类 型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构?什么是数据的物理结构?数据的逻辑结构与物理结构的区别和 联系是什么?
逻辑结构:数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻 辑结构包含下面两个方面的信息:
① 数据元素的信息; ② 各数据元素之间的关系。 物理结构:也叫储存结构,是指逻辑结构的存储表示,即数据的逻辑结构在计算机存 储空间中的存放形式,包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的,一个操作算法的设计取决于所选定的逻辑结 构,而算法的实现依赖于所采与的存储结构。采用不同的存储结构,其数据处理的效率是不 同的。因此,在进行数据处理时,针对不同问题,选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些? 对于各种数据结构而言,他们在基本操作上是相似的,最常用的操作有: ? 创建:建立一个数据结构; ? 清除:清除一个数据结构; ? 插入:在数据结构中增加新的结点; ? 删除:把指定的结点从数据结构中删除; ? 访问:对数据结构中的结点进行访问; ? 更新:改变指定结点的值或改变指定的某些结点之间的关系; ? 查找:在数据结构中查找满足一定条件的结点; ? 排序:对数据结构中各个结点按指定数据项的值,以升序或降序重新排列。 4.什么是抽象数据类型?如何定义抽象数据类型? 抽象数据类型(Abstract Data Type 简称 ADT)是指一个数学模型以及定义在此数学 模型上的一组操作。ADT 是与具体的物理存储无关的数据类型,因此,不论 ADT 的内部结 构如何变化,只要其数据结构的特性不变,都不影响其外部使用。 对抽象数据类型的描述一般用(D,R,P)三元组表示,抽象数据类型的定义格式为: ADT<抽象数据类型名> { 数据对象 D:<数据对象的定义> 数据关系 R:<数据关系的定义> 基本操作 P:<基本操作的定义>

}ADT<抽象数据类型名> 其中,D 是数据对象,R 是 D 上的关系集,P 是对 D 的基本操作集。 数据对象和数据关系的定义用伪代码来描述。基本操作的定义格式为: 基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述> 初始条件说明操作执行之前数据结构和参数应满足的条件;操作结果说明操作完成后, 数据结构的变化状况和应返回的结果。 5.什么是算法?算法的基本特征是什么? 算法:是在有限的步骤内解决数学问题的过程,是以一步接一步的方式来详细描述计算 机如何将输入转化为所要求的输出的过程,即算法是对计算机上执行的计算过程的具体描 述。一个有效的算法必须满足的五个重要特性: ① 有穷性:算法必须能在有限的时间内做完,即在任何情况下,算法必须能在执行有 限个步骤之后终止,都不能陷入无穷循环中。 ② 确定性:算法中的每一个步骤,必须经过明确的定义,并且能够被计算机所理解和 执行,而不能是抽象和模糊的概念,更不允许有二义性。 ③ 输入:算法有 0 个或多个输入值,来描述算法开始前运算对象的初始情况,这是算 法执行的起点或是依据。0 个输入是指算法本身给出了运算对象的初始条件。 ④ 输出:算法至少有 1 个或多个输出值,反映对运算对象的处理结果,没有输出的算 法没有任何意义。 ⑤ 可行性:算法中要做的运算都是基本运算,能够被精确地进行。即算法中执行的任 何计算都可以被分解为基本的运算步,每个基本的运算步都可以在有限的时间内完成。 6.什么是算法分析?算法分析主要考虑哪几方面的内容? 算法的研究与实际问题直接相关,用来解一个问题可以有很多不同的算法,他们之间的 效果可能会有很大差异。算法设计者最关心的就是什么是有效的算法,如何评价一个算法的 优劣,如何从多种算法中选择好的算法。除了要首先考虑算法的正确性外,还要分析和评价 算法的性能。分析和评价算法的性能主要要考虑以下两个方面: ①时间代价:执行算法所耗费的时间。一个好的算法首先应该比其他算法的运行时间代 价要小。算法的时间代价的大小用算法的时间复杂度来度量。 ②空间代价:执行算法所耗费的存储空间,主要是辅助空间。算法运行所需的空间消耗 是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。 7.分析下面算法的时间复杂度。 (1)答:时间复杂度为 n2 (2)时间复杂度:n
(3)时间复杂度: n
(4)时间复杂度:n2 (5)时间复杂度:O(log2n) 8.算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么? 递推法:是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分 成若干步,找出相邻几步的关系,从而达到求解问题的目的。具有如下性质的问题可以采用 递推法:当得到问题规模为 i-1 的解后,由问题的递推性质,能构造出问题规模为 i 的解。 因此,程序可以从 i=0 或 i=1 出发,由已知 i-1 规模的解,通过递推,获得问题规模为 i 的 解,直至得到问题规模为 n 的解。

递归法:递归策略是利用函数直接或间接地调用自身来完成某个计算过程。能采用递归 描述的算法通常有这样的特征:为求解规模为 n 的问题,设法将它分解成规模较小的问题, 然后从这些小问题的解方便地构造出更大问题的解,并且这些规模较小的问题也能采用同样 的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出较大规模问题的 解。
穷举法:穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行 逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。
迭代法:数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解 方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法。 9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思 想是什么?
分治策略的基本思想是把一个规模为 n 的问题划分为若干个规模较小、且与原问题相似 的子问题,然后分别求解这些子问题,最后把各子结果合并得到整个问题的解。分解的子问 题通常与原问题相似,所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题,决策一旦做 出,就不能再更改。它是通过若干次的贪心选择而得出最优解(或较优解)的一种解题策略。
动态规划策略与贪心策略类似,将一个问题划分为重复的子问题,通过对相同子问题的 求解来解决较大问题,即将一个问题的解决方案视为一系列决策的结果。不同的是,在贪心 策略中,每采用一次贪心准则便做出一个不可撤回的决策,可能得不到问题的最优解。而在 动态规划中,处理要按照某种规则进行选择,还要考察每个最优决策序列中是否包含一个最 优子序列,目的是得到问题的最优解。
回溯策略也叫试探法,它的基本思想是:在一些问题求解进程中,先选择某一种可能情 况向前探索,当发现所选用的试探性操作不是最佳选择,需退回一步,重新选择继续进行试 探,直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略,它的基本思想是:首先确定目标值的上下界, 然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支,提高搜索效率。

第二章 线性表

1.具有什么特征的数据结构被称为线性表?
线性表是一种最常用、最简单的典型线性数据结构,应用非常广泛。线性表是由 n(n ? 0)
个数据元素组成的一个有限序列,线性表中数据元素的个数 n 称为线性表的长度。当 n=0 时,称为空表。
对于非空线性表,数据元素之间存在一对一的关系,具体特性如下: 第一个数据元素没有前驱; 最后一个数据元素没有后继外; 其他数据元素都是首尾相接、有且只有一个前驱和后继。 2.如何实现线性表的顺序存储结构? 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的 顺序存储,采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特点: ? 线性表中所有元素所占的存储空间是连续的; ? 线性表的逻辑顺序与物理顺序一致; ? 数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的
存储地址(指第一个字节的地址,即首地址)为 LOC(e1),每一个数据元素占 k 个 字节,则线性表中第 i 个元素 ei 在计算机存储空间中的存储地址为:
LOC(ei)=LOC(e1)+(i-1)k 3.如何实现线性表的 4 种链式存储结构?
数据结构中的每一个数据元素对应于一个存储单元,这种存储单元称为存储结点,简称 结点。每个结点分为两部分:一部分用于存放数据元素的值,称为数据域;另一部分是指针, 用于指向与该结点在逻辑上相连的其他结点,称为指针域。对于线性表,指针域用于指向该 结点的前一个或后一个结点(即前驱结点或后继结点)。通过结点的指针域将 n 个结点按其 逻辑结构连接在一起的数据存储结构,称为链式存储结构。
单向链表:在线性链表中,用一个专门的指针指向线性表中第一个结点,每一个结点的 指针都指向它的下一个逻辑结点,线性链表的最后一个结点的指针为空(用 NULL 或 0 表 示),表示链表终止,这样的线性链表称为单向链表。下图是单向链表示意图。

first

e1

e2



ei



en

… 线性表的单向链式存储



NULLNULL

NULL

循环链表:将单向链表最后一个结点的指针指向头结点,这样整个链表就构成一个循环,

这种链式存储结构称为单向循环链表,简称循环链表。头结点的指针域指向线性表的第一个

元素的结点;循环链表中最后一个结点的指针域不再是 NULL,而是指向头结点。只有头结

点的循环链表称为空循环链表。下图是带头结点的非空循环链表和空循环链表示意图。

head
e1
头结点



en



head 头结点

(a)带头结点的非空循环链表 表
带头结点的循环链表

(b)带头结点的空循环链

双向链表:双向链表的每个结点含有两个指针域,一个指针指向其前驱结点;另一个指 针指向其后继结点。双向链表结点的结构下图(a)所示。
双向循环链表:如果将双向链表第一个结点的 prev 指针指向最后一个结点,将最后一 个结点的 next 指针与指向第一个结点,就构成了双向循环链表。下图(b)和(c)是双向 链表和双向循环表的逻辑结构示意图。

first

end

prev data next (a)双向链表结点结构

e1 first
e1

e2



en

(b)双向链表

e2



en

(c)双向循环链表 图 双向链表结点结构及双向链表
4.顺序表和线性链表分别有哪些优点和缺点?
线性表的顺序存储与链式存储比较

比较内容

顺序存储

链式存储

结点存储空间 空间利用率 插入、删除操作 访问元素

少(不需要为表示结点的逻辑关系增 加开销) 低(采用数组,按表的最大长度静态 分配存储空间) 慢(需要大量移动元素)
快(直接访问)

多(需要增加指针域来表示结点之间 的逻辑关系) 高(根据表的实际长度动态分配存储 空间) 快(仅更改指针指向,不需要移动元 素) 慢(通过指针移动才能访问)

实现难易程度 相对容易(基于数组操作,一般高级 相对困难(基于指针操作) 语言都提供数组类型)
5.请列举出一些线性表问题的实例。 ①按员工号排序的员工基本情况表; ②奥运会各项比赛日程; ③按学号记录的学生的成绩单; 等等。
6. 对于顺序表和单向链表,如何实现统计重复元素个数的操作?

在顺序表中实现统计重复元素个数的操作: 在教材的【描述 2-1】中,增加一个统计重复元素个数的成员函数:
int Count(const T&x); //返回 x 出现的次数 在教材的【描述 2-2】中,增加查找重复元素个数的成员函数的实现: //实现统计重复元素个数 template<class T> int LinearList<T>::Count(const T& x) {
int count=0; for (int i=0; i<length; i++)
if(element[i]==x) count++;
return count; } 在顺序表中实现统计重复元素个数的操作: 在教材的【描述 2-3】中,增加一个统计重复元素个数的成员函数:
int Count(const T&x); //返回 x 出现的次数 在教材的【描述 2-4】中,增加查找重复元素个数的成员函数的实现: //实现统计重复元素个数 template<class T> int LinkList<T>::Count(const T& x) {
LinkNode<T> * p=head->next; int count=0; while (p!=NULL && ) {
if (p->data ==x) count++;
p=p->next; } return count; }

第 3 章 栈和队列
1.具有什么特征的数据结构被称为栈和队列?先进后出、栈顶、栈底、先进先出、队头、 队尾的概念是什么?
栈:一种插入和删除都只能在表的同一端进行的线性表。 队列:一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。 先进后出:元素是以 e1,e2,……en 顺序进入数据结构,以相反的顺序即 en,en-1,……
e1 离开数据结构。 栈顶:允许进行插入和删除操作的一端。 栈底:栈中与栈顶相对的另一端。 先进先出:元素是以 e1,e2,……en 顺序进入数据结构,以相同的顺序即 e1,e2,……
en。 离开数据结构。 队头:允许删除操作的一端。 队尾:允许插入操作的一端。 2.简述在顺序栈的栈顶插入一个元素的操作过程。 在插入元素之前,首先要判断栈是否为满,如果栈满,返回“沾满无法插入”等错误提 示信息;否则让 top 指针(指向当前顺序栈的栈顶)向后移动一个元素空间(元素大小), 将要插入的元素放入 top 指针指向的内存单元中。 3. 一个栈的输入序列为 1、2、3,试给出全部可能的出栈序列。 可分为三种情况: ①、当只有一个存储空间时,只有一种出栈序列:1、2、3. ②、当有两个存储空间时,有:1、2、3, 2、1、3, 2、3、1 等 3 种出栈序列 ③、当存储空间大于等于三个时,有:1、2、3, 2、1、3, 2、3、1, 3、2、1
等 4 种出栈序列。 4.循环队列的优点是什么?在循环队列中,仅依据头尾指针相等,无法判断队列是“空”还 是“满”。要解决这个问题,常用的两种方法是什么?
循环队列的优点有两点:一是可以避免发生顺序队列的“假上溢”现象;二是充分利用 队列的存储空间。
两种判断队列是“空”还是“满”的方法:一是约定少用一个元素空间;二是使用计数 器 size 记录当前队列的实际长度。 5. 简述在链接栈中插入一个元素的操作过程。
链接栈的插入操作,先将待进栈结点的指针域指向原来的栈顶结点,然后将栈顶指针 top 修改指向该结点,使进栈元素结点成为新的栈顶结点。 6.请列举出一些可以用栈和队列表示的实际问题。
所有“后进先出”(LIFO,Last In First Out)的实际问题都可以用栈表示。栈的应用主要 有:数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数 的嵌套调用和递归的实现等。
所有“先进先出”(FIFO,First In First Out)的实际问题都可以用队列表示。如日常中的 排队问题,队列的应用主要有:操作系统中各种资源请求排队和各种缓冲区的先进先出管理, 各种应用系统中的事件规划和事件模拟,树的层次遍历和图的广度优先遍历等。

第 4 章 数组、字符串与广义表
1.具有什么特征的数据结构被称为数组? 数组可以看成是形如(index,value)的数据集合,其中,index 是元素的索引,表示数
据的逻辑位置,任意两个数据的 index 都不相同;value 表示数据元素的值。 2.设有二维数组 a[5][6],每个元素占相邻的 8 个字节,存储器按字节编址,已知 a 的起始地 址是 1000,试计算: (1)数组 a 的最后一个元素起始地址;
1000+(30-1)*8=1232。 (2)按行序优先时,元素 a[3][5]的起始地址;
1000+(3*6+5)*8=1184 (3)按行列序优先时,元素 a[4][3]的起始地址。
1000+(3*5+4)*8=1152 3.请简述数组和矩阵的关系。
矩阵是指纵横排列的二维数据表格。在高级语言编程中,通常用二维数组来描述一个矩 阵,从而可以对矩阵中的元素进行随机存取。但矩阵的索引通常从 1 而不是像数组那样从 0 开始,并且使用 A(i,j)而不是 A[i,j]的形式来引用矩阵中的元素。 4.矩阵有哪些基本运算?
矩阵的操作包括转置、加法、减法和乘法等。 5.稀疏矩阵的特点是什么?为什么要对稀疏矩阵采用压缩存储技术?
稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。 采用压缩存储技术主要是为了节省空间。 6.设 A 和 B 是稀疏矩阵,都以三元组作为存储结构,请写出矩阵相加的算法 C=A+B。 //稀疏矩阵的三元组表示 #include <iostream> using namespace std; #define M 50 #define N 50 #define MaxSize 20 typedef int ElemType; typedef struct { int r; int c; ElemType d; } TupNode; typedef struct { int rows; int cols; int nums; TupNode data[MaxSize]; } TSMatrix;

int A[M][N],B[M][N]; //建立三元组 void CreateMat(int A[M][N],TSMatrix &t,int row,int col) {
int i,j; t.rows=row;t.cols=col;t.nums=0; for(i=0;i<M;i++) {
for(j=0;j<N;j++) {
if(A[i][j]!=0) {
t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } } //矩阵相加 int MatAdd(TSMatrix &a,TSMatrix &b,TSMatrix &c) { int i=0,j=0,k=0; ElemType v; if(a.rows!=b.rows||a.cols!=b.cols) return 0; c.rows=a.rows;c.cols=a.cols; while(i<a.nums && j<b.nums) { if(a.data[i].r==b.data[j].r) { if(a.data[i].c<b.data[j].c) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } else if(a.data[i].c>b.data[j].c) { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } else

{ v=a.data[i].d+b.data[j].d; if(v!=0) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=v; k++; } i++;j++;
} } else if(a.data[i].r<b.data[j].r) {
c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } else { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } } if (i==a.nums) while (j<b.nums) { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; j++;k++; } if (j==b.nums) while (i<a.nums) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; i++;k++; } c.nums=k;

return 1; } //输出三元组 void DispMat(TSMatrix t) {
int i; if(t.nums<=0) {
cout<<"此矩阵所有元素都为"<<endl; return; } cout<<t.rows<<'\t'<<t.cols<<'\t'<<t.nums<<endl; cout<<"-----------------"<<endl; for(i=0;i<t.nums;i++) cout<<t.data[i].r<<'\t'<<t.data[i].c<<'\t'<<t.data[i].d<<endl<<endl; } //主函数 int main() { int row,col,i,j; TSMatrix a,b,c; cout<<"请输入矩阵的行、列数:\n"; cin>>row>>col; cout<<"请输入矩阵 A 的元素:\n"; for(i=0;i<row;i++) for(j=0;j<col;j++) cin>>A[i][j]; cout<<"请输入矩阵 B 的元素:\n"; for(i=0;i<row;i++) for(j=0;j<col;j++) cin>>B[i][j]; CreateMat(A,a,row,col); CreateMat(B,b,row,col); cout<<"矩阵 A 的三元组表示为:\n"; DispMat(a); cout<<"矩阵 B 的三元组表示为:\n"; DispMat(b); if(MatAdd(a,b,c)) { cout<<"矩阵 A、B 相加后得到的三元组表示为:\n"; DispMat(c); } return 0; }

7.简述字符串与一维字符型数组的区别与联系。 字符串简称串,它是一种以字符为元素的特殊线性表。字符串可以看成是以字符为元素
的一维数组。具体实现时,在 C/C++中的字符串使用为字符型数组来表示。为了便于确定字 符串的结尾,在字符型数组中使用\0(就是 0)作为字符串的截止符。 8.列举一些需要进行字符串模式匹配的应用场景。
例如,在文本编辑中经常要查找某一特定单词或者一段话在整篇文章中出现的位置,按 照姓名查找某个学生、员工、居民。有效的模式匹配能极大地提高文本编辑程序的能力。 9.列举几个字符串的其他操作。
求字符串中某个子串出现的次数,删除满足条件的子串,字符串字符移位等。 10.什么是广义表?广义表与线性表的区别是什么?
广义表又称列表,是由 n(n≥0)个元素组成的有穷序列:GL=(e1,e2,……en),但与 线性表不同的是,广义表中的元素允许以不同的形式出现:它可以是一个原子(逻辑上不能 再分解的元素),也可以是另一个广义表。 11.一个广义表是(a, (a, b, c), d, e, (m, n),(w, (i, j), x)),请问该广义表的长度、 深度分别是多少?请画出该广义表的单链表存储结构示意图。
该广义表的深度是 3,长度是 6。 该广义表的单链表存储结构示意图如下:

head

0

1a

2

1d

1e

2

2

head 0
1a

head

0

1w

2

1x

head

1m

0

1b

1n

1i

1c

1j

12.请列举出一些可以归纳成数组、矩阵、字符串和广义表数据结构的实际问题。 线性表的顺序存储、学生编号和姓名的问题、各班级的学生编号和姓名的问题等,都可
以归结为数组。 不同物品所需原材料的数量、不同产地原材料的价格、不同类型的住宅需要的物品数量
等,不同学生的计算机成绩,不同职工的工资等都可以归结为矩阵。 学生的姓名和学号、学校或各单位的名称、国家名称、一篇文章、一个高级语言源程序
等,都可归结为字符串。 应用高斯消元法求解方程组可以归结为广义表。

第 5 章 树和二叉树
1. 请简述树、二叉树、满二叉树和完全二叉树的结构特性。 树:只有最顶层的结点没有前驱,其余结点都有且只有一个前驱;一个结点可以没有后
继,也可以有一个或多个后继。 二叉树:一种特殊形态的树,每个结点至多有两个后继。 满二叉树:一种特殊形态的二叉树,除了最后一层的结点为叶子结点外其它结点都有左、
右两棵子树的二叉树。 完全二叉树:一种特殊形态的二叉树,其结点与相同深度的满二叉树中的结点编号完全
一致,即对于深度为 k 的完全二叉树,其前 k-1 层与深度为 k 的满二叉树的前 k-1 层完全一 样,只是在第 k 层上有可能缺少右边若干个结点。 2. 请解释结点的度、树的度、结点的层、树的深度、分支、路径、路径长度、树的路径长 度、叶子结点、分支结点、内部结点、孩子、双亲、兄弟、堂兄弟、祖先、子孙、有序树、 无序树和森林等基本术语的含义。
结点的度和树的度:一个结点的后继的数目称为该结点的度,树中各结点度的最大值 称为树的度。
结点的层和树的深度:树的根结点所在的层为第 1 层,其余结点的层等于其前驱结点 的层加 1,树中各结点的层的最大值称为树的深度。
分支、路径、路径长度和树的路径长度:从一个结点到其后继结点之间的连线称为一 个分支,从一个结点 X 到另一个结点 Y 所经历的所有分支构成结点 X 到结点 Y 的路径,一 条路径上的分支数目称为路径长度,从树的根结点到其他各个结点的路径长度之和称为树的 路径长度。
叶子结点、分支结点和内部结点:树中度为 0 的结点称为叶子结点(或终端结点), 度不为 0 的结点称为分支结点(或非终端结点),除根结点以外的分支结点也称为内部结点。
孩子和双亲:在树中,一个结点的后继结点称为该结点的孩子,相应地,一个结点的前 驱结点称为该结点的双亲,即一个结点是其孩子结点的双亲、其双亲结点的孩子。
兄弟和堂兄弟:同一双亲的孩子结点之间互称为兄弟,不同双亲但在同一层的结点之 间互称为堂兄弟。
祖先和子孙:从树的根结点到某一个结点 X 的路径上经历的所有结点(包括根结点但 不包括结点 X)称为结点 X 的祖先,以某一结点 X 为根的子树上的所有非根结点(即除结 点 X 外)称为结点 X 的子孙。
有序树和无序树:对于树中的任一结点,如果其各棵子树的相对次序被用来表示数据 之间的关系,即交换子树位置会改变树所表示的内容,则称该树为有序树;否则称为无序树。
森林:m(m≥0)棵互不相交的树的集合就构成了森林。 3. 请简述二叉树的五条基本性质。
性质 1:在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。 性质 2:深度为 k 的二叉树至多有 2k-1 个结点。 性质 3:在二叉树中,若度为 0 的结点(即叶子结点)数为 n0,度为 2 的结点数为 n2, 则 n0=n2+1。 性质 4:具有 n 个结点的完全二叉树其深度为 ?log2n?+1(其中 ?log2n? 表示不大于 log2n 的最大整数)。 性质 5:采用顺序编号的完全二叉树具有如下性质:若一个分支结点的编号为 i,则其

左子树的根结点(即左孩子结点)编号为 2*i,右子树的根结点(即右孩子结点)编号为 2*i+1; 反之,若一个非根结点的编号为 i,则其双亲结点的编号为 ?i/2?(其中 ?i/2? 表示不大于 i/2 的最大整数)。 4. 请简述二叉树的常用操作及各操作的含义。
创建一棵空二叉树:创建一棵没有任何结点的二叉树。在顺序表示中,根据树的深度 为结点分配内存;在二叉链表表示中,将指向根结点的指针赋值为 NULL。
删除一棵二叉树:将二叉树各结点所占据的内存释放。 清空二叉树:将二叉树的所有结点删除,使之成为一棵空二叉树。 以指定元素值创建根结点:创建根结点,并以指定值作为根结点的元素值。 将一个结点作为指定结点的左孩子插入:根据指定元素值生成一个新结点,并将其作 为指定结点的左孩子。 将一个结点作为指定结点的右孩子插入:根据指定元素值生成一个新结点,并将其作 为指定结点的右孩子。 先序遍历二叉树:也称为先根遍历,其访问方式递归定义如下:对于一棵二叉树,先 访问其根结点,再访问根结点的左、右子树;对于左、右子树中的结点仍然是按照先序遍历 方式访问,即先访问根结点,再访问根结点的左、右子树。 中序遍历二叉树:也称为中根遍历,其访问方式递归定义如下:对于一棵二叉树,先 访问根结点左子树,再访问根结点,最后访问右子树;对于左、右子树中的结点仍然是按照 中序遍历方式访问。 后序遍历二叉树:也称为后根遍历,其访问方式递归定义如下:对于一棵二叉树,先 访问根结点的左子树,后访问右子树,最后访问根结点;对于左、右子树中的结点仍然是按 照后序遍历方式访问。 逐层遍历二叉树:从第 1 层开始依次对每层中的结点按照从左至右的顺序进行访问。 获取指定结点的双亲结点:根据指定结点获取其双亲结点。在顺序表示中,可以直接 根据指定结点的位置计算双亲结点的位置;在二叉链表表示中,则需要从根结点开始遍历二 叉树直至找到指定结点的双亲结点。 删除以指定结点为根的子树:将以指定结点为根结点的子树上的所有结点(包括指定 结点)删除。 按关键字查找结点:按照某种规则(先序、中序、后序或逐层)依次访问二叉树中的 每一结点,直至找到与关键字匹配的结点。 判断二叉树是否为空:判断一棵二叉树是否为空二叉树。 修改指定结点的元素值:将指定结点的元素值修改为指定值。 计算二叉树的深度:按照某种规则依次访问二叉树中的每一结点,计算各结点所在层 的最大值。 计算二叉树的叶子结点数:按照某种规则依次访问二叉树中的每一结点,计算度为 0 的结点数。 5. 请简述顺序表示的二叉树中各结点的编号规则。 顺序表示的二叉树中各结点的编号与相同深度的完全二叉树中对应结点的编号相同。 6. 请简述二叉链表表示和三叉链表表示的二叉树中结点的结构。 在二叉链表表示中,双亲结点有指向其孩子结点的指针,而孩子结点不包含指向其双亲 结点的指针;在三叉链表表示中,双亲结点有指向其孩子结点的指针,而孩子结点也包含指 向其双亲结点的指针。 7. 请简述二叉树的四种遍历方式及每一种遍历方式中结点的访问顺序。 先序遍历二叉树:也称为先根遍历,其访问方式递归定义如下:对于一棵二叉树,先

访问其根结点,再访问根结点的左、右子树;对于左、右子树中的结点仍然是按照先序遍历 方式访问,即先访问根结点,再访问根结点的左、右子树。
中序遍历二叉树:也称为中根遍历,其访问方式递归定义如下:对于一棵二叉树,先 访问根结点左子树,再访问根结点,最后访问右子树;对于左、右子树中的结点仍然是按照 中序遍历方式访问。
后序遍历二叉树:也称为后根遍历,其访问方式递归定义如下:对于一棵二叉树,先 访问根结点的左子树,后访问右子树,最后访问根结点;对于左、右子树中的结点仍然是按 照后序遍历方式访问。
逐层遍历二叉树:从第 1 层开始依次对每层中的结点按照从左至右的顺序进行访问。 8. 已知一棵二叉树的先序遍历结果为 A、B、D、G、C、E、F、H、I,中序遍历结果为 D、 G、B、A、E、C、H、F、I,请给出该二叉树的后序遍历结果。
G、D、B、E、H、I、F、C、A 9. 已知一棵二叉树的中序遍历结果为 D、G、B、A、E、C、H、F、I,后序遍历结果为 G、 D、B、E、H、I、F、C、A,请给出该二叉树的先序遍历结果。
A、B、D、G、C、E、F、H、I 10. 已知一棵二叉树的先序遍历结果为 A、B、D、G、C、E、F、H、I,后序遍历结果为 G、 D、B、E、H、I、F、C、A,请给出该二叉树的中序遍历结果。
D、G、B、A、E、C、H、F、I 11. 请简述哈夫曼树的结构特性。
哈夫曼树,又称最优二叉树,是指在由 n 个叶子结点构成的一类二叉树中具有最短带权 路径长度的二叉树。 12. 请简述结点的权、结点的带权路径长度、树的带权路径长度等基本术语的含义。
结点的权和结点的带权路径长度:在实际应用中,往往给树中的结点赋予一个具有某 种意义的实数,该实数就称为是结点的权。结点的带权路径长度是指从树根到该结点的路径 长度与结点的权的乘积。

? 树的带权路径长度:是指树中所有叶子结点的带权路径长度之和,记为WPL ?

W n
i ?1 i

Li

(其中,n 为叶子结点的数目,Wi 为第 i 个叶子结点的权,Li 为根结点到第 i 个叶子结点的 路径长度,可知 WiLi 为第 i 个叶子结点的带权路径长度)。 13. 请简述哈夫曼树的构造方法。
哈夫曼树的构造方法如下:
(a)已知 n 个权值为 Wi(i=1, 2, …, n)的结点,将每个结点作为根结点生成 n 棵只有 根结点的二叉树 Ti,形成森林 F={T1, T2, …, Tn}。
(b)从森林 F 中选出根结点权值最小的两棵二叉树 Tp 和 Tq,并通过添加新的根结点 将它们合并为一棵新二叉树,新二叉树中 Tp 和 Tq 分别作为根结点的左子树和右子树,且根 结点的权值等于 Tp 和 Tq 两棵二叉树的根结点权值之和。以合并后生成的新二叉树替代森林 F 中的原有二叉树 Tp 和 Tq。重复该步骤直至森林 F 中只存在一棵二叉树。 14. 请简述哈夫曼码的作用及其编码方法。
哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间,
其具体方法为:
(a)以要编码的字符集 C={c1, c2, …, cn}作为叶子结点、字符出现的频度或次数 W={w1, w2, …, wn}作为结点的权,构造哈夫曼树。
(b)规定哈夫曼树中,从根结点开始,双亲结点到左孩子结点的分支标为 0,双亲结 点到右孩子结点的分支标为 1。从根结点到某一叶子结点经过的分支形成的编码即是该叶子

结点所对应字符的哈夫曼码。 15. 请简述树的四种常用表示方式。
双亲表示法:在孩子结点中设置一个指针域记录其双亲结点的存储位置。 孩子表示法:在双亲结点中设置指向孩子结点的指针域来表示一棵树。 孩子双亲表示法:综合了孩子表示法和双亲表示法的特点,既在孩子结点中设置记录 双亲结点位置的指针域,又在双亲结点中设置记录孩子结点位置的指针域。 孩子兄弟表示法:又称为二叉链表表示法,与二叉树的二叉链表表示法存储结构完全 相同,只是结点中指针域的含义有所不同(一个指针域指向该结点的第一个孩子结点,另一 个指针域指向该结点的下一个兄弟结点)。 16. 请简述森林转换为二叉树的具体步骤。 将森林中的每棵树都用二叉链表表示法表示,并将各棵二叉树的根结点看做是兄弟结 点,在它们之间加上连线;将结点到第一个孩子结点的连线作为左子树的边,结点到兄弟结 点的连线作为右子树的边。 17. 请简述二叉树转化为树或森林的具体步骤。 将一个结点左子树的边作为该结点指向第一个孩子结点的连线,右子树的边作为该结点 到兄弟结点的连线;在双亲结点和它的各孩子结点之间加上连线,并删除兄弟结点之间的连 线,得到一棵树或一个包含若干棵树的森林。

第6章 图

1. 请简述图的结构特性。 图 G 由顶点(图中通常将结点称为顶点)的非空有限集合 V 和边的集合 E 组成,记为
G=(V, E)。每一个顶点偶对就是图中的一条边,所以,E 用于表示 V 上的连接关系。在一个 图中,至少要包含一个顶点,但可以没有任何边。 2. 请解释有向图、无向图、弧、弧尾、弧头、顶点的度、顶点的入度、顶点的出度、路径、 路径长度、回路、简单回路、连通图、单向连通图、强连通图、子图、连通分量、强连通分 量、权、带权图、生成树、最小生成树等基本术语的含义。
有向图、弧、弧尾和弧头:若 E(G)中的顶点偶对是有序的,则这些有序偶对就形成了 有向边,此时图 G 称为有向图。其中,有向边也简称为弧。在有向图 G 中,对于一条从顶 点 vi 到顶点 vj 的弧,记为<vi, vj>并有<vi, vj>∈E(G),称 vi 为弧尾,vj 为弧头。
无向图:若 E(G)中的顶点偶对是无序的,则这些无序偶对就形成了无向边,此时图 G 称为无向图。
顶点的度、顶点的入度和顶点的出度:在无向图中,与顶点 vi 相关联的边的数目称为 顶点 vi 的度。在有向图中,以顶点 vi 为弧头的弧的数目称为顶点 vi 的入度;以顶点 vi 为弧 尾的弧的数目称为 vi 的出度;顶点 vi 的入度和出度之和称为 vi 的度。

路径和路径长度:在图

G

中,若存在一个顶点序列(

v

0 i

,

v

1 i

,

…,

v

n-1 i

),使得对于任意

0≤j<n-1



?

vij,

v

j?1 i

??

E(G)

(若

G

为有向图)或

(vij,

v

j?1 i

)

?

E(G)

(若

G

为无向图),则该序

列是从顶点

v

0 i

到顶点

vin-1

的一条路径。一条路径中边的数目称为路径长度。

回路和简单回路:在一条路径中,若组成路径的顶点序列中第一个顶点与最后一个顶 点相同,则该路径称为回路(或环);在一个回路中,若除第一个顶点与最后一个顶点外, 其他顶点只出现一次,则该回路称为简单回路(或简单环)。
连通图:无向图 G 中,若任意两个顶点都是连通的,则称 G 为连通图。 单向连通图和强连通图:有向图 G 中,若任意两个顶点都是单向连通的,则称 G 是单 向连通图;若任意两个顶点都是强连通的,则称 G 为强连通图。 子图:对于图 G、G',若满足 V(G' ) ? V(G) 且 E(G' ) ? E(G) ,则 G'是 G 的子图。 连通分量和强连通分量:一个无向图的极大连通子图称为该无向图的连通分量;一个 有向图的极大强连通子图称为该有向图的强连通分量。 权和带权图:可以为一个图中的每条边标上一个具有某种意义的实数,该实数就称为是 边的权。边上带权的图就称为带权图。 生成树和最小生成树:若无向图 G 的一个子图 G'是一棵包含图 G 所有顶点的树,则 G'称为图 G 的生成树。在所有形式的生成树中,边上的权之和最小的生成树,称为最小生 成树。 3. 请列举可以用图来描述的实际问题。 请参考例 6-1 和例 6-2。 4. 请简述图的基本操作及各操作的含义。 创建图:创建不包含任何顶点和边的空图。 对图作深度优先遍历:类似于树的先序遍历,即从某一个顶点开始访问,访问后将该顶

点去除得到若干子图,对每个子图再依次进行深度优先遍历。 对图作广度优先遍历:类似于树的逐层遍历,即先从某一个顶点开始访问,然后访问与 该顶点相邻接且未被访问过的顶点集 V1(G),再访问与 V1(G)中顶点相邻接且未被访问 过的顶点集 V2(G),重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连 通图或非强连通图,还要从某一个未被访问的顶点开始重复上一过程,直至所有顶点访 问完毕。 获取顶点数目:获取图中所包含的顶点的数目。 获取边的数目:获取图中所包含的边的数目。 获取与指定顶点相关联的第一条边:对无向图,获取到与指定顶点相关联的第一条边; 对有向图,获取到以指定顶点作为弧尾的第一条弧。不同表示方法获取到的结果会有所 不同(邻接矩阵法按顶点编号顺序,邻接压缩表和邻接链表按边的添加顺序)。 获取与指定边有相同关联顶点的下一条边:对无向图,获取到与指定边(nV1,nV2) 有相 同关联顶点 nV1 的下一条边;对有向图,获取到与指定弧<nV1,nV2>有相同弧尾 nV1 的下一条弧。不同表示方法获取到的结果会有所不同(邻接矩阵法按顶点编号顺序,邻 接压缩表和邻接链表按边的添加顺序)。 添加一个顶点:向图中添加一个新顶点。 添加一条边:对无向图,向图中添加一条新边;对有向图,向图中添加一条新弧。 获取一个顶点中存储的数据:根据顶点编号获取该顶点中存储的数据。 判断一条边是否存在:对无向图,判断两个顶点 nV1 和 nV2 之间是否存在边;对有向 图,判断是否存在从顶点 nV1 到顶点 nV2 的弧。 设置一条边的权:对无向图,设置指定边(nV1,nV2)上的权;对有向图,设置指定弧 <nV1,nV2>上的权。 获取一条边的权:对无向图,获取指定边(nV1,nV2)上的权;对有向图,获取指定弧 <nV1,nV2>上的权。 5. 请简述图的三种常用表示方法。 邻接矩阵法:用矩阵来表示各顶点之间的连接关系。对于有 n 个顶点的图 G=(V, E), 其邻接矩阵 A 为 n*n 的方阵,元素 A[i][j](0≤i,j<n)定义为:
?wij 对无向图存在 (vi , vj ) ? E(G) ,对有向图存在 ? vi , vj ?? E(G) A[i][j]???? 反之
其中,wij 为边(vi, vj)或<vi, vj>上的权。 邻接压缩表:邻接矩阵的一种压缩表示形式,使用 3 个顺序表来表示图中顶点之间的连 接关系和权。设图中共有 n 个顶点{v0, v1, …, vn-1},3 个顺序表分别为 s、w 和 h。在 s 中依 次记录与顶点 vi(i = 0, 1, …, n-1)相关联的顶点;在 w 中依次记录 s 中存储的各条边的权; 在 h 中依次记录与顶点 vi 相关联的顶点在 s 中的起始存储位置。 邻接链表:图的一种链式存储结构。每个顶点中设置一个指向链表头的指针,在链表中 保存与该顶点相邻接的顶点信息(包括顶点位置及两个顶点形成的边的权)。 6. 请简述图的两种常用遍历方法及每一种遍历方法中结点的访问顺序。 广度优先遍历:类似于树的逐层遍历,即先从某一个顶点开始访问,然后访问与该顶 点相邻接且未被访问过的顶点集 V1(G),再访问与 V1(G)中顶点相邻接且未被访问过的顶点 集 V2(G),重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连 通图,还要从某一个未被访问的顶点开始重复上一过程,直至所有顶点访问完毕。 深度优先遍历:类似于树的先序遍历,即从某一个顶点开始访问,访问后将该顶点去

除得到若干子图,对每个子图再依次进行深度优先遍历。 7. 请列举最小生成树和最短路径可以用于解决什么应用问题。
请参考例 6-1 和例 6-2。 8. 请简述 Prim 算法的作用和具体步骤。
Prim 算法用于最小生成树问题求解。对于有 n 个顶点的图 G=(V, E),Prim 算法从空树 T 开始,按照以下规则将 n 个顶点和 n-1 条边依次添加到树中,形成最小生成树:
(a)从某一顶点 v0'开始,将该顶点作为树的根结点加入到 T 中,使得 T 中的数据元素 集合 D={v0'},数据元素关系集合 R={}。
(b)对于一个顶点在集合 D 中、另一个顶点在集合 V-D 中的那些边,找出权最小的一 条边,将该边在集合 V-D 中的顶点 vi'(i=1,2,…,n-1)加入到集合 D 中,并将顶点间关系<vj', vi'>(j<i)加入到关系集合 R 中。
(c)重复上一步骤直至集合 D 中包括图 G 中所有 n 个顶点(此时关系集合 R 中包括 n-1 条边)。若在某一步骤中找不到边,则说明图 G 是一个非连通图或非强连通图,在这种 情况下不存在最小生成树。 9. 请简述 Kruskal 算法的作用和具体步骤。
Kruskal 算法用于最小生成树问题求解。对于有 n 个顶点的图 G=(V, E),Kruskal 算法根 据图 G 中所有 n 个顶点生成一个包括 n 棵只有根结点的树 Ti(i=0, 1, …, n-1)的森林 F,并 按照以下规则森林 F 中的树合并,形成最小生成树:
(a)从边集合 E 中选取未被访问过且具有最小权的边,置该边状态为已访问。判断该 边的两个顶点是否属于不同的树,若属于不同的树则使用该边将两棵树合并为一棵;若属于 同一棵树则不做任何处理。
(b)重复上一步骤直至森林 F 中只剩下一棵树,该树即是图 G 的最小生成树。若最后 森林 F 中剩下不止一棵树,则说明图 G 是非连通图或非强连通图,在这种情况下不存在最 小生成树。 10. 请简述 Dijkstra 算法的作用和具体步骤。
Dijkstra 算法用于计算从某个顶点到其余各顶点的最短路径。对于有 n 个顶点的图 G=(V, E),若要计算从顶点 v0'到其余各顶点 vi'(i=1,2,…,n-1)的最短路径,则其计算步骤为:
(a)令集合 S 为已计算出最短路径的顶点集合(初始时 S={v0'}),w(vj', vi')表示从顶 点 vj'到顶点 vi'的边的权(这里为方便计算,令 w(vi', vi')=0),D(v0', vi')表示当前计算得到的 从顶点 v0'到顶点 vi'的最短路径长度(初始 D(v0', vi')= w(v0', vi'))。
(b)将顶点 vm ' ? argmin(D(v0', vi ' )) 加入到集合 S 中,并将从顶点 v0'到顶点 vm'的最短
v i '?V?S
路 径 记 录 下 来 。 若 仍 有 顶 点 没 有 加 到 集 合 S 中 , 则 对 集 合 V-S 中 的 顶 点 vi' 计 算
D(v0', vi ' ) ? vmj '?inS(D(v0', v j' ) ? w(v j', vi ' )) 。
(c)重复上一步骤直至图中所有顶点都加到集合 S 中。 11. 请简述 Floyd 算法的作用和具体步骤。
Floyd 算法用于计算每一对顶点之间的最短路径。对于有 n 个顶点的图 G=(V, E),若要 计算任意两个顶点 vj'和 vk'(j,k 为[0,n-1]区间上的整数且 j≠k)之间的最短路径,则其计算步 骤为:
(a)令 w(vj', vk')表示连接顶点 vj'和顶点 vk'的边的权(这里为方便计算,令 w(vj', vj')=0), D(vj', vk')表示当前计算得到的从顶点 vj'到顶点 vk'的最短路径长度(初始 D(vj', vk')= w(vj', vk'))。
(b)对于图中每一个顶点 v(i' i 依次取值为 0, 1, …, n-1),若 D(vj',vk')>D(vj',vi')+D(vi',vk'),

则表明路径(vj', …, vi', …, vk')的长度更短,此时令 D(vj',vk')=D(vj',vi')+D(vi',vk')并更新从顶点 vj'到顶点 vk'的路径。

第 7 章 排序算法
1. 请简述排序的作用。 排序的作用是将一个待排序元素集合按关键字递增(或递减)顺序整理为一个有序序列。
2. 请简述稳定排序和不稳定排序的含义。 若采用某种排序算法对任一组元素进行排序,在排序前后,那些具有相同关键字值的元
素之间的相对次序都保持不变,则将这种排序算法称为是稳定的,否则称为是不稳定的。 3. 请简述各种排序算法的适用范围。
排序算法的适用范围如下: (a)直接插入排序、简单选择排序和冒泡排序都是简单排序算法,它们的时间复杂度 和空间复杂度分别为 O(n2)和 O(1)。若待排序元素数量 n 较小,可以选用直接插入排序和冒 泡排序。另外,当待排序元素基本有序时,也应选用直接插入排序和冒泡排序,此时时间复 杂度都能达到 O(n)。若元素本身数据量较大,元素移动操作代价较高,则应选用平均移动 元素次数最少的简单选择排序。希尔排序是对直接插入排序算法的改进,大大降低了时间复 杂度,但它是一种不稳定的排序算法。 (b)堆排序、快速排序和归并排序主要适用于待排序元素数量 n 较大的情况,当待排 序元素数量 n 较小时,它们的性能有可能劣于简单排序算法。因此,在实际应用时,快速排 序算法和归并排序算法经常与简单排序算法结合使用(例如,可以先用快速排序算法将集合 划分为规模更小的子集合,对于元素数量较小的子集合,则用直接插入排序算法进行排序)。 在所有平均时间复杂度为 O(nlog2n)的算法中,尽管快速排序在最坏情况下时间复杂度较高, 但它通常被认为是平均性能最好的一种算法,并且通过优化可以降低最坏情况出现的概率。 归并排序是一种稳定的排序算法,其时间性能一般要优于堆排序,但它所需要的辅助空间较 多,当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以考虑使用。堆排序 所需的辅助空间最少,当可用空间非常有限时可以考虑使用。 (c)箱排序和基数排序的时间复杂度最低,但它们的空间复杂度最高。箱排序主要适 用于待排序元素长度(即 d 值)较小的情况,在实际中应用不多;基数排序是箱排序的改进, 主要适用于整数或字符串的排序,或者与其他排序算法结合进行实数的排序(例如,可以先 用基数排序算法按整数部分将元素分成若干个子集合,再对每个子集合应用直接插入排序算 法进行排序)。 5. 请简述插入排序、选择排序、交换排序、归并排序和分配排序的原理。 插入排序:按关键字大小每次将一个待排序的元素插入到已排序的序列中,直至所有元 素都插入完毕。 选择排序:每次从待排序的元素中选择具有最小(或最大)关键字的元素放到已排序序 列的尾部(或头部),直至所有元素都排序完毕。 交换排序:从待排序的元素中选择两个次序相反的元素进行交换,直至任意两个元素的 次序都正确。 K 路归并排序:每次将 K(K≥2)个已排序的子序列组合在一起,形成一个有序的序列, 重复该过程直至得到一个包含所有待排序元素的有序序列。 分配排序:根据元素本身所具有的值将各元素逐一映射到一组有序空间中,最后再依次 从有序空间中将各元素取出即形成了排序结果。 5. 请简述直接插入排序的具体步骤。 直接插入排序是一种简单排序算法,其具体步骤为:

(a)初始已排序区为空,将第一个待排序的元素插入到已排序区中。 (b)将后继每一个待排序的元素依次取出,并按照关键字大小将其插入到已排序区中 的适当位置,使该序列仍然有序。 (c)重复上一步骤直至将待排序的元素都插入到已排序序列中。 6. 请简述希尔排序的具体步骤。 希尔排序,又称为“缩小增量排序”,其具体步骤为: (a)令 n 为待排序元素数目,设置增量序列{d0, d1, …, dk},其中 n>d0>d1>…>dk=1。 (b)按增量 di(i 依次取值为 0, 1, …, k)将待排序元素分为 di 组,将所有下标距离为 di 的倍数的元素放在同一组中,即 R[1], R[1+ di], R[1+2*di], …在第一组中,R[2], R[2+ di], R[2+2*di], ……在第二组中,……,依此类推。然后分别在各组内进行直接插入排序。 (c)重复上一步骤直至最后以 1 为增量对所有待排序元素进行直接插入排序。 7. 请简述简单选择排序的具体步骤。 简单选择排序是一种简单排序算法,其具体步骤为: (a)初始已排序区为空,待排序区包含所有待排序元素。 (b)从待排序区中选择具有最小关键字的元素,将其与待排序区的第一个元素交换位 置,并将该位置加到已排序区中。 (c)重复上一步骤直至所有元素都排序完毕。 8. 请简述堆的定义和堆的构建过程。 堆的定义: 对于包含 n 个元素的集合 R={R[1], R[2], …, R[n]},若满足: (1)R[i]≤R[2*i]且 R[i]≤R[2*i+1](即 R 所表示的完全二叉树中每一棵子树的根结点的 值均不大于其孩子结点的值)。 (2)或 R[i]≥R[2*i]且 R[i] ≥R[2*i+1](即 R 所表示的完全二叉树中每一棵子树的根结点 的值均不小于其孩子结点的值)。 则称集合 R 为堆。若满足前一个条件则称 R 为小根堆,满足后一个条件则称 R 为大根 堆。 堆的构建过程: 堆一般采用自底向上的构建方法,即在将以某一结点为根结点的二叉树构建成堆之前, 先将其左子树和右子树构建成堆。以叶子结点为根的子树必然是堆,因此,对于由 n 个元素 构成的完全二叉树,其对应的堆的构建过程从 R[?n/2?]作为根结点的子树开始,依次对 R[?n/2?-1]、R[?n/2?-2]、…、R[1]作为根结点的树进行堆的构建。 在将一棵 R[i]作为根结点的子树整理为堆时,只有根结点不满足堆的条件,因此,需将 根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件,这里以大 根堆构建为例介绍其具体过程: ( a ) 若 R[i] 存 在 左 孩 子 R[2*i] , 则 令 j=2*i ; 若 R[i] 存 在 右 孩 子 R[2*i+1] 且 R[2*i+1]>R[2*i],则令 j=2*i+1。将 R[j]与 R[i]比较,若 R[i]较小,则将 R[i]和 R[j]交换,并 令 i=j。 (b)重复上述步骤直至 R[i]无孩子结点或 R[i]比其孩子结点都大,此时该子树即为堆。 9. 请简述堆排序的具体步骤。 堆排序的具体过程: (a)采用自底向上的方法将包含 n 个元素的待排序集合 R={R[1], R[2], …, R[n]}整理为 大根堆,其元素数目 i=n,初始时已排序集合 R'为空集; (b)将 R[1]与 R[i]交换,并将 i 算作已排序集合中的元素位置,更新待排序集合中最 后一个元素的位置 i=i-1,此时待排序集合 R={R[1], R[2], …, R[i]},已排序集合 R'={R[i+1],

R[i+2], …, R[n]}。显然,待排序集合 R={R[1], R[2], …, R[i]}中只有根结点 R[1]不满足大根 堆的条件,通过下移 R[1]重新将 R 整理为大根堆;
(c)重复上一步骤直至待排序集合 R={R[1]},此时直接将 R[1]作为已排序集合 R'中的 元素,堆排序过程结束。 10. 请简述冒泡排序的具体步骤。
冒泡排序是一种简单排序算法,其具体步骤为: (a)初始已排序区为空,待排序区包含所有待排序元素。 (b)在一轮排序中,对待排序区所有相邻元素从前至后进行两两比较,若相邻两个元 素次序相反(即前一个元素的关键字值大于后一个元素的关键字值),则交换它们的位置。 每轮排序后,待排序区中的最大元素会移到待排序区的尾部,将待排序区的最后一个元素放 到已排序区的头部。 (c)重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元 素交换的情况,此时直接将待排序区中的所有元素按原次序放到已排序区的头部,冒泡排序 结束。 11. 请简述快速排序中划分的含义和过程。 划分的含义: 划分是以指定元素 x 为基准将一个集合 R 分为两个子集 R1 和 R2,其中 R1 中的元素都 小于或等于 x,R2 中的元素都大于或等于 x。 划分的过程: 对于包含(high-low+1)个元素的待排序集合 R={R[low], R[low+1], …, R[high]},以 R[k] (low ≤k ≤high)为基准对其进行划分的具体过程为: (a)令 i、j 分别指向集合 R 的第一个元素和最后一个元素(即 i=low、j=high),并将 R[k]与 R[i]交换(即初始基准元素在 i 所指向的位置,此时基准元素前面没有任何元素,下 面对基准元素后面、位置在 i+1 到 j 之间的元素按照从后至前的顺序逐一检查其是否大于或 等于基准元素)。 (b)若 j!=i 且 R[j]≥R[i],则令 j=j-1,重复直至 R[j]<R[i]或 j==i。上述处理后,若 j!=i (即通过 R[j]<R[i]这个条件退出循环)则将 R[j]与 R[i]交换、i=i+1,并转到下一步(该步处 理结束后,基准元素在 j 所指向的位置,此时基准元素后面的元素都大于或等于基准元素, 而位置 i 前面的元素都小于或等于基准元素,下面对基准元素前面、位置在 i 到 j-1 之间的 元素按照从前至后的顺序逐一检查其是否小于或等于基准元素)。 (c)若 i!=j 且 R[i]≤R[j],则令 i=i+1,重复直至 R[i]>R[j]或 i==j。上述处理后,若 i!=j (即通过 R[i]>R[j]这个条件退出循环)则将 R[i]与 R[j]交换、j=j-1,并回到上一步(该步处 理结束后,基准元素在 i 所指向的位置,此时基准元素前面的元素都小于或等于基准元素, 而位置 j 后面的元素都大于或等于基准元素,下面继续对基准元素后面、位置在 i+1 到 j 之 间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素);否则集合划分操作结 束。 12. 请简述快速排序的具体步骤。 快速排序就是对集合不断划分的过程:通过划分可以将一个集合分为两个子集合,若子 集合中元素数目大于 1 则再对子集合分别进行划分,重复该过程直至最终每个子集合中元素 数目都小于或等于 1 时快速排序结束。 13. 请简述二路归并排序的具体步骤。 二路归并排序的具体步骤为: (a)对于包含 n 个元素的待排序集合,将其分为 n 个长度为 1 的子序列。 (b)将每两个相邻的子序列进行归并,得到 ?n/2? 个长度为 2 的子序列和 0 或 1 个长

度为 1 的子序列。 (c)在此基础上,再对每两个相邻的子序列进行归并,得到 ?n/4? 个长度为 4 的子序
列和 0 或 1 个长度小于 4 的子序列。 (d)重复该过程直至得到一个长度为 n 的有序序列为止。
14. 请简述箱排序的具体步骤。 箱排序的具体步骤为: (1)假设待排序元素的取值范围为 m~m+n-1,则箱子数量为 n,设置包含 n 个元素的
队列集合 B={B[0], B[1], …, B[n-1]}代表 n 个箱子。 (2)依次取出每一个待排序元素,若其值为 m+i(i=0, 1, …, n-1),则通过入队操作
将其放在箱子 B[i]中。 (3)从 B[0]开始,依次检查集合 B 中每一个队列所代表的箱子,若箱子不为空,则通
过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。 15. 请简述基数排序的具体步骤。
基数排序是对箱排序的改进和推广,它先将待排序元素按规则分解得到多个分量、再根 据每一个分量对元素进行多次箱排序。
(a)对于数字排序问题,基数排序方法先将每一个数字写成以 r 为基数的按权展开式 形式:N= an-1*rn-1+…+a0*r0+a-1*r-1+…+a-m*r-m;再按照从低位到高位(即从 r-m 开始到 rn-1) 的顺序进行 n+m 次箱排序。
(b)对于字符串排序问题,基数排序方法按照从后至前的顺序对字符串中的每个字符 分别进行箱排序。若待排序字符串中最长的字符串长度为 n,则需进行 n 次箱排序;若某一 字符串长度为 m(0≤m≤n),则该字符串在前(n-m)次箱排序中对应的字符值为'\0'。

第 8 章 查找算法
1. 请简述查找的作用。 查找的作用是根据给定值从一个数据集合中搜索某个元素。若某个元素的关键字值与给
定值相等,则查找成功;否则查找失败。 2. 请简述静态查找和动态查找的含义。
静态查找只根据给定值在数据集合中按关键字查找匹配元素、访问匹配元素的属性,而 不对数据集合进行插入元素、删除元素等操作;而动态查找可能会在查找过程中向数据集合 中插入一个新元素或从数据集合中删除一个已有元素。 3. 请简述各种查找算法的适用范围。
各种查找算法的适用范围: (a)顺序查找虽然查找效率最低,但其对待查找数据集合的存储结构无特别要求,在 对数据集合进行增、删、改等操作时效率较高,因此,根据那些不需要经常作查找操作的关 键字进行查找时,一般采用顺序查找算法。若经常作查找操作,则应使用效率较高的其他查 找算法。 (b)折半查找和分块查找主要适用于数据集合增、删、改等操作较少的情况;二叉排 序树查找则适用于数据集合变化较频繁的情况。 (c)哈希查找虽然在理论上具有最短的平均查找长度,但它占用的存储空间较多,且 在实际中只有哈希函数构造得好才能达到常量级的平均查找长度。而要想构造出好的哈希函 数,必须以大量数据为基础,因此,哈希查找主要适用于数据分布已知的情况。 4. 请简述顺序查找对待查找数据集合的要求及顺序查找的具体步骤。 顺序查找是一种最简单、直观的查找算法,适用于采用任何存储结构的数据集合,其具 体步骤为: (a)按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比较,若某 个元素的关键字与给定值相同,则查找成功; (b)若遍历所有元素后,仍没有找到关键字与给定值相同的元素,则查找失败。 5. 请简述折半查找对待查找数据集合的要求及折半查找的具体步骤。 折半查找,又称二分查找,它要求数据集合采用顺序表存储结构,且数据集合中的元素 是按关键字大小有序排列的。假设数据集合的元素按关键字递增排列,折半查找算法的具体 步骤为: (a)对于包含 n 个元素的递增数据集合 R={R[1], R[2], …, R[n]}(R[i]≤R[i+1]),根据 给定元素 K 进行折半查找,初始化待查找数据集合的下标起始位置 low=1 和结束位置 high=n。 (b)计算中间元素下标 mid=?(low+high)/2?,若 R[mid]==K,则查找成功,折半查找算 法结束;若 R[mid]<K,则令 low=mid+1;否则,若 R[mid]>K,则令 high=mid-1。 (c)若新的待查找数据集合不为空,即 low≤high,则返回到上一步在新的数据集合 (R[low],R[low+1],…,R[high])上继续进行折半查找;否则查找失败。 6. 请简述分块查找对待查找数据集合的要求及分块查找的具体步骤。 在分块查找算法中,除了待查找的数据集合外,还需建立一个索引表。待查数据集合与 索引表的关系描述如下:(a)将包含 n 个元素的待查找数据集合均匀分为 b 块(即 b 个子 集合),前 b-1 块中元素数目 s=?n/b?,最后一块中元素数目小于等于 s。(b)分块后块内 元素可以无序,但块间必须有序,这里假设块间为递增排列,即第 i+1 块中的任一元素大于 第 i 块中的任一元素(i<b)。(c)构造一个包含 b 个元素的索引表,用于记录每块的起始

位置和最大元素值。 分块查找算法的具体步骤为:(a)在索引表中查找,确定待查找元素在哪一块,由于
索引表有序,因此可以使用二分查找算法。(b)在已确定的块中,进行顺序查找。 7. 请简述二叉排序树的定义。
二叉排序树,又称二叉查找树,它或者是一棵空树,或者是具有如下性质的二叉树: (a)若它的左子树非空,则左子树上所有结点的值均小于根结点的值。 (b)若它的右子树非空,则右子树上所有结点的值均大于根结点的值。 (c)左、右子树也分别是二叉排序树。 8. 请简述二叉排序树的插入和创建过程。 二叉排序树的插入过程: 在二叉排序树中插入一个新结点,应保证插入新结点后的二叉树仍然是一棵二叉排序 树。对于一个给定元素 K,将其插入到二叉排序树中的具体步骤如下: (a)若二叉排序树为一棵空树,则将元素 K 作为二叉排序树的根结点。 (b)若 K 等于根结点的值,则该元素已经是二叉排序树中的结点,不需重复插入,直 接返回;若 K 小于根结点的值,则将 K 插入到左子树中;若 K 大于根结点的值,则将 K 插 入到右子树中。重复该步骤,直至要插入的子树为空,此时将 K 作为该子树的根结点。 二叉排序树的创建过程就是不断插入新结点的过程。 9. 请简述二叉排序树的查找过程。 对于给定值 K,先将 K 与根结点的值比较,若相等则查找成功;若 K 小于根结点的值, 则在左子树中继续进行二叉排序树的查找;否则,若 K 大于根结点的值,则在右子树中继 续进行二叉排序树的查找。重复该过程,直至找到匹配的结点,查找成功;或者子树为空, 查找失败。 10. 请简述哈希表的元素存储原理。 确定一函数 h,对于关键字值是 k 的元素,以 k 为自变量计算函数值 h(k),这个函数值 被解释为一片连续存储空间中的一个地址(即数组中的一个下标值),元素即被存入到这个 地址中。 11. 请简述常用的四种哈希函数及其计算规则。
除余法:选取一个适当的正整数 p(通常 p 为不大于哈希表存储空间尺寸的最大素数), 以元素的关键字值 k 除以 p,得到的余数作为元素的存储地址,即 h(k)=k%p。
数字分析法:若元素的关键字由多位组成,且关键字的位数比存储空间地址码位数多、 每一位的取值范围及关键字的取值分布情况预先知道,则可以对元素关键字的各位进行分 析,去掉分布较集中的位、保留分布较均匀的位。
折叠法:若元素的关键字由多位组成,且关键字的位数比存储空间地址码位数多,但关 键字的取值分布情况未知,则可以用折叠法将关键字分为几段(除了最后一段位数可以少一 些,其他各段的位数均等于存储空间地址码位数),并将所有段的值做叠加求和运算,将叠 加和的最高位进位舍去后取剩余部分作为元素的存储地址。
平方取中法:对元素的关键字值求平方,并取中间几位作为元素的存储地址。 12. 请简述常用的两种哈希表冲突处理方法。
开放定址法:按照某个探查序列在哈希表中进行搜索,直至找到一个空闲的地址,将发 生冲突的新元素存储在该地址中。
拉链法:将所有同义词存储在一个线性链表中,从而避免开放定址法中的“二次聚集” 现象。用拉链法构造的哈希表,若其有 m 个存储地址(下标为 0, 1, …, m-1),则每个地址 存储一个线性链表的头指针,映射到地址 i 的元素以结点的方式插入到地址 i 所对应的链表 中。

第 9 章 文件
1. 请简述文件的定义。 文件,是由大量具有相同性质的记录组成的集合。
2. 请简述文件的组成。 文件是大量性质相同的数据记录的集合,即一个文件包含一条或多条记录。 记录是一个实体的所有数据项的集合,即一条记录包含一个或多个数据项。 数据项(也称为字段或属性)是反映实体某一方面属性的数据表示,是文件存取最基本
的操作对象。 3. 请简述文件的分类。
按文件中记录的信息长度,可以将文件分为定长记录文件和不定长记录文件。若每个 记录含有相同长度的信息,则称这类记录为定长记录;否则,若每个记录含有不同长度的信 息,则称这类记录为不定长记录。由定长记录组成的文件称为定长文件;由不定长记录组成 的文件则称为不定长文件。
按记录中关键字的数目,可以将文件分为单关键字文件和多关键字文件。若文件中的 记录只有一个用于唯一标识记录的主关键字,则这类文件称为单关键字文件;若文件中的记 录除了含有一个主关键字之外,还包含若干次关键字,则这类文件称为多关键字文件。 4. 请简述文件检索操作中的四种查询方式。
根据检索条件的不同可以分为以下 4 种查询方式: (a)简单查询:根据给定值 x 按单个关键字查询关键字值 k 等于 x 的记录。 (b)区域查询:根据给定取值范围按单个关键字查询满足条件的记录。 (c)函数查询:根据统计函数计算的值查询记录。 (d)布尔查询:将以上 3 种查询用逻辑运算符(包括逻辑与、逻辑或、逻辑非)连接起 来所形成的查询。 5. 请简述文件各维护操作的含义和过程。 文件维护是指对文件中记录所进行的插入、删除、修改等操作。这些操作的具体含义和 操作过程描述如下: (a)插入:向文件中添加一条新的记录。若文件按某个关键字顺序排列,则插入记录 前一般要先通过检索确定插入点的位置。 (b)删除:从文件中删除一条记录。删除记录前一般要先通过检索确定所要删除记录 的位置。 (c)修改:对记录中的一个或多个数据项进行修改。若文件按某个关键字顺序排列, 且对关键字值进行了修改操作,则修改后还需将记录移动到正确的位置(一般采用先删除再 插入的方式实现)。 6. 请简述文件的四种基本组织方式。 顺序结构、索引结构、散列结构和链式结构。 7. 请简述磁盘的逻辑结构。 磁盘的结构如下: (a)一个磁盘包含若干个盘片,所有盘片组成了盘片组;每个盘片有上下两面,称为 盘面;每个盘面上有很多同心圆形式的磁道,数据就存放在这些磁道上;每个磁道又可以划 分为若干段,称为扇区,一个扇区就是一次读写的最小数据量。 (b)每个盘面都配有一个读写磁头,通过读写磁头可以对磁道上的数据进行读写操作;

所有读写磁头都安装在动臂上,通过动臂可以将读写磁头移动到任一磁道上;所有盘面上具 有相同半径的磁道就构成了圆柱面,一个磁盘上圆柱面的个数就是一个盘面上的磁道数,同 一时刻所有读写磁头都位于一个圆柱面上。
(c)主轴带动所有盘面高速旋转,使得读写磁头可以访问到一个磁道上的所有扇区。 8.请简述对磁盘存储器进行一次读写操作的具体过程。
对磁盘存储器进行一次读写操作的具体步骤为: (a)根据待读写数据所处的柱面,用动臂将读写磁头移动到此柱面上。 (b)根据待读写数据所处的扇区,用主轴带动盘面将该扇区转到读写磁头下面。 (c)用指定盘面上的读写磁头读写所需数据。 9. 请简述在磁盘上存储信息的原则。 盘面的转速很快,磁盘读写数据的时间大部分花在柱面定位上。寻查时间的长短取决于 读写磁头移过的柱面数,所以在磁盘上存储信息时应尽量将相关的信息放在同一柱面或者邻 近柱面上,以减少寻查时间。 10. 请简述顺序文件的定义和分类。 顺序文件的定义: 顺序文件是结构最简单的文件,文件中记录的物理顺序与逻辑顺序一致,即记录按其逻 辑顺序依次存放在文件中。 顺序文件的分类: 按照存储方式的不同,顺序文件可以分为连续顺序文件和串联顺序文件。在连续顺序文 件中,全部记录顺序地存放在外存的一片连续存储空间中。连续顺序文件的优点是存取速度 快,缺点是存储空间尺寸需预先确定。在串联顺序文件中,以块为单位将记录存储在外存上, 块中的各记录顺序存放在一片连续存储空间中,但块与块之间可以不连续,通过链指针将各 块按一定顺序连接起来。串联顺序文件的优点是文件便于扩充,缺点是存取速度慢。 按照记录是否有序,顺序文件可以分为有序顺序文件和无序顺序文件。在有序顺序文件 中,全部记录按主关键字有序排列;在无序顺序文件中,记录按实际插入顺序排列。有序顺 序文件的优点是若记录定长则按主关键字检索时速度较快,无序顺序文件的优点是插入记录 时效率较高。 11. 请简述顺序文件批量处理的步骤。 将待处理的顺序文件称为主文件,主文件按主关键字大小顺序排列;对文件的插入、删 除、修改等操作请求全部放在事务文件中。根据事务文件中的操作对主文件进行更新生成新 的主文件,具体处理步骤如下: (a)对事务文件按照主文件中主关键字的顺序进行排序(对于修改主关键字值的操作, 应转为删除记录和插入记录两个操作)。 (b)顺序读出主文件与事务文件中的记录,比较它们的主关键字值: ① 若主文件记录的关键字值小于事务文件记录的关键字值,则说明没有对该主文件记 录做任何操作,此时将主文件记录直接写入新的主文件中,并读取下一条主文件记录。 ② 若关键字值相同,则依据事务文件记录进行更改或删除操作,若为删除操作,则主 文件记录不需要写入新的主文件中,若为修改操作则要将修改后的记录写入新的主文件中, 操作完毕后分别读取下一条主文件记录和事务文件记录。 ③ 若主文件记录的关键字值大于事务文件记录的关键字值,则为插入操作,需将事务 文件中的记录直接写入到新的主文件中,并读取下一条事务文件记录。 12. 请简述索引文件的构成。 索引文件由主文件和索引表两部分构成。主文件中存储了所有的数据记录;索引表是一 个映射关系表,存储了逻辑记录和物理记录的一一对应关系。

13. 请简述索引文件(即索引非顺序文件)和索引顺序文件的区别。 索引非顺序文件的主文件中各记录是无序的;索引顺序文件的主文件中各记录是按主关
键字有序排列的。 14. 请简述索引文件的检索过程。
索引文件的检索过程为: (a)将索引表读入内存中,并根据检索条件在索引表中进行查找(由于索引项按关键 字有序排列,因此在索引表上可以采用折半查找算法)。 (b)若索引表中存在匹配项,则根据匹配索引项中存储的物理地址直接读取外存上的 相应记录;若索引表中不存在该记录,则说明外存上也不存在该记录、不需做外存访问操作。 15. 请简述索引文件插入、删除、修改等维护操作的过程。 插入:在索引文件中插入一条新的记录时,直接将该记录写入主文件的末尾,并在索引 表中插入索引项。 删除:在删除一条记录时,只需在索引表中删除对应的索引项即可。 修改:在修改记录时,需将修改后的记录写入主文件的末尾,并同时对索引表进行修改、 将索引项中的物理地址改为修改后记录的存储地址。 16. 请简述稠密索引和稀疏索引的区别。 在索引非顺序文件中,记录没有按关键字有序排列,因此在建立索引表时,每个记录都 必须对应一个索引项,这样建立的索引表称为稠密索引。这类索引表虽然管理成本较高,但 它的优点是根据索引表即可确定待检索记录是否存在并可以根据索引项直接定位到记录,减 少了外存操作。 在索引顺序文件中,记录按关键字有序排列,因此可以对文件中的记录分块,每块对应 一个索引项,这样建立的索引表称为稀疏索引。在做检索操作时,这类索引表只能给出匹配 记录可能在哪个范围中,无法直接定位到记录,但它占用的存储空间小、便于管理。 17. 请简述 ISAM 文件的组织方法。 在 ISAM 文件中,每个柱面的磁道被分为 3 个部分: (a)一部分磁道作为记录存储的基本区,其中每一磁道将记录按主关键字大小进行有 序顺序存储。 (b)一部分磁道作为记录存储的溢出区,在一个已满磁道中插入新记录时,就会产生 溢出的记录(即该磁道容纳不下的记录),这些溢出记录以链表形式存储在溢出区中。 (c)一部分磁道作为索引区,用于存储磁道索引表。与基本区和溢出区相对应,表中 的每一索引项又由基本索引项和溢出索引项组成。基本索引项用来存放基本区一个磁道中记 录的最大关键字值和第一个记录的位置;溢出索引项用来存放从该磁道溢出记录的最大关键 字值和该磁道在溢出区中的第一个溢出记录的位置。 18. 请简述 VSAM 文件的组织方法。 VSAM 文件由索引集、顺序集和数据集三部分组成。文件的记录都存放在数据集中, 数据集中的每一个结点称为一个控制区间,该区间是一片连续的存储空间、按关键字顺序存 储若干条记录;顺序集中存放每一控制区间的索引项,索引项包括两部分内容:控制区间的 最大关键字值和指向该控制区间的指针,若干逻辑上相邻的控制区间的索引项就构成了顺序 集中的一个结点;索引集是按树型层次结构组织的索引集合,双亲结点包含了指向孩子结点 的指针及该孩子结点中的最大关键字值,以顺序集中的结点作为叶子结点,可以构造一棵以 索引集为非叶子结点的 B+树。 19. 请简述散列文件的组织方法。 散列文件中的记录是以桶为单位成组存放的。若一个桶能存放 m 条记录,则当桶中已 有 m 条同义词记录时,再存放第 m+1 条同义词记录就会发生“溢出”。在散列文件中,通

常采用拉链法作为冲突处理方法,即将第 m+1 条同义词记录存放到另一个称为“溢出桶” 的桶中,相应地,将存放前 m 条同义词记录的桶称为“基桶”,在基桶中设置一个指向溢 出桶的指针。 20. 请简述多关键字文件的作用。
多关键字文件是既包含主关键字索引、又包含多个次关键字索引的文件。在实际中,不 仅会根据主关键字做查找,同时也会根据一系列次关键字做查找,此时使用多关键字文件可 以提高查找效率。 21. 请简述多重表文件和倒排文件两种多关键字文件的组织方法。
多重表文件是将索引方法和链接方法相结合的一种文件组织方式,对主关键字建立的索 引称为主索引,对每个需做查询操作的次关键字建立的索引称为次索引。在多重表文件中, 记录通常按主关键字顺序排列,同时将具有相同次关键字值的记录链接成一个链表,并将此 链表的头指针、链表长度及次关键字作为对应次索引表中的索引项。
与多重表文件不同,倒排文件中具有相同次关键字的记录之间不进行链接,而是在对次 关键字建立的索引中列出具有该次关键字值的所有记录的物理地址。倒排文件中的次关键字 索引称为倒排表,倒排表与主文件一起就构成了倒排文件。 22. 请简述外排序与内排序的区别。
内排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列;而 外排序是指需进行多次内/外存之间的数据交换的排序过程,适合较大的元素序列。 23. 请简述归并排序的处理步骤。
归并排序的处理步骤为: (a)记录分段处理:将文件中的记录按照可用内存大小划分为若干段,依次将每段记 录读入到内存中对其进行内部排序,并将排序结果输出到子文件中。这样可以生成多个有序 的子文件(即文件内的记录是有序的),通常称经过排序后的段为初始归并段。 (b)文件归并处理:对上一步得到的初始归并段加以归并,直至将多段中的记录归并 为一个有序文件为止。 24. 请简述败者树的结构。 败者树的结构如下: (a)是一棵有 K 个叶子结点的完全二叉树。 (b)K 个叶子结点分别存储从 K 个初始归并段中读取出来的 K 个待比较的记录。 (c)分支结点存储两个记录比较后败者(即具有较大关键字值的记录)所在叶子结点 的序号,胜者参与更高一层的比较。 (d)通常在败者树的根结点之上再加一个结点来保存胜者(即当前 K 个记录中具有最 小关键字值的记录)所在叶子结点的序号。 (25)请简述败者树的重构方法和创建方法。 败者树的重构方法: 令 Loser[P]表示 P 号分支结点中保存的败者对应的叶子结点编号,若从第 Q(0≤Q<K) 个初始归并段中读取记录到序号为 Q 的叶子结点中,则败者树的重构过程如下: (a)计算编号为 Q 的叶子结点的双亲结点编号 P=?(Q+K)/2?,双亲结点中存储的是上 一轮比较中的败者 Loser[P(] 即 Q 号叶子结点的兄弟结点的编号),将 Q 号叶子结点与 Loser[P] 号叶子结点进行比较,若 Q 为胜者,则直接让 Q 参与更高一层的比较;否则,将 Q 作为败 者保存在 P 号分支结点中,并令 Q=Loser[P],即用 Q 保存胜者去参与更高一层的比较。 (b)计算 P 号分支结点的双亲结点,即 P=?P/2?,将 Q 号叶子结点与 Loser[P]号叶子结 点比较,同样,若 Q 为胜者,则直接让 Q 参与更高一层的比较;否则,将 Q 作为败者保存 在 P 号分支结点中,并令 Q=Loser[P],即用 Q 保存胜者去参与更高一层的比较。重复该步

骤直至到达胜者结点,即 P==0 时败者树重构完毕。 败者树的创建方法: 在败者树中添加一个编号为 K 的辅助叶子结点,该结点中的记录值为待排序记录不可
能达到的最小值 MI,令所有分支结点的初值均为 K(每插入一条记录就会有一个分支结点 的值由 K 变为 0~K-1 之间的值)。依次从 K 个初始归并段中读取第一条记录插入败者树中, 这样经过 K 次插入后,各分支结点的初始值 K 将被 0~K-1 所替代,此时即创建好了一棵败 者树。

第 10 章 算法设计策略及应用实例
1. 具有什么特征的问题适合用分治策略求解? 三个特征: (1) 原问题可以分解成规模较小、相互独立和类型相同的子问题; (2) 子问题的规模缩小到一定的程度,就不需要再分解,可以容易地求解; (3) 所有子问题的解能够合并成原问题的解。
2. 递归算法和迭代算法的区别是什么? 递归算法是利用函数直接或者间接调用自身来完成某个计算过程。为了求解规模为 n
的问题,设法将它分解成规模较小的问题,并能从规模较小的解构造出原问题的解。迭代法 根据问题规模为 i-1 的解,由问题的迭代性质,构造问题规模为 i 的解,最后得到规模为 n 的原问题的解。所以,递归算法是从大到小、从上到下地构造问题的解,而迭代算法是从小 到大、从下到上地构造或者逼近问题的解。 3. 具有什么性质的问题适合贪心策略求解?
具有如下性质:第一、最优子结构性质;第二、贪心选择性质。 4. 具有什么性质的问题适合动态规划策略求解?
具有如下性质:第一、最优子结构性质;第二、子问题重叠性质。 5. 贪心策略和动态规划策略之间的差别有哪些?
两种策略的不同之处在于,贪心策略做出的每步贪心选择都无法改变,因为贪心策略是 由上一步的最优解推导下一步的最优解,而上一步的最优解无需保留。动态规划策略的全局 最优解一定包括某个局部最优解,但是不一定包括前一个局部最优解,因此动态规划策略需 要保存之前的所有局部最优解。 6. 回溯策略和分支限界策略之间的差别有哪些?
回溯策略和分支限界策略的差别体现在以下方面:第一、分支限界策略没有限制树的搜 索方法,可以是广度优先搜索,也可以是最小成本搜索,而回溯策略采用的是深度优先搜索; 第二、分支限界策略只能用于优化问题,而回溯策略可以用于非优化问题,例如求问题的可 行解。
下午 13:00—17:00 度。全体员工都必须自觉遵守工作时间,实行不定时工作制的员工不必打卡。 3.1.2.2 打卡次数:一日两次,即早上上班打卡一次,下午下班打卡一次。 3.1.2.3 打卡时间:打卡时间为上班到岗时间和下班离岗时间;
3.1.2.4 因公外出不能打卡:因公外出不能打卡应填写《外勤登记表》,注明外出日期、事由、外勤起止时间。因公外出需事先申请,如因特殊情况不能事先申请,应在事毕到岗当日完成申请、
审批手续,否则按旷工处理。因停电、卡钟(工卡)故障未打卡的员工,上班前、下班后要及时到部门考勤员处填写《未打卡补签申请表》,由直接主管签字证明当日的出勤状况,报部门经理、
人力资源部批准后,月底由部门考勤员据此上报考勤。上述情况考勤由各部门或分公司和项目文员协助人力资源部进行管理。
3.1.2.5 手工考勤制度 3.1.2.6 手工考勤制申请:由于工作性质,员工无法正常打卡(如外围人员、出差),可由各部门提出人员名单,经主管副总批准后,报人力资源部审批备案。 3.1.2.7 参与手工考勤的员工,需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理,并于每月 26 日前向人力资源部递交考勤报表。 3.1.2.8 参与手工考勤的员工如有请假情况发生,应遵守相关请、休假制度,如实填报相关表单。 3.1.2.9 外派员工在外派工作期间的考勤,需在外派公司打卡记录;如遇中途出差,持出差证明,出差期间的考勤在出差地所在公司打卡记录; 3.2 加班管理 3.2.1 定义 加班是指员工在节假日或公司规定的休息日仍照常工作的情况。

A.现场管理人员和劳务人员的加班应严格控制,各部门应按月工时标准,合理安排工作班次。部门经理要严格审批员工排班表,保证员工有效工时达到要求。凡是达到月工时标准的,应扣减 员工本人的存休或工资;对超出月工时标准的,应说明理由,报主管副总和人力资源部审批。
B.因员工月薪工资中的补贴已包括延时工作补贴,所以延时工作在4小时(不含)以下的,不再另计加班工资。因工作需要,一般员工延时工作4小时至8小时可申报加班半天,超过8小 时可申报加班1天。对主管(含)以上管理人员,一般情况下延时工作不计加班,因特殊情况经总经理以上领导批准的延时工作,可按以上标准计加班。 3.2.2.2 员工加班应提前申请,事先填写《加班申请表》,因无法确定加班工时的,应在本次加班完成后 3 个工作日内补填《加班申请表》。《加班申请表》经部门经理同意,主管副总经理审核 报总经理批准后有效。《加班申请表》必须事前当月内上报有效,如遇特殊情况,也必须在一周内上报至总经理批准。如未履行上述程序,视为乙方自愿加班。 3.2.2.3 员工加班,也应按规定打卡,没有打卡记录的加班,公司不予承认;有打卡记录但无公司总经理批准的加班,公司不予承认加班。 3.2.2.4 原则上,参加公司组织的各种培训、集体活动不计加班。 3.2.2.5加班工资的补偿:员工在排班休息日的加班,可以以倒休形式安排补休。原则上,员工加班以倒休形式补休的,公司将根据工作需要统一安排在春节前后补休。加班可按1:1的比例冲 抵病、事假。 3.2.3 加班的申请、审批、确认流程 3.2.3.1《加班申请表》在各部门文员处领取,加班统计周期为上月 26 日至本月 25 日。 3.2.3.2员工加班也要按规定打卡,没有打卡记录的加班,公司不予承认。各部门的考勤员(文员)负责《加班申请表》的保管及加班申报。员工加班应提前申请,事先填写《加班申请表》加班 前到部门考勤员(文员)处领取《加班申请表》,《加班申请表》经项目管理中心或部门经理同意,主管副总审核,总经理签字批准后有效。填写并履行完审批手续后交由部门考勤员(文员)保 管。 3.2.3.3部门考勤员(文员)负责检查、复核确认考勤记录的真实有效性并在每月27日汇总交人力资源部,逾期未交的加班记录公司不予承认。

从群体上看,中专 毕业生的劣势是阅历较少、知识层次相对不高;优势是学校专业设置大多 贴近市场实际、贴近一线需要,且中专毕业生年青、肯吃苦、可塑性强。从个体来说,每位 毕业生的优势与长项又各不相同,如有相当一部分毕业生动手操作能力较好;有些学生非常 上进,上学期间还同时参加了职业资格考试或自学考试。所以,在实事求是,不弄虚作假的 前提下,要特别注意扬长避短,从而在竞争中取得优势,打动聘任者。没有重点和章法的写 作易使文章显得头绪不清、条理紊乱。

非常热爱市场销售
工作,有着十分饱满的创业激情。在××××两年从事现磨现煮的咖啡市场销售工作中积累了 大量的实践经验和客户资源。与省内主要的二百多家咖啡店铺经销商建立了十分密切的联 系,并在行业中拥有广泛的业务关系。在去年某省的咖啡博览会上为公司首次签定了海外的 定单。能团结自己的同事一起取得优异的销售业绩。

合理分配自我介绍的时间前文说过,自我介绍一般也就持续 1—3 分钟,所以应聘者得合理 分配时间。常规安排是:第一段用于表述个人基本情况,中段重点谈自己的工作经历或社会 实践经验,最后展望下自己的职位理想。但如果自我介绍被要求在 1 分钟完成,应聘者就 要有所侧重,突出最有料的一点。在实践中,有些应聘者试图在短短的时间内吐露自己的全 部经历,而有些应聘者则是三言两语就完成了自我介绍,这些都是不明智的做法。

突出和应聘职位相关的信息自我介绍的内容不宜太多的停留在诸如姓名、教育经历等部分 上,因为面试官可以在应聘者的简历上一目了然地看到这些内容。应聘者应该在自我介绍时 选择一至两项跟自己所应聘的职位相关的经历和成绩作简述,以证明自己确实有能力胜任所 应聘的工作职位。一个让人更有机会在面试中出彩的方法是在做一段自我介绍后适当停顿。 比如在“我曾在大学期间组织过有 2000 人参与的大型校园活动”之后的停顿可能会引导面试 官去问“那是什么样的活动呢?”,这样做的目的是为面试的深入打下基础。

一切以事实说话在证明自己确实有能力胜任所 应聘的工作职位时,应聘者可以
使用一些小技巧,如介绍自己做过的项目或参与过的活动来验证某种能力,也可以适当地引 用老师、同学、同事等第三方的言论来支持自己的描述。而这一切的前提是以事实为基础, 因为自吹自擂一般是很难逃过面试官的眼睛的,一旦被发现掺假,基本预示着应聘者将被无

情“秒杀”。 2×××年 5 月—至今: 担任某咖啡茶品配送服务部的市场部业务员。主要负责
与经销商签定经销合同、办理产品的包装、运输、保险、货款结算、售后产品跟踪、市场反 馈以及开拓新的销售渠道等。负责公司新业务员的培训,在实际工作中具体指导和协调业务 员的销售工作,并多次受到公司的表扬。


网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。3088529994@qq.com