折半查找和二叉排序树的时间性能_折半查找和二叉排序树的时间性能

【音频带背】数据结构考前必背简答题系列（四）：查找与排序　　抓码计算机考研将陆续推出数据结构、计网、计组、操作系统的必背文本及音频，文本由抓码专业团队的学长姐精心梳理，单篇推送后会推出PDF合集，帮助正在冲刺备考的你提高学习效率。　　此外，抓码运营小组将根据你的需求制作音频或视频带背，方便大家利用碎片化时间随时随地回顾知识点，以更多形式帮助你更好地冲刺备考。　　1.顺序查找　　

　　2.折半查找　　前提：有序的顺序表　　查找成功：　　查找失败：　　3.分块查找　　查找成功（索引表和块内采用顺序查找）：　　（b为分块的数目，s为一块内素的个数）　　查找成功（索引表采用折半查找）：　　

　　（b为分块的数目，s为一块内素的个数）　　4.顺序表顺序查找、折半查找、分块查找的3种查找方法比较：　　上述3种查找方法的比较如下: 　　❶就平均查找长度而言，折半查找的平均查找长度取小，分块查找次之，顺序查找最大。　　❷就表的结构而言，顺序查找对有序表、无序表均适用，折半查找仅适用于有序表，而分块查找要求表中素至少是分块有序的。　　❸就表的存储结构而言，顺序查找和分块查找可以适用于顺序表和链表两种存储结构,而折半查找只适用于以顺序表作为存储结构的表。　　❹分块查找综合了顺序查找和折半查找的优点，既能较快速地查找，又能适应动态变化的要求。　　5.对长度为2k-1的有序表进行折半查找，在成功查找时，最少需要多少次关键字比较?最多需要多少次关键字比较?查找失败时的平均比较次数是多少? 　　当查找的记录正好处于中间位置时，关键字比较次数最少，所以折半查找在成功查找时最少需要1次关键字比较。　　折半查找在成功查找时最多关键字比较次数为判定树的高度，即 log2(2k-1+1) = k。折半查找在不成功查找时比较过程都落在外部节点中，将判定树看成是一棵满二叉树，所有外部节点的高度为k+1，其关键字比较次数为k，所以查找失败时的平均比较次数是k 次。　　6.散列表　　查找成功：比较次数/表长　　查找失败：查找失败时的比较次数/（mod后的数字）　　决定散列表查找的ASL的因素：　　❶选用的散列函数; 　　❷选用的处理冲突的方法; 　　❸散列表饱和的程度，即装填因子的大小。（装填因子是指散列表中已存入的记录数ｎ与散列表长度ｍ的比值，单独凭n或m不构成影响ASL的因素）　　7.B树与B+树的不同点　　❶在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树;而在B树中，具有n个关键字的结点含有n+1棵子树。　　❷在B+树中，每个结点(非根内部结点)的关键字个数n的范围是［m/2］≤n≤m (根结点:1≤n≤m);在B树中，每个结点(非根内部结点)的关键字个数n的范围是［m/2］ -1≤n≤m-1 (根结点: l≤n≤m-1)。　　❸在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只　　含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。　　❹在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中;而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。　　❺B+树查找时是从上到下查找；B-树则是从下往上查找（中序遍历）。　　8.简述平衡二叉树中插入新节点导致不平衡进行调整的4种形态。　　在平衡二叉树中插入新节点可能导致不平衡，调整成平衡二叉树的4种形态如下。　　LL型调整:在节点的左子树的左子树上插入新节点导致不平衡。　　RR型调整:在节点的右子树的右子树上插入新节点导致不平衡。　　LR型调整:在节点的左子树的右子树上插入新节点导致不平衡。　　RL型调整:在节点的右子树的左子树上插入新节点导致不平衡。　　9.红黑树的定义与性质　　

　　10.排序算法时间性能对比　　按平均的时间性能来分，有三类排序方法：　　时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序　　时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序　　时间复杂度为O(d(n+r))的排序方法只有基数排序。　　11.哪些排序算法会受初始关键字分布的影响？　　当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。　　另外，简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。　　12.哪些排序算法会受初始关键字分布的影响？　　❶所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；　　❷快速排序为O(logn)，为栈所需的辅助空间; 　　❸归并排序所需辅助空间最多，其空间复杂度为O(n); 　　❹链式基数排序需要队列，则空间复杂度为O(r)。　　13.排序算法的稳定性　　❶稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。　　❷对于不稳定的排序方法，只要能举出一个实例说明即可。　　❸快速排序、简单选择排序、堆排序和希尔排序是不稳定的排序方法。　　14.排序算法的比较　　

　　15.比较直接插入排序算法和希尔排序算法的不同点　　直接插入排序算法是稳定的，更适合于原始素基本有序的情况。若采用折半查找而不是顺序查找待插入素的插入位置时，可减少素比较的次数，但移动素的次数没有减少;在采用顺序查找待插入素的插入位置时也适用于链式存储结构。　　希尔排序算法是不稳定的;素的总比较次数和移动次数都比直接插入排序时要少，n越大时，效果越明显;增量序列d可以有不同的取法，但有两个共同的特征，即最后一个增量必须是1，增量序列中的值没有除1之外的公因子;希尔排序不适用于链式存储结构。　　16.指出堆和二叉排序树的区别。　　以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，而两个孩子节点的关键字没有次序规定。而二叉排序树中，每个双亲节点的关键字均大于左子树节点的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每个双亲节点的左、右孩子的关键字有次序关系。　　17.堆排序是否是一种稳定的排序方法?为什么? 　　堆排序是一种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字被交换到前面来的情况。　　18.将快速排序算法改为非递归算法时通常使用一个栈，若把栈换为队列会对最终排序结果有什么影响? 　　在执行快速排序算法时，用栈保存每趟快速排序划分后左、右子区段的首、尾地址，其目的是为了在处理子区段未排序子序列时能够知道其范围，这样才能对该子序列进行排序(排序过程中可能产生新的左、右区段)，但这与处理子序列的先后顺序没什么关系，而仅仅起存储作用。因此，用队列同样可以存储子区段的首、尾地址，即可以取代栈的作用。在执行快速排序算法时，把栈换为队列对最终排序结果不会产生任何影响。　　19.外部排序的思想是什么？　　将大文件分段，将段依次读入内存并进行内部排序，并将排序后得到的有序段（归并段）重新写入外存　　20.外部排序的时间消耗主要来自于哪里，各自取决于哪些因素？　　时间消耗主要来自于读写外存时间、归并段的归并时间和内部排序时间。　　读写外存时间取决于归并树的WPL。　　归并段的归并时间取决于输入缓冲区数量k，归并就是不断从输入缓冲区选最小值，选取一次最小值需要比较k-1次关键字。　　内部排序时间取决于内部排序算法。　　21.外部排序的优化策略有哪些，是如何优化的？　　选择置换排序：增加初始归并段长度，从而减少归并趟数　　最佳归并树：优化了归并树的WPL，减少磁盘的读写（I/O）总次数　　败者树：归并过程中每次选出一个最小值需要比较的关键字次数除了第一次为k-1，其余降为「log2k」次关键字

折半查找和二叉排序树的时间性能_折半查找和二叉排序树的时间性能

相关推荐