27、树这种数据结构的基本特征

(1)在树结构中每一个结点只有一个前件，称为父结点没有前件的结点只有一个，称 为树的根结点，简称为树的根。

(2)在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后 件的结点称为叶子结点

(3)在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0在 树中，所有结点中的最大的度称为树的度

28、树的最大层次称为树的深度

29、在树中，以某结点的一个子结点为根构成的树称为该结点的一颗子树，叶子结点没有子树

30、二叉树，是一种很有用的非线性结构

31、二叉树的特点：(1)非空二叉树只有一个根结点

(2)每一个结点最多有两颗子树，每一个结点的度最大为2

32、二叉树的基本性质：(1)在二叉树的第k层上，最多有2的k-1次方(k>=1)个结点

(2)深度为m的二叉树最多有2的m次方-1个结点(深度为m的 二叉树是指二叉树共有m层)

(3)在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度 为2的结点多一个

(4)具有n个结点的二叉树，其深度至少为【log2N】+1,其中【log2N】 表示取其整数部分

33、满二叉树与完全二叉树(1)满二叉树：除最后一层外，每一层上的所有结点都有两个 子结点

(2)完全二叉树：除最后一层外，每一层上的结点树均达到最 大值，在最后一层上只缺少右边的若干结点

34、完全二叉树的性质：(1)具有m个结点的完全二叉树的深度为【log2N】+1

(2)设完全二叉树共有n个结点

35、计算机中二叉树通常采用链式存储结构

36、二叉树的遍历：是指不重复地访问二叉树中的所有结点

(1)前序遍历(2)中序遍历(3)后序遍历

37、二分法查找只适用于顺序存储的有序表。二分法查找只需要比较log2N次而顺序查找需要比较n次

38、交换类排序法：冒泡排序法、快速排序法

计算机二级公共基础知识试题及答案

1、下列叙述中正确的是(A)。

A.有的二叉树也能用顺序存储结构表示

B.有两个指针域的链表就是二叉链表

C.多重链表一定是非线性结构

D.顺序存储结构一定是线性结构

2、设二叉树共有 375 个结点，其中度为 2 的结点有 187 个。则度为 1 的结点个数是(A)。

A.0

B.1

C.188

D.不可能有这样的二叉树

3、某系统结构图如下图所示该系统结构图的宽度是(B)。

A.5

B.4

C.2

D.1

4、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为(A)。

A.ABCDEFGHIJ