2017年安徽农业大学信息与计算机学院829数据结构考研题库
● 摘要
一、选择题
1． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
2． 在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（ ）。
A. 可变分配，全局置换 B. 可变分配，局部置换 C. 固定分配，全局置换 D. 固定分配，局部置换 【答案】
【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；，或根据程序员、③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等）
程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n 个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。
3． 下列选项中，描述浮点数操作速度指标的是（ ）。
A.MIPS B.CPI C.IPC
D.MFLOPS 【答案】D
【解析】
表示每秒执行多少百万次浮点
. 表示每秒执行多少百万条指令。对于一个给定的程序，
MIPS 定义为
这里所说的指令一般是指加、减运算这类短指令。
就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，
造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。
运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。
每个时钟周期执行的指令数。
4． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
5． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
B.
C.
D. 【答案】C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
6． 两台主机之间的数据链路层采用后退N 帧协议（GBN ）传输数据，数据传输速率为16kbps ，单向传播时延为270ms ，数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因
此首先计算出发送一帧的时间
这段时间总共可以发送
故发送一帧到收到确认为止的总时间为
，为了保证发送帧序号和确认帧（帧）
序号在此期间不重复，因此帧序号的比特数至少为4, 答案为B
7． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。
A.1 B.2 C.4 D.5
【答案】B
【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆， （2）为插入18后，
（3）比较10与18，交换后，
（4）比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。
8． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 【答案】D