【2013】408联考数据结构真题整理

2013年

1

题目

解析

原始：升序 + 升序 变 升序 尾插法
改编：升序 + 升序 变 降序 头插法

2

题目

答案：C

解析

3

题目

答案：B

解析

二叉排序树，或者是空树，或者是满足以下性质的二叉树：

• 若它的左子树不空，则左子树上的所有关键字的值均小于根关键字的值
• 若它的右子树不空，则右子树上的所有关键字的值均大于根关键字的值
• 左右子树又各是一棵二叉排序树

依据序列建树，并计算平均查找长度：

总结： 平均查找长度与树的高度有关，平均查找长度越小，查找速度越快

平衡二叉树是二叉排序树的改进版：目的让树尽可能的矮

• 引入：平衡因子（=左子树高度 - 右子树高度）是一个数值
• 因此，平衡二叉树的条件（同时满足）：
  • 1.是二叉排序树
  • 2.满足每个结点的平衡因子绝对值不大于1

注意：平衡二叉树是特殊的二叉排序树。

本题采用RR方式变换

4

题目

答案：B

解析

5

题目

解析

6

题目

答案：C

解析

扩展答案：I、II、III、IV

7

题目

解析

8

题目

解析

9

题目

解析

10

题目

解析

11

题目

答案：C

解析

41（13分）

题目

解析

其中容易想到的算法中的①，思路以空间换时间，必须掌握

42

题目

解析