2018年西南民族大学计算机导论之数据结构(C语言版)复试实战预测

考研专业课资料、辅导、答疑一站式服务平台

第 1 页，共 40 页

目录

2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（一） (2)

2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（二） (11)

2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（三） (17)

2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（四） (23)

2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（五） (30)

考研专业课资料、辅导、答疑一站式服务平台

第 2 页，共 40 页 2018年西南民族大学计算机导论之数据结构(C 语言版)复试实战预测五套卷（一） 特别说明：

1-本资料为2018复试学员内部使用，终极模拟预测押题，实战检测复试复习效果。

2-资料仅供复试复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。 ————————————————————————————————————————

一、应用题

1． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60)，试完成下列各题。

(1)按次序构造一棵二叉排序树BS 。

(2)依此二叉排序树，如何得到一个从大到小的有序序列？

(3)画出在此二叉排序树中删除“66”后的树结构。

【答案】(1)构造的二叉排序树如图1所示:

图1二叉排序树

(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。

(3)如图2所示:

图2

2． 给出模式串在KMP 算法中的next 和nextval 数组。

【答案】模式串的next 函数定义如下:

根据此定义，

可求解模式串的next 和nextval 值如下:

考研专业课资料、辅导、答疑一站式服务平台

第 3 页，共 40 页

3． 某主机的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 第一个字节开始数

考研专业课资料、辅导、答疑一站式服务平台

第 4 页，共 40 页 14+16=30字节,得目的IP 地址为即。而以太网帧的前6字节是目的MAC 地址,即为主机的默认网关端口的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 地址。IP 数据报没经过一个路由器,生存时间TTL 值就减少1,并重新计算首部校验和。所以

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

4． 某16位计算机中,带符号整数用补码表示,数据Cache 和指令Cache 分离。题44表给出了指令系统中部分指令格式,其中Rs 和Rd 表示寄存器,mem 表示存储单元地址,(X)表示寄存器X 或存储单元X 的内容。

表 指令系统中部分指令格式

该计算机采用5段流水方式执行指令,各流水段分别是取指(IF)、译码/读寄存器(ID)、执行/计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB),流水线采用“按序发射,按序完成”方式,没有采用转发技术处理数据相关,并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。

(1)若int 型变量x 的值为-513,存放在寄存器R1中,则执行指令“SHRR1”后,R1的内容是多少？(用十六进制表示)

(2)若某个时间段中,有连续的4条指令进入流水线,在其执行过程中没有发生任何阻塞,则执行这4条指令所需的时钟周期数为多少？

(3)若高级语言程序中某赋值语句为

和b 均为int 型变量,它们的存储单元地址分别表示为和。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。则这4条指令执行过程中,的ID 段和的IF 段被阻塞的原因各是什么？

考研专业课资料、辅导、答疑一站式服务平台

第 5 页，共 40 页

图 指令序列及其执行过程示意图

(4)若高级语言程序中某赋值语句为

,x 和a 均为unsignedint 类型变量,它们的存储单元地址分别表示为,则执行这条语句至少需要多少个时钟周期?要求模仿上图画出这条语

句对应的指令序列及其在流水线中的执行过程示意图。 【答案】(1)x 的机器码为补,即指令执行前

,右移1wei 后

为

1111B ,即指令执行后。 (2)至少需要个时钟周期数。

(3)的ID 段被阻塞的原因:因为

与和都存在数据相关,需等到和将结果写回寄存器后,才能读寄存器内容,所以的ID 段被阻塞。

的正段被阻塞的原因:因为的前一条指令在HD 段被阻塞,所以的IF 段被阻塞。

(4)对应的指令序列为:

这5条指令在流水线中的执行过程如下图所示,执行语句最少需要17个时钟周期。

本文来源：https://www.bwwdw.com/article/vjaq.html