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

2011年软考程序员考试复习笔试知识点整理(9)

来源:考试吧Exam8.com) 2011-4-11 19:48:13 考试吧:中国教育培训第一门户 模拟考场
考试吧提供了“2011年软考程序员考试复习笔试知识点整理”,供考生参考。

  (3)B+树

  B+树是B-树的变体,也是一种多路搜索树:

  1.其定义基本与B-树同,除了:

  2.非叶子结点的子树指针与关键字个数相同;

  3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

  5.为所有叶子结点增加一个链指针;

  6.所有关键字都在叶子结点出现;

  如:(M=3)

  B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

  B+的特性:

  1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

  2.不可能在非叶子结点命中;

  3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

  4.更适合文件索引系统;

  (4)B*树

  是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

  B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

  B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

  B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

  所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

  (5)红黑树

  红黑树(Red-Black Tree)是二叉搜索树(BinarySearch Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点之后都会花O(log N)的时间来对树的结构作修改,以保持树的平衡。也就是说,红黑树的查找方法与二叉搜索树完全一样;插入和删除节点的的方法前半部分节与二叉搜索树完全一样,而后半部分添加了一些修改树的结构的操作。

  map就是采用红黑树存储的,红黑树(RB Tree)是平衡二叉树,其优点就是树到叶子节点深度一致,查找的效率也就一样,为logN。在实行查找,插入,删除的效率都一致,而当是全部静态数据时,没有太多优势,可能采用hash表各合适。

  相对来说,hash_map是一个hashtable占用内存更多,查找效率高一些,但是hash的时间比较费时。总体而言,hash_map 查找速度会比map快,而且查找速度基本和数据数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小, hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格,希望程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。

  现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

  红黑树的每个节点上的属性除了有一个key、3个指针:parent、lchild、rchild以外,还多了一个属性:color。它只能是两种颜色:红或黑。而红黑树除了具有二叉搜索树的所有性质之外,还具有以下4点性质:

  1. 根节点是黑色的。

  2. 空节点是黑色的(红黑树中,根节点的parent以及所有叶节点lchild、rchild都不指向NULL,而是指向一个定义好的空节点)。

  3. 红色节点的父、左子、右子节点都是黑色。

  4. 在任何一棵子树中,每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。

上一页  1 2 3 4 下一页
  相关推荐:

  软考程序员考试历年真题重点题总结及答案

  2011年上半年软考报名时间及方式汇总

  软考程序员考试历年真题汇总(2007年-2010年)

文章搜索
软件水平考试栏目导航
版权声明:如果软件水平考试网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本软件水平考试网内容,请注明出处。