本文提供2012年數據結構考研真題答案及解析，以下為具體內容

1、線性表（a1，a2，…，an）采用靜態鏈表存儲時，訪問第i位置元索的時間復雜度為（ ）。

A、O（n²）

B、O（n）

C、O（i）

D、O（1）

2、設深度為k的二叉樹上只有度為0和度為2的結點則這類二叉樹上所含結點總數最少（ ）個。

A、k+1

B、2k

C、2k-1

D、2k+1

3、設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為（ ）。

A、21

B、23

C、41

D、62

4、如下陳述中正確的是（  ）。

A、串是一種特殊的線性表

B、串的長度必須大于零

C、串中元素只能是字母

D、空串是由空格組成的串

5、與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ ）。

A、存儲結構

B、存儲實現

C、邏輯結構

D、運算實現

6、除了（  ），其它任何指針都不能在算法中作為常量出現。

A、頭指針

B、尾指針

C、指針型變量

D、空指針

7、稀疏矩陣的壓縮存儲方法是只存儲（  ）。

A、非零元素

B、三元組（i，j，a_i,j）

C、ai,j

D、i，j

8、設rear是指向非空帶頭結點的循環單鏈表的尾指針，delete是釋放結點的空間，則刪除表中第一個元素結點的操作可表示為（ ）。

A、p=rear; rear=rear- >next; delete p;

B、rear=rear->next; delete rear;

C、p=rear->next->next; rear->next->next=p->next; delete p;

D、rear=rear->next->next; delete rear;

9、對廣義表L=（a，（b，c）），進行Tail （L）操作后的結果為（  ）。

A、c

B、b，c

C、（b，c）

D、（（b， c））

10、若元素A、B、C、D、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（  ）。

A、dcebfa

B、cbdaef

C、bcaefd

D、afedcb