数据结构题目收录（十八）

1、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用____存储方式最节省运算时间。

• A：单链表
• B：仅有头指针的单循环链表
• C：双链表
• D：仅有尾指针的单循环链表

解析

选项A、单链表插入最后一个元素需要遍历链表到最后一个元素。
选项B、仅有头指针，删除第一个元素方便，但是末尾插入一个元素同选项A。
选项C、双链表，方便来回遍历但是末尾插入一个元素依旧需要遍历整个链表。
选项D、最节约运算时间。

答案：D

2、设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列____存储方式最节省运算时间。

• A：单向链表
• B：单向循环链表
• C：双向链表
• D：双向循环链表

解析

某链表中最常用的操作是在链表的尾部插入或删除元素时双向循环列表最节省运算时间。

答案：D

3、在含有n个结点的二叉排序树中查找某个关键字的结点时，最多进行（）次比较。

• A：n/2
• B：${\log }_{2}n$
• C：${\log }_2(n+1)$
• D：n

解析

当输入序列是一个有序序列时，构造的二叉排序树是一个单支树，当查找一个不存在的关键字值或最后一个结点的关键字值时，需要n次比较。

答案：D

4、含有20个结点的平衡二叉树的最大深度为（）。

• A：4
• B：5
• C：6
• D：7

解析

平衡二叉树结点数的递推公式为$n_0$=1，$n_1$=1，$n_2$=2，$n_h$=1+$n_{h-1}$+$n_{h-2}$（h为平衡二叉树高度，$n_h$为构造此高度的平衡二叉树所需的最少结点数）。通过递推公式可得，构造5层平衡二叉树至少需要12个结点，构造6层至少需要20个结点。

答案：C

5、具有5层结点的AVL至少有（）个结点。

• A：10
• B：12
• C：15
• D：17

解析

设$n_h$表示高度为h的平衡二叉树中含有的最少结点数，则有$n_1$=1，$n_2$=2，$n_h$=$n_{h-1}$+$n_{h-2}$+1，由此求出$n_5$=12，对应的AVL如下图所示。

答案：B

6、下列关于红黑树的说法中，不正确的是（）。

• A：一棵含有n个结点的红黑树的高度至多为2${\log }_2(n+1)$
• B：如果一个结点是红色的，则它的父结点和孩子结点都是黑色的
• C：从一个结点到其子孙结点的所有路径上包含相同数量的黑结点
• D：红黑树的查询效率一般要优于含有相同结点数的AVL树

解析

选项A、B和C都是红黑树的性质。AVL是高度平衡的二叉查找树，红黑树是适度平衡的二叉查找树，从这一点可以看出AVL的查找效率往往更优。

答案：D

7、下列关于红黑树和AVL树的描述中，不正确的是（）。

• A：两者都属于自平衡的二叉树
• B：两者查找、插入、删除的时间复杂度都相同
• C：红黑树插入和删除过程至多有2次旋转操作
• D：红黑树的任一结点的左右子树高度之差不超过2倍

解析

自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性，红黑树和AVL都属于自平衡二叉树，A正确。

在红黑树中删除结点时，情况1可能变为情况2、3或4，情况2会变为情况3，可能会出现旋转次数超过2次的情况，故C错误。

答案：C

8、下列关于红黑树的说法中，正确的是（）。

• A：红黑树是一种特殊的平衡二叉树
• B：如果红黑树的所有结点都是黑色的，那么它一定是一棵满二叉树
• C：红黑树的任何一个分支结点都有两个非空孩子结点
• D：红黑树的子树也一定是红黑树

解析

答案：B

9、将关键字1,2,3,4,5,6,7一次插入初始为空的红黑树T，则T中红结点的个数是（）。

• A：1
• B：2
• C：3
• D：4

解析

关键字1,2,3,4,5,6,7一次插入红黑树后的形态变化如下图所示：

答案：C

10、将关键字5,4,3,2,1一次插入初始为空的红黑树T，则T的最终形态是（）。

解析

关键字5,4,3,2,1一次插入红黑树后的形态变化如下：

答案：D