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

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

1、以下程序段的时间复杂性是（ ）。程序段如下: x=n; //n>1 的整数y=0; while (x≥(y+1)* (y+1)) y++;

A、O (n²)

B、O (n/2)

C、O (logn)

D、

2、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。

A、8

B、63.5

C、63

D、7

3、若一个栈以向量V[1..n]存贮，初始栈顶指针top设置为n+1，则元素x进栈的正确操作是（ ）。

A、top++; V[top]=x;

B、V[top]=x; top++;

C、top--; V[top]=x;

D、V[top]=x; top--;

4、数组A[0..4，-1..-3，5..7]中含有元素的个数（ ）。

A、55

B、45

C、36

D、16

5、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。

A、7

B、8

C、9

D、10

6、具有n个顶点的有向图最多有（ ）条边。

A、n

B、n(n-1)

C、n(n+1)

D、n²

7、用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。

A、栈

B、队列

C、树

D、图

8、设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。

A、8

B、3

C、5

D、9

9、堆是一种（ ）排序。

A、插入

B、选择

C、交换

D、归并

10、若一组记录的排序码为(46，79，56，38，40，84)， 则利用堆排序的方法建立的初始堆为（ ）。

A、79，46，56，38，40，84

B、84，79，56，38，40，46

C、84，79，56，46，40，38

D、84，56，79，40，46，38

1、试题答案：D

试题解析：

假设循环体执行Tn次，上述程序段的时间复杂度取决于while循环的执行次数。y=0，(y+1)²=1，循环执行1次；y=1，(y+1)²=2²，循环执行2次；y=2，(y+1)²=3²，循环执行3次；…. y=Tn-1，(y+1)²=Tn²，循环体执行Tn次，带入while循环的终止条件中，n>= Tn2，即，因此题干所示的程序段的时间复杂性为，故本题选D。

2、试题答案：B

试题解析：

向一个有127个元素的顺序表插入一个新元素时，一共有128个位置可以插入元素，平均要移动的元素=(127+126+125+…+0)/128=127/2=63.5。故本题选B。

【考点】本题考查顺序表查找操作。

3、试题答案：C

试题解析：

由题干可知，栈在向量V[1..n]，初始栈顶指针top=n+1，因此元素x入栈首先将栈顶指针移动到待存储位置，即top--；之后再将当前top指向的位置赋值为x，即V[top]=x。由于栈在向量V[1..n]中存储，因此A选项和B选项中涉及的top++会导致栈存储溢出。而D选项步骤颠倒，故本题选C。

【考点】本题考查栈的基本操作。

4、试题答案：B

试题解析：

题干所描述的数组A实际上是一个三维数组，x轴坐标为0、1、2、3、4，y轴坐标为-1、-2、-3，z轴坐标为5、6、7，因此数组的元素个数=5*3*3=45，故本题选B。

【考点】本题考查三维数组。

5、试题答案：C

试题解析：

本题要求在边数固定时顶点数最少，设顶点数为n，当该无向图是一个完全图时，顶点和边的关系为n*(n-1)/2=28，求得n=8。完全图是连通图，而题干要求非连通图，因此顶点个数+1，故本题选C。

【考点】本题考查图的连通性。

6、试题答案：B

试题解析：

n个顶点的有向图当为完全有向图时边数最多，每个顶点都能够和除自身之外的顶点相连，因此总的边数=n*(n-1)，故本题选B。

【考点】本题考查图的基本性质。

7、试题答案：B

试题解析：

图的广度优先搜索在遍历的过程中需要借助于访问的标志数组visited，并且为了实现“按照顶点被访问的先后次序”查询它们的邻接点，需要附设一个队列存储已被访问的点。广度优先搜索遍历无回溯操作，因此不需要采用栈结构来实现，故本题选B。

【考点】本题考查广度优先搜索的实现方法。

8、试题答案：D

试题解析：

求表中已有关键字的地址：H(15)=15%11=4；H(38)=38%11=5；H(61)=61%11=6；H(84)=84%11=7。画出此时的哈希表如下所示：

H(49)=49%11=5。地址发生冲突，采用二次探测再散列法解决冲突，H1=(5+1)%14=6，冲突；
H2=(5-1)%14=4，冲突；H3=(5+4)%14=9，不冲突，故本题选D。

【考点】本题考查哈希表的构造。

9、试题答案：B

试题解析：

排序算法的分类如下图所示，由图可知，堆排序是选择排序的一种，故本题选B。

【考点】本题考查排序算法的分类。

10、试题答案：B

试题解析：

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
① 堆中某个结点的值总是不大于或不小于其父结点的值；② 堆总是一棵完全二叉树。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。首先将上述排序码转换为完全二叉树，并画出构造初始堆的步骤如下：

初始堆的结构为上述最后一个图结构，对其进行层次遍历后得到初始堆序列，故本题选B。

【考点】本题考查初始堆的构造。