2018年安徽农业大学信息与计算机学院829数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
2． 下列选项中，操作系统提供的给应用程序的接口是（ ）.
A. 系统调用
B. 中断
C. 库函数
D. 原语
【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种:命令输入和系统调用. 其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口(GUI)、自然命令用户接口(NUI)等，而系统调用中除了常规的一些传统的系统调用(例如read （ ）) 以外，还有经过扩展的复杂调用(例如多种API) ，以及包含在Lib 库中的各种封装好的过程调用(最终都是通过系统调用陷入到操作系统中去的）等.
3． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。
4． 在下图所示的平衡二叉树中, 插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中, 插入48以后, 树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL(先右后左) 型平衡旋转, 需做两次(先右旋后左旋转) 旋转操作。过程如下图所示:
显然, 在调整后的新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
5． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
中含有元素的个数（ ）。 6． 数组
A.55
B.45
C.36
D.16
【答案】B
【解析】该数组为三维数组。其个数为5*3*3＝45。
7． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
C.G 中没有弧
【答案】D
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
B.G 中有一条从到的路径 D.G 中有一条从到的路径