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

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

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

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

B、 事前分析估算的方法

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

D、 事后分析估算的方法

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

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

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

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

D、 以上都不對(duì)

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

A、 插入操作更加方便

B、 刪除操作更加方便

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

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

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

A、 可以順序存儲(chǔ)

B、 可以鏈接存儲(chǔ)

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

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

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

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

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

C、 散列表和十字鏈表

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

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

A、 2^h-1

B、 2^h-1-1

C、 2^h-1

D、 2^h

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

A、 1/2

B、 1

C、 2

D、 4

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

A、 ①②都正確

B、 ①②都不正確

C、 只有①正確

D、 只有②正確

10、假設(shè)對(duì)已經(jīng)正序的n個(gè)關(guān)鍵字序列用直接插入排序法、簡單選擇排序法和一般的快速排序法對(duì)其排序，這些算法的時(shí)間復(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）