数据结构与算法-等级考试试题(程序员软考 2016年春二叉排序树)

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

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

A、30 20 10 40

B、30 40 20 10

C、30 20 40 10

D、30 40 10 20

答案解析

D根据二又排序树的定义，将新元素插入二叉排序树时，需要先查找插入位置。若等于树根，则不再插入，若大于树根，则递归地在右子树上查找插入位置，否则递归地在左子树上查找插入位置，因此，新结点总是以叶子的方式...

查看完整答案

讨论

查找

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

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

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

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

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

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

动态查找表

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

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【】次元素间的比较。

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

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

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

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

一棵满二叉排序树深度为k，节点数为2k-1；节点值为1至（2k - 1），给出k和任意三个节点的值，输出包含该三个节点的最小子树的根节点。样例输入：4 10 15 13样例输出：12

某二叉排序树如下所示，新的元素45应作为【】插入该二叉树中。

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

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

二叉排序树

按照逻辑关系的不同可将数据结构分为【】。

最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wn的n个叶结点的二叉树中带权路径长度最小的二叉树。【】是哈夫曼树(叶结点中的数字为其权值)。

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

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

线性表采用单链表存储时的特点是【】。

设有字符串S和P，串的模式匹配是指确定【】。

特殊矩阵是非零元素有规律分布的矩阵，以下关于特殊矩阵的叙述中，正确的是【】。

完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【】。

数组是程序语言提供的基本数据结构，对数组通常进行的两种基本操作是数组元素的【】。

已知某带权图G的邻接表如下所示，其中表结点的结构为:以下关于该图的叙述中，正确的是【】。