数据结构与算法-考研试题(中国科学技术大学 1996年二叉排序树)

单项选择（1996年中国科学技术大学）

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

A、顺序查找

B、折半查找

C、不确定

答案解析

B

【解析】

在随机的情况下，二叉排序树的平均查找长度为O(log₂n)

讨论

查找

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

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

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

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

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

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

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

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

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

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

动态查找表

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

利用逐点插入法建立序列（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。

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

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

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

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

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

二叉排序树

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

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

对于正整数n ，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ，程序输出为：4 = 44 = 3 + 14 = 2 + 24 = 2 ＋ 1 ＋ 1 4 = 1 ＋ 1 ＋ 1 ＋ 1test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数， k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数（称为和数）存于二数组 a[]中。当其中一个分解己不再需要进一步进行时，即找到一个解，将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时，以要进一部分解的数及分解深度为参数，递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){ int i,j; for (j=__________；j>=1；j--）{ a[k]=j; if (__________）{ printf ( "%d = %d" , a[0]，a[l]); for (i = 2 ; i < = k ; i + + ) printf ( " + % d " , a[i]); printf ( " n " ); }else test(__________，k + l ); } }

在一个有n个顶点的无向网中，有O(n1.5*log2n)条边，则应该选用【】算法来求这个网的最小生成树，从而使计算时间较少。

G是一个非连通无向图，共有28条边，则该图至少有【】个顶点。

如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有【】

在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法【】。

对于前序遍历和中序遍历结果相同的二叉树为__________；对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

由二叉树的前序和后序遍历序列【】唯一地确定这棵二叉树。

n个顶点的连通图用邻接矩阵表示时，该矩阵至少有__________个非零元素。