《数据结构C语言版查找》由会员分享，可在线阅读，更多相关《数据结构C语言版查找（10页珍藏版）》请在金锄头文库上搜索。
1、文档供参考，可复制、编制，期待您的好评与关注！ 第八章 查找重点难点要求理解查找表的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。典型例题1. 若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的
2、平均查找长度：(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查找失败时，最多的
3、关键字比较次树不超过判定树的深度，此处为5.3.为什么有序的单链表不能进行折半查找? 【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。4. 设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元
4、也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。新结点总是作为叶子插入在二叉排序树中的。5. 在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。若删去某结点中一个关键字而导致结点合并时，该结点中原有m/2-1个关键字。6. 设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，
5、33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么?答：(1)拉链法如下图： T0.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 T0.10331 131234382722 探查次数 1 1 1 3 4 1 7 8 用拉链法的查找成功平均查找长度为： ASLsucc=(1*4+2*3+3*1)/8=1.625 查找失败时平均查找长度为： ASLunsucc=
6、(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.737. 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。【解】由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结
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-datalchild-data) return -1;/不是二叉排序树else EnQueue(&Q,p-lchild);if (
8、p-rchild)if (p-datap-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视应用情况而定
9、，下面不处理它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(%d,T-key);OUTPUTNODE( T-Lchild,x);习题精选1选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。A(n-1)/2 B n/2 C(n+1)/2 Dn （2）
10、适用于折半查找的表的存储方式及元素排列要求为（ ）。 A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。 A必定快 B不一定 C在大部分情况下要快 D取决于表递增还是递减（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（5）对22个记录的有序表作折半查找，当
11、查找失败时，至少需要比较（ ）次关键字。A3 B4 C5 D6（6）折半搜索与二叉排序树的时间性能（ ）。 A相同 B完全不同 C有时不相同 D数量级都是O(log2n)（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 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)（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子
12、的平衡因子为1，则应作（ ）型调整以使其平衡。ALL BLR CRL DRR（9）下列关于m阶B-树的说法错误的是（ ）。 A根结点至多有m棵子树 B所有叶子都在同一层次上C非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D根结点中的数据是有序的（10）下面关于B-和B+树的叙述中，不正确的是（ ）。 AB-树和B+树都是平衡的多叉树 BB-树和B+树都可用于文件的索引结构CB-树和B+树都能有效地支持顺序检索 DB-树和B+树都能有效地支持随机检索（11）m阶B-树是一棵（ ）。Am叉排序树 Bm叉平衡排序树 Cm-1叉平衡排序树 Dm+1叉平衡排序树（12）下面关于哈希查找的说法，正确的是（ ）。 A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定D哈希表的平均查找长度有时也和记录总数有关（13）下面关于哈希查找的说法，不正确的是（ ）
