北航2014考研计算机学科专业基础综合考点速记手册

章节摘录

版权页：   插图：   ①从输入文件读k个记录到工作区。 ②对工作区中的k个记录建立败者树。 ③将根结点对应记录（关键字值最小者）送入当前的初始归并段。 ④从输入文件取下一个记录进入工作区以替代刚输出的记录的结点位置。 ⑤对工作区中关键字大于或等于已输出记录的关键字的所有记录，建立败者树（如果新加入记录的关键字大于或等于已输出记录的关键字，只要对原败者树进行调整即可）。 ⑥重复步骤③～⑤直到工作区的k个记录关键字都小于刚输出记录的关键字为止。此时已产生一个归并段。 ⑦重复步骤②～⑥直到工作区为空。 （2）败者树 在磁盘排序的两个阶段中，采用败者树进行最小关键字的查找可减少比较次数。 败者树是一棵完全二叉树。其中每个结点的关键字取它的两个子结点的关键字中较小者，因此，根结点的关键字是这棵树中所有结点的关键字中最小的。这就像k个参加淘汰赛的球队，胜者（值较小者）进入下一轮的比赛，根结点为冠军（值最小者）。 败者树的构造过程是：对于具有k个记录的序列，首先用这k个记录作为叶子结点，然后把相邻的两个结点进行比较，把关键字小的记录（优胜者）作为这两个结点的父结点，按此方法自下而上一层一层地产生败者树的结点。为了节约内存空间，非叶子结点可不包含整个记录，只要存放记录的关键字及指向该记录的指针即可。 败者树的根结点的值是构成败者树的元素中最小的。在后面的应用中，往往把根结点的值输出，并用一个新的元素替换，要求构成新的败者树，这时只要在原来的败者树的基础上进行调整即可。调整仅在从根到新加入的叶子结点的树枝j一的结点及它们的兄弟结点之间进行，自下而上进行比较并调整其父结点。 （3）k路归并方法 有了m个初始归并段（都是有序段），便可以进行k路归并了，即将k个初始归并段采用某种方法进行归并产生一个段，这样m个初始归并段产生多个更大的段，然后对这些段再进行归并，如此下去，直到只生成一个段为止，这个段就是最后生成的归并段。 在内存里进行k路归并的方法有多种。当归并路数k较大时，为了减少归并时的比较次数，常采用败者树进行归并的方法，其归并过程如下： ①用参加归并的k个有序段的第一个记录构造出一棵初始败者树，该树中的根结点就是这k个记录中具有最小关键字的记录。 ②把败者树根结点所代表的记录送到输出缓冲区。 ③输出记录所在的有序段的下一个记录代替输出记录的位置，调整败者树。 ④重复步骤②和③直到k个有序段的所有记录都输出为止。 k路平衡归并的败者树的深度为[log2k]，因此，利用败者树在k个记录中选择最小者，只需要进行[log2k]次关键字比较。若每一趟归并u个记录，总共归并s趟（s=[logkm]），每次的调整找下一个具有最小关键字的记录时，最多[log2k]次关键字比较，这时归并总共需要的比较次数为。

内容概要

崔巍、蒋本珊、孙卫真、白龙飞均为重点大学计算机专业一线教师，主讲计算机专业课程，拥有丰富的计算机教学经验。对计算机专业硕士研究生专业课考试有深入研究。自2009年实行考研计算机专业课统考以来，已编写出版多部计算机专业考研书，深受广大考生推崇。

书籍目录

第一部分数据结构 第1章绪论 1.1知识结构图 1.2重点归纳 1.3难点释疑 1.4真题高频考点总结 第2章线性表 2.1知识结构图 2.2重点归纳 2.3难点释疑 2.4真题高频考点总结 第3章栈、队列和数组 3.1知识结构图 3.2重点归纳 3.3难点释疑 3.4真题高频考点总结 第4章树和二叉树 4.1知识结构图 4.2重点归纳 4.3难点释疑 4.4真题高频考点总结 第5章图 5.1知识结构图 5.2重点归纳 5.3难点释疑 5.4真题高频考点总结 第6章查找 6.1知识结构图 6.2重点归纳 6.3难点释疑 6.4真题高频考点总结 第7章排序 7.1知识结构图 7.2重点归纳 7.3难点释疑 7.4真题高频考点总结 第二部分计算机组成原理 第1章计算机系统概述 1.1知识结构图 1.2重点归纳 1.3难点释疑 1.4真题高频考点总结 第2章数据的表示与运算 2.1知识结构图 2.2重点归纳 2.3难点释疑 2.4真题高频考点总结 第3章存储层次结构 3.1知识结构图 3.2重点归纳 3.3难点释疑 3.4真题高频考点总结 第4章指令系统 4.1知识结构图 4.2重点归纳 4.3难点释疑 4.4真题高频考点总结 第5章中央处理器（CPU） 5.1知识结构图 5.2重点归纳 5.3难点释疑 5.4真题高频考点总结 第6章总线 6.1知识结构图 6.2重点归纳 6.3难点释疑 6.4真题高频考点总结 第7章输入输出（I／O）系统 7.1知识结构图 7.2重点归纳 7.3难点释疑 7.4真题高频考点总结 第三部分操作系统 第1章操作系统概述 1.1知识结构图 1.2重点归纳 1.3难点释疑 1.4真题高频考点总结 第2章进程管理 2.1知识结构图 2.2重点归纳 2.3难点释疑 2.4真题高频考点总结 第3章存储管理 3.1知识结构图 3.2重点归纳 3.3难点释疑 3.4真题高频考点总结 第4章文件管理 4.1知识结构图 4.2重点归纳 4.3难点释疑 4.4真题高频考点总结 第5章输入输出（I／O）管理 5.1知识结构图 5.2重点归纳 5.3难点释疑 5.4真题高频考点总结 第四部分计算机网络 第1章计算机网络体系结构 1.1知识结构图 1.2重点归纳 1.3难点释疑 1.4真题高频考点总结 第2章物理层 2.1知识结构图 2.2重点归纳 2.3难点释疑 2.4真题高频考点总结 第3章数据链路层 3.1知识结构图 3.2重点归纳 3.3难点释疑 3.4真题高频考点总结 第4章网络层 4.1知识结构图 4.2重点归纳 4.3难点释疑 4.4真题高频考点总结 第5章传输层 5.1知识结构图 5.2重点归纳 5.3难点释疑 5.4真题高频考点总结 第6章应用层 6.1知识结构图 6.2重点归纳 6.3难点释疑 6.4真题高频考点总结

编辑推荐

《考研计算机学科专业基础综合考点速记手册(2014)》自出版后以其独特的内容编排、精辟的要点讲解获得广大考研学子的一致推崇。

---

 北航2014考研计算机学科专业基础综合考点速记手册下载

---