本文提供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