2017年北京交通大学10101数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，
，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序
割成两部分：和和
且
将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[28]，07，39，10，65，14，61，17，50，21
21移动：21，07，39，10，65，14，61，17，50，[]
39移动：21，07，[]，10，65，14，61，17，50，39
17移动：21，07，17，10，65，14，61，[]，50，39
65移动：21，07，17，10，[]，14，61，65，50，39
14移动：21，07，17，10，14，[28]，61，65，50，39
2． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：
（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；
（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。
【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：
图1
（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：
图2
3． 假定有下列，矩阵（n 为奇数）
如果用一维数组B 按行主次序存储A 的非零元素，问：
（1）A 中非零元素的行下标与列下标的关系；
（2）给出A 中非零元素的下标
位在B 中的位置公式。
【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有
所以A 中非零元素的行下标和列下标的关系是或 的关系，与B 中的下标R 的关系； 给出利用的下标定（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标
是
副对角线上的元素，在中心元素前，在向量B
中存储的下标是
在中心元素后，其下标如下：
（3）在B 中的位置如下：
4． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。
（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
【答案】
⑴如图1所示：
图1
（2）开始结点（入度为0）:
（3）拓扑序列：
规则：开始结点为
或之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 （4）正向邻接表如图2所示，逆向邻接表如图3所示：
终端结点（出度为0）:
图2 正向邻接表
相关内容
相关标签