考研数据结构和计算机组成原理在线题库每日一练（二十六）

本文提供考研数据结构和计算机组成原理在线题库每日一练，以下为具体内容

1、下列四个关键字序列中，（ ）不是堆。

A、{05，23，16，68，94，72，71，73}

B、{05，16，23，68，94，72，71，73}

C、{05，23，16，73，94，72，71，68}

D、{05，23，16，68，73，71，72，94}

2、在平衡二叉树中插入一个节点后引起了不平衡，设最接近叶子的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是（ ）型旋转。

A、LL

B、LR

C、RL

D、RR

3、指令系统中采用不同寻址方式的目的主要是（ ）。

A、实现程序控制的快速查找存储器地址

B、缩短指令长度，扩大寻址空间，提高编程灵活性

C、可以直接访问主存和外存

D、降低指令译码难度

4、对于三个结点A、B、C，可构成（ ）棵不同的二叉树。

A、4

B、5

C、30

D、6

5、在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的先后顺序（ ）。

A、完全相同

B、先序和中序相同，而与后序不同

C、都不相同

D、中序和后序相同，而与先序不同

1、试题答案：C

试题解析：

根据堆的定义，一个堆需要满足父节点的值大于等于子节点的值（大根堆）或者小于等于子节点的值（小根堆）。因此，我们可以检查每一个序列是否满足这个条件。在序列C中，节点为73的左子节点为68，68大于73，不符合前面最大堆的设定，因此序列C不是堆。故本题选C。

2、试题答案：B

试题解析：

（1）第一种情况：假设是因为A的左孩子的平衡因子发生变化而导致的不平衡，则A的左孩子的平衡因子只有可能是从0变为-1。这样进行的操作是在A节点的左孩子的右子树上插入节点，左子树的高度加一，最接近叶子的不平衡点是A的平衡因子由1变为2，则应进行的平衡旋转是LR型旋转。
（2）第二种情况：假设是因为A的右孩子的平衡因子发生变化而导致的不平衡，则A的右孩子的平衡因子只有可能是从-1变为0或1变为0。这样进行的操作可能是在A节点的右孩子的左子树或右子树上插入节点，右子树的高度并未发生变化，A的平衡因子也因此没有发生变化，不会导致不平衡。
故本题选B。

3、试题答案：B

试题解析：

数据寻址方式是根据指令中给出的地址码字段寻找真实操作数地址的方式。一般情况下，由于指令长度的限制，指令中的地址码不会很长，而主存的容量却可能越来越大。就是在字长很长的大型机中，即使指令中能够拿出足够的位数来作为访问整个主存空间的地址，为了灵活方便地编制程序，也需要对地址进行必要的变换。故本题选B。

4、试题答案：B

试题解析：

对于三个结点A、B、C，可构成5棵不同的二叉树。具体形态如下图所示。

故本题选B。

5、试题答案：A

试题解析：

在二叉树的先序遍历序列中，先访问根结点，然后访问左子树和右子树；在中序遍历序列中，先访问左子树，然后访问根结点，最后访问右子树；在后序遍历序列中，先访问左子树，然后访问右子树，最后访问根结点。因此，在先序遍历和中序遍历中，叶子结点的顺序与树的形状相同，即完全相同。在后序遍历中，叶子结点的顺序也与树的形状相同，因此也完全相同。因此，所有叶子结点的先后顺序是完全相同的。故本题选A。