数据结构与算法-考研试题(腾讯校园招聘 2014年查找)

不定项选择（2014年腾讯校园招聘）

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

A、有序数组

B、有序链表

C、AVL树

D、Hash表

答案解析

CD

讨论

数据结构与算法

已知一棵二叉树，如果先序遍历的顺序是ADCEFGHB，中序遍历的顺序是CDFEGHAB，则后序遍历的结果为【】。

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【】遍历方法最合适。

对二叉排序树进行【】遍历，可以得到该二叉树所有结点构成的排序序列。

证明一棵二叉树无论进行先序、中序、后序遍历，其叶子结点的相对次序不发生改变。

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？

用一维数组存放的一棵完全二叉树如下：A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ，中序遍历结果是CDEBAFHGIJ，试画出这棵二叉树。

证明，由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

查找

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

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

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

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

对关键码序列(12，24，15，56，20，87，69，9)采用散列法进行存储和查找，并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法（顺地探查可用存储单元）解决冲突所构造的散列表为【】。

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

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

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

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

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

#tts_2#

#tis_2#