《算法与数据结构考研试题精析》笔记(9) - 集合
Published:
by
Authur Lee
- Categories:
- Data_Structure 44
相关知识点链接：《Searching》
Static Search Table
例题：长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是多少？答案：5.
想象折半查找的判定树。最多比较次数也就是判定树的最大高度。而判定树为二叉树，可以类似于一棵“完全树”。故而由，可知判定树的最大高度为5层。
【推广】长度为n的顺序表L，其元素按关键字有序排列。若采用折半查找法找一个L中不存在的元素，则关键字的比较次数最多为
对于顺序查找，假定查找成功和不成功的可能性相等，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为0.75(n+1)。相关推理见博客Static Search Table。
如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用分块查找法(索引顺序查找)。
折半查找地平均查找长度为，若是n足够大，则可写为
。
【错误说法】有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
【错误原因】对于顺序查找顺序存储中的集合，对于查找成功的情况下平均查找长度相同；但是在查找不成功时，是否为有序表对平均查找长度是有影响的：有序表的平均查找长度较小，无序表较大。
【错误说法】对与满足折半查找和分块查找条件的文件而言，无论它存放在何种介质上，均能进行顺序查找、折半查找和分块查找。
【错误原因】磁带只能顺序查找，不能折半、分块查找。
在等概率情况下，对具有n个元素的顺序进行顺序查找，查找成功(即表中有关键字等于给定值K的记录)的平均查找长度为(n+1)/2；查找不成功的平均查找长度为n+1。
假定查找有序表A[1…12]中每个元素的概率都相等，则进行二分查找时的平均查找长度为37/12。
怎么做呢？一个一个列出来每个数字都需要比较几次才能被查找到？ 快速做法：类比完全二叉树(折半查找法的判定树和完全二叉树在某些方面有些类似，比如说树高之类)。 【做题详细过程】因为
，则
n个结点的用于折半查找的判定树，表示查找失败的外部结点共有(n+1)个。
长度为10的按关键字有序的查找表采用顺序存储，若使用折半查找法，则在等概率情况下，查找失败的ASL值是39/11。
【分析】同样用完全二叉树来分析。失败的虚结点相当于结点数为10的完全树的NULL指针。 因为
10 < 2^4-1，于是第四层的虚结数为(2^4-1)-10=5，第五层的虚结点数为2*(10-(2^3-1))=6，那么
分块查找时要求块内顺序存储，块间有序。
Dynamic Search Table
例题：若二叉平衡树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为(20)。
其中
表示高度为i、所有非叶结点的平衡因子均为1时的平衡二叉树结点总数。
m阶B树中，非叶结点分为如下两类：
- 根结点：最少两棵子树（关键字数为子树数减1）
- 非根结点：最少
棵子树（关键字数为子树数减1）
构造一棵具有n个结点的二叉排序树，最理想情况下的深度为。联想n个结点的二叉完全树的高度。
【如何判断一个序列是否是BST上查找的序列】若为BST的查找序列，则该序列上任一元素a后面元素的值，要么都比a小，要么都比a大。
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作(RL)型调整以使其平衡。
关于做如何调整，我们可以观察此博客中的四种平衡旋转图例。观察RR型和RL型平衡旋转，我们可以发现，此两种平衡旋转的原图都满足“A的左孩子BF为0，A的右孩子BF为1”。所以个人认为此种条件不足的情况下，RL型抑或是RR型调整都是有可能的。
关于B树和B+树的说法：
- B树和B+树都是平衡的二叉树；
- B树和B+树都可用于文件的索引结构；
- B树和B+树都能有效地支持随机索引；
- B+树支持顺序检索，而B树不行。
【错误说法】若在一棵(分类)平衡树T中先删除某结点N，然后再查入该结点N，得到新的平衡树T，则T和T1不一定相同。但是如果在T上先插入结点M，然后再删除M结点，那么得到的新的平衡树T2一定与T完全相同。
【错误原因】插入1，删除1.
3 2 2
/ -> / \ -> \
2 1 3 3
在二叉排序树上成功地找一个结点，在平均情况下的时间复杂度为O(logn)，在最坏情况下地时间复杂度为O(n)。
完全二叉树一定是AVL树。
这种命题，颇有争议。争议地纠结点在于“AVL树是否是BST”。如果AVL树的本质是BST，那么完全树不一定是AVL树；否则，完全二叉树一定是AVL树。 这里以Leetcode上的说法，认为AVL树仅与平衡因子BF有关。 （王道的数据结构中认为AVL树的本质是BST；清华的数据结构中没有明确表述，其将平衡的二叉搜索树称为BBST）
设高为h的m阶B树上共有k个关键字，则其叶子结点有k+1个。
具有n个关键字的B树的查找路径长度不会大于
B树的高度包括叶子结点那一层。
清华教材上为此说法。也有不包含叶子层的说法。
【2-3树】3阶的B-树上所有非终端结点至多可有两个关键字，至少可有一个关键字(即子树个数为2或3，故又称为2-3树)。
Hash Table
为了提高散列表的查找效率，可以采取的正确措施是：设计冲突(碰撞)少的散列函数。
“增大填装因子”或者“处理冲突时避免产生聚集(堆积)现象”都无法提高Hash表的查找效率。
会受堆积现象直接影响的是平均查找长度。
堆积现象不会直接影响存储效率、散列函数、填装因子。
理论上，散列表地平均比较次数为1次。
散列函数有一个共同的性质，即函数值当以同等概率取其值域的每个值。
采用链地址法解决冲突的哈希表中，查找成功的平均查找长度直接与哈希函数有关。
开放定址法的情况下，不能随便物理删除表中已有元素(如果删除元素，就会截断其他具有相同散列地址的元素的查找地址)。处理方法是给要删除的元素做一个删除标记，进行逻辑删除(这样做的副作用：执行多次删除操作之后，表面上看起来散列表很满，实际上有许多位置未利用，故而定期维护散列表，把有删除标记的元素物理删除)。
散列文件的特点是存取速度快，但占用的存储空间较多。
再哈希法不易产生聚集。
构造散列函数的方法之：移位叠加法、间接叠加法。链接跳转
散列表的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
【错误说法】随着填装因子a的增大，用闭散列法解决冲突，其平均搜索长度比用开散列法解决解决冲突时的平均搜索长度增长得慢。
在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希查找。
【处理哈希冲突的方法】开放定址法、拉链法、再哈希法、建立公共溢出区。
散列表的查找，要求线性表的存储方式是散列存储。
哈希表用关键字确定记录的存储位置。