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

一、综合题

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

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

2． 假定在一个8位字长的计算机中运行下列C 程序段:

若编译器编译时将8个8位寄存器R1〜R8分别分配给变量x 、y 、m 、n 、z1、Z2、k1和k2。请回答下列问题。(提示:带符号整数用补码表示)

(1)执行上述程序段后, 寄存器R1、R5和R6的内容分别是什么？(用十六进制表示)

(2)执行上述程序段后, 变量m 和k1的值分别是多少？(用十进制表示)

(3)上述程序段涉及带符号整数加/减、无符号整数加/减运算, 这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。

(4)计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中, 哪些带符号整数运算语句的执行结果会发生溢出？

【答案】(1)无符号整数运算,

(R1)=x=134=10000110B=86H、(R5)=x-y=246=10010000B=90H、(R6)=x+y=01111100B=7CH。

(2)m的机器数与x 的机器数相同为86H=10000110B, 解释为带符号整数(用补码表示) 时, 其值为-1111010B=-112;

同理kl=(m-n)=(x-y)=90H=10010000B, 解释为带符号整数(用补码表示) 时, 其值为-1111010B=-112;

(3)四种运算可以利用同一个加法器及辅助电路实现, n

位加法器实现的是模

法运算。对于无符号整数a 和b , a+b可以直接用加法器实现, 而

无符号整数加实现; 对于带

符号整数用补码表示, 补码加减运算公式为:

,

所以四种运算都可在n 位加法器中实现。

(4)判断溢出的方法有3种:一位符号位、进位位和双符号位。上述程序段中只有

负数。

3． 某主机的MAC 地址为语句会发生溢出, 因为2个带符号整数均为负数, 它们相加之后, 结果小于8位二进制所能表示的最小, :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 地址, 头部校验和, 生存时间。

4． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。

【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O(n)；而在链式存储方式下，插入和删除时间复杂度都是O(1)。

5． 下列关于堆(Heap)的一些问题:

(1)堆的存储表示是顺序的还是链接的？

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

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

【答案】(1)堆的存储是顺序的。

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

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

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

6． 将关键字序列(7，8，30，11，18，9，14) 散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组. 散列函数是:H(key)＝(key×3)M0D7，处理冲突采用线性探测再散列法，要求装填(载）因子为.

(1)请画出所构造的散列表.

(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度.