2017年武汉纺织大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。
【答案】删除P 后
删除D 后
2．
某局域网采用程。
协议实现介质访问控制，
数据传输率为主机甲和主机乙之
间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过
（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以太网帧的前导码）
【答案】（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短
：
=
（lkm/200000km/s）×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时，另一台主机才
发送数据，两台主机均检测到冲突的时间最长：
=1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps=间=2km/200000km/s
=
确认帧的发送时间=64×
8/10Mbps=
数据帧的传播时
;
（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
; 确认帧的传播时间
=2km/200000km/s=
发送1518B
所用的总时间为
1285.6μs=9.33Mbps。
3． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？ 【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下： 由于第i 层上的结点数至多是
以它为根的二叉树的深度为
则调用
次筛选算
法时总共进行的关键字比较次数不超过下式之值：
4． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序割成两部分：
和
和
且
将分
然后再递归地将
主机甲的有效数据传输率为12000bit ／
进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法
改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[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
5． 请阅读下列算法，回答问题。
问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置
|的作用是什么? 若将WHILE--DO 语句中判断条件改为
该
算法将会有什么变化，是否还能正确工作？
【答案】问题一：此为直接插入排序算法，该算法稳定。 问题二：采用
的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。
描述算法后，算法变为不稳定排序，但能正常工作。
6． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。
【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。
7． （1）判定起泡排序的结束条件是什么？
（2）请简单叙述希尔排序的基本思想。 （3）将下列序列调整成堆（堆顶为最小值）。
（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。
【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。
（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）
组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
（3）13，24，33，65，70，56，48，92，80，112
（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15
相关内容
相关标签