2017年數(shù)據(jù)結(jié)構(gòu)考研真題答案及解析

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

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

A、 事前統(tǒng)計的方法

B、 事前分析估算的方法

C、 事后統(tǒng)計的方法

D、 事后分析估算的方法

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

A、 訪問第i個結(jié)點（1≤i≤n） 和第i個結(jié)點的直接前驅(qū)（2≤i≤n）

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

C、 刪除第i個結(jié)點（1≤i≤n）

D、 以上都不對

3、雙向循環(huán)鏈表的結(jié)點中有兩個指針域，next和prior，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個結(jié)點，s指向一待插入結(jié)點，現(xiàn)要求在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、鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（ ）。

A、 插入操作更加方便

B、 刪除操作更加方便

C、 通常不會出現(xiàn)棧滿的情況

D、 不會出現(xiàn)?？盏那闆r

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

A、 可以順序存儲

B、 可以鏈接存儲

C、 數(shù)據(jù)元素可以是多個字符

D、 數(shù)據(jù)元素是一個字符

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

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

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

C、 散列表和十字鏈表

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

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

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、針對下述結(jié)論，正確答案是（ ）。① 在索引順序表中，實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊中元素個數(shù)有關(guān)。② 對大小均為 n的有序表和無序表分別進行順序查找，在等概率查找情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。

A、 ①②都正確

B、 ①②都不正確

C、 只有①正確

D、 只有②正確

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

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）