本文提供2016年數(shù)據(jù)結構考研真題答案及解析，以下為具體內(nèi)容

1、具有12個關鍵字的有序表，折半查找的平均查找長度（ ）。

A、3.1

B、4

C、2.5

D、5

2、設有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（   ）。

A、求子串

B、聯(lián)接

C、匹配

D、求串長

3、稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。

A、二維數(shù)組和三維數(shù)組

B、三元組和散列

C、三元組和十字鏈表

D、散列和十字鏈表

4、二叉樹在線索化后，仍不能有效求解的問題是（ ）。

A、先序線索化二叉樹中求先序后繼

B、中序線索化二叉樹中求中序后繼

C、后序線索化二叉樹中求后序后繼

D、中序線索化二叉樹中求中序前驅

5、對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度是（ ）。

A、O(1)

B、O(n)

C、

D、

6、在線性表中最常用的操作是存取第i個元素及其前驅的值，采用（ ）存儲方式最省時間？

A、順序表

B、帶頭結點的單向鏈表

C、帶頭指針的雙向循環(huán)鏈表

D、帶頭指針的單向循環(huán)鏈表

7、設head為一帶頭結點的循環(huán)鏈表的頭指針，則其判斷空表的條件是（ ）。

A、

B、

C、

D、

8、設n個元素進棧序列是p1，p2，p3，...，n，其輸出序列是1，2，3，...，n，若p3=1，則p1的值（ ）。

A、可能是2

B、一定是2

C、不可能是3

D、不可能是2

9、以數(shù)組Q[0..m-1]存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（ ）。

A、rear-qulen

B、rear-qulen+m

C、m-qulen

D、(1+rear+m-qulen)%m