2018年齐鲁工业大学信息学院872数据结构考研仿真模拟五套题
● 摘要
一、应用题
1． 索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引？
【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道(盘面) 三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面) 三级索引。在ISAM 文件上检索记录时，先从主索引(柱面索引的索引) 找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。
2． 设某文件经内排序后得到100个初始归并段(初始顺串) ，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则
，因
，且k 为整数，故k=5，
即最少5-路归并可以完成排序。
3． 已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M), 下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里
)
(1)画出这六大城市的交通网络图； (2)画出该图的邻接表表示法；
(3)画出该图按权值递増的顺序来构造的最小(代价) 生成树。 【答案】(1)这六大城市的交通网络图如图1所示:
图1
(2)该图的邻接表表示法如图2所示:
图2
(3)最小生成树有6个顶点与条边:
4． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？
【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。
(2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。 5． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0 中的数据由 . 要求: (1)给出算法的基本设计思想. (2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由得到最终得到结果 然后 ， 变换为 原地逆置， 再将数组R 中的前，ti-P 个数和后P 个数分别原地逆置， (2)用C 语言算法描述如下: (3)说明算法的复杂性:上述算法中3个Reverse 函数的的时间复杂度分别为O(p/2)、O((p-2)/2)为0(n/2)，故算法的时间复杂度为O(n)，算法的空间复杂度为0(1). 二、算法设计题 6． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。 【答案】算法如下: 以后序遍历算法求以二叉树表示的算术表达式的 值 . 求左子树表示的子表达式的值