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

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

1、具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長度（ ）。

A、3.1

B、4

C、2.5

D、5

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

A、求子串

B、聯(lián)接

C、匹配

D、求串長

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

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

B、三元組和散列

C、三元組和十字鏈表

D、散列和十字鏈表

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

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

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

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

D、中序線索化二叉樹中求中序前驅(qū)

5、對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是（ ）。

A、O(1)

B、O(n)

C、

D、

6、在線性表中最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，采用（ ）存儲(chǔ)方式最省時(shí)間？

A、順序表

B、帶頭結(jié)點(diǎn)的單向鏈表

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

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

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

A、

B、

C、

D、

8、設(shè)n個(gè)元素進(jì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)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是（ ）。

A、rear-qulen

B、rear-qulen+m

C、m-qulen

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