2017年安徽农业大学信息与计算机学院829数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． —
组记录的关键码为
准得到的一次划分结果为（ ）。
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为一次划分结束。
2． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A
【解析】磁带存储是一种顺序存储，顺序文件
是记录按其在文件中的逻辑顺序
依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。
3． 下列关于中断方式和DMA 方式比较的叙述中，错误的是（ ）
A.
中断
方式请求的是方式请求的是CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后，中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C.
中断D. 中断部设备
第 2 页，共 72 页
则利用快速排序的方法，以第一个记录为基
方式下数据传送通过软件完成，方式下数据传送通过软件完成，DMA 方式下数据方式适用于所有外部设备，方式适用于所有外部设备，DMA 方式仅适用于快速外
传送由硬件完成
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中，由于无需CPU 干预，因而可使CPU
设备并行工作。仅当输完一个数据时，才需CPU 花费极短的时间去做些中断处理。因此中
断申请使用的是CPU 处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式：数据传输的基本单位是数据块，即在CPU 与设备之间，每次传送至少一个数据块，DMA 方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的或者相反；仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
4． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果 B. 指令和数据的寻址方式 C. 指令周期的不同阶段 D. 指令和数据所在的存储单元 【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
5． 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录 一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
6． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N B.2N-1 C.2N D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂
第 3 页，共 72 页
度为
7． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A
【解析】进程等待的操作完成便会从等待状态转移到就绪状态。
8． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表 B. 广度优先搜索网 C. 前序（根）遍历二叉树 D. 深度优先搜索网 【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
9． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A
【解析】
归并排序的辅助空间为
快速排序所占用的辅助空间为
堆排序所占
用的辅助空间为
10．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 【答案】A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
分别变为新的有序区和新的无序区。
和
该趟排序
交换，使
将它与无序区的第1个记录
第 4 页，共 72 页
相关内容
相关标签