2017年江苏师范大学智慧教育学院管理信息系统与数据结构(加试)之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
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． 请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60
（ ）排序的结果为：13，15，18，12，20，60
（ ）排序的结果为：13，15，20，18，12，60
（ ）排序的结果为：12，13，20，18，15，60
【答案】①快速排序②起泡排序③直接插入排序④堆排序
4． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
5． 一个循环队列的数据结构描述如下：
给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？
【答案】（1）队空：
（2）队满：
这种判断方法，会“牺牲一个存储单元”。为了不损失存储空间，可以通过设置标志位的方式来进行队空和队满的判断。设标记tag ，tag 等于0情况下，若删除时导致front=rear为队空; tag=l情况下，若因插入导致front=rear则为队满。
6． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，