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 个顶点和多于n-1条边的无向连通图G —定不是树。
【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。
3． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。
4． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。 （2）求什么？
【答案】（1）邻接矩阵为
矩阵
中位于0行3列元素值的含义是什么？
非零元素的含义是
（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）
中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为
m 的路径的条数。
5． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足虑h 是整数. 则有
即任一结点个数为n 的二叉树的高度至少为
。解此不等式，并考
6． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为小为
因为
所以768和所以首址
大小为
互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回
其伙伴地址为
512、；大小为的空闲块。因为收后该伙伴系统的状态图如图2所示：
图2 回收后该伙伴系统的状态图
7． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：
（1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C 或，关键之处请给出简要注释。 现）
【答案】（1）算法的基本设计思想定义两个指针变量p 和q ，初始时均指向头结点的下一个结点。p 指针沿链表移动；当p 指针移动到第k 个结点时，q 指针开始与p 指针同步移动；当p
或JA V A 语言实