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

单项选择（2017年秋程序员软考）

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

A、

B、

C、

D、

答案解析

B按顺序计算各关键码的哈希(散列)地址如下：H(12)=12%11=1，H(24)=24%11=2，H(15)=15%11=4，H(56)=56%11=1，H(20)=20%11=9，H(87)=87%11=10，H(69)=69%11=3，H(9)=9%11=9初始时哈希表为空，关键码12、24和15存入时没有发生冲突，因此这些关键码的存储位置即为由哈希函数计算所得，如下表所示。存入关键码56时，计算得到其哈希地址为1，发生冲突，用线性探查法探查哈希地址为2的单元，仍然冲突，再探查哈希地址为3的单...

查看完整答案

讨论

数据结构与算法

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

对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为【】。

递归函数执行时，需要【】来提供支持。

表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为【】。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串【】。

对于连通无向图 G，以下叙述中，错误的是【】。

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

设 S 是一个长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串(非空且不同于S本身)的个数为【】。

在C程序中有一个二维数组 A[7][8]，每个数组元素用相邻的 8 个字节存储，那么存储该数组需要的字节数为【】。

为支持函数调用及返回，常采用称为“【】”的数据结构。

哈希表

设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表示整除取余运算)，则构造散列冲突次数最多的哈希单元的地址是【】。

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

假定有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应该设计多大？② 试为该散列表设计相应的散列函数（用除留余数法）并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

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

算术表达式a+b-c*d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

以下关于字符串的叙述中，正确的是【】

查找

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

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

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

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

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

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

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

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

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

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