2017年合肥工业大学计算机与信息学院848软件工程学科专业基础综合之数据结构考研强化模拟题
● 摘要
一、填空题
1． 模式串
的next 函数值序列为_____。
【答案】01122312
2． 实现字符串拷贝的函数strcpy 为：
【答案】
3． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
4． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
5． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
6．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
7． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
8． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
9． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、判断题
11．两个长度不相同的串有可能相等。（ ）
【答案】
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
12．设栈采用顺序存储结构。若已有杂性为
（ ）
【答案】
个元素入栈，则将第i 个元素入栈时，入栈算法的时间复
【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
13．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
14．2，... ，n , 输出序列是 栈的输入序列是1，若则有：（ ）
【答案】
【解析】出栈序列不一定满足比如1进栈，然后出栈，
15．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）
【答案】
【解析】队列只在下端（队尾）增加，在上端（队头）减少。
16．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环（回路）。
【答案】√
【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。
17．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
【答案】×
【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。
18．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
19．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
20．深度为k 的二叉树中结点总数小于等于（ ）
【答案】√
【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为
三、算法设计题
21．已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture , 否则返回false 。
【答案】算法如下：