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

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

1、下面程序段的时间复杂度是（ ）。for(i=0;i<n;i++) for(j=1;j<m;j++) A[i][i]=0;

A、O(n)

B、O(m+n+1)

C、O(m+n)

D、O(m*n)

2、链表不具有的特点是（ ）。

A、可随机访问任一元素

B、插入、删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

3、若某栈的输入序列为1，2，3，...，n，输出序列的第一个元素为n，则第2个输出元素为（ ）。

A、1

B、n-1

C、n

D、都有可能

4、判定一个循环队列Q（最多元素为m个）为满队列的条件是（ ）。

A、Q.front==Q.rear

B、Q.front!=Q.rear

C、Q.front==(Q.rear+1)%m

D、Q.front!=(Q.rear+1)%m

5、设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）。

A、联结

B、求子串

C、字符定位

D、子串定位

6、将一个A[10][10]（下标从0开始计算）的矩阵按行优先顺序存放，每个元素占4个存储单元，并且A[0][5]的存储地址是1020，则A[7][2]的地址是（ ）。

A、1000

B、1020

C、1108

D、1288

7、一棵含有18个结点的二叉树的高度至少为（ ）。

A、3

B、4

C、5

D、6

8、已知某非空二叉树采用顺序存储结构，树中结点的数据信息按完全二叉树的层次序列依次存放在一个一维数组中，即则该二叉树的后序遍历序列为（ ）。

A、G，D，B，E，F，H，C，A

B、G，B，D，E，H，C，F，A

C、G，D，B，H，E，F，C，A

D、B，G，D，E，H，C，F，A

1、试题答案：D

试题解析：

该程序段是一个双层for循环，外层循环i从0递增到n-1，内层循环j从1递增到m-1，因此循环内的语句指向n*(m-1)次，程序段的时间复杂度为O(m*n)，故本题选D。

2、试题答案：A

试题解析：

对于A，链表不是随机访问的结构，顺序表才是；对于B，链表的插入和删除不需要移动元素，仅需要改变指针；对于C，链表是动态存储，每插入一个结点就开辟一个新的存储空间，不必预先估计空间，而顺序表需要预先估计存储空间；对于D，线性表的长度与结点个数成正比，而存储空间也和结点个数成正比，因此链表所需空间与线性表长度成正比。故本题选A。

3、试题答案：B

试题解析：

栈具有“先进后出”的特性，根据栈的输入序列和第一个输出序列推断出栈的基本操作为：push(1)、push(2)、…、push(n-1)、push(n)、pop(n)、push(n-1)、…、pop(2)、pop(1)，故本题选B。

4、试题答案：C

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满。队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，队满条件为（rear+1）%s==front；队空条件为rear==front。故本题选C。

5、试题答案：D

试题解析：

对于A，串的联结是指将两个串联结成一个新的串。对于B，串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。对于C，串的定位算法通常称为串的子串定位，而非字符定位。对于D，正文编辑的软件中，提供“查询”功能，即要求在正文串中，查询有没有和一个“给定的串”相同的子串，若存在，则屏幕上的光标移动到这个子串的起始位置。这个操作即为串的定位操作。故本题选D。

6、试题答案：D

试题解析：

LOC(A[0][5])=SA+(10-5)*4=1020，解得SA=1000。LOC(A[7][2])=SA+(7*10+2)*4=1288，故本题选D。

7、试题答案：C

试题解析：

当这棵二叉树为完全二叉树时，二叉树的高度最小。根据完全二叉树的性质可知，具有n个结点的完全二叉树的深度为⎿log₂n⏌+1，将n=18代入，解得树的高度至少是5，故本题选C。

8、试题答案：C

试题解析：

按照二叉树的顺序存储结构画出这棵二叉树如下：

得出上述树结构的后序遍历序列为：G、D、B、H、E、F、C、A。故本题选C。