2023年自考计算机软件基础13178复习资料（3）

2023年自考计算机软件基础13178复习资料（3）

21、    结点的度：结点上分支出的子树个数。一棵树中最大的结点度称为树的度。

22、    深度：树中结点的最大层次数。

23、    二叉树是n个结点的有限集合，它或是空树，或是由一个根结点，以及两颗互不相交的、 分别称为左子树和右子树的二叉树组成。

24、    二叉树性质：1、二叉树的第i层上至多有2"个结点2、深度为k的二叉树至多有2匕1 个结点3、对任何一棵二叉树，若2度结点树为血，则叶子数no=n2+lo 4、深度为k且有 2=1个结点的二叉树称为满二叉树。5、具有n个结点的完全二叉树的深度为［log2nl+l

25、    具有n个结点的二叉树采用二叉链表进行存储在2n个指针域中，共有n+1个指针域是 空的。

26、    一棵树可以通过加线、抹线、旋转转换成二叉树。其特点是根结点没有右孩子，右子树 为空。

27、    遍历：指循某条搜索搜索路线巡査某数据结构中的结点，而且每个结点只被访问一次。

28、    先序遍历：先根结点，后左再右。中序：先左，后根再右。后序：先左，后右再根。

29、    二叉树的排序树：具有1、若它的左子树不空，则左子树上所有结点的值均小于它的根 结点的值2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。3、它 的左右子树也分别为二叉树排序树。

30、    线性査找的优点是对于线性表的逻辑次序无要求，表中的记录不必按关键字值的大小排 序，链表和顺序表结构都可以。苴缺点是查找速度慢。线性查找的平均比较次数(n+l)/2.

31、    二分査找又称折半查找或对半查找，要求对向必须是按关键字大小顺序排序的顺序储存 表。貝比较次数为log2n.

32、    散列查找，存储结构为散列存储结构

33、    散列函数处理冲突中的开地址法包括线性探测法和双重散列法

34、    排序：是将一组记录按其关键字值的递增或递减的次序排列成一个有序序列。