《2017年南京大学工程管理学院962管理学与管理信息系统之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南京大学工程管理学院962管理学与管理信息系统之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南京大学工程管理学院962管理学与管理信息系统之数据结构考研强化模拟题一、选择题1 下列选项中，在用户态执行的是（ ）。A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。 2 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。A. 递归次数与初始数据的排列次
2、序无关B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。 在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的
3、分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。 3 设栈S 和队列Q 的初始状态为空，元素依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是则栈S 的容量至少应该是（ ）。A.6 B.4 C.3 D.2【答案】C4 在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）。A. 数据链路层 B. 传输层 C. 会话层 D. 应用层 【答案】B【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路
4、层不满足题意。题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输。所以本题答案应该是B 项。在OSI 模型中网络层提供的是主机到主机的通信服务。 5 采用简单选择排序，比较次数与移动次数分别为（ ）。 【答案】C【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比 较的次数为 6 在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。 A.13、48 B.24、48 C.24、53 D.24、90 【答
5、案】C【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示： 显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。 7 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）A.1和5 B.2和4 C.4和2 D.5和1 【答案】B【解析】入队操作的主要步骤：个后， 8 动态存储管理系统中，通常可有（ ）种不同的分配策略
6、。 【答案】C【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。9 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。I. 若该文件的数据不在内存，则该进程进入睡眠等待状态；II. 请求read 系统调用会导致CPU 从用户态切换到核心态；III. read系统调用的参数应包含文件的名称A. 仅 I 、II加入一个后，再加入一删除一个后，出队操作的主要步骤：一、选择题考研试题
