山西省2024年专升本选拔考试《数据结构》
主观题常见题型及答案解析完整版
一、 名词解释
1、队列：是一种先进先出的线性表,它只允许在表的一段进行插入,而另一端删除元素,允许插入的一端叫做队尾,允许删除的一端称为队首。
2、满二叉树：是一棵深度为 k的,且有(2^k)-1个结点的二叉树。 3、折半查找：取表的中间位置的记录关键字和所给关键字进行比较。 4、关键字：是数据元素中某个数据项的值,用它可以识别一个或一组数据元素。
5、循环链表：是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
6、分块查找：先确定待查记录所在的块(子表),然后在块中顺序查找。 7、动态查找表:在查找过程中同时插入查找不存在的数据元素,或者从查找表中删除已存在的某个数据元素。
8、双向链表：采用链式存储结构的线性表,每个结点除一个数据域外,还有两个指针域, 其一指向直接前驱,另一指向直接后继。
9、循环队列：循环队列是将队列的数据区看成头尾相接的循环结构。 10、二叉树:是一种树型的结构，它的特点是每个结点最多有两棵子树，且有左右之分，不可任意颠倒。
11、顺序存储：用一组地址连续的存储单元依次存放线性表的元素。 12、有向完全图：有 n(n-1)条边的有向图称为有向完全图(图中每个顶点和其余 n-1个 顶点都有弧相连)。
13、查找表:是由同一类型的数据元素或记录构成的集合。
14、排序：就是按关键字值的递增或递减的次序，把文件中的各记录一次排列起来，可使一个无序文件变成有序文件的一种操作。
15、顺序查找：对于给定的关键字 k，从线性表的第一个元素开始依次向后与记录的关键字域相比较。
16、连通图:在无向图中，任意两个顶点之间都有路径相通。
17、线性表:是最常用,最简单的一种数据结构，一个线性表是 n个数据元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。
18、线索二叉树：
采用某种方法遍历二叉树的结果是一个结点的线性序列。 修改空链域改为存放指向结点的前驱和后继结点的地址。 这样的指向该线性序列中的“前驱”和“后继”的指针，称作线索（thread）。 创建线索的过程称为线索化。
线索化的二叉树称为线索二叉树。
显然线索二叉树与采用的遍历方法相关，有先序线索二叉树、中序线索二叉树和后序线索二叉树。
线索二叉树的目的是提高该遍历过程的效率。
1
19、哈夫曼树：设二叉树具有n个带权值的叶结点，那么从根结点到各个叶
结点的路径长度与相应结点权值的乘积的和，叫做二叉树的带权路径长度。
WPL??wilii?1n
20、完全二叉树： 深度为k，有n个节点的二叉树，当且仅当其每个结点都占深度为k的满二叉树中编号从1至n的结点一一对应。
21、链表：n个结点链组成一个链表。
22、栈： 限定仅在表尾进行插入或删除操作的线性表。
23、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
25、排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个关键字的有序序列。
25、关键字：是数据元素中某个数据项的值，用它可以识别一个数据元素
二、 简答题
1、二分查找法的基本思想。
折半(二分)查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之,则在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败.
2、简述深度优先遍历的方法。
假设初始状态是图中所有顶点均未被访问过,则深度优先搜索可从某个顶点 V出发，首先访问此顶点(称此顶点为初始点)，然后依次从 V的任一个未被访问的邻接点出发进行深度优先搜索遍历,直到图中所有与 V有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为初始点，重复上述步骤，直到图中所有顶点都被访问过为止。
3、简述顺序表和链表各自的缺点。 顺序表：
1）结点中只存放数据元素本身的信息,无附加内容。 2）可直接存取数据元素。 3）存取操作速度较快。
4）插入.删除数据元素时,由于需要保持数据元素之间的逻辑关系,必须大量移动元素,因此实现起来较慢。
5）顺序存储是一种静态结构,存储密度大,空间利用率低,预分配空间大小难以确定。
链表：
1）.结点中除存放数据元素本身的信息外,还需存放附加的指针。 2）.不能直接存取数据元素,需顺链查找,存取速度较慢。 3）.插入.删除元素时不必移动其他元素,速度较快。
4）.链式存储是一种动态存储结构,空间利用率高,存储密度小,不存在预分配空间问题。
4、简述线性结构的特点。
2
线性结构的特点是：除第一个元素和最后一个元素外，每个数据元素都有唯一的前驱和唯一的后继，第一个元素没有前驱，最后一个元素没有后继，关系是一对一的。
5、树和二叉树之间的区别。
二叉树的一个结点至多有2个子树，树则不然。二叉树的一个结点的子树有左右之分，而树则没有此要求。
6、简述图的广度优先搜索遍历的方法。
1）.从图中某个顶点 V0出发，首先访问 V0，依次访问 V0的各个未被访问的邻接点。
2）.分别从这些邻接点(端结点)出发,依次访问各个未被访问的邻接点，访问时应保证：:如果 Vi和 Vk为当前结点，且 Vi在 Vk之前被访问，则 Vi的所有未被访问的邻接点应在 Vk的所有未被访问的邻接点之前访问。
3）.重复步骤 2，直到所有结点均没有未被访问的邻接点。
4）.若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。
7、什么叫遍历二叉树？写出对下图所示二叉树进行先序、中序、后序遍历结点序列。
二叉树遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。
先序遍历序列：中序遍历序列：后序遍历序列：
8、什么样的图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间复杂度各是多少？他们分别适合于哪类图？
Prim算法和Kruskal算法都是从连通图中找出最小生成树的经典算法。
3
从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的最小生成树。
所以说，Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到最小生成树。
Prim算法的实现过程
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。
Kruskal算法的实现过程
Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边），当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树。
如果一个图的各个边的权值各不相同,那么它的最小生成树是唯一的。 Prim算法：适合于求边稠密的最小生成树，时间复杂度为O(n2)。 Kruskal算法：更适合稀疏图求最小生成树，时间复杂度为O(elog2e) 9、具有三个结点的二叉树有哪些不同的形态? (5 分)
10、 树与二叉树之间有何区别? (6 分)
二叉树的一个结点至多有 2 个子树， 树则不然(3 分);
二叉树的一个结点的子树有左右之分，而树则没有此要求(3 分)。 11、（7分）用S表示人栈操作，X表示出栈操作，若元素人栈顺序为1234. 相应的S和 X如何操作串才能得到1342的出栈顺序，请写出各步操作结果。
应是SXSSXSXX 各步操作结果如下: S 1人栈
x 1出栈 输出序列:1 (1分) S 2入栈 (1分) S 3入栈 (1分)
x 3出栈 输出序列:13 (1分) S 4入栈 (1分)
X 4出栈 输出序列:134 (1分) x 2出栈 输出序列:1342 (1分) 12、（5分）什么是外部排序？
外部排序指的是大文件的排序(2 分)，即待排序的记录存储在外存储器上，待排序的文件无法一一次装人内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的(3 分)。 13、简述顺序查找法的基本思想。
4
从表的一端开始，用所给定的关键字依次与顺序表中各记录的关键字逐个比较(3分)，若找到相同的查找成功(1分；否则查找失败(1 分)。 14、简述数据结构的定义及其常见的基本结构。
数据结构是指相互之间存在着一种或多种关系的数据元素的集合。(1分)通常有以下四类基本结构:集合(1分)；线性结构(1分)；树形结构(1分)以及图状结构(1分)。 15、简述在选择排序方法时需要考虑的因素。 在选择排序方法时需要考虑的因素有如下4点: (1)待排序的记录数目的大小: （1 分）
(2)记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小:（1分） (3)关键字的结构及其分布情况: （1 分） (4)对排序稳定性的要求。（1 分）
16、写出图1中二叉树的先序、中序、后序遍历的结点序列。 —
/ +
e f * a
b —
c d
先序: -+a*b-cd/ef （2分） 中序: a+b*c-d-e/f（2分） 后序: abcd-*+ef/-（2分）
17、简述邻接矩阵表示法的特点。
(1) 无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。 （1分） (2)对于无向图，顶点V1的度是邻接矩阵中第i行(或第i列)的非零元素的个数。（1分）
(3)对于有向图，顶点V1的度是邻接矩阵中第i行和第i列的非零元素的个数之和。（1分）
(4)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连，但要确定图中的边数，则必须按行、按列对每个元素进行检查，所花费的时间代价很大。（1分）
18、简述空串与空格串的区别。(6分) 零个字符的串称为“空串”（3分）
由一个或多个空格组空格组成的串称为“空格串”（3分） 19、简述栈和线性表的差别。（6分）
线性表是具有相同特性的数据元素的一个有限序列。（3分）栈是限定仅在表尾进行插入或删除操作的线性表。（3分）
5
山西省2024年专升本选拔考试《数据结构》主观题常见题型及答案解析完整版
