发布时间 : 星期六 文章数据结构、算法与应用(C++语言描述)》习题参考答案doc更新完毕开始阅读9218270c7e192279168884868762caaedd33ba88
所有读写磁头都安装在动臂上，通过动臂可以将读写磁头移动到任一磁道上；所有盘面上具有相同半径的磁道就构成了圆柱面，一个磁盘上圆柱面的个数就是一个盘面上的磁道数，同一时刻所有读写磁头都位于一个圆柱面上。
（c）主轴带动所有盘面高速旋转，使得读写磁头可以访问到一个磁道上的所有扇区。 8.请简述对磁盘存储器进行一次读写操作的具体过程。
对磁盘存储器进行一次读写操作的具体步骤为：
（a）根据待读写数据所处的柱面，用动臂将读写磁头移动到此柱面上。
（b）根据待读写数据所处的扇区，用主轴带动盘面将该扇区转到读写磁头下面。 （c）用指定盘面上的读写磁头读写所需数据。 9. 请简述在磁盘上存储信息的原则。
盘面的转速很快，磁盘读写数据的时间大部分花在柱面定位上。寻查时间的长短取决于读写磁头移过的柱面数，所以在磁盘上存储信息时应尽量将相关的信息放在同一柱面或者邻近柱面上，以减少寻查时间。
10. 请简述顺序文件的定义和分类。
顺序文件的定义：
顺序文件是结构最简单的文件，文件中记录的物理顺序与逻辑顺序一致，即记录按其逻辑顺序依次存放在文件中。
顺序文件的分类： 按照存储方式的不同，顺序文件可以分为连续顺序文件和串联顺序文件。在连续顺序文件中，全部记录顺序地存放在外存的一片连续存储空间中。连续顺序文件的优点是存取速度快，缺点是存储空间尺寸需预先确定。在串联顺序文件中，以块为单位将记录存储在外存上，块中的各记录顺序存放在一片连续存储空间中，但块与块之间可以不连续，通过链指针将各块按一定顺序连接起来。串联顺序文件的优点是文件便于扩充，缺点是存取速度慢。
按照记录是否有序，顺序文件可以分为有序顺序文件和无序顺序文件。在有序顺序文件中，全部记录按主关键字有序排列；在无序顺序文件中，记录按实际插入顺序排列。有序顺序文件的优点是若记录定长则按主关键字检索时速度较快，无序顺序文件的优点是插入记录时效率较高。
11. 请简述顺序文件批量处理的步骤。
将待处理的顺序文件称为主文件，主文件按主关键字大小顺序排列；对文件的插入、删除、修改等操作请求全部放在事务文件中。根据事务文件中的操作对主文件进行更新生成新的主文件，具体处理步骤如下：
（a）对事务文件按照主文件中主关键字的顺序进行排序（对于修改主关键字值的操作，应转为删除记录和插入记录两个操作）。
（b）顺序读出主文件与事务文件中的记录，比较它们的主关键字值：
① 若主文件记录的关键字值小于事务文件记录的关键字值，则说明没有对该主文件记录做任何操作，此时将主文件记录直接写入新的主文件中，并读取下一条主文件记录。
② 若关键字值相同，则依据事务文件记录进行更改或删除操作，若为删除操作，则主文件记录不需要写入新的主文件中，若为修改操作则要将修改后的记录写入新的主文件中，操作完毕后分别读取下一条主文件记录和事务文件记录。
③ 若主文件记录的关键字值大于事务文件记录的关键字值，则为插入操作，需将事务文件中的记录直接写入到新的主文件中，并读取下一条事务文件记录。 12. 请简述索引文件的构成。
索引文件由主文件和索引表两部分构成。主文件中存储了所有的数据记录；索引表是一个映射关系表，存储了逻辑记录和物理记录的一一对应关系。
13. 请简述索引文件（即索引非顺序文件）和索引顺序文件的区别。
索引非顺序文件的主文件中各记录是无序的；索引顺序文件的主文件中各记录是按主关键字有序排列的。
14. 请简述索引文件的检索过程。
索引文件的检索过程为：
（a）将索引表读入内存中，并根据检索条件在索引表中进行查找（由于索引项按关键字有序排列，因此在索引表上可以采用折半查找算法）。
（b）若索引表中存在匹配项，则根据匹配索引项中存储的物理地址直接读取外存上的相应记录；若索引表中不存在该记录，则说明外存上也不存在该记录、不需做外存访问操作。 15. 请简述索引文件插入、删除、修改等维护操作的过程。
插入：在索引文件中插入一条新的记录时，直接将该记录写入主文件的末尾，并在索引表中插入索引项。
删除：在删除一条记录时，只需在索引表中删除对应的索引项即可。 修改：在修改记录时，需将修改后的记录写入主文件的末尾，并同时对索引表进行修改、将索引项中的物理地址改为修改后记录的存储地址。 16. 请简述稠密索引和稀疏索引的区别。
在索引非顺序文件中，记录没有按关键字有序排列，因此在建立索引表时，每个记录都必须对应一个索引项，这样建立的索引表称为稠密索引。这类索引表虽然管理成本较高，但它的优点是根据索引表即可确定待检索记录是否存在并可以根据索引项直接定位到记录，减少了外存操作。
在索引顺序文件中，记录按关键字有序排列，因此可以对文件中的记录分块，每块对应一个索引项，这样建立的索引表称为稀疏索引。在做检索操作时，这类索引表只能给出匹配记录可能在哪个范围中，无法直接定位到记录，但它占用的存储空间小、便于管理。 17. 请简述ISAM文件的组织方法。
在ISAM文件中，每个柱面的磁道被分为3个部分：
（a）一部分磁道作为记录存储的基本区，其中每一磁道将记录按主关键字大小进行有序顺序存储。
（b）一部分磁道作为记录存储的溢出区，在一个已满磁道中插入新记录时，就会产生溢出的记录（即该磁道容纳不下的记录），这些溢出记录以链表形式存储在溢出区中。
（c）一部分磁道作为索引区，用于存储磁道索引表。与基本区和溢出区相对应，表中的每一索引项又由基本索引项和溢出索引项组成。基本索引项用来存放基本区一个磁道中记录的最大关键字值和第一个记录的位置；溢出索引项用来存放从该磁道溢出记录的最大关键字值和该磁道在溢出区中的第一个溢出记录的位置。 18. 请简述VSAM文件的组织方法。
VSAM文件由索引集、顺序集和数据集三部分组成。文件的记录都存放在数据集中，数据集中的每一个结点称为一个控制区间，该区间是一片连续的存储空间、按关键字顺序存储若干条记录；顺序集中存放每一控制区间的索引项，索引项包括两部分内容：控制区间的最大关键字值和指向该控制区间的指针，若干逻辑上相邻的控制区间的索引项就构成了顺序集中的一个结点；索引集是按树型层次结构组织的索引集合，双亲结点包含了指向孩子结点的指针及该孩子结点中的最大关键字值，以顺序集中的结点作为叶子结点，可以构造一棵以索引集为非叶子结点的B+树。
19. 请简述散列文件的组织方法。
散列文件中的记录是以桶为单位成组存放的。若一个桶能存放m条记录，则当桶中已有m条同义词记录时，再存放第m+1条同义词记录就会发生“溢出”。在散列文件中，通
常采用拉链法作为冲突处理方法，即将第m+1条同义词记录存放到另一个称为“溢出桶”的桶中，相应地，将存放前m条同义词记录的桶称为“基桶”，在基桶中设置一个指向溢出桶的指针。
20. 请简述多关键字文件的作用。
多关键字文件是既包含主关键字索引、又包含多个次关键字索引的文件。在实际中，不仅会根据主关键字做查找，同时也会根据一系列次关键字做查找，此时使用多关键字文件可以提高查找效率。
21. 请简述多重表文件和倒排文件两种多关键字文件的组织方法。
多重表文件是将索引方法和链接方法相结合的一种文件组织方式，对主关键字建立的索引称为主索引，对每个需做查询操作的次关键字建立的索引称为次索引。在多重表文件中，记录通常按主关键字顺序排列，同时将具有相同次关键字值的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字作为对应次索引表中的索引项。
与多重表文件不同，倒排文件中具有相同次关键字的记录之间不进行链接，而是在对次关键字建立的索引中列出具有该次关键字值的所有记录的物理地址。倒排文件中的次关键字索引称为倒排表，倒排表与主文件一起就构成了倒排文件。 22. 请简述外排序与内排序的区别。
内排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列；而外排序是指需进行多次内/外存之间的数据交换的排序过程，适合较大的元素序列。 23. 请简述归并排序的处理步骤。
归并排序的处理步骤为：
（a）记录分段处理：将文件中的记录按照可用内存大小划分为若干段，依次将每段记录读入到内存中对其进行内部排序，并将排序结果输出到子文件中。这样可以生成多个有序的子文件（即文件内的记录是有序的），通常称经过排序后的段为初始归并段。
（b）文件归并处理：对上一步得到的初始归并段加以归并，直至将多段中的记录归并为一个有序文件为止。 24. 请简述败者树的结构。
败者树的结构如下：
（a）是一棵有K个叶子结点的完全二叉树。
（b）K个叶子结点分别存储从K个初始归并段中读取出来的K个待比较的记录。 （c）分支结点存储两个记录比较后败者（即具有较大关键字值的记录）所在叶子结点的序号，胜者参与更高一层的比较。
（d）通常在败者树的根结点之上再加一个结点来保存胜者（即当前K个记录中具有最小关键字值的记录）所在叶子结点的序号。 （25）请简述败者树的重构方法和创建方法。
败者树的重构方法：
令Loser[P]表示P号分支结点中保存的败者对应的叶子结点编号，若从第Q（0≤Q （a）计算编号为Q的叶子结点的双亲结点编号P=(Q+K)/2，双亲结点中存储的是上一轮比较中的败者Loser[P]（即Q号叶子结点的兄弟结点的编号），将Q号叶子结点与Loser[P]号叶子结点进行比较，若Q为胜者，则直接让Q参与更高一层的比较；否则，将Q作为败者保存在P号分支结点中，并令Q=Loser[P]，即用Q保存胜者去参与更高一层的比较。 （b）计算P号分支结点的双亲结点，即P=P/2，将Q号叶子结点与Loser[P]号叶子结点比较，同样，若Q为胜者，则直接让Q参与更高一层的比较；否则，将Q作为败者保存在P号分支结点中，并令Q=Loser[P]，即用Q保存胜者去参与更高一层的比较。重复该步骤直 至到达胜者结点，即P==0时败者树重构完毕。 败者树的创建方法： 在败者树中添加一个编号为K的辅助叶子结点，该结点中的记录值为待排序记录不可能达到的最小值MI，令所有分支结点的初值均为K（每插入一条记录就会有一个分支结点的值由K变为0～K-1之间的值）。依次从K个初始归并段中读取第一条记录插入败者树中，这样经过K次插入后，各分支结点的初始值K将被0～K-1所替代，此时即创建好了一棵败者树。