首页 考试吧论坛 Exam8视线 考试商城 网络课程 模拟考试 考友录 实用文档 求职招聘 论文下载
2011中考 | 2011高考 | 2012考研 | 考研培训 | 在职研 | 自学考试 | 成人高考 | 法律硕士 | MBA考试
MPA考试 | 中科院
四六级 | 职称英语 | 商务英语 | 公共英语 | 托福 | 雅思 | 专四专八 | 口译笔译 | 博思 | GRE GMAT
新概念英语 | 成人英语三级 | 申硕英语 | 攻硕英语 | 职称日语 | 日语学习 | 法语 | 德语 | 韩语
计算机等级考试 | 软件水平考试 | 职称计算机 | 微软认证 | 思科认证 | Oracle认证 | Linux认证
华为认证 | Java认证
公务员 | 报关员 | 银行从业资格 | 证券从业资格 | 期货从业资格 | 司法考试 | 法律顾问 | 导游资格
报检员 | 教师资格 | 社会工作者 | 外销员 | 国际商务师 | 跟单员 | 单证员 | 物流师 | 价格鉴证师
人力资源 | 管理咨询师考试 | 秘书资格 | 心理咨询师考试 | 出版专业资格 | 广告师职业水平
驾驶员 | 网络编辑
卫生资格 | 执业医师 | 执业药师 | 执业护士
会计从业资格考试会计证) | 经济师 | 会计职称 | 注册会计师 | 审计师 | 注册税务师
注册资产评估师 | 高级会计师 | ACCA | 统计师 | 精算师 | 理财规划师 | 国际内审师
一级建造师 | 二级建造师 | 造价工程师 | 造价员 | 咨询工程师 | 监理工程师 | 安全工程师
质量工程师 | 物业管理师 | 招标师 | 结构工程师 | 建筑师 | 房地产估价师 | 土地估价师 | 岩土师
设备监理师 | 房地产经纪人 | 投资项目管理师 | 土地登记代理人 | 环境影响评价师 | 环保工程师
城市规划师 | 公路监理师 | 公路造价师 | 安全评价师 | 电气工程师 | 注册测绘师 | 注册计量师
缤纷校园 | 实用文档 | 英语学习 | 作文大全 | 求职招聘 | 论文下载 | 访谈 | 游戏

2010年9月计算机等级考试二级公共基础知识考点

来源:考试吧Exam8.com) 2010-9-14 14:09:35 考试吧:中国教育培训第一门户 模拟考场

  1.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)首先遍历左子树,然后访问遍历右子树,最后访问根结点。

  1.7 查找技术

  顺序查找的使用情况:

  (1)线性表为无序表;

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

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

  1.8 排序技术

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

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

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

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

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

上一页  1 2 3 4 5 6 7 8 9 10  ... 下一页  >> 
  相关推荐:2010年计算机等考二级公共基础知识汇总
       2010全国计算机等考二级:公共基础知识习题汇总
文章搜索
版权声明:如果计算机等级考试网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本计算机等级考试网内容,请注明出处。