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

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

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

A、最短的回路

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

C、最长的回路

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

2、稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A、二维数组和三维数组

B、三元组和散列

C、三元组和十字链表

D、散列和十字链表

3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

4、二叉树在线索化后，仍不能有效求解的问题是（ ）。

A、先序线索化二叉树中求先序后继

B、中序线索化二叉树中求中序后继

C、后序线索化二叉树中求后序后继

D、中序线索化二叉树中求中序前驱

5、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，该树共有（ ）个结点。

A、

B、

C、

D、

6、下列（ ）序列不是堆。

A、100，85，40，77，80，60，66，98，82，10，20

B、100，98，85，82，80，77，66，60，40，20，10

C、100，85，98，77，80，60，82，40，20，10，66

D、10，20，40，60，66，77，80，82，85，98，100

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

A、起泡排序

B、插入排序

C、基数排序

D、快速排序

8、执行下面程序段的时间复杂度是（ ）。for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j;

A、O(n)

B、O(m²)

C、O(m*n)

D、O(m+n)

1、试题答案：D

试题解析：

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

2、试题答案：C

试题解析：

稀疏矩阵是指大部分元素为0的矩阵，因此常用压缩存储方法来节省存储空间。常见的稀疏矩阵压缩存储方法有两种：
（1）三元组：将矩阵中的非零元素按行、列、值三个属性分别存储，可以用一个三元组(i,j,a[i][j])来表示一个非零元素。此方法适用于存储元素数量较少的稀疏矩阵。
（2）十字链表：将矩阵分成行链表和列链表两部分，每个非零元素既是某个行链表中的一个结点，也是某个列链表中的一个结点，两部分链表通过结点共享表示矩阵。此方法适用于存储元素数量较多的稀疏矩阵。故本题选C。

3、试题答案：A

试题解析：

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1)，因为只需要将新结点插入到p之后，然后更新指针即可。而在给定值为x的结点后插入一个新结点的时间复杂度为O(n)，因为需要先遍历整个链表找到值为x的结点，然后再进行插入操作。故本题选A。

4、试题答案：C

试题解析：

在二叉树的后序线索化过程中，如果要求某个结点的后继，则需要遍历整棵树，因为后序遍历的顺序是左子树、右子树、根节点，所以在后序线索化后的二叉树中，一个结点的后继可能在其右子树中，也可能在其祖先结点的右子树中，因此需要遍历整棵树才能找到后继。而对于其他线索化方式，都可以通过对结点的左、右指针进行判断来快速找到后继或前驱。对于先序线索化二叉树，可以通过判断结点的左指针是否为线索指针来找到先序后继；对于中序线索化二叉树，可以通过判断结点的右指针是否为线索指针来找到中序后继或前驱。故本题选C。

5、试题答案：A

试题解析：

6、试题答案：A

试题解析：

根据堆的定义，一个堆需要满足父节点的值大于等于子节点的值（大根堆）或者小于等于子节点的值（小根堆）。因此，我们可以检查每一个序列是否满足这个条件。在序列A中，节点为40的左右子节点分别为60和66，两者均大于40，不符合最大堆的定义，因此序列A不是堆。故本题选A。

7、试题答案：C

试题解析：

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

8、试题答案：C

试题解析：

双重循环的时间复杂度是循环次数的乘积，即m*n。因此，程序段的时间复杂度是O(m*n)。故本题选C。