2017年武汉纺织大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47 第二趟：12，16，23，35，16，25，36， 19，21，47 第三趟：12，16，23，16，25，35， 19，21，36， 47 第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47 第五趟：12，16，16，19，23，25，21，35， 36， 47 第六趟：12，16，16，19，21， 23，25，35， 36， 47 第七趟：12，16，16，19，21，23，25，35， 36， 47
2． 假定有下列，
矩阵（n 为奇数）
如果用一维数组B 按行主次序存储A 的非零元素，问： （1）A 中非零元素的行下标与列下标的关系； （2）给出A 中非零元素的下标
与B 中的下标R 的关系；
（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为位在B 中的位置公式。
给出利用的下标定
【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有所以A 中非零元素的行下标和列下标的关系是
或
的关系，
（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标
是
副对角线上的元素，在中心元素前，在向量B
中存储的下标是
在中心元素后，其下标如下：
（3）在B 中的位置如下：
3． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？ 【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下： 由于第i 层上的结点数至多是
以它为根的二叉树的深度为
则调用
次筛选算
法时总共进行的关键字比较次数不超过下式之值：
4． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为小为
因为
所以768和所以首址
大小为
互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回
其伙伴地址为
512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
5． 设LS 是一个线性表，
若采用顺序存储结构，则在等概率的前提下，插
与
之间
的概率
为
入一个元素需要平均移动的元素个数是多少? 若元素插
在
【答案】需要分两种情况讨论：
，插入位置0..n ，则平均移动个数为（1）等概率（后插）
（2）若不等概率，则平均移动的元素个数为
则插入一个元素需要平均移动的元素个数又是多少？