2017年中山大学S3405005数学综合考试之数据结构考研复试核心题库
● 摘要
一、应用题
1．
某局域网采用
程。
（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。
2． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
数据帧的传播时（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据协议实现介质访问控制，
数据传输率为主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。
2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
3． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。
（1）画出可利用空间表的初始状态。
（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3）画出在回收3个占用块之后可利用空间表的状态。
【答案】（1）因为可利用空间表的初始状态图如图1所示：
图1 可利用空间表的初始状态
（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，
故将
的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为
的块。又将其中大小为的一块挂到可利用空间表上，
另一块再分裂成两个大小为的
块。其中一块的块挂到可利用空间表上，
另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
图2 每个用户得到的存储空间的起始地址
]
图3 可利用空间表的状态
（3）在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192，也在占用。回收大小为11的占用块时，其伙伴地址是48，可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示：
相关内容
相关标签