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