设二叉排序树中关键字由1至1000的整数构成,现要查找关键字为363的结点,下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?
(a) 2,252,401,398,330, 344,397,363;
(b) 924, 220, 911, 244, 898, 258, 362, 363;
(c) 925, 202, 911, 240, 912, 245, 363;
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
答:
(c)是不可能查找到的序列。把这四个序列各插入到一个初始为空的二叉排序树中,结果可以发现,(c)序列所形成的不是一条路径,而是有分支的,可见它是不可能在查找过程中访问到的序列。
图例:在附件
- 大小: 7.1 KB
分享到:
相关推荐
* TREE 的结构:二叉排序树的结构需要满足关键字的顺序关系,即左子树的关键字小于根结点的关键字,右子树的关键字大于根结点的关键字。 * 查找算法:查找算法需要能够快速地找到树中是否存在关键字相同的数据元素。...
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...
在实际应用中,二叉排序树的节点可能包含重复的关键字,因此在定义中,我们可以将“小于”改为“大于等于”,将“大于”改为“小于等于”。 二叉排序树的存储结构通常使用结构体来表示,如下所示: ```c typedef ...
用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
本题涉及到了多种查找方法和数据结构,包括二叉排序树、完全二叉树、静态查找与动态查找、折半查找、哈希表以及平衡二叉树。 1. 二叉排序树(BST)是一种特殊的二叉树,其中每个节点的左子树只包含比其键值小的节点...
- 在二分法查找中,平均查找长度与序列长度有关,而对于平衡的二叉排序树,查找长度取决于树的高度。通过具体的计算可以得出平均查找长度。 #### 五、程序题解析 **程序题示例代码填写** ```c++ int Search_Bin...
数据结构中的哈希表是一种高效的数据组织方式,它允许我们以接近常数时间的复杂度进行查找、插入和删除操作。哈希表的核心思想是通过一个哈希函数将输入(通常为键)映射到一个固定大小的数组索引上,从而实现快速...
2. 编程题:输入n个两两互不相等的整数,以这些整数为关键字建立平衡的二叉排序树。判断该二叉树是否为平衡的,输出判断结果;输出该二叉树的中序遍历关键字访问次序。 3. 从空树起连续插入以下20个关键字构建m=4的B...
10. **题目:** 在AVL树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作〔〕型调整以使其平衡。 - **选项:** - A. LL - B. LR - C. RL - D...
2. 编程题:输入n个两两互不相等的整数,以这些整数为关键字建立平衡的二叉排序树。判断该二叉树是否为平衡的,输出判断结果;输出该二叉树的中序遍历关键字访问次序。 3. 从空树起连续插入以下20个关键字构建m=4的B...
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...
在二叉排序树中插入一个结点的时间复杂度在最好情况下为O(1),最坏情况下为O(n)。 3. **图**:图由顶点和边组成。无向图中每条边连接两个顶点,所以所有顶点的入度之和等于边的数量的两倍,即2e。有向图的邻接表中...
4. **平衡二叉排序树**:平衡二叉排序树是一种特殊的二叉树,它保持了二叉排序树的性质,同时保证左右子树的高度差不超过1,以达到高效查找的目的。题目要求找出满足平衡条件的二叉排序树。 5. **完全二叉树**:在...
- **二叉排序树上的查找**:利用二叉排序树的性质,通过比较节点值来进行查找。 #### 五、哈希表(HashTable) **5.1 哈希表的概念** - **哈希函数**:用于计算键值对应的哈希码。 - **解决冲突的方法**:包括开放...
- **二叉排序树**:左子树上所有结点的键值均小于它的根结点的键值;右子树上所有结点的键值均大于它的根结点的键值;左、右子树也分别为二叉排序树。 - 插入新结点时不会引起树的整体重组,但可能会影响局部结构。 ...
6. **二叉排序树**:问题6探讨了在二叉排序树中删除和重新插入节点的影响。如果删除的是叶子节点,插入后树结构不变;如果删除的是非叶子节点,插入后树的结构可能会改变。 7. **图的邻接矩阵**:问题7提到的是图的...