数据结构_数据结构9
- 格式：ppt
- 大小：467.00 KB
- 文档页数：10
下载文档原格式
合集下载
数据结构第九章--查找-习题及答案
第九章查找一、选择题1•若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为()。
A ．(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度()A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) ：A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。
7. 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A ．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90) C. (100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。
《数据结构》_第9章 图
int edges[MAXV][MAXV]; int vexnum,arcnum; VertexType vexs[MAXV];
} MGraph;
9.2.2
邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结 合的存储方法。在邻接表中,对图中每个顶点建立一个单链 表,第i个单链表中的结点表示依附于顶点vi 的边(对有向图 是以顶点vi为尾的弧)。每个单链表上附设一个表头结点。 表结点和表头结点的结构如下： 表结点 advex nextarc info 表头结点
(2)在邻接表上查找相邻结点,找到后修改相应邻接矩阵元素 的值。算法如下： void ListToMat(ALGraph *G,MGraph &g) /*将邻接表G转换成邻接矩阵g*/ { int i,j,n=G->n;ArcNode *p; for (i=0;i<n;i++) /*g.edges[i][j]赋初值0*/ for (j=0;j<n;j++) g.edges[i][j]=0; for (i=0;i<n;i++) { p=G->adjlist[i].firstarc; while (p!=NULL) { g.edges[i][p->adjvex]=1; p=p->nextarc; } } g.vexnum=n;g.arcnum=G->e; }
(5)对于有向图,邻接矩阵的第i行(或第i列)非零元素(或 非∞元素)的个数正好是第i个顶点vi的出度(或入度)。 (6)用邻接矩阵方法存储图,很容易确定图中任意两个顶 点之间是否有边相连。但是,要确定图中有多少条边,则必须 按行、按列对每个元素进行检测,所花费的时间代价很大。 这是用邻接矩阵存储图的局限性。
数据结构教案第9章 查找
●性能分析 定义：为了确定记录在查找表中的位置，需和给定值进行比 较的关键字个数的期望值称为查找算法在查找成功时的平均查找 长度。
ASL = ∑ Pi C i
i =1
n
其中：Pi为查找表中第i个记录的概率；Ci为找到第i个记 录的比较次数； 查找成功的平均查找长度：
1 n n +1 ASL = ∑ (n − i + 1) = 2 n i =1
索引表 最大关键字 起始地址
22 48 86 1 7 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
9．2动态查找表 特点：表结构本身是在查找过程中动态生 成的，即对于给定值key，若表中存在其关键 字等于key的记录，则查找成功返回；否则插 入关键字等于key的记录。
10 10 9 15 9 17 17 15
a
16
作业：(P55)9.9, 9. 33
9．3哈希表 9．3．1什么是哈希表 哈希函数：在记录的关键字和它的存储位置之间建立 一个确定的对应关系f，使每个关键字和结构中一个 唯一的存储位置相对应，称对应关系f为哈希(Hash) 函数。 哈希表：按哈希函数建立的表称为哈希表。
void Delete(BiTree &p){ if(!p->rchild) { q=p; p=p->lchild; free(q); } else if(!p->lchild) { q=p; p=p->rchild; free(q); } else{ q=p; s=p->lchild; while(s->rchild) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; \*q！=p正常情况 else q->lchile= s->lchild; \* q=p意外者，p的左子树的根没有右子树 free(s); }\\else }
《数据结构》第九章作业参考答案
第九章查找9.3 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：判定树应当描述每次查找的位置：9.9已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
解：9.19解：H(22)=(3×22) mod 11=0 H(41)=(3×41) mod 11=2 H(53)=(3×53) mod 11=5 H(46)=(3×46) mod 11=6H(30)=(3×30) mod 11=2 冲突d1=(7×30) mod 10+1=1 H1（30）=(2+1)/11=3 H(13)=(3×13) mod 11=6 冲突d1=(7×13) mod 10+1=2 H1（13）=(6+2)/11=8 H(01)=(3×01) mod 11=3冲突d1=(7×1) mod 10+1=8 H1（01）=(3+8)/11=0冲突d2=2*（(7×1) mod 10+1）=16 H2（01）=（3+16）/11=8冲突d3=3*（(7×1) mod 10+1）=24 H3（01）=（3+24）/11=5冲突d4=4*（(7×1) mod 10+1）=32 H4（01）=（3+32）/11=2冲突d5=5*（(7×1) mod 10+1）=40 H5（01）=（3+40）/11=10H(67)=(3×67) mod 11=3冲突d1=(7×67) mod 10+1=10 H1（67）=（3+10）/11=2冲突d2=2*((7×67) mod 10+1)=20 H2（67）=（3+20）/11=1哈希表：ASL=(1+1+1+1+2+2+6+3)/8=17/8X。
数据结构第9章 排序
R[3] 10
R[4] 60
R[5] 25
R[6] 30
R[7] 18 18 18 18
18 36 20
10 10 36
60 60 60
25 25 25
30 30 30
【算法】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的 个数*/ for(i=2; i<=n; i++) if (R[i].key<R[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中， R[0]为监测哨*/ for(j=i-1; R[0].key<R[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } }
空间性能：除排序表以外的内存占用情况。 时间性能：比较关键码的次数，数据移动的次数。 它们往往是排序表规模（n）的函数
6. 记录和排序表的数据结构
一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数 typedef struct { keytype key; …… } datatype; datatype R[MAXNUM]; /*关键码字段*/ /*其它信息*/ /*记录类型*/ /*定义排序表的存储
第一趟排序结果，使得间隔为5的字表有序： P=3
29 7 41 30 11 39 50 76 41 13 10 0 80 78 86
子序列分别为:{29,30,50,13,78}，{7,11,76,100,86}， {41,39,41,80}。第二趟排序结果： P=1
第9章 数据结构
数据项：数据项是数据的不可分割的最小标识单位。数据元素是由若
干个数据项组成的。 如：书名、书号、作者名称为数据元素的数据项
数据结构
数据结构概述： 数据结构概述：
数据结构是由一个逻辑结构S，一个定义在S上的基本运算 集△和一个存储实现D所构成的整体（S，△，D）。 数据结构包括逻辑结构 基本运算 逻辑结构和基本运算 逻辑结构 基本运算两部分： •逻辑结构是用来完成数据表示的 •基本运算是用来完成数据处理的。
M
栈顶 top→ 入栈 退栈 ↓ ↑ an a2 栈底 bottom→ a1
队列的基本概念
队列（queue） 队列（queue）是指允许在一端进行插入而在另一端进行删除 的线性表。 允许插入的一端称为队尾 允许删除的一端称为排头（也称为队头） 显然，在队列这种数据结构中，最先插入的元素将最先能够 被删除，最后插入的元素将最后被删除。因此，队列又称为 “先进先出”（First In First Out，FIFO）或“后进后出” 先进先出” Out，FIFO）或“后进后出” （Last In Last Out，LILO）的线性表。 Out，LILO）的线性表。
数据的逻辑结构基本概念
数据的逻辑结构有两个要素： 数据的逻辑结构有两个要素： 逻辑结构有两个要素 一是数据元素的集合，通常记为D 一是数据元素的集合，通常记为D； 二是据元素之间的前后件关 通常记为R 系，通常记为R。
逻辑结构—线性结构和非线性结构
第9章 数据结构
教学目的
•了解数据结构的基本概念 •了解数据的逻辑结构和存储结构 •了解栈、队列及线性链表的概念及运算 了解栈、
数据结构的基本概念
数据、 数据、数据元素和数据项 数据结构 数据的逻辑结构
数据结构类型
大学数据结构课件--第9章 查找
——这种既查找又插入的过程称为动态查找。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p
数据结构第9章作业 查找答案
第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m-1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
数据结构第9章 排序
数据结构第9章排序数据结构第9章排序第9章排名本章主要内容：1、插入类排序算法2、交换类排序算法3、选择类排序算法4、归并类排序算法5、基数类排序算法本章重点难点1、希尔排序2、快速排序3、堆排序4.合并排序9.1基本概念1.关键字可以标识数据元素的数据项。
如果一个数据项可以唯一地标识一个数据元素，那么它被称为主关键字；否则，它被称为次要关键字。
2．排序是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。
如果排序依据的是主关键字，排序的结果将是唯一的。
3.排序算法的稳定性如果要排序的记录序列中多个数据元素的关键字值相同，且排序后这些数据元素的相对顺序保持不变，则称排序算法稳定，否则称为不稳定。
4.内部排序与外部排序根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。
内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放在内存中，另一部分放在外围设备上。
整个排序过程需要在内存和外存之间进行多次数据交换才能得到排序结果。
本章仅讨论常用的内部排序方法。
5.排序的基本方法内部排序主要有5种方法：插入、交换、选择、归并和基数。
6.排序算法的效率评估排序算法的效率主要有两点：第一，在一定数据量的情况下，算法执行所消耗的平均时间。
对于排序操作，时间主要用于关键字之间的比较和数据元素的移动。
因此，我们可以认为一个有效的排序算法应该是尽可能少的比较和数据元素移动；第二个是执行算法所需的辅助存储空间。
辅助存储空间是指在一定数据量的情况下，除了要排序的数据元素所占用的存储空间外，执行算法所需的存储空间。
理想的空间效率是，算法执行期间所需的辅助空间与要排序的数据量无关。
7.待排序记录序列的存储结构待排序记录序列可以用顺序存储结构和和链式存储结构表示。
在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。
图解数据结构9左偏树
十三、左偏树（Leftist Tree）树这个数据结构内容真的很多，上一节所讲的二叉堆，其实就是一颗二叉树，这次讲的左偏树（又叫“左翼堆”），也是树。
二叉堆是个很不错的数据结构，因为它非常便于理解，而且仅仅用了一个数组，不会造成额外空间的浪费，但它有个缺点，那就是很难合并两个二叉堆，对于“合并”，“拆分”这种操作，我觉得最方面的还是依靠指针，改变一下指针的值就可以实现，要是涉及到元素的移动，那就复杂一些了。
左偏树跟二叉堆比起来，就是一棵真正意义上的树了，具有左右指针，所以空间开销上稍微大一点，但却带来了便于合并的便利。
BTW：写了很多很多的程序之后，我发觉“空间换时间”始终是个应该考虑的编程方法。
:)左偏左偏，给人感觉就是左子树的比重比较大了，事实上也差不多，可以这么理解：左边分量重，那一直往右，就一定能最快地找到可以插入元素的节点了。
所以可以这样下个定义：左偏树就是对其任意子树而言，往右到插入点的距离（下面简称为“距离”）始终小于等于往左到插入点的距离，当然了，和二叉堆一样，父节点的值要小于左右子节点的值。
如果节点本身不满，可插入，那距离就为0，再把空节点的距离记为-1，这样我们就得出：父节点的距离= 右子节点距离+ 1，因为右子节点的距离始终是小于等于左子节点距离的。
我把距离的值用蓝色字体标在上图中了。
左偏树并一定平衡，甚至它可以很不平衡，因为它其实也不需要平衡，它只需要像二叉堆那样的功能，再加上合并方便，现在来看左偏树的合并算法，如图：这种算法其实很适合用递归来做，但我还是用了一个循环，其实也差不多。
对于左偏树来说，这个合并操作是最重要最基本的了。
为什么？你看哦：Enqueue，我能不能看作是这个左偏树的root和一个单节点树的合并？而Dequeue，我能不能看作是把root节点取出来，然后合并root的左右子树？事实上就是这样的，我提供的代码就是这样干的。
Conclusion：左偏树比同二叉堆的优点就是方便合并，缺点是编程复杂度略高（也高不去哪），占用空间稍大（其实也大不去哪）。
数据结构 实验9 哈希查找
数据结构实验9 哈希查找实验9：哈希查找一、实验目的本实验旨在掌握哈希查找算法的原理、实现方法和应用场景，通过实际操作加深对哈希查找的理解。
二、实验内容本实验包括以下几个部分：⒈哈希查找的原理介绍⑴哈希函数的定义⑵哈希表的构建⑶哈希冲突的处理方法⒉哈希查找的实现方法⑴开放定址法⑵链地质法⑶再哈希法⑷其他哈希方法（可根据需要添加）⒊哈希查找的应用场景⑴字典查找⑵关键词过滤⑶地质映射⑷其他应用场景（可根据需要添加）⒋实验步骤⑴初始化哈希表⑵插入关键字⑶查找关键字⑷删除关键字⑸哈希表的扩容⑹其他操作（可根据需要添加）⒌实验数据分析对比不同哈希方法在不同数据规模下的查找效率、空间利用率等指标，分析结果并给出结论。
三、实验结果与讨论（在此部分添加实验结果的展示，包括各种操作的执行结果、性能指标的分析等）四、实验总结（在此部分总结实验过程中遇到的问题、解决方法，以及对哈希查找算法的理解和应用等方面进行总结）附件：（在此添加实验所需的附件，如代码文件、测试数据等）法律名词及注释：⒈哈希函数：一种将任意长度的输入转换成固定长度输出的函数，常用于数据加密和查找算法中。
⒉哈希表：一种以键-值对形式存储数据的数据结构，通过哈希函数将关键字映射到表中的位置实现快速查找。
⒊哈希冲突：当不同关键字经过哈希函数计算得到相同的哈希地质时发生的情况，需要通过冲突处理方法解决。
⒋开放定址法：一种解决哈希冲突的方法，当发生冲突时，通过一系列的计算实现关键字的再散列。
⒌链地质法：一种解决哈希冲突的方法，将哈希地质相同的关键字存储在同一个链表中。
⒍再哈希法：一种解决哈希冲突的方法，通过使用不同的哈希函数进行再散列。
（可根据需要添加其他法律名词及注释）。
数据结构.第9章.查找.4.哈希表
§9.3 哈希表
开放地址法
例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表： 0 1
11 22
2
3
4
5
6
3
7
7
8
29
9
8
10
47 92 16
§9.3 哈希表
开放地址法
选用关键字的某几位组合成哈希地址。
选用原则应当是：各种符号在该位上出现的频率大致
相同。
适于关键字位数比哈希地址位数大，且可能出现的关 键字事先知道的情况。
§9.3 哈希表
数字分析法
例：有一组（例如80个）关键码，其样式如下： 讨论： 3 4 7 0 5 2 4 ① 第1、2位均是“3和4”，第3位也只有 3 4 9 1 4 8 7 3 4 8 2 6 9 6 “ 7、8、9”，因此，这几位不能用，余 3 4 8 5 2 7 0 下四位分布较均匀，可作为哈希地址选用。 3 4 8 6 3 0 5 ② 若哈希地址取两位（因元素仅80个）， 3 4 9 8 0 5 8 则可取这四位中的任意两位组合成哈希地 3 4 7 9 6 7 1 址，也可以取其中两位与其它两位叠加求 3 4 7 3 9 1 9 和后，取低两位作哈希地址。 位号：① ② ③ ④ ⑤ ⑥ ⑦
拟用二次探测法处理冲突。建哈希表如下： Hi = ( H(K)+di ) mod m 其中di =12, -12, 22,-22,…, j2, -j2 ( j≤m/2)。
0 1
11 22
2
3
3
4
5
6
7
数据结构 第9章 查找3-B树
∧ 20 20 40 ∧ ∧ 40 ∧ ∧ 60∧60∧90∧ ∧ ∧ ∧ ∧ 60∧80∧ ∧ ∧ ∧ ∧ ∧ ∧ 8080 ∧90∧ ∧
插入关键字 = 60, 90, 30
2、B-树的删除
在深度为(h+l)的m阶B-树中删除一个键值k,首先要查 到键值k所在的结点及在结点中的位置。若k在非终端 节点中，则把该结点的右边(或左边)指针所指子树中 的最小(或最大)键值与k对调，使k移到终端节点。 在终端节点中删除一个键值后,使得该结点的值个数n 减1,此时应分以下三种情况进行处理： – (1)若删除后结点中键值数目n≥ ┌m/2┐－1,在该结点 中删去键值k连同右边的指针。 – (2)若删除后结点中键值数目n< ┌m/2┐ －1,且左(或 右)兄弟结点的关键字数目＞ ┌m/2┐－1,则把左(或 右)兄弟结点中最大(或最小)键值移到父结点中,再 把父结点大于(或小于)上移键值的键值下移到被删 关键字所在结点中。
(3)若删除后结点中键值数目n< ┌m/2┐ －1,及 其左、右兄弟结点的键值数目都等于┌m/2┐ －1,则就必须进行结点的“合并”,即把应删 的键值删去后,将该结点中的剩余键值和指针 连同父结点中指向该结点指针的左边(或右边) 一个键值ki一起合并到左兄弟(或右兄弟)结点 中,将ki从父结点中删去。如果因此使父结点 中关键字数目< ┌m/2┐－1,则对此父结点做同 样处理,以致于可能直到对根结点做这样的处 理而使整个树减少一层。
２．查找性能的分析
在B-树中进行查找时，其查找时间 主要花费在搜索结点（访问外存）上， 即主要取决于B-树的深度 树的深度。 树的深度
问：含 N 个关键字的 m 阶 B-树可 能达到的最大深度 H 为多少？
反过来问： 深度为H的B-树中， 至少含有多少个结点？ 先推导每一层所含最少结点数： 第1层 第2层 第3层 第4层 … … 第 H+1 层 1个 2个 2×m/2 个 × 2×(m/2)2 个 × 2×(m/2) H-1 个 ×
插入关键字 = 60, 90, 30
2、B-树的删除
在深度为(h+l)的m阶B-树中删除一个键值k,首先要查 到键值k所在的结点及在结点中的位置。若k在非终端 节点中，则把该结点的右边(或左边)指针所指子树中 的最小(或最大)键值与k对调，使k移到终端节点。 在终端节点中删除一个键值后,使得该结点的值个数n 减1,此时应分以下三种情况进行处理： – (1)若删除后结点中键值数目n≥ ┌m/2┐－1,在该结点 中删去键值k连同右边的指针。 – (2)若删除后结点中键值数目n< ┌m/2┐ －1,且左(或 右)兄弟结点的关键字数目＞ ┌m/2┐－1,则把左(或 右)兄弟结点中最大(或最小)键值移到父结点中,再 把父结点大于(或小于)上移键值的键值下移到被删 关键字所在结点中。
(3)若删除后结点中键值数目n< ┌m/2┐ －1,及 其左、右兄弟结点的键值数目都等于┌m/2┐ －1,则就必须进行结点的“合并”,即把应删 的键值删去后,将该结点中的剩余键值和指针 连同父结点中指向该结点指针的左边(或右边) 一个键值ki一起合并到左兄弟(或右兄弟)结点 中,将ki从父结点中删去。如果因此使父结点 中关键字数目< ┌m/2┐－1,则对此父结点做同 样处理,以致于可能直到对根结点做这样的处 理而使整个树减少一层。
２．查找性能的分析
在B-树中进行查找时，其查找时间 主要花费在搜索结点（访问外存）上， 即主要取决于B-树的深度 树的深度。 树的深度
问：含 N 个关键字的 m 阶 B-树可 能达到的最大深度 H 为多少？
反过来问： 深度为H的B-树中， 至少含有多少个结点？ 先推导每一层所含最少结点数： 第1层 第2层 第3层 第4层 … … 第 H+1 层 1个 2个 2×m/2 个 × 2×(m/2)2 个 × 2×(m/2) H-1 个 ×
数据结构 第9章 查找4-哈希表
7、随机数法 Hash(key) = random ( key ) (random为伪随机函数)
适用于：关键字长度不等的情况。造表和查找都很方便。
小结：构造哈希函数的原则：
① ② ③ ④ ⑤ 执行速度（即计算哈希函数所需时间）； 关键字的长度； 哈希表的大小； 关键字的分布情况； 查找频率。
三、冲突处理方法
14 H(14)=14%7=0
6个元素用7个 地址应该足够!
1
2
23 9
3
4
39 25 11
5
6
H(25)=25%7=4 H(11)=11%7=4
有冲突！
在哈希查找方法中，冲突是不可能避免的，只能 尽可能减少。
所以，哈希方法必须解决以下两个问题：
1）构造好的哈希函数
（a）所选函数尽可能简单，以便提高转换速度； （b）所选函数对关键码计算出的地址，应在哈希地址集中 大致均匀分布，以减少空间浪费。
讨论：如何进行散列查找？
根据存储时用到的散列函数H(k)表达式，迅即可查到结果！ 例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。
缺点：空间效率低！
若干术语
哈希方法 (杂凑法)
选取某个函数，依该函数按关键字计算元素的存储位置， 并按此存放；查找时，由同一个函数对给定值k计算地址， 将k与地址单元中元素关键码进行比较，确定查找是否成 功。
3. 乘余取整法
4. 数字分析法
5. 平方取中法
常用的哈希函数构造方法有：
6. 折叠法
7. 随机数法
1、直接定址法
(a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址， 不会产生冲突. 缺点：要占用连续地址空间，空间效率低。
《数据结构》第九章习题 参考答案
《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、快速排序是一种稳定的排序方法。
（×）2、在任何情况下，归并排序都比简单插入排序快。
（×）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
（√）4、内排序要求数据一定要以顺序方式存储。
（×）5、直接选择排序算法在最好情况下的时间复杂度为O（n）。
( ×)6、快速排序总比简单排序快。
( ×)二、单项选择题1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）。
A．直接插入排序B．直接选择排序C．快速排序D．归并排序2．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．折半插入排序C．希尔排序D．快速排序3、比较次数与排序的初始状态无关的排序方法是( B)。
A．直接插入排序B．起泡排序（时间复杂度O（n2））C．快速排序D．简单选择排序4、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是( A)。
A. 选择B. 冒泡C. 快速D. 插入5、快速排序方法在（D）情况下最不利于发挥其长处。
A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序6、用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序，各趟排序结束时的结果为：（基准）20，21，15，25，84，27，68，35，47（25）15，20，21，25，47，27，68，35，84（左20右47）15，20，21，25，35，27，47，68，84（左35右68）15，20，21，25，27，35，47，68，84 ；则采用的排序方法为（C）。
数据结构_第9章_查找2-二叉树和平衡二叉树
F
PS
C
PR
CL Q
QL SL S SL
10
3
18
2
6 12
6 删除10
3
18
2
4 12
4
15
15
三、二叉排序树的查找分析
1) 二叉排序树上查找某关键字等于给定值的结点过程，其实 就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 log2 n+1
-0 1 24
0 37
0 37
-0 1
需要RL平衡旋转 (绕C先顺后逆）
24
0
-012
13
3573
0
01
37
90
0 53 0 53
0 90
作业
已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
(1) 试按表中元素的顺序依次插入一棵初始为空的二叉 排序树，画出插入完成之后的二叉排序树，并求其在 等概率的情况下查找成功的平均查找长度。
2) 一棵二叉排序树的平均查找长度为：
n i1
ASL 1
ni Ci
m
其中：
ni 是每层结点个数； Ci 是结点所在层次数； m 为树深。
最坏情况：即插入的n个元素从一开始就有序， ——变成单支树的形态！
此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。
最好情况：即：与折半查找中的判ห้องสมุดไป่ตู้树相同（形态比较均衡） 树的深度为：log 2n +1 ； ASL=log 2(n+1) –1 ；与折半查找相同。
数据结构-第9章 查找
静态查找表 对查找表的查找仅是以查询为 目的，不改动查找表中的数据。 动态查找表 在查找的过程中同时插入不存 在的记录，或删除某个已存在的记录。
查找成功 查找表中存在满足查找条件的记 录。 查找不成功 查找表中不存在满足查找条件 的记录。
内查找 整个查找过程都在内存中进行。 外查找 在查找过程中需要访问外存。 平均查找长度ASL——查找方法时效的度量 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。 n 查找成功时的ASL计算方法： ASL pici
3. 在二叉排序树上的操作
1)查找
[例] Key=28 f 24 12 T
45
53 28 90
Key=32 T 45 24 53 12 f 28 90 32
[算法描述]
2) 插入
[算法描述]
3) 生成
查找算法
返回
BiTree SearchBST(BiTree T,KeyType key){
//在根指针T所指二叉树中递归地查找某关键字等于 //key的数据元素,若查找成功,则返回指向该数据元 //素结点的指针,否则返回空指针
图9.1 用折半查找法查找12、50的过程 其中mid=(low+high)/2，当high<low时，表 示不存在这样的子表空间，查找失败。
成功！ 位 置 1 2 3 4 5 6 7 8 9 10 11
值
6 12 15 18 22 25 28 35 45 58 60
low hign mid mid hign mid low mid (a) 用折半查找法查找12的过程
[性能分析] • 空间：一个辅助空间。 • 时间： 查找成功时的平均查找长度 设表中各记录查找概率相等 n ASLs(n)= PiCi =(1+2+ ... +n)/n =(n+1)/2 i 1 [算法特点] • 算法简单，对表结构无任何要求 • n很大时查找效率较低 • 改进措施：非等概率查找时，可将查找概率高 的记录尽量排在表后部。
数据结构第9章习题
试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉 链表作存储结构。且树中结点的关键字均不同。 bool BiSortTree( BiTree t ) // 以二叉链表作二叉查找树的存储结构,若以 t 为根 // 指针的二叉树是二叉查找树，则返回 true, 否则返回 false
Data Structure
Data Structure
2015/10/21
Page 3
已知如下所示长度为12的表 (Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec)
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画 出插入完成之后的二叉排序树，并求其在等概率的情况下查找成 功的平均查找长度。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此 有序表进行折半查找时查找成功的平均查找长度。
按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情 况下查找成功的平均查找长度。
Data Structure
2015/10/21
Page 4
可以生成下方二叉排序树的关键字初始排列有几种？请写 出其中的任意三个。
Data Structure
2015/10/21
Page 5
选取哈希函数 H(k)=(3k) MOD 11。用开放定址法处理冲 突，di = i((7k) MOD 10+1) (i=1,2,3,…)。试在 0～ 10 的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概情况下查找成功时 的平均查找长度。
数 据 结 构
计算机科学与技术学院
基础知识题
若对大小均为 n 的有序的顺序表和无序的顺序表分别进 行顺序查找，试在下列三种情况下分别讨论两者在等概时 的平均查找长度是否相同?
Data Structure
Data Structure
2015/10/21
Page 3
已知如下所示长度为12的表 (Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec)
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画 出插入完成之后的二叉排序树，并求其在等概率的情况下查找成 功的平均查找长度。 若对表中元素先进行排序构成有序表，求在等概率的情况下对此 有序表进行折半查找时查找成功的平均查找长度。
按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情 况下查找成功的平均查找长度。
Data Structure
2015/10/21
Page 4
可以生成下方二叉排序树的关键字初始排列有几种？请写 出其中的任意三个。
Data Structure
2015/10/21
Page 5
选取哈希函数 H(k)=(3k) MOD 11。用开放定址法处理冲 突，di = i((7k) MOD 10+1) (i=1,2,3,…)。试在 0～ 10 的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概情况下查找成功时 的平均查找长度。
数 据 结 构
计算机科学与技术学院
基础知识题
若对大小均为 n 的有序的顺序表和无序的顺序表分别进 行顺序查找，试在下列三种情况下分别讨论两者在等概时 的平均查找长度是否相同?
数据结构第九章--查找-习题及答案
第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 55．当采用分块查找时，数据的组织方式为 ( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:A. 相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D. (100，80， 60， 90， 120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。