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

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

1、快速排序在（ ）情况下最不利于发挥其长处。

A、被排序的数据量太大

B、被排序数据中含有多个相同的关键字.

C、被排序的数据完全无序

D、被排序的数据已基本有序

2、图中有关路径的定义是（ ）。

A、由不同顶点所形成的序列

B、由不同边所形成的序列

C、由顶点和相邻顶点序偶构成的边所形成的序列

D、上述定义都不对

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

A、按层遍历

B、先序遍历

C、中序遍历

D、后序遍历

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

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

5、在双向链表指针p的指针前插一个指针q的结点，操作是（ ）。注：双向链表的结点结构为(prior,data,next)。

A、

B、

C、

D、

6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

A、d，c，e，b，f，a

B、c，b，d，a，e，f

C、a，f，e，d，c，b

D、b，c，a，e，f，d

7、若串S='software'，其子串的个数是（ ）。

A、8

B、9

C、36

D、37

8、已知广义表A=((a,b,c),(d,e,f))，从A中取出原子e的运算是（ ）。

A、head(tail(head(tail(A))))

B、head(tail(tail(head(A))))

C、head(tail(A))

D、tail(head(A))

1、试题答案：D

试题解析：

快速排序的基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再按此方法对这两部分记录进行排序，以达到整个序列有序的目的。在被排序数据已经基本有序的情况下，每次划分时都只能将序列分为一个较小的子序列和一个较大的子序列，导致递归树的深度增加，时间复杂度也会增加，使得快速排序的效率大大降低。因此，对于已经基本有序的数据，选择其他排序算法可能更加适合。故本题选D。

2、试题答案：C

试题解析：

选项A中，仅仅指出路径由不同顶点所构成的序列，但并没有明确说明这些顶点是如何连接起来的；选项B中，仅仅指出路径由不同边所构成的序列，但并没有明确说明这些边是连接哪些顶点的。因此，这两个选项都没有给出完整的路径定义。图论中，路径指的是图中从一个顶点到另一个顶点的一系列边构成的序列。在有向图中，路径由一系列有向边连接的顶点构成；在无向图中，路径由一系列无向边连接的顶点构成。路径的长度是指路径上所有边的权值之和。由于路径是由顶点和相邻顶点的边构成的，因此选项C描述了路径的定义是正确的。故本题选C。

3、试题答案：A

试题解析：

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

4、试题答案：A

试题解析：

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

5、试题答案：B

试题解析：

选项A中，插入操作的顺序是先将p的前驱结点指向q，再将q的后继结点指向p，接着将p的前驱结点的后继结点指向q，最后将q的前驱结点指向p。但是这个顺序是错误的，因为在将p的前驱结点的后继结点指向q之前，p的前驱结点就已经被修改为q了，导致指针的丢失。选项C和选项A的错误一致。选项D中，插入操作的顺序是先将q的前驱结点指向p的前驱结点，再将q的后继结点指向q，因此错误。故本题选B。

6、试题答案：C

试题解析：

选项C中栈的执行过程是：a入栈、a出栈、b入栈、c入栈、d入栈、e入栈、f入栈、f出栈、e出栈、d出栈、c出栈、b出栈。由此可知，出现了连续三次以上的退栈操作。故本题选C。

7、试题答案：C

试题解析：

串S='software'的子串包括单个字符的子串、两个字符的子串、三个字符的子串、四个字符的子串、五个字符的子串、六个字符的子串、七个字符的子串和八个字符的子串。其中单个字符的子串有8个，两个字符的子串有7个，以此类推，八个字符的子串只有一个，因此总共的子串数为：8+7+6+5+4+3+2+1=36，故串S='software'的子串的个数是36。故本题选C。

8、试题答案：A

试题解析：

可以运用head和tail函数取A中原子e的步骤如下：
（1）使用tail函数取出A中第二个元素构成的列表：tail(A)=((d,e,f))；
（2）使用head函数取出tail(A)的第一个元素：head(tail(A))=(d,e,f)；
（3）再使用tail函数取出head(tail(A))的尾巴部分：tail(head(tail(A)))=(e,f)
（4）最后使用head函数取出尾巴部分的第一个元素，即原子e：head(tail(head(tail(A))))=e
因此，A中原子e的运算为head(tail(head(tail(A))))= e。故本题选A。