2017年大连海事大学交通运输管理学院813管理信息系统与数据结构考研冲刺密押题
● 摘要
一、填空题
1． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
2． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
5． 建立索引文件的目的是_____。
【答案】提高查找速度
6． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
7． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____
，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
第 2 页，共 42 页
8． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】
【解析】叶子节点的左右孩子都不存在。
9． 设有两个算法在同一机器上运行，其执行时闻分别为
_____。
【答案】15
【解析】当
10．设广义表
时，则而，时， 要使前者快于后者，n 至少为 是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
二、判断题
11．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
12．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
13．通常使用队列来处理函数或过程的调用。（ ） 【答案】
【解析】经常使用栈来处理函数或过程的调用。
14．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）
【答案】×
【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。
15．二叉树是一般树的特殊情形。（ ）
【答案】×
【解析】树与二叉树是两种不同的树形结构，二叉树中的孩子结点有着严格左右之分的。
第 3 页，共 42 页
16．有n 个数顺序（依次）入栈，出栈序列有Cn 种
，
（ ） 【答案】
17．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】√
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
18．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ） 【答案】
【解析】队列只在下端（队尾）增加，在上端（队头）减少。
19．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 【答案】
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
20．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
三、算法设计题
21．已知深度为h 的二叉树, 以一维数组
应的算法。
【答案】算法如下：
int Leaves （int BT[]，int n）
//计算深度为h. 以一维数BT 作为其存储结构的二叉树的叶结点数，n 为数组长度{int num=0; //记叶结点数
for （i=0; i if （i<=（n-l ）/2） {if 2*i+l return num; }//结束Leaves 第 4 页，共 42 页 作为其存储结构，试编写一算法，求该二叉树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相
相关内容
相关标签