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

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

1、在一个双链表中，在p结点之后插入结点q的操作是（ ）。

A、q→prior=p;p→next=q;p→next→prior=q;q→next=p→next;

B、q→next=p→next;p→next→prior=q;p→next=q;q→prior=p;

C、p→next=q;q→prior=p;q→next=p→next;p→next→prior=q;

D、q→prior=p:p→next=q;q→next=p→next;p→next→prior=q;

2、设某链表中最常用操作是在链表尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。

A、单向链表

B、单向循环链表

C、双向链表

D、双向循环链表

3、含有4个元素值均不相同的结点的二叉排序树有（ ）种。

A、4

B、6

C、10

D、14

4、查找哈希Hash表，不会发生冲突的哈希函数（ ）。

A、除留余数法

B、伪随机探测再散列法

C、直接地址法

D、线性探测再散列法

5、散列函数有一个共同性质，即函数值应按（ ）取其值域的每一个值。

A、最大概率

B、最小概率

C、同等概率

D、平均概率

6、在下列排序方法中，（  ）方法可能出现这种情况: 在最后一趟开始之前， 所有的元素都不在其最终应在的正确位置上。

A、快速排序

B、冒泡排序

C、堆排序

D、插入排序

7、直接插入排序在最好情况下的时间复杂度为（ ）。

A、

B、

C、

D、

8、长度为n的顺序存储线性表，在任何位置上插入或删除一个元素a的概率相等，则删除一个元素时，平均需要移动（ ）个元素。

A、（n+1）/2

B、n/2

C、（n-1）/2

D、（n-2）/2

9、设依次进入一个栈的元素序列为d、a、c、b，不可能得到出栈的元素序列是（ ）。

A、d、c、b、a

B、a、c、d、b

C、a、b、c、d

D、c、b、d、a

10、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是（ ）。

A、A*B+C/D-E+F

B、AB*C+D/E-F+

C、ABC+*DE-+/

D、ABCDEF*+/-+

1、试题答案：B

试题解析：

【考点】本题考查双链表的删除。
【解析】在一个双链表中，在p结点之后插入结点q的操作示意图如下所示，其中① q->next=p->next; ② p->next->prior=q; ③ p->next=q; ④ q->prior=p;。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查双向循环链表。
【解析】在单向链表、单向循环链表以及双向链表中，均需要从头到尾遍历整个链表才能找到尾元素的位置，花费时间长。而在双向循环链表中，通过头结点指针可以直接在O(1)的时间复杂度内找到尾元素的位置。在链表尾部插入或删除元素时，双向循环链表这一存储方式相较于其他三种而言，最能节省运算时间。故本题选D。

3、试题答案：D

试题解析：

【考点】本题考查二叉排序树。
【解析】
假设4个元素值均不相同的结点值为1、2、3、4，分析其构成二叉排序树的种类过程如下所示：
① 若结点1为根结点，构成的二叉排序树有5种，如下所示：

② 若结点2为根结点，构成的二叉排序树有2种，如下所示：

③ 若结点3为根结点，构成的二叉排序树有2种，如下所示：

④ 若结点4为根结点，构成的二叉排序树有5种，如下所示：

综上所述，含有4个元素值均不相同的结点的二叉排序树有5+2+2+5=14种。故本题选D。

4、试题答案：C

试题解析：

【考点】本题考查哈希函数。
【解析】直接地址法散列函数的优点是简单、均匀，也不会产生冲突，但是这需要事先知道关键字的分布情况，它适合查找表较小且关键字分布连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查散列函数的性质。
【解析】构造哈希函数的原则是：① 函数本身便于计算；② 计算出来的地址分布均匀，即对任一关键字，哈希值对应不同地址的概率相等，目的是尽可能减少冲突。故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查几种常见的排序算法。
【解析】
（1）快速排序：每一趟排序都可以确定枢轴元素的最终位置。
（2）冒泡排序：每一趟排序都可以确定一个最大或最小元素的最终位置。
（3）堆排序：每一趟都选取堆顶元素（最大或最小元素）加入有序序列，即可确定最大或最小元素的最终位置。
（4）插入排序：最后一趟插入的可能是最小元素，导致所有元素都不在其最终位置上。
综上所述，本题选D。

7、试题答案：B

试题解析：

【考点】本题考查直接插入排序在最好情况下的时间复杂度。
【解析】直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小则交换，直到全部元素都比较过。若整个待排序元素已经有序，则只需要比较n-1，且没移动元素，所以时间复杂度为O(n)。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查顺序表删除元素时平均需要移动的元素个数。
【解析】
（1）在线性表上插入一个元素时，插入位置有n+1个，分别移动的元素次数为n，n-1，…，1，0，所以插入时的平均移动元素的次数为（n+n-1+…+1+0）/（n+1）=n/2。
（2）在线性表上删除一个元素时，从第一个位置删除，分别移动的元素次数为n-1，n-2…，1，0，所以插入时的平均移动元素的次数为（n-1+n-2+…+1+0）/n=（n-1）/2。
综上所述，在顺序表中删除一个元素时，平均需要移动（n-1）/2个元素。故本题选C。

9、试题答案：D

试题解析：

【考点】本题考查正确的出栈顺序。
【解析】栈的特点是“先进后出”。入栈序列中，d先于a入栈，所以出栈时d应该在a的后面出栈，而选项D的序列中，d先于a出栈，不符合出栈要求，所以该序列不可能是出栈序列。故本题选D。

10、试题答案：C

试题解析：

【考点】本题考查中缀表达式转后缀表达式。
【解析】
（1）首先从左至右标出中缀表达式中各个元素符号运算的先后顺序，如下所示：

（2）依次按照运算符的先后顺序将运算符移动到两个操作数的后面，即可得到中缀表达式A*（B+C）/（D-E+F）对应的后缀表达式为BC+*DE-+/。故本题选C。