2018年数据结构考研真题答案及解析（六）

本文提供2018年数据结构考研真题答案及解析，以下为具体内容

1、关键路径是事件结点网络中（ ）。

A、最短的回路

B、从源点到汇点的最短路径

C、最长的回路

D、从源点到汇点的最长路径

2、链表不具有的特点是（ ）。

A、可随机访问任一元素

B、插入删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

3、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、先序遍历

C、中序遍历

D、后序遍历

4、树最适合用来表示的结构是（ ）。

A、元素间的有序结构

B、元素间具有分支及层次关系的结构

C、元素间的无序结构

D、元素间无联系的结构

5、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（ ）。

A、肯定发生变化

B、肯定不发生变化

C、有时发生变化

D、无法确定

6、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，在下列（ ）情形不可能出现。

A、

B、

C、

D、

7、具有12个关键字的有序表，折半查找的平均查找长度（ ）。

A、1

B、17/5

C、37/12

D、1/12

8、关于哈希查找，以下说法不正确的是（ ）。

A、哈希查找中，记录的存储地址是计算出来的，因而不需要比较

B、装填因子越大，越容易产生冲突

C、哈希查找有两个关键问题：哈希函数和处理冲突的方法

D、链地址法和线性探测再散列都是解决冲突的方法

9、下列几种排序方法中，要求内存量最大的是（ ）。

A、插入排序

B、选择排序

C、快速排序

D、归并排序

10、在下列排序算法中，（ ）算法的效率与待排数据的原始状态无关。

A、起泡排序

B、插入排序

C、基数排序

D、快速排序

1、试题答案：D

试题解析：

本题考查关键路径的定义。
关键路径是指从开始点到完成点的最长路径，该路径不能是回路。故本题选D。

2、试题答案：A

试题解析：

链表不具有的特点是可随机访问任一个元素。链表是一种线性结构，元素的访问只能从头结点或尾结点开始，沿着指针一个一个遍历，无法像数组一样通过下标随机访问任意一个元素。故本题选A。

3、试题答案：A

试题解析：

广度优先遍历算法是一种遍历图的算法，用于按照广度优先的顺序遍历图中所有顶点。该算法通过邻接表存储的图，从指定的起始顶点开始，首先访问与其相邻的所有顶点，然后按照它们的访问顺序依次访问它们的相邻顶点，直到遍历完整个图。类比于二叉树，广度优先遍历算法类似于按层遍历。在按层遍历二叉树时，也是从根节点开始，依次访问每一层的节点，直到遍历完整个树。故本题选A。

4、试题答案：B

试题解析：

树最适合用来表示的结构是元素间具有分支及层次关系的结构。树是一种非线性数据结构，其中元素之间存在分支及层次关系。树的根节点在最上面，每个节点可以有多个子节点，每个节点只有一个父节点，从根节点到每个节点都存在一条唯一的路径。这种结构很适合用来表示具有分支关系、层次关系的数据。故本题选B。

5、试题答案：B

试题解析：

由于二叉树中叶子节点没有子节点，所以它们在先序、中序、后序遍历中的位置是不会发生变化的。在先序遍历中，叶子节点会被最先遍历到，因此它们在先序序列中的相对位置是不变的；在中序遍历中，叶子节点位于左子树和右子树之间，因此它们在中序序列中的相对位置也是不变的；在后序遍历中，叶子节点会被最后遍历到，因此它们在后序序列中的相对位置同样是不变的。故本题选B。

6、试题答案：B

试题解析：

如果G中有一条从Vj到Vi的路径，那么拓扑排序不可能将Vi排在Vj之前。拓扑排序的目的是使所有依赖关系都得到满足。故本题选B。

7、试题答案：C

试题解析：

折半查找的平均查找长度为log2(n+1)-1，其中n为表长，所以具有12个关键字的有序表，平均查找长度为log2(12+1)-1=3.08，与37/12最接近。故本题选C。

8、试题答案：A

试题解析：

虽然哈希查找是通过计算关键字的哈希值来确定记录的存储地址，但是在处理冲突时，仍然需要进行比较，以确定正确的存储位置。在处理冲突时，通常需要比较哈希值和关键字，或者比较不同哈希值对应的存储地址，以确定正确的存储位置。故本题选A。

9、试题答案：D

试题解析：

归并排序是一种基于分治思想的排序算法，其主要思路是将待排序序列分成若干个子序列，对每个子序列进行排序，然后再将已排序的子序列合并成一个有序序列。在合并的过程中，需要使用额外的存储空间来存储已排序的子序列，因此归并排序的空间复杂度较高。故本题选D。

10、试题答案：C

试题解析：

基数排序算法的效率与待排数据的原始状态无关。基数排序算法是一种非比较型排序算法，它是根据元素的键值进行排序的，而且对于每一个键值，都需要进行一次桶排序，因此其时间复杂度为O(d*(n+k))，其中d表示最大元素的位数，k表示每一位的基数，n表示待排序元素的个数。与比较型排序算法相比，基数排序不需要进行元素之间的比较操作，因此其效率与待排数据的原始状态无关。故本题选C。