2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题
● 摘要
目录
2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题（一） ... 2 2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题（二） . 14 2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题（三） . 25 2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题（四） . 37 2017年桂林理工大学信息科学与工程学院878数据结构及程序设计考研冲刺密押题（五） . 49
第 1 页，共 58 页
一、选择题
1． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
2． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。
A.X 的双亲
B.X 的右子树中最左的结点
C.X 的左子树中最右的结点
D.X 的左子树中最右的叶结点
【答案】C
【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。
3． 下列各类存储器中，不采用随机存取方式的是（ ）。
A.EPROM
B.CDROM
C.DRAM
D.SRAM
【答案】B
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM 是只读的光盘存储器，采用串行存取方式而不是随机存取方式。
第 2 页，共 58 页 其Next 数组值为（ ）。
4． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。
5． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps , 电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）。
A. 增加160m
B. 增加80m
C. 减少160m
D. 减少80m
【答案】D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x 报文发送速率，本题最小数据帧长度减少800b ，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×）/（l ×）=160m，由于时间延时存在两倍的关系，因此减少的距离为80m 。
6． 数据链路层采用选择重传协议（SR ）传输数据，发送方已发送了0H3号数据倾，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（ ）。
A.1
B.2
C.3
D.4
【答案】B
【解析】在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接 收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认，要特别注意其与GBN 协议的区别。本题收到1号帧的确认，说明1号帧正确接收，0和2号帧依次超时，因此必须重传，然而3号帧尚未超时，是否正确接收未知，故不用重传，因此必须重传0和2号帧，答案是B 。
第 3 页，共 58 页
7． 将森林F 转换为对应的二叉树T , F中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩 子指针指向当前节点的兄弟节点，所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以 选C
8． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器
II.RAM 和ROM 都采用随机存取方式进行信息访问
III.RAM 和ROM 都可用作Cache
IV.RAM 和ROM 都需要进行刷新
A. 仅I 和II
B. 仅II 和III
C. 仅 I 、II 和IV
D. 仅II 、III 和IV
【答案】A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性）
，同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）区别在
于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
9． 某同步总线的时钟频率为
所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz ，贝时钟周期为10ns 。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5=50ns。
第 4 页，共 58 页 宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据