2018年数据结构考研真题答案及解析

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

1、以下说法正确的是()。① 数据的逻辑结构是指数据的各数据项之间存在的逻辑关系② 顺序存储结构的优点是存储密度大③ 数据元素是表示数据的最小单位

A、 只有①正确

B、 只有②正确

C、 只有③正确

D、 ①②③都正确

3、在单链表的指针为p的结点之后插入指针为s的结点，正确的操作是()。

A、 p->next=s;p->next =s->next;

B、 s->next=p->next;p->next=s;

C、 p->next=s->next;p->next=s;

D、 p->next=s;s->next=p->next;

4、若一个栈以下标范围是1到n的数组elems存储元素，初始空栈的栈顶指针top为n+1，则下面x进栈的正确操作是()。

A、 top--; elems[top] =x;

B、 elems[top]=x; top--;

C、 top++; elems[top] =x;

D、 elems[top]=x; top++;

5、设有两个串s和t，求t在s中首次出现的位置的运算称作()。

A、 求子串

B、 判断是否相等

C、 模式匹配

D、 连接

6、程序设计语言对数组的操作主要有()。

A、 建立和删除

B、 索引和修改

C、 存储和提取

D、 查找和索引

7、一棵完全二叉树上有234个结点，其中叶子结点的个数是()。

A、 117

B、 233

C、 235

D、 115

8、在用邻接表表示一个有n个顶点和e条弧的有向无环图时，拓扑排序算法时间复杂度为()。

A、 O（n）

B、 O（n*n）

C、 O（n*e）

D、 O（n+e）

9、既希望较快的查找又便于线性表动态变化的查找方法是()。

A、 顺序查找

B、 折半查找

C、 哈希法查找

D、 索引顺序查找

10、下列排序算法中，其中()是稳定的。

A、 直接插入排序和快速排序

B、 折半插入排序和冒泡排序

C、 简单选择排序和二路归并排序

D、 锦标赛排序和希尔排序

1、试题答案：B

试题解析：

【考点】本题考查数据的结构与相关术语的基本概念。
【解析】对于①，数据的逻辑结构是指数据元素之间的逻辑关系而不是数据项之间的逻辑关系，①错误。对于②，顺序存储结构是用一组地址连续的存储单元依次存储该线性表，因此其存储密度大，②正确。对于③，数据元素是数据的基本单位，数据项是数据不可分割的最小单元，③错误。故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查单链表的插入操作
【解析】单链表的插入操作的过程如下图所示：

A和C不符合上述两个步骤，D选项如果若先执行步骤②，则p的原先的后继结点会丢失，D错误。按照上图所示，故本题选B。

4、试题答案：A

试题解析：

【考点】本题考查栈的基本操作
【解析】空栈的栈顶指针top为n+1说明栈顶指针随着元素入栈而减小，随着元素出栈而增加。当x入栈时，第一步先将栈顶指针减一，再将元素放入栈顶指针所指的位置，B选项先后顺序错误，C和D选项元素入栈栈顶指针应当减小，故本题选A。

5、试题答案：C

试题解析：

【考点】本题考查模式匹配的含义
【解析】对于A，子串是指串中任意连续的字符组成的子序列，如“ABC”的子串为“AB”，A错误。对于B，两个串相等是指两个串长度相等且两个串的对应位置也相等，B错误。对于C，正文编辑的软件中，提供“查询”功能，即要求在正文串中，查询有没有和一个“给定的串”相同的子串，若存在，则屏幕上的光标移动到这个子串的起始位置。这个操作即为串的定位操作，通常称为正文的模式匹配，C正确。对于D，串的连接指将一个串连接调另一个串之后，D错误。故本题选C。

6、试题答案：C

试题解析：

【考点】本题考查数组的操作
【解析】数组一旦被定义，其维数和每一维的上下界均不能改变，数组中元素之间的关系也不再改变。因此数组的基本操作除初始化和结构体销毁之外，只有通过给定的下标存和取操作。数组中的下标即数组的索引，不属于数组的操作。因此B、D错误。在程序设计语言中，数组只需定义，通常无需构造和删除，若数组中的元素不再需要可以通过覆盖等方法进行处理，因此A错误。故本题选C。

7、试题答案：A

试题解析：

【考点】本题考查完全二叉树的性质
【解析】具有n个结点的完全二叉树叶子结点的个数：当n为偶数时，叶子结点的个数为n/2个；当n为奇数时，叶子结点的个数为n/2+1个。证明为：在完全二叉树中设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2。由二叉树的性质可知，n2=n0-1。因此当n为偶数时， 完全二叉树中n1=1。带入上述式子：n=n0+n1+n2=n0+1+(n0-1)=2*n0。当n为奇数时，完全二叉树中n1=0。带入上述式子：n=n0+n1+n2=n0+0+(n0-1)=2*n0-1。题干中n=234，因此叶子结点个数=234/2=117，故本题选A。

8、试题答案：D

试题解析：

【考点】本题考查拓扑排序算法的时间复杂度
【解析】对于n个顶点e条弧的有向图而言，建立各个顶点的入度的时间是O(e)，建立零入度的顶点栈的时间复杂度为O(n)。顶点进一次栈、出一次栈，入度减1的操作总共执行e次，因此的时间复杂度是O(n+e)，故本题选D。

9、试题答案：C

试题解析：

【考点】本题考查查找方法的比较
【解析】顺序查找需遍历此表，时间复杂度为O(n)，动态变化时将值插入到线性表尾端，时间复杂度为O(1) 。折半查找通过二分的方法来查找，时间复杂度为O(logn)，折半查找是顺序有序表，为了保持有序性，其移动的时间复杂度为O(n)。哈希查找通过函数求关键字的地址，其查找的时间复杂度为O(1)，哈希表是动态查找表，通过再散列可以实现动态变化，时间复杂度为O(1)。索引顺序查找也称为分块查找，分块查找只要求索引表是有序的，对块内节点没有排序要求。块内查找的时间复杂度为O(n)。其动态变化的时间复杂度为O(1)。综上所述，哈希表既能较快查找，又能动态变化，故本题选C。

10、试题答案：B

试题解析：

【考点】本题考查排序算法的稳定性
【解析】排序算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。快速排序是不稳定性排序。假定存在这种情况：若基准值为首元素，存在两个相同的元素均比基准值小，左指针首先指向比基准小的元素在较靠后的位置，则通过交换后，靠后位置的元素放在了前面。因此A错误。简单选择排序是不稳定性排序。假定存在这种情况：第一趟排序如果一个元素比当前元素小，而该小的元素在一个和当前元素值相等的元素的后面，则通过交换后，当前元素放在与之相等的元素的后面。因此C错误。希尔排序是不稳定性排序，增量间数据的排序可能会改变相同数据的相对位置。锦标赛排序又称树形选择排序，是一种按照锦标赛思想进行的排序，是不稳定排序。因此D错误。故本题选B。