在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1

(1)【◆题库问题◆】：[判断题] 在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1
A．正确
B．错误

【◆参考答案◆】：正确

(2)【◆题库问题◆】：[单选] 直接选择排序在最好情况下的时间复杂度是（）。
A．O（n）
B．O（nlog2n）
C．O（1）
D．O（n2）

【◆参考答案◆】：A

(3)【◆题库问题◆】：[单选] 散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）
A．同义词之间发生冲突引起的
B．非同义词之间发生冲突引起的
C．同义词之间或非同义词之间发生冲突引起的
D．散列表"溢出"引起的

【◆参考答案◆】：B

(4)【◆题库问题◆】：[问答题] 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

【◆参考答案◆】：

(5)【◆题库问题◆】：[名词解释] 线索二叉树

【◆参考答案◆】：
对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。线索化了的二叉树称为线索二叉树。

(6)【◆题库问题◆】：[单选] 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）
A．空或只有一个结点
B．完全二叉树
C．二叉排序树
D．高度等于其结点数

【◆参考答案◆】：D

(7)【◆题库问题◆】：[名词解释] 队列

【◆参考答案◆】：
是一种受限线性表，是先进先出的线性表。

(8)【◆题库问题◆】：[问答题] 具有n个顶点的连通图至少有多少条边？

【◆参考答案◆】：
具有n个顶点的连通图至少有n-1条边。
这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。

(9)【◆题库问题◆】：[问答题] 什么是队列的上溢现象？一般有几种解决方法，试简述之。

【◆参考答案◆】：
在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种"假溢出"现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。
（2）要避免出现"假溢出"现象可用以下方法解决：
第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循"先进先出"的原则。

(10)【◆题库问题◆】：[单选] 一个广义表的表尾总是一个（）。
A．广义表
B．元素
C．空表
D．元素或广义表

【◆参考答案◆】：A