判断题(1998年北京邮电大学)

快速排序的速度在所有排序方法中为最快,而且所需附加的空间也最少。

答案解析

【解析】

快速排序需要一个额外的栈空间,比堆排序所需的空间要大。

讨论

若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。

在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是【 】。

下述排序算法中,所需辅助存储量最多的是__________,所需辅助存储量最少的是__________,平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序

在分析二叉查找树性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若设失败结点i所在层次为li,那么查找失败到达失败结点时所做的数据比较次数是多少?

最佳二叉树是AVL树(平衡二叉树)。

二叉树中,具有两个子女的结点的中序后继结点最多只能有一个子女。

若散列表的负载因子α<1,则可避免碰撞的产生。

设a、b、c、d和e这5个字符的编码分别为1、2、3、4和5,并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和cd。要求用哈希(Hash)方式将它们存放在具有10个位置的表中。① 对上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少。② 用线性探测再散列法解决冲突。写出上述各关键字在表中的位置。

设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大?② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

若杂凑表(Hash)的地址范围为[0,9],杂凑函数为H(key)=(key2+2) MOD 9,并采用链地址法处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。