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

一、综合题

1． 外排序中为何采用k 一路(k>2)合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什么？

【答案】外排序用k-路归并(k>2)是因为k 越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

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

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

【答案】KMP 算法的时间复杂性是O(m＋n) 。

p 的next 和nextval 值分别为01112212321和01102201320。

3． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

4． 索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道(盘面) 三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面) 三级索引。在ISAM 文件上检索记录时，先从主索引(柱面索引的索引) 找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

5． 证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。

【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对

左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

6． 分析ISAM 文件() 和

VSAM 文件() 的应用场合、优缺点等。

【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。

VSAM 文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。

优缺点:与ISAM 文件相比，VSAM 文件有如下优点:动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于B+树的VSAM 文件通常作为大型索引顺序文件的标准组织。

7． 某主机的MAC 地址为, :IP 地址为(私有地址) 。图a 是网络拓扑, 图b 是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASC Ⅱ码内容。

图a 网络拓扑

图b 以太网数据帧(前80字节)

请参考图中的数据回答以下问题。

(1)Web服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？

(2)该主机在构造图b 的数据帧时, 使用什么协议确定目的MAC 地址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？

(3)假设协议以持续的非流水线方式工作, 以此请求一响应时间为页面引用了5个JPEG 小图像,

则从发出图b 中的Web 请求开始到浏览器收到全部内容为止, 需要多少个RTT?

(4)该帧所封装的IP 分组经过路由器R 转发时, 需修改IP 分组头中的哪些字段? 注:以太网数据帧结构和IP 分组头结构分别如图c 、图d 所示。

图c 以太网帧结构

图d IP分组头结构

【答案】(1)以太网的数据部分是IP 数据报, 只要找出相应字段所在的字节即可。根据图c 可知以太网头部有6+6+2=14字节, 根据图d 可知IP 地址有16字节, 从图b 第一个字节开始数14+16=30字节, 得目的IP 地址为是目的MAC 地址, 即为主机的默认网关即。而以太网帧的前6字节端口的MAC 地址。

(2)该主机在构造题b 图的数据帧时, 使用ARP 协议确定目的MAC 地址。封装该协议请求报文的以太网帧的目的MAC 地址是广播地址即FF-FF-FF-FF-FF-FF 。

(3)假设HTTP/1.1协议以持续的非流水线方式工作, 客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT 用于请求Web 页面, 客户机收到第一个请求的响应后, 每访问一次对象就需一个页面引用了5个JPEG 小图像, 则从发出图b 中的Web 请求开始到浏览开始到浏览器受到全部内容为止, 故共需1+5=6个RTT 后浏览器收到全部内容。

(4)私有地址要和Internet 上的主机通信时, 须由NA T 路由器进行网络地址转换, 转换为一个全

IP 数据报没经过一个路由器, 生存时间TTL 值就减少1, 并重新计算首部校验和。球IP 地址。所以

需修改的信息有源IP 地址, 头部校验和, 生存时间。

8． 某计算机字长16位，主存地址空间大小为128KB ，按字编址，采用单字长指令格式，指令各字段定义如下:

源操作数 目的操作数

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下: