2018年中国农业科学院资源区划所808数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 用户程序发出磁盘
（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
2． 若一个栈以向量 存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
A.top :＝top ＋l ；V[top]:＝x
B.V[top]:＝x ；top :＝top ＋l
C.top :＝top ﹣l ；V[top]:＝x
D.V[top]:＝x ；top :＝top ﹣l
【答案】C
【解析】题中初始栈顶指针top 为n ＋1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
3． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
4． 某自治系统内采用RIP 协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息“＜netl ，16＞”，则能得出的结论是（ ）.
A.R2可以经过R1到达netl ，跳数为17
B.R2可以到达netl ，跳数为16
C.R1可以经过R2到达netl ，跳数为17
D.R1不能经过R2到达netl
【答案】D
【解析】RIP 允许一条路径最多只能包含15个路由器，因此距离等于16时相当于不可达，因此RIP 协议里规定16为路由不可达，答案为D.
5． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
6． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
7． 假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.
A.110， 170， 180， 195， 68， 45， 35， 12
B.110， 68， 45， 35， 12， 170， 180， 195
C.110， 170， 180， 195， 12， 35， 45， 68
D.12， 31， 45， 68， 110， 170， 180， 195
可直接在将数据带入公
【答案】A
【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返. 因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号(从小到大的顺序) ；往回返时又会按照从大到小的顺序进行服务. 注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110， 170， 180， 195， 68， 45， 35， 12
8． 现在有一颗无重复关键字的平衡二叉树(AVL 树) , 对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中, 正确的是（ ）。
A. 根节点的度一定为2
B. 树中最小元素一定是叶节点
C. 最后插入的元素一定是叶节点
D. 树中最大元素一定是无左子树
【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空, 则空操作; 否则:
①中序遍历左子树; ②访问根节点; ③中序遍历右子树”。
A 项错误, 当树中仅有一个或者两个结点时, 根节点的度就可能不为2; B 项错误, 树中最小元素是中序遍历时最后访问的节点, 当没有右子树时, 最后访问的节点是根节点; C 项错误, 当最后插入的元素破坏树的平衡后, 树会进行调整, 使其成为中间节点; D 项正确, 由中序遍历的特点可知, 左子树的值大于根节点, 所以最大元素一定没有左子树。
9． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为
用的辅助空间为O(1)。
10．输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，
，堆排序所占