2018年齐鲁工业大学信息学院872数据结构考研核心题库
● 摘要
一、应用题
1． 设LS 是一个线性表，
，若采用顺序存储结构，则在等概率的前提下，
之间
的概率为
插入一个元素需要平均移动的元素个数是多少?
若元素插在
与
【答案】需要分两种情况讨论:
(1)等概率(后插) ，插入位置0..n ，则平均移动个数为n/2。 (2)若不等概率，则平均移动的元素个数为
2． 在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPACE[N﹣1]分别是两个栈的栈底。
(1)对栈1、栈2，试分别写出(元素X) 入栈的主要语句和出栈的主要语句。 (2)对栈1、栈2，试分别写出栈满、栈空的条件。 【答案】(1)入栈主要语句
//设X 为入栈元素
.
出栈主要语句
//返回出栈元素
//返回出栈元素
(2)
栈满条件:top2﹣topl ＝l
栈空条件:topl ＝﹣l 并且top2＝N //topl＝﹣l 为左栈空，top2＝N 为右栈空
3． 分析ISAM 文件(
VSAM 文件(
) 和
) 的应用场合、优缺点等。
，则插入一个元素需要平均移动的元素个数又是多少？
【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存
储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。
VSAM 文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。
优缺点:与ISAM 文件相比，VSAM 文件有如下优点:动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于B+树的VSAM 文件通常作为大型索引顺序文件的标准组织。
4． 给出一组关键字:29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程:
归并排序，每归并一次书写一个次序。 快速排序，每划分一次书写一个次序。
堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】(1)2—路归并第一趟:18，29，25，47，12，58，10，51; 第二趟:18，25，29，47，10，12，51，58; 第三趟:10，12，18，25，29，47，51，58
(2)快速排序第一趟:10，18，25，12，29，58，51，47; 第二趟:10，18，25，12，29，47，51，88; 第三趟:10，12，18，25，29，47，51，88 (3)堆排序
建大堆:58，47，51，29，18，12，25，10; ①②③④⑤⑥⑦
5． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？
【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。
二、算法设计题
6． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
7． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
8． 编写算法，求二叉树的宽度。
【答案】算法如下:
相关内容
相关标签