考研数据结构在线题库每日一练（六十七）

本文提供考研数据结构在线题库每日一练，以下为具体内容

1、串“ababaabab”的nextval为（）。

A、010104101

B、010102101

C、010100011

D、010101011

2、在内部排序中，排序时不稳定的有（ ）。

A、插入排序

B、冒泡排序

C、快速排序

D、归并排序

3、深度为k的完全二叉树至少有（ ）个结点，至多有（ ）个结点。

A、

B、

C、

D、

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

A、-A+B*C/DE

B、-A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

5、某哈弗曼树的结点总数为2n-1，若用二叉链表作为存储结构，则该哈夫曼树中一共有多少个空指针域（）。

A、2n-1

B、2n

C、2n+1

D、4n

1、试题答案：A

试题解析：

【考点】本题考查串和数组的应用。 

【解析】第一位的next的值是0，第二位的next的值为1，后面求解每一位的next的值时，首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容与前一位进行比较，直到找到某个位上的内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。根据上述思想求出该字符串所对应的next值。故本题选A。

2、试题答案：C

试题解析：

本题考查排序算法的稳定性。
排序算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。上述选项中，插入排序、冒泡排序、归并排序均为稳定性排序，而快速排序可能会改变相同元素的相对位置，是不稳定排序。故本题选C。

3、试题答案：A

试题解析：

4、试题答案：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。

5、试题答案：B

试题解析：

哈夫曼树的每个结点有两个指针域，含2n-1个结点的哈夫曼树共有4n-2个指针域。由于哈夫曼树有2n-1个结点，则有2n-2个边，即有2n-2个非空指针域，则空指针域=4n-2-(2n-2)=2n，故本题选B。