数据结构章节练习题及答案9.docx

《数据结构章节练习题及答案9.docx》由会员分享，可在线阅读，更多相关《数据结构章节练习题及答案9.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9章文件1 .请简述文件的定义。文件，是由大量具有相同性质的记录组成的集合。2 .请简述文件的组成。文件是大量性质相同的数据记录的集合，即一个文件包含一条或 多条记录。记录是一个实体的所有数据项的集合，即一条记录包含一个或多 个数据项。数据项（也称为字段或属性）是反映实体某一方面属性的数据表 示，是文件存取最基本的操作对象。3 .请简述文件的分类。按文件中记录的信息长度，可以将文件分为定长记录文件和不定 长记录文件。假设每个记录含有相同长度的信息，那么称这类记录为定长 记录；否那么，假设每个记录含有不同长度的信息，那么称这类记录为不定 长记录。由定长记录组成的文件称为定长文件；由不定长记录组

2、成的 文件那么称为不定长文件。按记录中关键字的数目，可以将文件分为单关键字文件和多关键 字文件。假设文件中的记录只有一个用于唯一标识记录的主关键字，那么 这类文件称为单关键字文件；假设文件中的记录除了含有一个主关键字 之外，还包含假设干次关键字，那么这类文件称为多关键字文件。4 .请简述文件检索操作中的四种查询方式。个待比拟的记录。(C)分支结点存储两个记录比拟后败者(即具有较大关键字值的 记录)所在叶子结点的序号，胜者参与更高一层的比拟。(d)通常在败者树的根结点之上再加一个结点来保存胜者(即当 前K个记录中具有最小关键字值的记录)所在叶子结点的序号。25 .请简述败者树的重构方法和创立方法

3、。败者树的重构方法：令LoserP表示P号分支结点中保存的败者对应的叶子结点编号, 假设从第Q (0QK)个初始归并段中读取记录到序号为Q的叶子结 点中，那么败者树的重构过程如下：(a)计算编号为Q的叶子结点的双亲结点编号PT(Q+K)/2，双 亲结点中存储的是上一轮比拟中的败者LoserfP(即Q号叶子结点的 兄弟结点的编号)，将Q号叶子结点与LoserP号叶子结点进行比拟, 假设Q为胜者，那么直接让Q参与更高一层的比拟；否那么，将Q作为败 者保存在P号分支结点中，并令Q=LoserP,即用Q保存胜者去参 与更高一层的比拟。(b)计算P号分支结点的双亲结点，即PfP/2，将Q号叶子结 点与L

4、oseHP号叶子结点比拟，同样，假设Q为胜者，那么直接让Q参 与更高一层的比拟；否那么，将Q作为败者保存在P号分支结点中， 并令Q=LoserP,即用Q保存胜者去参与更高一层的比拟。重复该 步骤直至到达胜者结点，即P=0时败者树重构完毕。败者树的创立方法:在败者树中添加一个编号为K的辅助叶子结点，该结点中的记 录值为待排序记录不可能到达的最小值MI,令所有分支结点的初值 均为K （每插入一条记录就会有一个分支结点的值由K变为。K-1 之间的值）。依次从K个初始归并段中读取第一条记录插入败者树 中，这样经过K次插入后，各分支结点的初始值K将被。K-1所替 代，此时即创立好了一棵败者树。根据检索条

5、件的不同可以分为以下4种查询方式:(a)简单查询：根据给定值x按单个关键字查询关键字值k等 于x的记录。(b)区域查询：根据给定取值范围按单个关键字查询满足条件 的记录。(C)函数查询：根据统计函数计算的值查询记录。(d)布尔查询：将以上3种查询用逻辑运算符(包括逻辑与、逻 辑或、逻辑非)连接起来所形成的查询。5 .请简述文件各维护操作的含义和过程。文件维护是指对文件中记录所进行的插入、删除、修改等操作。这些操作的具体含义和操作过程描述如下：(a)插入：向文件中添加一条新的记录。假设文件按某个关键字 顺序排列，那么插入记录前一般要先通过检索确定插入点的位置。(b)删除：从文件中删除一条记录。删

6、除记录前一般要先通过 检索确定所要删除记录的位置。(c)修改：对记录中的一个或多个数据项进行修改。假设文件按 某个关键字顺序排列，且对关键字值进行了修改操作，那么修改后还需 将记录移动到正确的位置(一般采用先删除再插入的方式实现)。6 .请简述文件的四种基本组织方式。顺序结构、索引结构、散列结构和链式结构。7 .请简述磁盘的逻辑结构。磁盘的结构如下：(a) 一个磁盘包含假设干个盘片，所有盘片组成了盘片组；每个 盘片有上下两面，称为盘面；每个盘面上有很多同心圆形式的磁道， 数据就存放在这些磁道上；每个磁道又可以划分为假设干段，称为扇区, 一个扇区就是一次读写的最小数据量。(b)每个盘面都配有一个

7、读写磁头，通过读写磁头可以对磁道 上的数据进行读写操作；所有读写磁头都安装在动臂上，通过动臂可 以将读写磁头移动到任一磁道上；所有盘面上具有相同半径的磁道就 构成了圆柱面，一个磁盘上圆柱面的个数就是一个盘面上的磁道数， 同一时刻所有读写磁头都位于一个圆柱面上。(c)主轴带动所有盘面高速旋转，使得读写磁头可以访问到一 个磁道上的所有扇区。8 .请简述对磁盘存储器进行一次读写操作的具体过程。对磁盘存储器进行一次读写操作的具体步骤为：(a)根据待读写数据所处的柱面，用动臂将读写磁头移动到此 柱面上。(b)根据待读写数据所处的扇区，用主轴带动盘面将该扇区转 到读写磁头下面。(c)用指定盘面上的读写磁头

8、读写所需数据。9 .请简述在磁盘上存储信息的原那么。盘面的转速很快，磁盘读写数据的时间大局部花在柱面定位上。 寻查时间的长短取决于读写磁头移过的柱面数，所以在磁盘上存储信 息时应尽量将相关的信息放在同一柱面或者邻近柱面上，以减少寻查 时间。10 .请简述顺序文件的定义和分类。顺序文件的定义：顺序文件是结构最简单的文件，文件中记录的物理顺序与逻辑顺 序一致，即记录按其逻辑顺序依次存放在文件中。顺序文件的分类：按照存储方式的不同，顺序文件可以分为连续顺序文件和串联顺 序文件。在连续顺序文件中，全部记录顺序地存放在外存的一片连续 存储空间中。连续顺序文件的优点是存取速度快，缺点是存储空间尺 寸需预先

9、确定。在串联顺序文件中，以块为单位将记录存储在外存上, 块中的各记录顺序存放在一片连续存储空间中，但块与块之间可以不 连续，通过链指针将各块按一定顺序连接起来。串联顺序文件的优点 是文件便于扩充，缺点是存取速度慢。按照记录是否有序，顺序文件可以分为有序顺序文件和无序顺序 文件。在有序顺序文件中，全部记录按主关键字有序排列；在无序顺 序文件中，记录按实际插入顺序排列。有序顺序文件的优点是假设记录 定长那么按主关键字检索时速度较快，无序顺序文件的优点是插入记录 时效率较高。11 .请简述顺序文件批量处理的步骤。将待处理的顺序文件称为主文件，主文件按主关键字大小顺序排 列；对文件的插入、删除、修改等

10、操作请求全部放在事务文件中。根 据事务文件中的操作对主文件进行更新生成新的主文件，具体处理步骤如下:(a)对事务文件按照主文件中主关键字的顺序进行排序(对于 修改主关键字值的操作，应转为删除记录和插入记录两个操作)。(b)顺序读出主文件与事务文件中的记录，比拟它们的主关键 字值：假设主文件记录的关键字值小于事务文件记录的关键字值，那么 说明没有对该主文件记录做任何操作，此时将主文件记录直接写入新 的主文件中，并读取下一条主文件记录。假设关键字值相同，那么依据事务文件记录进行更改或删除操作, 假设为删除操作，那么主文件记录不需要写入新的主文件中，假设为修改操 作那么要将修改后的记录写入新的主文件

11、中，操作完毕后分别读取下一 条主文件记录和事务文件记录。 假设主文件记录的关键字值大于事务文件记录的关键字值，那么 为插入操作，需将事务文件中的记录直接写入到新的主文件中，并读 取下一条事务文件记录。12 .请简述索引文件的构成。索引文件由主文件和索引表两局部构成。主文件中存储了所有的 数据记录；索引表是一个映射关系表，存储了逻辑记录和物理记录的 一一对应关系。13 .请简述索引文件(即索引非顺序文件)和索引顺序文件的区 别。索引非顺序文件的主文件中各记录是无序的；索引顺序文件的主文件中各记录是按主关键字有序排列的。14 .请简述索引文件的检索过程。索引文件的检索过程为：(a)将索引表读入内存

12、中，并根据检索条件在索引表中进行查 找(由于索引项按关键字有序排列，因此在索引表上可以采用折半查 找算法)。(b)假设索引表中存在匹配项，那么根据匹配索引项中存储的物理 地址直接读取外存上的相应记录；假设索引表中不存在该记录，那么说明 外存上也不存在该记录、不需做外存访问操作。15 .请简述索引文件插入、删除、修改等维护操作的过程。插入：在索引文件中插入一条新的记录时，直接将该记录写入主 文件的末尾，并在索引表中插入索引项。删除：在删除一条记录时，只需在索引表中删除对应的索引项即 可。修改：在修改记录时，需将修改后的记录写入主文件的末尾，并 同时对索引表进行修改、将索引项中的物理地址改为修改后

13、记录的存 储地址。16 .请简述稠密索引和稀疏索引的区别。在索引非顺序文件中，记录没有按关键字有序排列，因此在建立 索引表时，每个记录都必须对应一个索引项，这样建立的索引表称为 稠密索引。这类索引表虽然管理本钱较高，但它的优点是根据索引表 即可确定待检索记录是否存在并可以根据索引项直接定位到记录，减少了外存操作。在索引顺序文件中，记录按关键字有序排列，因此可以对文件中 的记录分块，每块对应一个索引项，这样建立的索引表称为稀疏索弓I。 在做检索操作时，这类索引表只能给出匹配记录可能在哪个范围中， 无法直接定位到记录，但它占用的存储空间小、便于管理。17 .请简述ISAM文件的组织方法。在ISAM

14、文件中，每个柱面的磁道被分为3个局部：(a) 一局部磁道作为记录存储的基本区，其中每一磁道将记录 按主关键字大小进行有序顺序存储。(b) 一局部磁道作为记录存储的溢出区，在一个已满磁道中插 入新记录时，就会产生溢出的记录(即该磁道容纳不下的记录)，这 些溢出记录以链表形式存储在溢出区中。(c) 一局部磁道作为索引区，用于存储磁道索引表。与基本区 和溢出区相对应，表中的每一索引项又由基本索引项和溢出索引项组 成。基本索引项用来存放基本区一个磁道中记录的最大关键字值和第 一个记录的位置；溢出索引项用来存放从该磁道溢出记录的最大关键 字值和该磁道在溢出区中的第一个溢出记录的位置。18 .请简述VSA

15、M文件的组织方法。VSAM文件由索引集、顺序集和数据集三局部组成。文件的记录 都存放在数据集中，数据集中的每一个结点称为一个控制区间，该区 间是一片连续的存储空间、按关键字顺序存储假设干条记录；顺序集中 存放每一控制区间的索引项，索引项包括两局部内容：控制区间的最 大关键字值和指向该控制区间的指针，假设干逻辑上相邻的控制区间的 索引项就构成了顺序集中的一个结点；索引集是按树型层次结构组织 的索引集合，双亲结点包含了指向孩子结点的指针及该孩子结点中的 最大关键字值，以顺序集中的结点作为叶子结点，可以构造一棵以索 引集为非叶子结点的B+树。19 .请简述散列文件的组织方法。散列文件中的记录是以桶为

16、单位成组存放的。假设一个桶能存放m 条记录，那么当桶中已有m条同义词记录时，再存放第m+1条同义词 记录就会发生“溢出在散列文件中，通常采用拉链法作为冲突处理 方法，即将第m+1条同义词记录存放到另一个称为“溢出桶”的桶中, 相应地，将存放前m条同义词记录的桶称为“基桶”，在基桶中设置 一个指向溢出桶的指针。20 .请简述多关键字文件的作用。多关键字文件是既包含主关键字索引、又包含多个次关键字索引 的文件。在实际中，不仅会根据主关键字做查找，同时也会根据一系 列次关键字做查找，此时使用多关键字文件可以提高查找效率。21 .请简述多重表文件和倒排文件两种多关键字文件的组织方 法。多重表文件是将索

17、引方法和链接方法相结合的一种文件组织方 式，对主关键字建立的索引称为主索引，对每个需做查询操作的次关 键字建立的索引称为次索引。在多重表文件中，记录通常按主关键字 顺序排列，同时将具有相同次关键字值的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字作为对应次索引表中的索引项。与多重表文件不同，倒排文件中具有相同次关键字的记录之间不 进行链接，而是在对次关键字建立的索引中列出具有该次关键字值的 所有记录的物理地址。倒排文件中的次关键字索引称为倒排表，倒排 表与主文件一起就构成了倒排文件。22 .请简述外排序与内排序的区别。内排序是指待排序列完全存放在内存中所进行的排序过程，适合 不太大

18、的元素序列；而外排序是指需进行屡次内/外存之间的数据交 换的排序过程，适合较大的元素序列。23 .请简述归并排序的处理步骤。归并排序的处理步骤为：(a)记录分段处理：将文件中的记录按照可用内存大小划分为 假设干段，依次将每段记录读入到内存中对其进行内部排序，并将排序 结果输出到子文件中。这样可以生成多个有序的子文件(即文件内的 记录是有序的)，通常称经过排序后的段为初始归并段。(b)文件归并处理：对上一步得到的初始归并段加以归并，直 至将多段中的记录归并为一个有序文件为止。24 .请简述败者树的结构。败者树的结构如下：(a)是一棵有K个叶子结点的完全二叉树。(b) K个叶子结点分别存储从K个初始归并段中读取出来的K