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

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

1、数据结构是研究数据的（ ）以及它们之间的相互关系。

A、理想结构，物理结构

B、理想结构，抽象结构

C、物理结构，逻辑结构

D、抽象结构，逻辑结构

2、线性表的链接实现有利于（ ）运算。

A、插入

B、读表元素

C、查找

D、定位

3、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。

A、n-i

B、n-i+1

C、n-i-1

D、i

4、具有n个顶点的完全有向图的边数为（ ）。

A、n（n-1）/2

B、n（n-1）

C、n2

D、n2-1

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

A、被排序的数据量太大

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

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

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

6、线性表采用链式存储时，其地址（ ）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续与否均可以

7、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。

A、edcba

B、decba

C、dceab

D、abcde

8、采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。

A、n

B、n/2

C、（n+1）/2

D、（n-1）/2

1、试题答案：C

试题解析：

本题考查数据结构的基本概念。
数据结构是研究数据的物理关系、逻辑关系，以及它们之间的相互关系。物理结构指数据结构在计算机中的表示；逻辑结构指数据元素之间的关系。故本题选C。

2、试题答案：A

试题解析：

本题考查线性表的存储。
线性表有两种存储结构，一种为顺序存储，另一种是链式存储。链表插入和删除操作不移动元素，其时间复杂度为O(1)，与之相比顺序表插入和删除操作均需要移动元素，其时间复杂度为O(n)。链表是非随机存储结构，因此读表、查找、定位操作均需要遍历表，时间复杂度为O(n)。故本题选A。

3、试题答案：A

试题解析：

本题考查顺序表的基本操作。
顺序表的插入操作是指在第i-1个元素和第i个元素之间插入一个数据元素，使长度为n的线性表长度变为n+1，需要将第n到i的元素向后移动一位，共需移动元素的个数为n-i+1； 线性表的删除操作是指在删除第i个元素，需要将第i+1至第n个元素依次向前移动一位，共需移动元素的个数为n-i。故本题选A。

4、试题答案：B

试题解析：

本题考查完全有向图的性质。
完全有向图是指图中各边均有方向，且图中任意两点之间都有两条方向相反的边连接的图，因为有向图有n个顶点，根据完全有向图的性质每个边均需要和n-1条边相连接，因此边的总数= n*( n-1)。故本题选B。

5、试题答案：D

试题解析：

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

6、试题答案：D

试题解析：

本题考查线性表的存储。
线性表有两种存储结构，一种为顺序存储，另一种是链式存储。线性表采用链式存储的特点是用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的。线性表采用顺序存储是地址是连续的存储空间，故本题选D。

7、试题答案：C

试题解析：

本题考查栈的基本操作。
栈是先进后出的结构，根据该思想C选项中b是在a之后入栈的，相应的b应当比a先出栈。其余选项的出栈序列均符合栈“后进先出”的特性，故本题选C。

8、试题答案：C

试题解析：

本题考查顺序表的查找。
在等概率下查找顺序表，第i个元素的查找长度为i，则n个元素的总的查找长度为：1+2+3+……+n=n/2*（1+n），则平均查找长度=[ n/2*（1+n）]/n=（n+1）/2。故本题选C。