2022年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 31 页

目录

2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（一） (2)

2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（二） (8)

2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（三） (12)

2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（四） (18)

2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（五） (25)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 31 页 2018年沈阳工业大学信息科学与工程学院808数据结构考研冲刺狂背五套题（一） 说明：本套狂背五套题按照考研侧重点和出题难度，严格筛选提取了历年考试高频核心试题及重点题型，更突出针对性和实战性，适用于考研冲刺最后狂背。

——————————————————————————————————————————

一、填空题

1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t ,则结点i 和j 在同一层上的条件是

。

2． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1)表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l ＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

3． 有向图G=(V ,E)，其中，用三元组表示弧

及弧上的

权d 。E(G)为

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4

4． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

5． 在单链表中设置头结点的作用是_____。

【答案】方便运算

6． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0,则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

二、解答题

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 31 页 7． 某局域网采用CSMA/CD 协议实现介质访问控制，数据传输率为10Mbps ，主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/s.请回答下列问题，要求说明理由或写出计算过程.

(1)若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间?最长需经过多长时间？(假设主机甲和主机乙发送数据过程中，其他主机不发送数据）

(2)若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧(1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？(不考虑以太网帧的前导码）

【答案】(1)当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短:Tmin

＝

当一台主机发送的数据就要到达另一台主机时，另一台主机才发

送数据，两台主机均检测到冲突的时间最长:

(2)有效数据传输速率＝发送的有效数据/发送有效数据所用的总时间.发送的有效数据＝

1500B ＝1500×8bit ＝12000bit ;发送1518B

的发送时间

数据帧的传播时间＝2km/200000km/s

＝;确认帧的发送时间＝64×8/10Mbps

＝

;

确认帧的传播时间；发送1518B 所用的总时间为主机甲的有效

数据传输率为

8． 设度为m 的树采用多重链表存储。每个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。则空指针的数目是多少?说明这种存储方式的利弊。

【答案】(1)空指针数目:n(n>0)个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有

+1个。 (2)利弊:这种存储结构统一，便于处理但空链域造成存储效率低。

9． 某主机的MAC 地址为,:IP 地址为(私有地址)。图a 是网络拓扑,图b 是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASC Ⅱ码内容。

图a 网络拓扑

图b 以太网数据帧(前80字节)

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 31 页 请参考图中的数据回答以下问题。

(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 地址为即。而以太网帧的前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 地址,头部校验和,生存时间。

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