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

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

1、下列二叉排序树中，满足平衡二叉树定义的是（ ）。

A、

B、

C、

D、

2、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

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

A、n-i+1

B、n-1

C、i

D、哪个元素都有可能

4、串的模式匹配是指（）。

A、判断两个串是否相等

B、对两个串进行大小比较

C、找某字符在主串中第一次出现的位置

D、找某子串在主串中第一次出现的第一个字符位置

6、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为（）。

A、12

B、5.5

C、9

D、10

7、一棵二叉树结点的（）可唯一确定一棵二叉树。

A、先序序列和中序序列

B、先序序列和后序序列

C、中序序列

D、后序序列

8、若对图1的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（）。

A、EC

B、EA

C、DC

D、BA

9、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T中的叶子结点个数是（）。

A、41

B、82

C、113

D、122

10、5个字符有4种编码方案，不是前缀编码的是（）。

A、01，0000，0001，001，1

B、011，000，001，010，1

C、000，001，010，011，100

D、0，100，110，1110，1100

1、试题答案：B

试题解析：

平衡二叉树，也称为AVL树，是一种自平衡二叉搜索树。它的定义是：它是一棵空树或者具有以下性质的二叉搜索树：（1）左子树和右子树的高度差不超过1；（2）左子树和右子树都是平衡二叉树。故本题选B。

2、试题答案：A

试题解析：

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1)，因为只需要将新结点插入到p之后，然后更新指针即可。而在给定值为x的结点后插入一个新结点的时间复杂度为O(n)，因为需要先遍历整个链表找到值为x的结点，然后再进行插入操作。故本题选A。

3、试题答案：A

试题解析：

据栈的先进后出原则，最后一个进入的元素n会最后一个出栈，即为输出序列的第一个元素。而在它之前进栈的元素都需要在n之后出栈，因此第i个输出元素为n-i+1。故本题选A。

4、试题答案：D

试题解析：

串的模式匹配是指在一个主串中查找一个模式串第一次出现的位置。主串是指整个字符串，模式串是指要在主串中查找的子串。在串的模式匹配中，需要比较主串和模式串的字符，从而确定模式串在主串中的位置。故本题选D。

6、试题答案：C

试题解析：

先计算后缀表达式的值：
（1）a=6，将6入栈；
（2）b=4，将4入栈；
（3）c=2，将2入栈；
（4）-，弹出栈顶的2和4，计算4-2=2，将2入栈；
（5）/，弹出栈顶的2和6，计算6/2=3，将3入栈；
（6）d=3，将3入栈；
（7）e=2，将2入栈；
（8）*，弹出栈顶的2和3，计算3*2=6，将6入栈；
（9）+，弹出栈顶的6和3，计算3+6=8，得出最终结果9。
故本题选C。

7、试题答案：A

试题解析：

二叉树是一种特殊的树形数据结构，其中每个结点最多有两个子结点。由于这种结构的特殊性，一棵二叉树的结点的先序序列和中序序列可以唯一确定这棵二叉树。这是因为在先序序列中，第一个结点总是根结点，而在中序序列中，根结点之前的部分就是左子树，根结点之后的部分就是右子树。因此，通过先序序列和中序序列就可以唯一确定一棵二叉树。而其他选项则不能唯一确定一棵二叉树，因为它们都缺少了某些必要信息。故本题选A。

8、试题答案：D

试题解析：

在中序线索二叉树中，对于每一个节点，可以定义两个指针，分别指向其在中序遍历下的前驱和后继节点。当该节点的左子树为空时，可以将其左指针指向前驱节点；当该节点的右子树为空时，可以将其右指针指向后继节点。该二叉树的中序遍历序列是DEBXAC，因此结点x的左、右线索指向的结点分别是BA。故本题选D。

9、试题答案：B

试题解析：

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

10、试题答案：D

试题解析：

在一个前缀编码中，任何一个字符的编码都不是另一个字符编码的前缀。选项D中'110'的编码是'1100'的前缀，不是前缀编码。故本题选D。