2017年青海大学程序设计之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。
2． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：
其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，
若
OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；
量，用补码表示。转移执行时，转移目标地址为
为请回答下列问题。
（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？
（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行
时
则该指令执行后PC 的值是多少？若该指令执行时
则该指令执行后PC 的值又是多少？请给出计算过程。
（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？
（4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。 顺序执行时，下条指令地址
【答案】
（1）因为指令长度为16位且下条指令地址为
向后最多可跳转127条指令。
N=l, 故应根据ZF 和NF 的值来判断是否转移。（2）指令中C = 0, Z=l，当CF=0, ZF=0, NF=1
时需转移。已知指令中偏移量为1110 0011B=E3H, 符号扩展后为FFE3H , 左移一位（乘2）后为FFC6H , 故PC 的值（即转移目标地址）为
PC
的值为
（3）指令中的C 、Z 和N 应分别设置为
法器：地址相加。
3． 主机H 通过快速以太网连接Internet , IP地址为
题 a 表
时不转移。故编址单位是字节。 题中给出偏移量OFFSET 为8位补码，其范围为-128〜127, 故相对当前指令进行条件跳转，（4）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加服务器S 的IP 地址为211.68.71.80。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号已经收到的应用层数据的字节数
为
相关内容
相关标签