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

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

1、下面程序段的時間復(fù)雜度是（ ）。i=1; while(i<=n) i=i*3;

A、O(n)

B、O(nlog(n))

C、O(log(n))

D、O(log₃n)

2、在n個元素的順序表中插入或刪除一個元素，需要平均移動表中（ ）個元素。

A、(n)

B、(n/2)

C、(n²)

D、(1)

3、設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0，...，m-1，其頭指針front指向隊(duì)首元素，rear指向隊(duì)尾元素，則隊(duì)列的長度為（ ）。

A、(rear-front+1)%(m+1)

B、(rear-front+m+1)%m

C、rear-front

D、rear-front+1

4、設(shè)計(jì)一個十進(jìn)制轉(zhuǎn)換為八進(jìn)制的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。

A、棧

B、隊(duì)列

C、順序結(jié)構(gòu)線性表

D、鏈?zhǔn)浇Y(jié)構(gòu)線性表

5、若某個棧的輸入序列為1，2，3，...，n，輸出序列的第一個元素為n，則第i個輸出元素為（ ）。

A、i

B、n-i

C、n-i+1

D、哪個元素?zé)o所謂

6、六個元素按6，5，4，3，2，1的順序進(jìn)棧，下列哪個出棧序列是錯誤的（ ）。

A、5 4 3 6 1 2

B、4 5 3 1 2 6

C、3 4 6 5 2 1

D、2 3 4 1 5 6

7、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）二叉樹。

A、空或只有一個結(jié)點(diǎn)

B、高度等于其結(jié)點(diǎn)數(shù)

C、任一結(jié)點(diǎn)無左孩子

D、任一結(jié)點(diǎn)無右孩子

8、高度為k的完全二叉樹至少有（ ）個結(jié)點(diǎn)（空樹高度為0）。

A、2^k-1

B、2^k

C、2^k-1

D、k

9、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹中至多有（ ）個結(jié)點(diǎn)。

A、2^h-1

B、2^h-1

C、2^h+1

D、2^h+1-1

10、數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行優(yōu)先存放時，元素A[8][5]的起始地址為（ ）。

A、SA+141

B、SA+222

C、SA+144

D、SA+225