1、全国自考数据结构导论（树、文件）模拟试卷 1 及答案与解析一、单项选择题1 设树 T 的度为 4，其中度为 1、2、3、4 的结点个数分别为 4、2、1、1，则 T 中的叶子树为_。（A）5（B） 6（C） 7（D）82 树的先序遍历与_等价。（A）二叉树的前序遍历（B）二叉树的中序遍历（C）二叉树的后序遍历（D）树的后序遍历3 树最适合用来表示_。（A）有序数据元素（B）元素之间具有分支层次关系的数据（C）无序数据元素（D）元素之间无联系的数据4 树的基本遍历策略可分为先序遍历和后序遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。若把由树转化得到的二叉树叫做这棵树对应的二叉树。
2、下列结论正确的是_。（A）树的先序遍历序列与其对应的二叉树的后序遍历序列相同（B）树的后序遍历序列与其对应的二叉树的后序遍历序列相同（C）树的先序遍历序列与其对应的二叉树的中序遍历序列相同（D）以上都不对5 树中所有结点的度等于所有结点数加_。（A）0（B） 1（C）一 1（D）26 直接存取文件的特点是_。（A）记录按关键字排序（B）记录可以进行顺序存取（C）存取速度快，但占用较多的存储空间（D）记录不需要排序，存取效率高7 对文件进行直接存取的根据是_。（A）按逻辑记录号去存取某个记录（B）按逻辑记录的关键字去存取某个记录（C）按逻辑记录的结构去存取某个记录（D）按逻辑记录的具体内容去存取
3、某个记录8 倒排文件的主要优点是_。（A）便于进行插入和删除运算（B）便于进行文件的合并（C）能大大提高次关键字的查找速度（D）能大大节省存储空间9 索引顺序文件的记录，在逻辑上按关键字的顺序排列，但物理上不一定按关键字顺序存储，故需建立一张指示逻辑记录和物理记录之间一一对应关系的_。（A）链接表（B）索引表（C）符号表（D）交叉访问题10 索引非顺序文件是指_。（A）主文件有序，索引表有序（B）主文件有序，索引表无序（C）主文件无序，索引表有序（D）主文件无序，索引无有序二、填空题11 除根结点以外，树中每个结点有_个前趋，_个后继。12 如下图所示的树有_个叶结点，有_个分支结点，度为_，
4、A 结点的兄弟是_。13 树的存储结构主要有_、_和_。14 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为_。15 一棵树的广义表表示为 a(b(c，d(e ，f)，g(h)， i(j，k(x，y)，结点 d 和 x 的层数分别为_和_。16 散列文件关键在于选择好的_和_方法。17 对索引顺序文件既能进行_存取，又能进行_存取，因而是最常用的文件组织方式之一。18 对磁带上的顺序文件进行更新某记录时，必须_整个文件。而在顺序文件的最后添加新的记录时，则不必_整个文件。19 记录的_结构是数据在物理存储器上的存储方式。20 文件的基本运算分为检索和修改两类，前者有 3 种方式，分别
5、是_、_和_。21 索引文件的检索分两步完成，第一步是_，第二步是_。22 直接存取文件是用_方法组织的。23 树索引文件的特点是_。24 磁带和磁盘的主要差别是_。25 磁带文件和磁盘文件排序的主要差别是_。三、应用题26 如下图所示的树，回答以下问题： (1)写出根结点；(2)写出所有叶结点；(3) 写出 E 的双亲；(4)写出 E 的兄弟；(5)写出 H 的祖先；(6)写出 A 的子孙；(7)树的深度是多少?(8)E 的层次数是多少?27 如图所示的树，给出该树的先序遍历序列和后序根遍历序列。28 如图所示的树，给出该树的双亲表示法和孩子兄弟表示法的图示。29 如下图所示的一棵树，请把它
6、转换成二叉树。30 如下图所示的二叉树，请把它转换成森林。31 如下图所示的森林，将它转换成二叉树。32 试编写算法，对一棵以孩子一兄弟链表表示的树统计叶子的个数。32 试编写一个算法，将双亲表示法存储的树转化为：33 带双亲的孩子链表；34 孩子一兄弟表示法。35 什么是文件的逻辑记录和物理记录?它们有什么区别与联系?36 简述磁带和磁盘的结构和存储信息的特点。37 简述 ISAM 文件组织方法和操作特点。38 简述散列文件的查找方法及优缺点。39 文件的检索效率取决于哪些因素。40 某一文件有 18 个记录，关键字分别为：285，116，070，923，597，177，512，262，01
7、5，076，157，208，337，817，613，117，390，362。桶的容量 m=3，桶数 b=7，用除留余数法构造哈希函数 H(key)=keyMOD7。所得散列文件如下图所示，若还有两个键值分别为 132，370 的记录，它们将如何存放。41 设有一个职工文件，每个记录有如下格式： 职工号、姓名、职称、性别、工资 其中“职工号 ”为主关键字，其他为次关键字，如下表所示。试用下列结构组织这个文件：(1)索引无序文件 (2)多重表文件 (3) 倒排文件全国自考数据结构导论（树、文件）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 度为 0 的结点数为：n 0=1
8、+ (i 一 1)ni=1+(21)2+(31)1+(4 一1)1=8【知识模块】 树2 【正确答案】 B【知识模块】 树3 【正确答案】 B【知识模块】 树4 【正确答案】 A【知识模块】 树5 【正确答案】 C【知识模块】 树6 【正确答案】 D【知识模块】 文件7 【正确答案】 A【知识模块】 文件8 【正确答案】 C【知识模块】 文件9 【正确答案】 B【知识模块】 文件10 【正确答案】 C【知识模块】 文件二、填空题11 【正确答案】 1 0 或多【知识模块】 树12 【正确答案】 3 3 3 B 和 C【知识模块】 树13 【正确答案】 双亲存储结构孩子存储结构孩子兄弟存储结构【
9、知识模块】 树14 【正确答案】 n 一 1【知识模块】 树15 【正确答案】 34【知识模块】 树16 【正确答案】 散列函数冲突处理。【知识模块】 文件17 【正确答案】 顺序二分。【试题解析】 索引顺序文件是带有索引的有序文件，所以在其上既可以进行顺序存取，又可以进行二分存取。【知识模块】 文件18 【正确答案】 复制复制。【试题解析】 顺序文件中逻辑记录的顺序与物理记录的顺序是一致的。其特点是若存取第 j 个记录，必须先依次搜索它前面的 i 1 个记录，因此插入的新记录只能添加在文件的末尾，而要更新文件中的某个记录时，必须将整个文件进行复制。【知识模块】 文件19 【正确答案】 物理【
10、知识模块】 文件20 【正确答案】 顺序存取 直接存取 按关键字存取。【知识模块】 文件21 【正确答案】 将索引表读入内存查找到相应的物理地址根据索引表所指示的物理地址将记录所在的数据块读入内存进行查找【知识模块】 文件22 【正确答案】 哈希【知识模块】 文件23 【正确答案】 一种适合分支查找的动态索引【知识模块】 文件24 【正确答案】 磁盘是直接存取设备，读写一个信息块的时间与当前读写头所处的位置关系不大，而磁带是顺序存取设备，读写一个信息块的时间与所读位息块距当前读写头的位置关系很大。【知识模块】 文件25 【正确答案】 初始归并段在外存储介质中的分布方式【知识模块】 文件三、应用
11、题26 【正确答案】 (1)I (2)C，E，F ，G，H (3)B (4)F，G (5)I ，A，D (6)D，H (7)4 (8)3【知识模块】 树27 【正确答案】 先序遍历序列：IADHBEFGC；后序遍历序列：HDAEFGBCI。【知识模块】 树28 【正确答案】 【知识模块】 树29 【正确答案】 【知识模块】 树30 【正确答案】 【知识模块】 树31 【正确答案】 【知识模块】 树32 【正确答案】 int CountLeavies(CsTreeT) *统计用孩子一兄弟表示法存储的树 T 的叶子结点数*count=0jif(T) InitQueue(Q)；EnQueue(Q，T
12、) ； *初始化队列并让根入队列*while(iEmptyQueue(Q)DeQueue(Q，P)；if(p 一frrstchild=NULL)count+;elseEnQueue(Q，p 一firstchild) ；q=P 一nextsibiling；while(q) *右兄弟非空 * EnQueue(O，q)；q=q 一nextsibling；retum count；【试题解析】 由树的孩子一兄弟表示法可知，若结点 p 的 firstchild 为空，则该结点即为叶子结点，对树 T 进行层次遍历，找出所有满足条件的结点即为叶子结点的数目，算法描述如下。【知识模块】 树【知识模块】 树33
13、【正确答案】 void PChangeC(PTreeT1，CTreefbr(i=0;ifrrstchild=q；first=0;sibling=P 一frrstchild；elsesibling 一nextsibling=q;sibling=q;returnp；【试题解析】 将双亲表示的存储结构转化成孩子一兄弟表示法，首先找出根结点，然后在双亲表示法的存储结构中找出双亲是根的所有结点，若根的第一个孩子为空，则将某结点作为根的第一个孩子，其余结点作为兄弟。对双亲表示法中的任意一结点，均递归建立其孩子一兄弟链表。算法描述如下。【知识模块】 树35 【正确答案】 记录是文件存取操作的基本单位。逻辑记
14、录是按用户观点的基本存取单位，物理记录是按外存设备观点的基本存取单位。通常逻辑记录和物理记录之间存在三种关系：(1)一个物理记录存放一个逻辑记录；(2)一个物理记录包含多个逻辑记录；(3)多个物理记录表示一个逻辑记录。【知识模块】 文件36 【正确答案】 磁带结构：目前使用的磁带一般有 12 英寸宽，最长可达 3 600 英尺。在 12 英寸的带面上，横向上可记录 9 位或 7 位二进制信息(分别称为 9 道带或 7 道带)。磁带上的信息是以块为单位存放的。一个信息块由若干字节构成，如 512 字节或 1024 字节。要读写某一个块上信息，首先要定位，即通过磁带的移动使磁头对准被读块的前端。磁
15、带不是连续运转的设备，而是一种启停设备，为适应启动的加速和停止时的滑动，磁带上块之间需要留出间隙，间隙通常为 1434 英寸长，间隙一般是一段空白区，不存放数据信息。磁带存储信息的特点：(1)一个信息块就是磁带存放的一个物理记录。通常一个信息块可存放多个逻辑记录；(2)磁带存放信息的优点是存储量大，缺点是因为磁带是一种顺序存储设备，它读写速度较慢。磁盘结构：磁盘存储器通常分为两种：硬盘和软盘。磁盘由若干个同心的圆磁道构成，若干个盘片可以通过一个主轴串在一起，构成一个盘组。各个盘面上半径相同的磁道在一起构成一个柱面，盘组有多少个盘面，因此说每个柱面有多少个磁道。一个磁道可分为若干段，每段是一个物
16、理记录。因此对盘组来讲其从大到小的存储单位依次为：柱面、磁道、物理记录。读写盘组上信息，首先要经过定位动作：(1)选定柱面：通过磁臂移动使磁头对准指定的柱面；(2)选定磁道：即选择对应所需盘面的磁头，这由电子线路实现，速度快；(3)找物理记录：磁头定位到要读写的区段，这是机械动作，速度较慢，需要几毫秒，真正用到读写信息的时间比定位时间少得多。磁盘存储信息的特点：与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应顺序存取，又适应随机存取。【知识模块】 文件37 【正确答案】 索引顺序存取方法 ISAM 是一种专为磁盘存取设计的索引顺序文件组织方法。ISAM 文件由多级主索引、柱面索引、磁道索
17、引和主文件组成。文件记录在同一盘组上存放时，应尽量先放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序存放。从操作上看其特点是：(1)ISAM 文件检索方法，先从主索引出发，找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发，在该磁道上进行顺序查找，直至找到为止。反之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。(2)在插入记录时，可能会发生溢出，因此，每个柱面上还开辟有一个溢出区。磁道索引项中有溢出索引项，由于 ISAM 文件中记录是按关键字顺序存放的，则在插人记录时，需移动记录，并将同一磁道
18、上最末一个记录移至溢出区，同时修改磁道索引。(3)在删除记录时，只需找到待删记录，在其存储位置上作删除标志即可，而不需移动记录或改变指针。在经过多次增删后，文件的结构可能变得很不合理，此时可能溢出区中存有大量记录，而基本区中，又浪费很多空间，因此需要周期地整理ISAM 文件，将溢出区中记录移到基本区中，空出溢出区。【知识模块】 文件38 【正确答案】 散列文件是用散列技术组织成的文件，其组织方法类似于散列表，但存储介质是外存储器。散列文件查找：在散列文件中进行查找时，首先根据给定值求得散列地址(即基桶号)，将基桶中的记录读入内存进行顺序查找。若查到关键字等于给定值的记录，则检索成功。当在基桶内
19、查不到时，若基桶没有填满，则文件不含待查记录；否则根据指针域的值找到溢出桶，并将桶中的记录读入内存，继续进行顺序查找，直到查找成功或不成功。优缺点：散列文件具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。但散列文件不能顺序存取，只能按关键字随机存取，在经过多次插入、删除后，可能出现溢出而其桶内多数记录已被删除的情况，此时需要重新组织文件。【知识模块】 文件39 【正确答案】 为提高文件的检索效率，应对文件的组织方式、文件采用何种物理结构、文件的存储类型、记录的类型、大小、关键字的数目以及文件操作等因素进行综合考虑。【知识模块】 文件40 【正确答案】 因为 1327=6，将 132 直接插入基桶编号 6，如图 6(a)(b)所示。又因为 3707=6，将 370 插入基桶编号 6，发生“溢出” ，采用拉链法解决溢出，如图 6(c)所示。【知识模块】 文件41 【正确答案】 (1)索引无序文件如图(a)所示。(2)多重表文件如图(b)所示。(3)倒排文件如图(c)所示。【知识模块】 文件
