考研数据结构与操作系统在线题库每日一练（二十七）

本文提供考研数据结构与操作系统在线题库每日一练，以下为具体内容

2、采用线性探测再散列解决冲突的方式，若查找到一个关键字可能经过多次探测地址，则这些探测到的关键字？（）

A、一定是同义字

B、一定不是同义字

C、可能是同义字

D、以上说法均错误

3、以3，1，2建成的AVL树，如何平衡（）。

A、单左旋

B、单右旋

C、先左旋后双右旋

D、先右旋后双左旋

2、试题答案：C

试题解析：

线性探测再散列法：设Hash(x)=Hash(y)=i，则x与y发生冲突；根据线性探测再散列，则y查看下一位置i+1，若有Hash(z)=i+1，则z与y发生冲突，但z与y不是同义字；故可能是同义字，可能不是同义字。综上本题选C。
同义字：关键字x、y经过哈希函数映射到同一个地址，则称x和y产生了冲突，即x与y是同义字。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--查找--动态查找表--平衡二叉树--平衡二叉树的应用--平衡二叉树的构造。
【解析】由3，1，2画出的树如下所示，其最小不平衡结点是3，这是因为在其的左孩子的右子树位置插入元素2所导致的，所以需要进行LR型调整，先左旋后双右旋。故本题选C。