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

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

1、若一棵度为3的树T中，有A个度为1的结点，B个度为2的结点，C个度为3的结点，则该树有（ ）个叶结点。

A、1+2B+3C

B、A+2B+3C

C、2B+3C

D、1+B+2C

2、按照下列关键码序列23，15，18，40，50，26，11，19，20，依次插入一棵初始为空的二叉查找树中，在构造好的二叉查找树中查找一个关键码，查找成功的最大比较次数是（ ）。

A、4

B、5

C、6

D、7

3、下列所示各图中是中序线索化二叉树的是（ ）。

A、

B、

C、

D、

4、字长8位，定点整数表示，补码表示的最小数是（ ）。

A、00000000

B、10000001

C、11111111

D、10000000

5、在顺序表中访问第i个位置的元素和在第i个位置插入一个新元素的时间复杂度为（ ）。

A、O(1)，O(1)

B、O(1)，O(n)

C、O(n)，O(1)

D、O(n)，O(n)

1、试题答案：D

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3（结点数量）=n1+2n2+3n3+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3+1=1+B+2C。故本题选D。

2、试题答案：B

试题解析：

根据关键字序列，构造的二叉排序树如下图所示。

因此查找成功的最大比较次数是5。故本题选B。

3、试题答案：A

试题解析：

在中序线索化二叉树中，对于一个结点，若其左子树为空，则将其左指针指向其前驱结点，否则将其左指针指向其左子树；若其右子树为空，则将其右指针指向其后继结点，否则将其右指针指向其右子树。该二叉树的中序遍历序列为bac，因此中序线索化二叉树的结构如选项A中所示。故本题选A。

4、试题答案：D

试题解析：

定点整数表示中，补码表示法是最常用的一种。在补码表示中，最高位为符号位，0表示正数，1表示负数，其余位为数值位。由于是8位字长，那么最高位是符号位，其余7位为数值位，所以最小数的补码表示应该是最高位为1，其余位都为0的形式。对于8位补码表示，最小数为-128。其补码表示为 10000000。故本题选D。

5、试题答案：B

试题解析：

在顺序表中，访问第i个位置的元素的时间复杂度为O(1)，因为在内存中直接通过计算可以得到其地址。插入一个新元素到第i个位置需要将第i个位置及之后的元素向后移动，因此需要O(n)的时间复杂度。故本题选B。