2017年军事医学科学院生物工程研究所836计算机应用之数据结构考研题库
● 摘要
一、填空题
1． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
2． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
3． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
4． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
5． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
6． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
7． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
第 2 页，共 32 页
存放还没有转换过的结点，它的栈顶指针为。
（1）
{（2）
If （ （3） ）
} }}
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
8． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
9． 设数组
数组中任一元素均占内存48个二进制位，从首地址2000开始
连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】
数组的元素个数为需要
第8列有9个元素，共占
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
个单元。按列存储时，的起始地址为
10．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）
第 3 页，共 32 页
置成若
【答案】（1）
已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边
（3）算法结束时，相邻矩阵中的元素指出最小生成树的
11．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
12．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
13．高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为
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．表达式
【答案】
的后缀表达式是_____。
二、选择题
16．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
第 4 页，共 32 页