2017年天津大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量
求写出完整的过程；并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空，初值为1000 full ：
表示缓冲区是否为满，初值为0
mutex 1：生产者之间的互斥信号，初值为1 mutex2：消费者之间的互斥信号，初值为1 available :当前消费者能否访问缓冲区，初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0
生产者进程：
生产一个产品；
产品送入buffer （in ）;
消费者进程
取出产品buffer （out ）;
第 2 页，共 36 页
操作实现进程间的互斥和同步，要
2． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
【答案】循环单链表若只设头指针，则出队操作时间复杂度是是
若只设尾指针，则出队和入队操作时间复杂度都是
而如对操作时间复杂度
因此，用循环单链表来实现队
列，设置一个尾指针更合适。
3． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第
个结点；若
则使q 指向链表中的第
表尾的长度相等。
③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。
（2）用C 语言算法描述如下：
两个指针同步向后移动
第 3 页，共 36 页
请设计一
个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字
或JA V A 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。
则使p 指向链
个结点，即使指针p 和q 所指的结点到
返回共同C 缀的起始点
或
其中m 、n 分别为两个链表的
（3）参考答案的时间复杂度为：长度。
4．
某局域网采用程。
协议实现介质访问控制，
数据传输率为主机甲和主机乙之
间的距离为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=
; 确认帧的传播时间
=2km/200000km/s=
;
发送1518B
所用的总时间为
主机甲的有效数据传输率为12000bit ／
1285.6μs=9.33Mbps。
5． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为
外部归
并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
（2）因为归并的趟数部排序的效率。
第 4 页，共 36 页
数据帧的传播时
（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都
可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外
相关内容
相关标签