当前位置：问答库＞考研试题

一、应用题

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． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。

3． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：

（1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。

（2）当n=7时，给出一个最好情况的初始排序的实例。

第 2 页，共 36 页 协议实现介质访问控制，

数据传输率为主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过 数据帧的传播时（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据请

（3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。

（4）当n=7时，给出一个最坏情况的初始排序的实例。

【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为

以此类推，

总共进行

需2次，共10次即可。

（2）在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。

（3）在最坏情况下，若每次用来划分的记录的关键字具有最大（或最小）值，那么只能得到左（或右）子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递増次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

n=7时，最坏情况下的比较次数为21次。

（4）在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递増排序。

4．

已知一个整数序列

其中

则称x 为A 的主元素。

例如若存在

且则称5为主元素；

又如所以当的子文件，第二趟划分得到4个长度均为的子文件，趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一趟需比较6次，第二趟分别对两个子文件（长度均为3，k=2）进行排序，各

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中，请设计一个

尽可能高效的算法，找出A 的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或

【答案】

（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num 是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num 保存到c 中，记录Num 的出现次数为1; 若遇到的下一个整数仍等于Num ，则计数加1否则计数减1; 当计数减到0时，将遇到的下一个整数保存到c 中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c 中元素是否是真正的主元素，再次扫描该数组，统计c 中元素出现的次数，若大于则为主元素；否则，序列中不存在主元素。

（2）算法实现如下：

用来保存候选主元素，count 用来计数

设置A [0]为候选主元素

查找候选主元素

第 3 页，共 36 页 或Java 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。

为A 中的候选主元素计数

处理不是候选主元素的情况

更换候选主元素

统计候选主元素的实际出现次数

确认候选主元素

不存在主元素

，空间复杂度为O （1）（3）时间复杂度为O （n ）。

5． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

6． 一个循环队列的数据结构描述如下：

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？

【答案】（1）队空：

（2）队满：

这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。

第 4 页，共 36 页