2017年北京师范大学地理学与遥感科学学院978数据结构考研题库
● 摘要
一、填空题
1． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
2． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
3． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
4． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
5． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
6． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
8．
【答案】5
=_____
9． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则则的地址为，）则 的地址为_____。若
的地址为将代入得33。
10．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。 【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
11．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
12．在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
13．—个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
14．设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的
数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。
【答案】①1; 1; f （m ，n －1）; n ②9
15．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
二、选择题
16．冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
17．下列寄存器中，汇编语言程序员可见的是（ ）。
A. 存储器地址寄存器（MAR ）
B. 程序计数器（PC ）
C. 存储器数据寄存器（MDR ）
D. 指令寄存器（IR ）
【答案】B
【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址
，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）
是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。
18．计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A. 可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
【答案】B
【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输