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

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

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

A、被排序的数据量太大

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

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

D、被排序的数据中有实数

2、对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算是（）。

A、查找第i个元素

B、将n个元素从小到大排序

C、从顺序表中删除第i1个元素（1<=i<=n）

D、在第1个元素（1<=i<=n）后插入一个新元素

3、双向链表指针p的指针前插一个指针q的结点，操作是（）。

A、

B、

C、

D、

4、现有一个顺序栈，其空间大小为N，top作为栈顶指针，假定以地址高端作为栈底（即初始化时top=N）。则向栈中压入一个元素时，top的变化是（）。

A、top不变

B、top=n

C、top=top-1

D、top=top+1

5、设有二维数组A[5][6]，其每个元素占2个字节，首元素A[1][1]的存储地址为100，则按列优先存储时，则A[2][3]的地址是（）。

A、122

B、121

C、123

D、120

6、已知串s="ABCDEFG"，则计算串长StrLength(s)的值是（）。

A、5

B、6

C、7

D、8

7、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有（）个叶子结点。

A、10

B、12

C、11

D、13

8、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。

A、-A+B*C/DE

B、-A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

9、在下列叙述中，正确的是（）。①只有一个根结点的二叉树，它的度为0；②二叉树的度为2；③二叉树的左右子树可以任意交换；④深度为k的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A、①②③

B、②③④

C、②④

D、①④

10、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2

B、1

C、2

D、4

1、试题答案：C

试题解析：

在被排序的数据已基本有序的情况下，快速排序可能会出现极端的不平衡分割，使得排序时间复杂度变为O(n2)，而快速排序的优势正是在平均情况下的排序效率最高。故本题选C。

2、试题答案：A

试题解析：

在顺序存储结构中，查找第i个元素的时间复杂度为O(1)，因为可以通过计算元素在存储空间中的位置直接访问到。而将n个元素从小到大排序、从顺序表中删除第i个元素、在第1个元素后插入一个新元素的时间复杂度都是O(n)，因为需要遍历整个顺序表进行操作。故本题选A。

3、试题答案：C

试题解析：

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

4、试题答案：C

试题解析：

在顺序栈中，栈顶指针top指向栈顶元素在栈中的位置，即指向栈顶元素的下一个位置，因此当要向栈中压入一个元素时，需要将栈顶指针top向下移动一个位置。故本题选C。

5、试题答案：A

试题解析：

按列优先存储时，先存储第一列，再存储第二列，以此类推。因此，A[2][3]的地址为=100+2×(3-1)×5+2×(2-1)=122。故本题选A。

6、试题答案：C

试题解析：

计算串长时需要遍历整个串，统计其中的字符数，因此计算串长StrLength(s)的值应该是7。故本题选C。

7、试题答案：B

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2+n3（结点数量）=n1+2n2+3n3+1（边数量+1）。则树T中的叶子结点n0的个数是n2+2n3+1=3+2×4+1=12。故本题选B。

8、试题答案：D

试题解析：

前缀式也称为波兰式，是运算符位于操作数之前的表达式形式。后缀表达式转前缀表达式的方法类似于后缀表达式转中缀表达式，可以使用栈来实现。具体步骤如下：
（1）从左到右扫描后缀表达式，对于每个元素进行如下操作：
①如果是操作数，直接入栈。
②如果是操作符，则从栈中弹出两个操作数，并将该操作符和两个操作数按照“操作符+操作数2+操作数1”的顺序组成一个新的操作数，将该操作数入栈。
（2）扫描结束后，栈中仅剩一个元素，即为前缀表达式。
对于后缀表达式“ABC*+DE/-”，可以按照如下步骤转换为前缀表达式：
（3）从左到右扫描后缀表达式，遇到'A'、'B'、'C'、'*'、'+'、'D'、'E'、'/'依次进行如下操作：
①'A'、'B'、'C'：入栈。
②'*'：弹出'C'和'B'，生成新的操作数“*BC”，入栈。
③'+'：弹出“*BC”和'A'，生成新的操作数“+A*BC”，入栈。
④'D'、'E'：入栈。
⑤'/'：弹出'E'和'D'，生成新的操作数“/DE”，入栈。
扫描结束后，栈中仅剩一个元素“-+A*BC/DE”，即为前缀表达式。
因此，该后缀表达式对应的前缀表达式为：-+A*BC/DE。故本题选D。

9、试题答案：D

试题解析：

10、试题答案：B

试题解析：

在一个有向图中，每个顶点的入度是指有多少个有向边以该顶点为终点，每个顶点的出度是指有多少个有向边以该顶点为起点。设该有向图共有n个顶点，m条边，则所有顶点的入度之和为S1，所有顶点的出度之和为S2。因为每条边都恰好有一个起点和一个终点，所以每条边的贡献都被计算了一次，即S1=S2=m。所以所有顶点的入度之和等于所有顶点的出度之和，即S1=S2=m，所以它们的比值为1，即入度之和等于出度之和的1倍。故本题选B。