2017年北京市培养单位光电研究院864程序设计之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
2． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
3． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
5． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
6． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
7． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
8． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、判断题
11．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
12．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
13．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
14．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
15．数据结构的抽象操作的定义与具体实现有关。（ ）
【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表
示和实现无关。
16．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
17．2，... ，n , 输出序列是栈的输入序列是1，若则有：
【答案】
【解析】出栈序列不一定满足比如1进栈，然后出栈，
18．哈希表的平均查找长度与处理冲突的方法无关。（ ）
【答案】×
【解析】常见的处理冲突的方法：开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。
19．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）
【答案】×
【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。
20．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
（ ）
三、算法设计题
21．若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下：
22．已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中, 试编写算法建立该二叉树的二叉链表。
【答案】算法如下：
//根据二叉树前序序列pre 和中序序列in 建立二叉树。11. hi和l2、h2是两个序列首、尾元素下标
相关内容
相关标签