计算机二级考试公共基础知识重点【3】

发布于 2018-07-19 14:48  编辑:jokex
0
计算机等级考试题库 扫码微信刷题

跟随小编接上一篇接续了解吧 :

6 树与二叉树

树是一种简单的非线性结构,所有元素之间具有明显的层次特性。

在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。

二叉树的基本性质:

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;

(2)深度为m的二叉树最多有2m-1个结点;

(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;

(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;

(5)具有n个结点的完全二叉树的深度为[log2n]+1;

(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,….n给结点进行编号(k=1,2….n),有以下结论:

①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为int(k/2);

②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。

满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。

二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。

二叉树的遍历:

(1)前序遍历(dlr),首先访问根结点,然后遍历左子树,最后遍历右子树;

(2)中序遍历(ldr),首先遍历左子树,然后访问根结点,最后遍历右子树;

(3)后序遍历(lrd)首先遍历左子树,然后访问遍历右子树,最后访问根结点。

7 查找技术

顺序查找的使用情况:

(1)线性表为无序表;

(2)表采用链式存储结构。

二分法查找只适用于顺序存储的有序表,对于长度为n的有序线性表,最坏情况只需比较log2n次。

8 排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2; (2)快速排序法。

插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;(2)希尔排序法,最坏情况需要o(n1.5)次比较。

选择类排序法:(1)简单选择排序法,

最坏情况需要n(n-1)/2次比较;(2)堆排序法,最坏情况需要o(nlog2n)次比较。

文章推荐:

计算机等级考试准考证打印错过时间了怎么办?


本文网址:http://www.k51.com.cn/info/jsjdjks/1807/1940889.html
选择分享到: