2023年沈阳航空航天大学数据结构复试实战预计五套卷

本文格式为Word版，下载可任意编辑——2023年沈阳航空航天大学数据结构复试实战预计五套卷

目录

2023年沈阳航空航天大学数据结构复试实战预计五套卷（一）22023年沈阳航空航天大学数据结构复试实战预计五套卷（二）92023年沈阳航空航天大学数据结构复试实战预计五套卷（三）172023年沈阳航空航天大学数据结构复试实战预计五套卷（四）222023年沈阳航空航天大学数据结构复试实战预计五套卷（五）30

第1页，共35页

2023年沈阳航空航天大学数据结构复试实战预计五套卷（一）

说明：本资料为2023复试学员内部使用，终极模拟预计押题，实战检测复试复习效果。————————————————————————————————————————

一、应用题

1．简述广义表属于线性结构的理由。

广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个〞的元素，只有一个称为“最终一个〞的元素，第一元素有后继而没有前驱，最终一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

2．某主机的MAC地址为00-15-C5-C1-5E-28,IP地址为00（私有地址）。题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图以太网帧结构

第2页，共35页

题d图IP分组头结构

（1）以太网的数据部分是IP数据报，只要找出相应字段所在的字节即可。根据图47-c可知以太网头部有6+6+2=14字节，根据图47-d可知IP地址有16字节，从图47-b第一个字节开始数14+16=30字节，得目的IP地址为40.aa.62.20即2。而以太网帧的前6字节00-21-27-21-51-ee是目的MAC地址，即为主机的默认网关端口的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地址，头部校验和，生存时间。

2023年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解

3．已知有5个顶点的图G如下图所示

请回复以下问题

（1）写出图G的邻接矩阵A（行、列下标从0开始）。（2）求什么？

（1）邻接矩阵为

第3页，共35页

矩阵中位于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中的