2017年南京师范大学教育科学学院829数据结构考研题库
● 摘要
一、选择题
1． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。
2． 下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS 管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
【答案】A 。
【解析】考查闪存的特性，闪存是EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是ROM 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由flash 芯片组成的，故答案为A 。
3． 下列选项中，导致创建新进程的操作是（ ）。
用户登录成功
设备分配
启动程序执行
A. 仅和
B. 仅和
C. 仅和
D.
和
【答案】C
【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填
，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调）
，也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”
统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。
4． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块
B. 顺序
C. 折半
D. 哈希
【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
5． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
6． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
7． 计算机开后，操作系统最终被加载到（ ）
A.BIOS
B.ROM
C.EPROM
D.RAM
【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区，这段区城是RAM ，故答案选D 。
8． 在任意一棵非空二叉排序树T1中，删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）
I. 若v 是T1的叶结点，则T1与T3不同
II. 若v 是T1的叶结点，则T1与T3相同
III. 若v 不是T1的叶结点，则T1与T3不同
IV. 若v 不是T1的叶结点，则T1与T3相同
A. 仅 I 、III
B .仅 I 、IV
C. 仅 II 、III
D. 仅 II 、IV
【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。
9． 假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ） A.
B.
C.
D.
【答案】B
转换为等价后缀表达式的过程中，