2017年常州大学信息学院、数理学院858数据结构考研仿真模拟题
● 摘要
一、选择题
1． 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48 B.24、48 C.24、53 D.24、90 【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
2． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
3． 可以用（ ）定义一个完整的数据结构。
A. 数据元素
B. 数据对象 C. 数据关系 D 抽象数据类型 【答案】D
【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。
4． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
5． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。
A.3, 5，12，8, 28，20, 15，22，19 B.3, 5, 12, 19, 20, 15, 22, 8, 28 C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。
6． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ）
A. B. C. D. 【答案】A
IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】
0000 0000 0000 0000, 转换为标准的格式为：
. 因此，浮点数的值为
7． 有一个的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60 B.66 C.18000 D.33
【答案】B
【解析】如果是全部，
则是需要
个字节；但是用三元组表示的话，只需要记录非零
字节，
数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即
相关内容
相关标签