文档介绍：1
内部资料
2011年3月计算机等级考试
二级公共基础知识培训讲义
理工大楼915
2
ess考试介绍
一、考试方式 :90 分钟,满分100 分,其中含公共基础知识部分30分
:90 分钟,满分100 分
二、笔试题型及分值(根据考试大纲及往年试题) 分(每小题2分,共3 5题) 分(每空2 分,共15题)
三、上机操作 (30 分) (40 分) (30 分)
3
我们的目标
通过二级考试
4
基础知识部分:30分
设有10道选择题和5道填空题
5
第一章数据结构与算法
算法
数据结构的基本概念
线性表及其顺序存储结构
栈和队列
线性链表
树与二叉树
查找技术
排序技术
6
树与二叉树
树的基本概念
树是一种简单的非线性结构,所有元素之间具有明显的层次特性。
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。
7
二叉树及其基本性质
二叉树的特点:
(1)非空二叉树只有一个根结点;
(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
8
二叉树的基本性质:
(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点; (2)深度为m的二叉树最多有2m-1个结点; (3)度为0的结点(即叶子结点)总是比度为2的结点多一个; (4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;
9
满二叉树
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
10