第八章 查找
重点难点
要求理解\查找表\的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
典型例题
1. 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
(1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。
【解】 查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。
查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。
2. 画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解】
等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556
查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 3.为什么有序的单链表不能进行折半查找?
【解】 因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。
4. 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。
新结点总是作为叶子插入在二叉排序树中的。
5. 在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字? 【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。
若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。 6. 设散列表长度为11，散列函数h(x)=x,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答：
(1)拉链法如下图：
T[0..10] ┌──┐
0│ │→ 33 → 22 →∧ ├──┤
1│ │→ 1 → 12 →34→ ∧ ├──┤
2│ │→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤
5│ │→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│ ∧ │
├──┤ 8│ ∧ │ ├──┤ 9│ ∧ │ ├──┤ 10│ ∧ │ └──┘
(2)线性探查法如下图：
下
标 0 1 2 3 4 5 6 7 8 9 10 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ T[0..10]│33│1 │13│12│34│38│27│22│ │ │ │ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ 探查次数 1 1 1 3 4 1 7 8
用拉链法的查找成功平均查找长度为： ASLsucc=(1*4+2*3+3*1)/8=1.625 查找失败时平均查找长度为：
ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73 用线性探查法查找成功时平均查找长度为： ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25 查找失败时平均查找长度为：
ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3 装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73
7. 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。
【解】 由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。
typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针 int BinSortStree(BinTree T) {
CirQueue Q; BinTNode *p;
if (!T) return 1;//空树为二叉排序树 InitQueue(&Q); EnQueue(&Q,T); while(!QueueEmpty(&Q)) {
p=DeQueue(&Q); if (p->lchild)
if (p->data
if (p->data>p->rchild->data) return -1;//不是二叉排序树 else EnQueue(&Q,p->rchild); }
return 1;//是二叉排序树 }
8. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。
typedef int KeyType； //假定关键字类型为整数 typedef struct node { //结点类型 KeyType key； //关键字项
InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它 struct node *lchild，*rchild； //左右孩子指针 } BSTNode；
typedef BSTNode *BSTree；
void OUTPUTNODE(BSTree T,KeyType x)
{//从大到小输出二叉排序树中所有其值不小于x的关键字 if (T) {
OUTPUTNODE( T->rchild,x);
if (T->key>=x) printf(\ OUTPUTNODE( T->Lchild,x); } }
习题精选 1．选择题
（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
A．(n-1)/2 B． n/2 C．(n+1)/2 D．n （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。
A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A．必定快 B．不一定
相关推荐：
loading