数据结构与算法-等级考试试题(程序员软考 2016年春哈希表)

单项选择（2016年春程序员软考）

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

A、0

B、1

C、5

D、6

答案解析

C根据散列函数计算出每个关键字的哈希地址如下：H(54)=54 MOD 7=5H(34)=34 MOD 7=6H(5)=5 MOD 7=5H(14)=14 MOD 7=0H(50)=50 MOD 7=...

查看完整答案

讨论

数据结构与算法

某二又树的先序遍历序列为 ABCDFGE，中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中，正确的是【】。

对二叉树中的结点如下编号：树根结点编号为1，根的左孩子结点编号为2、右孩子结点编号为3，以此类推，对于编号为i的结点，其左孩子编号为2i、右孩子编号为2i+1。例如，下图所示二又树中有6个结点，结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么，当结点数为n(n>0)的【】时，其最后一个结点编号为2n-1。

队列采用如下图所示的循环单链表表示，左图表示队列为空，右图为e1、e2、e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是【】。

设有初始为空的栈S，对于入栈序列a、b、c、d，经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次)，以c作为第一个出栈的元素时，不能得到的序列为【】。

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

递归函数执行时，其调用和返回控制是利用【】来进行的。

与算术表达式3-(2+7)/4对应的二又树为【】。

在待排序的一组关键码序列k1，k2，…，kn中，若ki和kj相同，且在排序前ki领先于kj，那么排序后，如果ki和kj的相对次序保持不变，ki仍领先于kj，则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形，则称此类排序为不稳定的。【】是稳定的排序方法。

若待排序记录按关键字基本有序，则宜采用的排序方法是【】。

【】不符合二叉排序树的定义。

哈希表

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

假定有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，则可避免碰撞的产生。

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

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

在数据结构中，【】是与存储结构无关的术语。

已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【】。

查找

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

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

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

最佳二叉树是AVL树（平衡二叉树）。

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

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

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

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

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

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