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

1、下列函數的時間復雜度是（ ）。

A、

B、

C、

D、

2、下列關于棧的敘述中，錯誤的是（ ）。Ⅰ.采用非遞歸方式重寫遞歸程序時必須使用棧Ⅱ.函數調用時，系統要用棧保存必要的信息Ⅲ.只要確定了入棧次序，即可確定出棧次序Ⅳ.棧是一種受限的線性表，允許在其兩端進行操作

A、僅Ⅰ

B、僅Ⅰ、Ⅱ、Ⅲ

C、僅Ⅰ、Ⅲ、Ⅳ

D、僅Ⅱ、Ⅲ、Ⅳ

3、適用于壓縮存儲稀疏矩陣的兩種存儲結構是（ ）。

A、 三元組表和十字鏈表

B、 三元組表和鄰接矩陣

C、 十字鏈表和二叉鏈表

D、 鄰接矩陣和十字鏈表

4、要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結點須滿足的條件是（ ）。

A、 只有左子樹

B、 只有右子樹

C、 結點的度均為1

D、 結點的度均為2

5、已知一棵二叉樹的樹形如下圖所示，其后序序列為e， a， c， b， d， g， f，樹中與結點a同層的結點是（ ）。

A、 c

B、 d

C、 f

D、 g

6、已知字符集{a， b， c ，d ， e， f， g， h}，若各字符的哈夫曼編碼依次是0100，10，0000，0101，001，011，11，0001，則編碼序列0100011001001011110101的譯碼結果是（ ）。

A、 a c g a b f h

B、 a d b a g b b

C、 a f b e a g d

D、 a f e e f g d

7、已知無向圖G含有16條邊，其中度為4的頂點個數為3，度為3的頂點個數為4，其他頂點的度均小于3。圖G所含的頂點個數至少是（ ）。

A、 10

B、 11

C、 13

D、 15

8、下列二叉樹中，可能成為折半查找判定樹（不含外部結點）的是（ ）。

A、

B、

C、

D、

9、下列應用中，適合使用B+樹的是（ ）。

A、 編譯器中的詞法分析

B、 關系數據庫系統中的索引

C、 網絡中的路由表快速查找

D、 操作系統的磁盤空閑塊管理