2017年北京物资学院计算机软件与理论911计算机学科专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
2． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
3． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和每个元素占2个单元，按行优先顺处的元素为_____。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
4． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
5． 建立索引文件的目的是_____。
【答案】提高查找速度
6． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
7． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
8． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
9． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
编号，以rear 指示实际的队尾元素，现
要在此队列中插入一个新元素，新元素的位置是（ ）。
10．二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
二、选择题
11．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3 C.2 D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
12．关键路径是AOE 网中（ ）。
A. 从始点到终点的最短路径 B. 从始点到终点的最长路径 C. 从始点到终点的边数最多的路径 D. 从始点到终点的边数最少的路径 【答案】B
【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。
13．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 【答案】B
14．设有向图
G= （V ，E ），顶点集
V={V0, VI ，V2, V3}，边
集
若从顶点V0开始对图进行深度优先遍历，则可
能得到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：