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

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

2、在双向链表存储结构中，删除p所指的结点时须修改指针( )。

A、p->next->prior=p->prior; p->prior->next=p->next;

B、p->next=p->next->next; p->next->prior=p;

C、p->prior->next=p; p->prior=p->prior->prior;

D、p->prior=p->next->next; p->next=p->prior->prior;

3、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是()。

A、2

B、3

C、4

D、6

4、则计算fact(n)需要调用该函数的次数为( )。 

A、n+1

B、n-1

C、n

D、n+2

5、对图2所示的带权有向图，若采用迪杰斯特拉(Dijkstra)算法求从原点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是( )。

A、f，d，e

B、e，d，f

C、d，e，f

D、f，e，d

6、串“ababaaababaa”的next数组为( )。

A、012345678999

B、012121111212

C、0123012322345

D、011234223456

7、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()遍历实现编号。

A、先序

B、中序

C、后序

D、从根开始按层次遍历

8、下面关于B-和B+树的叙述中，不正确的是()。 

A、B-树和B+树都是平衡的多叉树

B、B-树和B+树都可用于文件的索引结构

C、B-树和B+树都能有效地支持顺序检索

D、B-树和B+树都能有效地支持随机检索

9、对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能()。

A、希尔排序

B、起泡排序

C、归并排序

D、基数排序

10、图3是一个有向无环图，其拓扑排序结果为( )。

A、v0、v1、v2、v4、v5、v3、v6

B、v1、v0、v3、v4、v5、v2、v6

C、v1、v0、v3、v4、v5、v6、v2

D、v1、v0、v3、v4、v6、v2、v5

2、试题答案：B

试题解析：

【考点】本题考查双向链表的删除。 

【解析】双向链表的删除操作涉及两个方向的指针，第一步是p的next指针指向其后继的后继。此时，原本的p->next->next更新为p->next。第二步p->next的前驱指针指向p，由此就删除了原本的p->next结点。故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查栈和队列的特性。 【解析】栈具有先进后出的特性，因此元素的入栈顺序的逆序为元素的出栈顺序。队列具有先进先出的特性，因此元素的出队列顺序即为元素的入队列顺序。因此，出队列的顺序即为出栈的顺序。根据该规则分析，栈中出现e1、e3、e4共存的情况，e1、e5、e6共存的情况。因此栈S的容量至少应该为3。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查递归函数的调用。 

【解析】将fact(n)带入函数中，执行return n*fact(n-1)，函数调用一次；带入fact(n-1)，执行return (n-1)*fact(n-2)，函数调用两次；......；将fact(1) 带入函数中， 执行return 1*fact(0)，函数调用n-1次；将fact(0) 带入函数中， 执行return 1，函数结束。计入fact(n)为一次调用，则函数一共调用n次。故本题选C。

5、试题答案：A

试题解析：

【考点】本题考查Dijkstra算法的运用。 

【解析】根据Dijkstra算法，每次得到的目标顶点为未加入的顶点中到a的距离最小的点。根据算法的基本思想，得出该算法的每一个步骤如下：
初始时，a到其余各点的距离如下：

加入顶点b，更新各点的距离如下：

加入顶点c，更新各点如下：

加入顶点f，更新各点如下：

加入顶点d，更新各点的距离如下：

加入顶点e，更新各点的距离如下：

由上图可知，各定点加入的顺序为a b c f d e。故本题选A。

6、试题答案：D

试题解析：

【考点】本题考查数组和字符串的基本运用。 

【解析】第一位的next的值是0，第二位的next的值为1，后面求解每一位的next的值时，首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容与前一位进行比较，直到找到某个位上的内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。根据上述思想求出该字符串所对应的next值。故本题选D。

7、试题答案：C

试题解析：

【考点】本题考查二叉树的遍历。 

【解析】根据题意，二叉树中的结点大小为左孩子<右孩子<根结点。且二叉树的结点从1开始编号，则可以对二叉树进行后序遍历，遍历之后的结点序列再从1开始编号。故本题选C。

8、试题答案：C

试题解析：

【考点】本题考查B-树和B+树的基本概念。

【解析】B树仅支持随机查找，B+树支持随机查找和顺序查找。故本题选C。

9、试题答案：B

试题解析：

【考点】本题考查排序算法的基本思想。 

【解析】冒泡排序的基本思想为对无序序列区中的记录进行相邻记录关键字间的比较和记录位置的交换实现关键字较小的记录向一头漂浮，而关键字大的记录向另一头漂浮。一般情况下，整个冒泡排序只需要进行k(1<=k<n)趟冒泡操作。因此，根据该思想，上述排序的第一、二、三趟结果符合题目序列。故本题选B。

10、试题答案：D

试题解析：

【考点】本题考查拓扑排序的思想。 

【解析】在拓扑排序中，只有入度为0的点才可以添加到拓扑序列中。A选项中，V5的入度来自结点V2 V3 V4，而V3不在V5之前的拓扑序列中，因此A选项错误。同理，B选项中V5之前的拓扑序列中应该有V2。C选项与B选项问题一致。故本题选D。