2018年东北财经大学计算机应用技术806计算机综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移
24空间，因此最大段长为2B.
2． 用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
3． 以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队
D. 栈
【答案】A
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
4． 无向图G=(V，E) ，其中:
，
对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f
B.a , c , f , e , b , d
C.a , e , b , c , f , d
D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
根据
关系。依据
上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。
5． 若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、
堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。
6． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
7． 中断处理和子程序调用都需要压桟以保护现场, 中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
可知各顶点之间的邻接
D. 通用地址寄存器
【答案】B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关, 而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序, 并要求其去处理某一事件的一种常用手段。因此, 除了要保护当前程序的地址, 计数器(指针) 和数据寄存器以外, 还需要保存程序状态字。子程序调用是与当前进程有关, 是正在运行的程序有意安排执行的, 这一类调用发生的时间以及位置具有确定性, 处于同一个进程内, 因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。
8． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是:假设待排序的记
录存放在数组中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区中适当的位置上。使和，其中:前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。将当前无序区的第1个记录变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
9． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
10．线性表是具有n 个（ ）的有限序列(n＞0) 。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
E. 信息项