A、 多重链表一定是非线性结构
B、 顺序存储结构一定是线性结构
C、 有的二叉树也能用顺序存储结构表示
D、 有两个指针域的链表就是二叉链表
答案：C
解析：解析：在计算机中,二叉树属于非线性结构,通常采用链式存储,但对于满二叉树和完全二叉树来说,也可以按层次进行顺序存储,因此B选项错误、C选项正确。双向链表中结点有两个指针域,但双向链表属于线性结构,不属于二叉链表,A、D两项错误。本题答案为C选项。
A、 多重链表一定是非线性结构
B、 顺序存储结构一定是线性结构
C、 有的二叉树也能用顺序存储结构表示
D、 有两个指针域的链表就是二叉链表
答案：C
解析：解析：在计算机中,二叉树属于非线性结构,通常采用链式存储,但对于满二叉树和完全二叉树来说,也可以按层次进行顺序存储,因此B选项错误、C选项正确。双向链表中结点有两个指针域,但双向链表属于线性结构,不属于二叉链表,A、D两项错误。本题答案为C选项。
A. 叶子结点总是比度为2的结点少一个
B. 叶子结点总是比度为2的结点多一个
C. 叶子结点数是度为2的结点数的两倍
D. 度为2的结点数是度为1的结点数的两倍
解析：解析：对任何一棵二叉树,度为0的结点(即叶子结点〉总是比度为2的结点多一个。本题答案为B选项。
A. 循环队列
B. 二维数组
C. 二叉链表
D. 双向链表
解析：解析：【解析】二叉树的链式存储结杓称为二叉链表,二叉树是一种非线性结构,所以二叉链表属于非线性结构。本题答案为C选项。
A. 15
B. 16
C. 17
D. 18
解析：解析：【解析】完全二叉树是指除最后一层外,每一层上的节点数均达到最大值,在最后一层上只缺少右边的若干结点。深寖为4的满二叉树的结点数为2?-1=15,深度为5的满二叉树的结点数为2?-1=31,所以深度为5的完全二叉树的结点数应大于15且小于等于31。本题答案为A选项。
A. 多重链表必定是非线性结构
B. 任何二叉树只能采用链式存储结构
C. 排序二叉树的中序遍历序列是有序序列
D. 堆可以用完全二叉树表示,其中序遍历序列是有序序列
解析：解析：【解析】结点中具有多个指针域的链表就称为多重链表,双向链表有两个指针域,属于线性结构,A选项错误。在二叉树中,满二叉树与完全二叉树可以按层次进行顺序存储,B选项错误。设非空二叉树的所有子树中,其左子树上的结点值均小于根结点值,而右子树上的结点值均不小于根结点值,则称该二叉树为排序二叉树。对排序序列进行中序遍历,遍历结果为有序序列,C选项正镉。若有n个元素的序列,将元素按顺序组成一裸完全二叉树,当且仅当满足条件①:相结点值大于等子左子树的结点值且大于等于右子树的结点值;或条件②:根结点值小于等于左子树的结点值且小于等于右子树的结点值时称为堆。堆的左子树的结点值与右子树的结点值大小无法确定,所以对堆进行中序遍历无法确定是否为有序序列,D选项错误。本题答案为C选项。
A. 2
B. 3
C. 4
D. 6
解析：解析：【解析】二叉树遍历可以分为3种:前序遍历(访问根结点在访问左子树和访问右子树之前〉、中序遍历〈访问根结点在访问左子树和访问右子树两者之间)、后序遍历(访问根结点在访问左子树和访问右子树之后),并且在遍历左右子树时也遵循同样的规则。二叉树的前序序列为.ABCDE,可确定这棵二叉树的相结点为A﹔ 中序序列为BDFECA,可确定根结点A没有右子树,结点B没有左子树,结点B的右子树的根结点为C。按照同样的原理来分析以C为相结点的子树,其前序序列为CDEF,中序序列为DFEC,可知结点C没有右子树﹔再继续分析下去,结点D没有左子树,结点E没有右子树,结点F为叶子结点。该二叉树如下图所示,则二叉树的深度为6。本题答案为D选项。
A. 12
B. 15
C. 24
D. 不可能有这样的树
解析：解析：【解析】假设叶子结点个数为n。树的总的结点数为度为3的结点数+度为2的结点数+度为1的结点数+度为0的结点数,即为5+4+0+n。再根据树的总的结点数为树中所有结点的度数之和再加1,则总结点数为3×5+2×4+1×0+O×n+1。3×5+2×4+1=5+4+n,贝n=15,叶子结点数为15。本题答案为B选项。
A. 向量是顺序存储的线性结构
B. 只有一个根结点和一个叶子结点的结构必定是线性结构
C. 非线性结构只能采用链式存储结构
D. 所有非线性结构都能采用顺序存储结构
解析：解析：【解析】只有一个根结点和一个叶子结点的数据结构可以是树结构(非线性结构),所以只有两个结点无法确定是否为线性结构,B选项叙述错误。二叉树属于非线性结构,满二叉树与完全二叉树可以按层次进行顺序存储,C选项叙述错误。只有部分非线性结构可以采用顺序存储,D选项叙述错误。本题答案为A选项。
A. FEDCBA
B. ABCDEF
C. BDFECA
D. CBAFED
解析：解析：【解析】二叉树遍历可以分为3种:前序遍历(访问根结点在访问左子树和访问右子树之前〉、中序遍历(访问相结点在访问左子树和访问右子树两者之间)、后序遍历(访问根结点在访问左子树和访问右子树之后),并且在遍历左右子树时也遵循同样的规则。二叉树的前序序列为ABCDEF,可确定这棵二叉树的相结点为A,在后序遍历中最后访问结点A,因此排除B、D两项。中序序列为BDFECA,贝结点A不存在右子树,在对以结点B为相结点进行后序遍历对,最后访问的肯定是B结点,因此排除C项。本题答案为A选项。
A. 7
B. 8
C. 6
D. 不存在这样的树
解析：解析：【解析】树的结点数为25,只有度为3的结点和叶子结点,其中叶子结点有7个,则按照题意度为3的结点数为25-7=18。由于树中的结点数为树中所有结点的度数之和再加1,则树的总的结点数为3×18+1=55,与题目矛盾,所以不存在这样的树。本题答案为D选项。
A. n-1
B. n/2
C. n
D. 与有序顺序表的对分查找相同
解析：解析：最坏情况为:查找的元素为表中最后一个元素或查找的元素不在表中,贝需要比较表中所有元素,所以最坏情况下需要比较次数为n。本题答案为C选项。
