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

一、应用题

1．

设与记录

对应的关键字分别是

进行交换。

之前全部记录（其的关键字一定如果存在

和

使得

且成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括在之前且则即说明和【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极是反序；设对于和）中关键字最大为，故经过起泡排序前i-2次比较后，必定交换，证毕。

服务器S 的IP 地址为211.68.71.80。为又因故和Rf 为反序，由此可知 2． 主机H 通过快速以太网连接Internet , IP地址为

题 a 表

H 与S 使用TCP 通信时，在H 上捕获的其中5个IP 分组如题a 表所示。

请回答下列问题。

（1）题a 表中的IP 分组中，哪几个是由H 发送的? 哪几个完成了TCP 连接建立过程? 哪几个在通过快速以太网传输时进行了填充？

（2）根据题a 表中的IP 分组，分析S 已经收到的应用层数据字节数是多少？

（3）若题a 表中的某个IP 分组在S 发出时的前40字节如题b 表所列，则该IP 分组到达H 时经过了多少个路由器？

题 b 表

注：IP 分组头和TCP 段头结构分别如题a 图、题b 图所示：

题a 图IP 分组头结构

题b 图TCP 段头结构

【答案】（1）由于题a 表中1、3、4号分组的源IP 地址（第13〜16字节）均为192.168.0.8

，所 以1、3、4号分组是由H 发送的。 （coa80008H ）

，seq=846b41c5H, 2题a 表中1号分组封装的TCP 段的FLAG 为02H （即SYN=1，ACK=0）

，seq=e059 9feffl，ack=846b41c6H，号分组封装的TCP 段的 FLAG 为12H （即 SY=1, ACK=1）

3号分组封装的TCP 段的FLAG 为10H （即 ACK=1）seq=846b41c6H, ack=e059 9ff0H，，所以 1、2、3号分组完成了 TCP 连接建立过程。

5号分组的总长度为40由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、（28H ）

字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。

（2）由3号分组封装的TCP 段可知，发送应用层数据初始序号为846b 41c6H, 由5号分组封装的TCP 段可知，ack 为846b 所以5号已经收到的应用层数据的字节数

为

（3）由于S 发出的IP 分组的标识=6811H，所以该分组所对应的是题47-a 表中的5号分组。S 发出的IP 分组的TTL=40H=64, 5号分组的TTL=31H=49, 64-49=15。所以，可以推断该IP 分组到达H 时经过了15个路由器。

3． 请回答下列关于堆（Heap ）的一些问题：

（1）堆的存储表示是顺序的还是链接的？

（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？

【答案】（1）堆的存储是顺序的。

（2）最大值元素一定是叶结点，在最下两层上。

（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下：

由于第i 层上的结点数至多是以它为根的二叉树的深度为则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：

4． 为什么文件的倒排表比多重表组织方式节省空间？

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

5． 已知一个大小为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所示。