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

1、計算算法的時間復雜度是屬于一種（  ）。

A、 事前統計的方法

B、 事前分析估算的方法

C、 事后統計的方法

D、 事后分析估算的方法

2、若有n個結點的線性表（a1，a2， ...，an） 以順序方式存儲，則算法的時間復雜度是O（1）的操作是（  ）。

A、 訪問第i個結點（1≤i≤n） 和第i個結點的直接前驅（2≤i≤n）

B、 在第i個結點后插入一個新結點（1≤i≤n）

C、 刪除第i個結點（1≤i≤n）

D、 以上都不對

3、雙向循環鏈表的結點中有兩個指針域，next和prior，分別指向前驅及后繼，設p指向鏈表中的一個結點，s指向一待插入結點，現要求在p后插入s，則正確的插入為（ ）。

A、 p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B、 s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

C、 p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;

D、 s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

4、鏈棧與順序棧相比，有一個比較明顯的優點是（ ）。

A、 插入操作更加方便

B、 刪除操作更加方便

C、 通常不會出現棧滿的情況

D、 不會出現棧空的情況

5、串是一種特殊的線性表，其特殊性體現在（）。

A、 可以順序存儲

B、 可以鏈接存儲

C、 數據元素可以是多個字符

D、 數據元素是一個字符

6、稀疏矩陣一般的壓縮存儲方法有兩種，即(  )。

A、 二維數組和三維數組

B、 三元組順序表和散列表

C、 散列表和十字鏈表

D、 三元組順序表和十字鏈表

7、一棵高度為h的完全二叉樹至少有(  )個結點。

A、 2^h-1

B、 2^h-1-1

C、 2^h-1

D、 2^h

8、在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的(  )倍。

A、 1/2

B、 1

C、 2

D、 4

9、針對下述結論，正確答案是（ ）。① 在索引順序表中，實現分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數有關，而且與每塊中元素個數有關。② 對大小均為 n的有序表和無序表分別進行順序查找，在等概率查找情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。

A、 ①②都正確

B、 ①②都不正確

C、 只有①正確

D、 只有②正確

10、假設對已經正序的n個關鍵字序列用直接插入排序法、簡單選擇排序法和一般的快速排序法對其排序，這些算法的時間復雜度依次應為（ ）。

A、 O（n），O（n²），O（n²）

B、 O（n²），O（n²），O（n²）

C、 O（n），O（n），O（n）

D、 O（n），O（n²），O（nlog₂n）