2017年兰州大学综合考试之数据结构复试仿真模拟三套题
● 摘要
一、应用题
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，3，4，5，并设标识符依以下次序出现
：
要求用哈希（Hash ）方法将它们存入具有10个位置的表
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少； （2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。 【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
（关键字各字符编码之和）
数据帧的传播时
（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
协议实现介质访问控制，
数据传输率为
主机甲和主机乙之
间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过
3． 阅读下列算法，指出算法A 的功能和时间复杂性。
【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。
时间复杂度：0（n ）。
4． 一个循环队列的数据结构描述如下：
给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？
【答案】（1）队空：
（2）队满：
这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。
5． 在某程序中，有两个栈共享一个一维数组空间的栈底。
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句
分别是两个栈
出栈主要语句
（2）
6． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？ （2）试证明
。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
7． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。
完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
图1
【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0
相关内容
相关标签