2017年沈阳航空航天大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
2． 某主机的MAC 地址为00-15-C5-C1-5E-28, IP 地址为10.2.128.100 （私有地址）。题a 图是网络拓扑，题b 图是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASCII 码内容。
题a 图网络拓扑
题b 图以太网数据帧（前80字节）
请参考图中的数据回答以下问题。
（1）Web 服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？
（2）该主机在构造题47-b 图的数据帧时，使用什么协议确定目的MAC ±也址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？
（3）假设HTTP/1.1协议以持续的非流水线方式工作，以此请求一响应时间为RTT ，rfc.html 页面引用了5个JPEG 小图像，则从发出题b 图中的Web 请求开始到浏览器收到全部内容为止，需要多少个RTT?
（4）该帧所封装的IP 分组经过路由器R 转发时，需修改IP 分组头中的哪些字段? 注：以太网数据帧结构和IP 分组头结构分别如题c 图、题d 图所示。
题c 图以太网帧结构
题d 图IP 分组头结构
【答案】（1）以太网的数据部分是IP 数据报，只要找出相应字段所在的字节即可。根据图47-c 可知以太网头部 有6+6+2=14字节，根据图47-d 可知IP 地址有16字节，从图47-b 第一个字节开始数14+16 = 30字节，得目的IP 地址为40.aa.62.20即64.170.98.32。而以太网帧的前6字节00-21-27-21-51-ee 是目的MAC 地址，即为主机的 默认网关10.2.128.1端口的MAC 地址。
（2）该主机在构造题47-b 图的数据帧时，使用ARP 协议确定目的MAC 地址。封装该协议请求报文的以太网帧的目的MAC 地址是广播地址即FF-FF-FF-FF-FF-FF 。
（3）假设HTTP/1.1协议以持续的非流水线方式工作，客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT 用于请求Web 页面，客户机收到第一个请求的响应后，每访问一次对象就需一个RTT 。rfc.html 页面引用了5个JPEG 小图像，则从发出题47-b 图中的Web 请求开始到浏览开始到浏览器受到全部内容为止，故共需1+5 = 6个RTT 后浏览器收到全部内容。
（4）私有地址要和Internet 上的主机通信时，须由NAT 路由器进行网络地址转换，转换为一
IP 数据报没经过一个路由器，个全球IP 地址。生存时间TTL 值就减少1，并重新计算首部校验和。
所以需修改的信息有源IP 地址，头部校验和，生存时间。
2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
3． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。
（2）求什么？
【答案】（1）邻接矩阵为
矩阵中位于0行3列元素值的含义是什么？ 非零元素的含义是（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为m 的路径的条数。
4． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?