本文提供2015年408計算機學科專業基礎考研真題答案及解析，以下為具體內容

1、已知程序如下：程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息依次對應的是（  ）。

A、 main（）→ S（1） →S（0）

B、 S（0）→S（1）→ main（）

C、 main（）→S（0）→S（1）

D、 S（1）→S（0）→main（）

2、先序序列為a， b， c， d的不同二叉樹的個數是（  ）。

A、 13

B、 14

C、 15

D、 16

3、下列選項給出的是從根分別到達兩個葉結點路徑上的權值序列，能屬于同一棵哈夫曼樹的是（  ）。

A、 24，10，5和24，10，7

B、 24，10，5和24，12，7

C、 24，10，10和24，14，11

D、 24，10，5和24，14，6

4、現有一棵無重復關鍵字的平衡二叉樹（AVL樹），對其進行中序遍歷可得到一個降序序列。下列關于該平衡二叉樹的敘述中，正確的是（  ）。

A、 根結點的度一定為2

B、 樹中最小元素一定是葉結點

C、 最后插入的元素一定是葉結點

D、 樹中最大元素一定是無左子樹

5、設有向圖G=（V， E），頂點集V = {v0，v1，v2，v3}， 邊集E= {<v0，v1>， <v0，v2>， <v0，v3>，<v1，v3>}。若從頂點v0開始對圖進行深度優先遍歷則可能得到的不同遍歷序列個數是（  ）。

A、 2

B、 3

C、 4

D、 5

6、求下面帶權圖的最小（代價）生成樹時，可能是克魯斯卡（Kruskal）算法第2次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是（  ）。

A、 （V1，V3）

B、 （V1，V4）

C、 （V2，V3）

D、 （V3，V4）

7、下列選項中，不能構成折半查找中關鍵字比較序列的是（  ）。

A、 500， 200， 450， 180

B、 500， 450， 200， 180

C、 180， 500， 200， 450

D、 180， 200， 500， 450

8、已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”。采用KMP算法進行匹配，第一次出現“失配”（s[i]≠t[j]）時，i=j=5，下次開始匹配時，i和j的值分別是（  ）。

A、 i=1，j=0

B、 i=5，j= 0

C、 i=5，j=2

D、 i=6，j=2