单项选择(2023年计算机统考

现有长度为 5,初始为空的散列表HT,散列函数H(k)=(k+4) mod 5, 用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入HT中,然后删除关键字 25 ,则HT中查找失败的平均查找长度为【 】。

A、1

B、1.6

C、1.8

D、2.2

答案解析

C

【解析】

1)插入2022,H(2022)=(2022+4) mod 5 =1;1位为空,可插入;

2)插入12,H(12)=(12+4) mod 5 =1,冲突,采用线性探测法,每次向右探索一位,当前为空,可插入;

3)插入25,H(25)=(25+4) mod 5 =4,4位为空,可插入。

4)删除25,该散列表采用线性探测再散列法,属于开放寻址法,从中删除关键字时,不能简单地置NIL,而是作一个标记,如DELETED,简记为D。

5)计算查找失败时的平均查找长度:

查找元素失败统计项数目与散列表空间大小和散列函数均有关,这里取5。

按照冲突处理方法,计算出每种情况查找失败需要的次数,即失败查找长度:

散列到0:

查找次数为1;

散列到1:

查找次数为3;

散列到2:

查找次数为2;

散列到3:

查找次数为1;

散列到4:

查找次数为2。

查找失败时的平均查找长度为:(1+3+2+1+2)/5=1.8

讨论

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

下列关于非空 B 树的叙述中,正确的是【 】Ⅰ. 插入操作可能增加树的高度Ⅱ. 删除操作一定会导致叶结点的变化Ⅲ. 查找某关键字一定是要查找到叶结点Ⅳ. 插入的新关键字最终位于叶结点中

已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索

已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】

在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】

若采用三元组表存储结构存储系数矩阵 M.则除三元组外,下列数据中还需要保存的是【 】Ⅰ. M 的行数;Ⅱ. M 中包含非零元素的行数;Ⅲ. M 的列数;Ⅳ. M 中包含非零元素的列数.

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码ki时,其前面的 i-1 个关键码已排好序,因此令k与 ki-1、ki-2、…,依次比较,最多到 k1为止,找到插入位置并移动相关元素后将ki插入有序子序列的适当位置,完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中,正确的是【 】 。

对于下面的有向图,采用邻接链表存储时,顶点 0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为【 】。

负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度。

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

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

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

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

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

对于关键码序列(54,34,5,14,50,36,47,83),用链地址法(或拉链法)解决冲突构造散列表(即将冲突的元素存储在同一个单链表中,单链表的头指针存入散列地址对应的单元),设散列函数为H(Key)= Key MOD7(MOD表示整除取余运算),则构造散列冲突次数最多的哈希单元的地址是【 】。

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

对含有n (n>0)个记录的文件进行外部排序,采用置换-选择排序生成初始归并段时需要使用一个工作,工作区中能保存m个记录,请回答下列问题。(1) 如果文件中有19条记录,其关键字分别为:51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100,当m=4时,可生成几个初试归并段,各是什么?(2)对任意m (n≫m>0),生成的第一个初试归并段长度最大值和最小值分别多少?

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。

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

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

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

若在线性表中采用折半查找元素,该线性表应该【 】。

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

有n个数存放在一维数组A[1..n]中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同。

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

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

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

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