位置和最大元素值。
分块查找算法的具体步骤为：（a）在索引表中查找，确定待查找元素在哪一块，由于索引表有序，因此可以使用二分查找算法。（b）在已确定的块中，进行顺序查找。 7. 请简述二叉排序树的定义。
二叉排序树，又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树：
（a）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。 （b）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。 （c）左、右子树也分别是二叉排序树。 8. 请简述二叉排序树的插入和创建过程。
二叉排序树的插入过程：
在二叉排序树中插入一个新结点，应保证插入新结点后的二叉树仍然是一棵二叉排序树。对于一个给定元素K，将其插入到二叉排序树中的具体步骤如下：
（a）若二叉排序树为一棵空树，则将元素K作为二叉排序树的根结点。
（b）若K等于根结点的值，则该元素已经是二叉排序树中的结点，不需重复插入，直接返回；若K小于根结点的值，则将K插入到左子树中；若K大于根结点的值，则将K插入到右子树中。重复该步骤，直至要插入的子树为空，此时将K作为该子树的根结点。 二叉排序树的创建过程就是不断插入新结点的过程。 9. 请简述二叉排序树的查找过程。
对于给定值K，先将K与根结点的值比较，若相等则查找成功；若K小于根结点的值，则在左子树中继续进行二叉排序树的查找；否则，若K大于根结点的值，则在右子树中继续进行二叉排序树的查找。重复该过程，直至找到匹配的结点，查找成功；或者子树为空，查找失败。
10. 请简述哈希表的元素存储原理。
确定一函数h，对于关键字值是k的元素，以k为自变量计算函数值h(k)，这个函数值被解释为一片连续存储空间中的一个地址（即数组中的一个下标值），元素即被存入到这个地址中。
11. 请简述常用的四种哈希函数及其计算规则。
除余法：选取一个适当的正整数p（通常p为不大于哈希表存储空间尺寸的最大素数），以元素的关键字值k除以p，得到的余数作为元素的存储地址，即h(k)=k%p。
数字分析法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多、每一位的取值范围及关键字的取值分布情况预先知道，则可以对元素关键字的各位进行分析，去掉分布较集中的位、保留分布较均匀的位。
折叠法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多，但关键字的取值分布情况未知，则可以用折叠法将关键字分为几段（除了最后一段位数可以少一些，其他各段的位数均等于存储空间地址码位数），并将所有段的值做叠加求和运算，将叠加和的最高位进位舍去后取剩余部分作为元素的存储地址。
平方取中法：对元素的关键字值求平方，并取中间几位作为元素的存储地址。 12. 请简述常用的两种哈希表冲突处理方法。
开放定址法：按照某个探查序列在哈希表中进行搜索，直至找到一个空闲的地址，将发生冲突的新元素存储在该地址中。
拉链法：将所有同义词存储在一个线性链表中，从而避免开放定址法中的“二次聚集”现象。用拉链法构造的哈希表，若其有m个存储地址（下标为0, 1, …, m-1），则每个地址存储一个线性链表的头指针，映射到地址i的元素以结点的方式插入到地址i所对应的链表中。
第9章 文件
1. 请简述文件的定义。
文件，是由大量具有相同性质的记录组成的集合。
2. 请简述文件的组成。
文件是大量性质相同的数据记录的集合，即一个文件包含一条或多条记录。
记录是一个实体的所有数据项的集合，即一条记录包含一个或多个数据项。
数据项（也称为字段或属性）是反映实体某一方面属性的数据表示，是文件存取最基本的操作对象。
3. 请简述文件的分类。
按文件中记录的信息长度，可以将文件分为定长记录文件和不定长记录文件。若每个记录含有相同长度的信息，则称这类记录为定长记录；否则，若每个记录含有不同长度的信息，则称这类记录为不定长记录。由定长记录组成的文件称为定长文件；由不定长记录组成的文件则称为不定长文件。
按记录中关键字的数目，可以将文件分为单关键字文件和多关键字文件。若文件中的记录只有一个用于唯一标识记录的主关键字，则这类文件称为单关键字文件；若文件中的记录除了含有一个主关键字之外，还包含若干次关键字，则这类文件称为多关键字文件。 4. 请简述文件检索操作中的四种查询方式。
根据检索条件的不同可以分为以下4种查询方式：
（a）简单查询：根据给定值x按单个关键字查询关键字值k等于x的记录。 （b）区域查询：根据给定取值范围按单个关键字查询满足条件的记录。 （c）函数查询：根据统计函数计算的值查询记录。
（d）布尔查询：将以上3种查询用逻辑运算符(包括逻辑与、逻辑或、逻辑非)连接起来所形成的查询。
5. 请简述文件各维护操作的含义和过程。
文件维护是指对文件中记录所进行的插入、删除、修改等操作。这些操作的具体含义和操作过程描述如下：
（a）插入：向文件中添加一条新的记录。若文件按某个关键字顺序排列，则插入记录前一般要先通过检索确定插入点的位置。
（b）删除：从文件中删除一条记录。删除记录前一般要先通过检索确定所要删除记录的位置。
（c）修改：对记录中的一个或多个数据项进行修改。若文件按某个关键字顺序排列，且对关键字值进行了修改操作，则修改后还需将记录移动到正确的位置（一般采用先删除再插入的方式实现）。
6. 请简述文件的四种基本组织方式。
顺序结构、索引结构、散列结构和链式结构。 7. 请简述磁盘的逻辑结构。
磁盘的结构如下：
（a）一个磁盘包含若干个盘片，所有盘片组成了盘片组；每个盘片有上下两面，称为盘面；每个盘面上有很多同心圆形式的磁道，数据就存放在这些磁道上；每个磁道又可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。
（b）每个盘面都配有一个读写磁头，通过读写磁头可以对磁道上的数据进行读写操作；
所有读写磁头都安装在动臂上，通过动臂可以将读写磁头移动到任一磁道上；所有盘面上具有相同半径的磁道就构成了圆柱面，一个磁盘上圆柱面的个数就是一个盘面上的磁道数，同一时刻所有读写磁头都位于一个圆柱面上。
（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保存胜者去参与更高一层的比较。重复该步