2017年华东交通大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
2． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示：
图
3． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？
【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。
4． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）判定树如图所示：
图 判定树
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。 （3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。 （4）
5． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？ （2）试证明
。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
6． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
最大递归深度n 。
7． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
要求：
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别
为
为O
8． 对下面的关键字集
故算法的时间复杂度为
，算法的空间复杂度为0（1）。 若查找表的装填因子为0.8，采用线性探
原地逆置，
得到
个数和后P 个数分别原地逆置，
最终得到结果
测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为
时的查找次数。本例中
（4）算法如下：
用除留余数法设计
故查找失败和查找成功时的平均查找长度分别为：
相关内容
相关标签