数据结构与算法-考研试题(中国科学院软件研究所 1997年有序表查找)

判断题（1997年中国科学院软件研究所）

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

答案解析

错

【解析】

链表表示的有序表不能用折半查找法查找。

讨论

查找

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

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

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

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

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

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

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

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

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

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

静态查找表

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

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

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

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

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

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

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

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

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

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

有序表查找

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

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

在n个结点的无向图中，若边数>n-1，则该图必是连通图。

用DFS遍历一个无环有向图，并DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是【】。

图的遍历方式有__________和__________两种。

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

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

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