填空题(1994年北京大学)

在分块检索中,对256个元素的线性表分成__________块最好,每块的最佳长度是__________;若每块的长度为8,其平均检索长度为__________。

答案解析

16;17;21分块查找的平均查找长度是平均块查找长度Lb,与块内平均查找长度Lw之和,即ASLbs=Lb+Lw=(s+n/s)/2+1,其中s为每块的长度。当s=sqrt(n)时,ASLbs取最小值...

查看完整答案

讨论

下列哪两个数据结构,同时具有较高的查找和删除性能【 】?

在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与【 】量级相当。

在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二叉排序树与删除前原二叉排序树相同。

已知序列17,31,13,11,20,35,25,8,4,11,24,40,27,请画出该序列的二叉排序树,并分别给出下列操作后的二叉排序树:① 插入数据9;② 删除结点17;③ 再删除结点13。

假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。

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

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

设有关键码序列(10,40,30,20),根据该序列构建的二叉排序树是【 】。

设有二叉排序树如下图所示,根据关键码序列【 】可构造出该二叉排序树。

对关键码序列(12,24,15,56,20,87,69,9)采用散列法进行存储和查找,并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法(顺地探查可用存储单元)解决冲突所构造的散列表为【 】。

对关键码序列(9,12,15,20,24,29,56,69,87)进行二分查找(折半查找),若要查找关键码15,则需依次与【 】进行比较。

对含有 600 个元素的有序顺序表进行折半查找,关键字之间的比较次数最多是【 】

最优二叉树(哈夫曼树)、最优查找树均为平均查找路径长度wihi最小的树,其中对最优二叉树,n表示__________,对最优查找树,n表示__________,构造这两种树均__________。(1)结点数(2)叶结点数(3)非叶结点数(4)度为2的结点数(5)需要一张n个关键字的有序表(6)需要对n个关键字进行动态插入(7)需要n个关键字的查找概率表(8)不需要任何前提

分块查找要求将待查找的表均匀地分成若干块,块中诸记录的顺序可以是任意的,但块与块之间____________。

在一个线性表上可以进行二分查找(折半查找)的充分必要条件是【 】。

折半(二分)查找法适用的线性表应该满足【 】的要求。

在n个记录的有序顺序表中进行折半查找,最大的比较次数是__________。

用二分法查找一个线性表时,该线性表必须具有的特点是____________。

在分块检索中,若索引表和各块内均用顺序查找,则有900个元素的线性表分成__________块最好;若分成25块,其平均查找长度为__________。

在有13个元素构成的有序表data[1..13]中,用折半查找(即二分查找,计算时向下取整)方式查找值等于data[8]的元素时,先后与【 】等元素进行了比较。

顺序队列一般应该组织成为环状队列的形式,而且一般队列头或尾其中之一应该特殊处理。例如,队列为 listarray [ 0 ... n-1] ,队列头指针为front ,队列尾指针为 rear ,则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

试列中下列图中全部可能的拓扑排序序列。

已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->rlink=q且q->llink=p),请写出删除q所指结点的程序段。

求具有最小带权路径长度的二叉树的算法称为__________算法。对于给出的一组权W={10,12,16,21,30},通过该算法示出的二叉树的带权路径长度为__________。

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

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

在分块检索中,对256个元素的线性表分成__________块最好,每块的最佳长度是__________;若每块的长度为8,其平均检索长度为__________。

在分块检索中,对256个元素的线性表分成__________块最好,每块的最佳长度是__________;若每块的长度为8,其平均检索长度为__________。

在分块检索中,对256个元素的线性表分成__________块最好,每块的最佳长度是__________;若每块的长度为8,其平均检索长度为__________。

在分块检索中,对256个元素的线性表分成__________块最好,每块的最佳长度是__________;若每块的长度为8,其平均检索长度为__________。