數(shù)據(jù)結(jié)構(gòu)試題 (三)

數(shù)據(jù)結(jié)構(gòu)

1.順序表中第一個元素的存儲

地址是100,每個元素的長度為

2,則第5個元素的地址是()0

110

108

100

120

2.在n個結(jié)點的順序表中，算法

的時間復(fù)雜度是0(1)的操作是

()。

2.[單選題]*

訪問第i個結(jié)點(l<i<n)和求第i個結(jié)點的直接前驅(qū)(2<i<n)

在第i個結(jié)點后插入一個新結(jié)點(l<i<n)

刪除第i個結(jié)點(l<i<n)

將n個結(jié)點從小到大排序

答案解析：采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。順序表是將表中的結(jié)點依

次存放在計算機內(nèi)存中一組地址連續(xù)的存儲單元中。

假設(shè)順序表L,長度為n,求bai第i個節(jié)點L[i],直接前驅(qū)因此為duO(1)

答案B需要移動zhin-i個節(jié)點，因此為0(n)

答案C也需要移動n-i個節(jié)點

答案D根據(jù)排序方法不同最慢0(22),最快O(nlogn)

3向一個有127個元素的順序

表中插入一個新元素并保持原

來順序不變，平均要移動的元

素個數(shù)為()。

3.

［單選題］*

8

63.5(正確答案)

63

7

答案解析：n(n+l)/

(2*(n+l))=n/2

4線性表若采用鏈式存儲結(jié)構(gòu)

時,要求內(nèi)存中可用存儲單元的

地址()0

4.［單選題］*

必須是連續(xù)的

部分地址必須是連續(xù)的

一定是不連續(xù)的

連續(xù)或不連續(xù)都可以

5.將兩個各有n個元素的有序

表歸并成一個有序表，其最少的

比較次數(shù)是（）。

［單選題］*

n（正確答案）

2n-l

2n

n-1

答案解析：歸并排序基本思想：歸并排序是多次將兩個或兩個以上的有序表合并成

一個新的有序

表。最簡單的歸并是直接將兩個有序的子表合并成一個有序的表。歸并排序最好情

況下的復(fù)雜度

為。（嘰

6.將兩個各有N個元素的有序表歸并成一個有序表，其最多的比較次數(shù)是（）。

［單選題］*

2n-l（正確答案）

2n

n-1

答案解析：最多的比較次數(shù)是當兩個有序表的數(shù)據(jù)剛好是插空順序的時候，比如：

第一個序列是1,3,5,第二個序列是2,4,6,把第二個序列插入到第一個序列中，先

把第二個序列中的第一個元素2和第一個序列依次比較，需要比較2次（和1,3

比較），第二個元素4需要比較2次（和3,5比較，因為4比2大，2之前的元素

都不用比較了），第三個元素6需要比較1次（只和5比較），所以最多需要比較

5次。即2n-l次。

7.線性表1=（al,a2,………）.下列說法正確的是（）。［單選題］*

每個元素都有一個直接前驅(qū)和一個直接后繼

線性表中至少有一個元素

表中諸元素的排列必須是由小到大或由大到小

除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后

繼。（正確答案）

8.以下說法錯誤的是（）［單選題］*

求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈式存儲結(jié)構(gòu)

時實現(xiàn)的效率低

順序存儲的線性表可以隨機存取

由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活

線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

9.線性表L在（）情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。［單選題］*

需經(jīng)常修改L中的結(jié)點的值

需不斷對L進行刪除插入

L中含有大量的結(jié)點

L中結(jié)點結(jié)構(gòu)復(fù)雜

10.在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句為（）［單選題］*

S->next=p+1;p->next=s;.

（*p）.next=s;（*s）.next=（*p）.next;

S->next=p->next;p->next=S->next;

S->next=p->next;p->next=s;正確答案）

答案解析：s所指的結(jié)點的指針（s->next）指向當前P指針所指結(jié)點的指針（p->next）

所指向的結(jié)點

P指針所指結(jié)點的指針（p->next）指向的結(jié)點為s所指的結(jié)點（s）

II.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（）［單選題］*

分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點關(guān)系的指針

只有一部分，存放結(jié)點值

只有一部分，存儲表示間關(guān)系的指針

分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)

12.()是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

［填空題］*

___________________________________(答案:數(shù)據(jù)元素)

13._是數(shù)據(jù)的最小單位，—是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。［填空題］

*

空1答案：數(shù)據(jù)項

空2答案：數(shù)據(jù)元素

14.從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為___________和。［填空題］*

空1答案：集合

空2答案：線性結(jié)構(gòu)

空3答案：樹結(jié)構(gòu)

空4答案：圖結(jié)構(gòu)

15.數(shù)據(jù)的存儲結(jié)構(gòu)主要有—和—兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲

兩方面的內(nèi)容：一和一o［填空題］*

空1答案：順序存儲結(jié)構(gòu)

空2答案：鏈接存儲結(jié)構(gòu)

空3答案：數(shù)據(jù)元素

空4答案：數(shù)據(jù)元素之間的關(guān)系

16.算法具有五個特性，分別是______________________

［填空題］*

空1答案：有窮性

空2答案：確定性

空3答案：可行性

空4答案：有零個或多個輸入

空5答案：有一個或多個輸出

17.算法的描述方法通常有__、_、_和一四種，其中，—被稱為算法語言。

［填空題］*

空1答案：自然語言

空2答案：程序設(shè)計語言

空3答案：流程圖

空4答案：偽代碼

空5答案：偽代碼

18.在一般情況下，一個算法的時間復(fù)雜度是()的函數(shù)。［填空題］*

___________________________________(答案：問題規(guī)模)

19.設(shè)待處理問題的規(guī)模為n,若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)

量級的形式為_,若為n*log25n,則表示成數(shù)量級的形式為一。［填空題］*

空1答案：0（1）

空2答案：O（nlog2n）

2（）.順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由一表示的，鏈接存儲結(jié)構(gòu)中的數(shù)

據(jù)元素之間的邏輯關(guān)系是由一表示的。［填空題］*

空1答案：存儲位置

空2答案：指針

答案解析：順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系

由存儲位置（即元素在數(shù)組中的下標）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈

表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。

21.假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親

或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)

應(yīng)該是（）。［填空題］*

___________________________________（答案：圖）

22.算法指的是（）。

［填空題］*

（答案：對特定問題求解步驟的一種描述，是

指令的有限序列。）

答案解析：計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；

數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的準確定義。

算法指的是（）。A對特定問題求解步驟的一種描述，是指令的有限序列。

23.下面（）不是算法所必須具備的特性。［單選題］*

有窮性

確切性

高效性

可行性

24.算法分析的目的是（）,算法分析的兩個主要方面是（）。*

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中輸入和輸出的關(guān)系

C.分析算法的效率以求改進

D.分析算法的易讀性和文檔性

E空間性能和時間性能

F正確性和簡明性

G可讀性和文檔性

H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

25.算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。［判斷題］*

對

錯正確答案）

答案解析：時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。

26.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。［判斷題］*

對

錯正確答案）

答案解析：如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。

27.所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。［判斷題］*

對

錯

答案解析：是數(shù)據(jù)之間的邏輯關(guān)系的整體。

28.邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。［判斷題］*

對

錯

答案解析：因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。

29.基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。［判斷題］*

對

錯（正確答案）

答案解析：基本操作的實現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。

簡答［矩陣題］*

很不滿意不滿意一般滿意很滿意

順序存儲

結(jié)構(gòu)的特OOOOO

點是

鏈接存儲

結(jié)構(gòu)的特OOOOO

點是

答案解析：1.用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

2.用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

30.算法在發(fā)生非法操作時可以作出處理的特性稱為（）。［填空題］*

___________________________________（答案：健壯性）

31.常見的算法時間復(fù)雜度用大。記號表示為：常數(shù)階__、對數(shù)階_、線性階

一、平方階一和指數(shù)階一。［填空題］*

空1答案：0(1)

空2答案：O(log2n)

空3答案：0(n)

空4答案：0(nA2)

空5答案：0(2人n)

32.將下列函數(shù)按它們在n時的無窮大階數(shù)，從小到大排列。

n,n-nA3+7nA5,nlog2n,2A(n/2),nA3,log2n,nA(l/2)+log2n,(3/2)An,n!,nA2+log2n

［填空題】*

空1答案：log2n

空2答案："(1/2)+log2n

空3答案：n

空4答案:nlog2n

空5答案:nA2+log2n

空6答案:nA3

空7答案：n-nA3+7nA5

空8答案:2A(n/2)

空9答案：(3/2)人n

空10答案：n!

33.可以用()定義一個完整的數(shù)據(jù)結(jié)構(gòu)。［單選題］*

數(shù)據(jù)元素

數(shù)據(jù)對象

數(shù)據(jù)關(guān)系

抽象數(shù)據(jù)類型

34.數(shù)據(jù)的邏輯結(jié)構(gòu)分為—和—

前者包括一般線性表、受限線性表______________線性表的推廣__、

后者包括一，一形結(jié)構(gòu)_________一狀結(jié)構(gòu)________［填空題］*

空1答案：線性結(jié)構(gòu)

空2答案：非線性結(jié)構(gòu)

空3答案：棧

空4答案：隊列

空5答案：串

空6答案：數(shù)組

空7答案：廣義表

空8答案：集合

空9答案：樹

空10答案：一般樹

空11答案：二叉樹

空12答案：圖

空13答案：有向圖

空14答案：無向圖

35.以下屬于邏輯結(jié)構(gòu)的是［單選題］*

順序表

哈希表

有序表

單鏈表

答案解析：順序表、哈希表和單鏈表表示幾種數(shù)據(jù)結(jié)構(gòu)，既描述邏輯結(jié)構(gòu)，又描述

存儲結(jié)構(gòu)和數(shù)據(jù)運算。

而有序表是指關(guān)鍵字有序的線性表，可以鏈式存儲也可以順序存儲，僅描述元素之

間的邏輯關(guān)系，故它屬于邏輯結(jié)構(gòu)。

36.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）［單選題］*

循環(huán)隊列

鏈表

哈希表

棧（正確答案）

答案解析：數(shù)據(jù)的存儲結(jié)構(gòu)有順序存儲、鏈式存儲、索引存儲和散列存儲。循環(huán)隊

列（易錯點）是用順序表表示的隊列（見322節(jié)），是一種數(shù)據(jù)結(jié)構(gòu)。棧是一種

抽象數(shù)據(jù)類型，可采用順序存儲或鏈式存儲，只表示邏輯結(jié)構(gòu)。

37.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法中，正確的是（）.

［單選題］*

A.數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于其存儲結(jié)構(gòu)

B.數(shù)據(jù)的存儲結(jié)構(gòu)獨立于其邏輯結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)唯一決定了其存儲結(jié)構(gòu)

D.數(shù)據(jù)結(jié)構(gòu)僅由其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)決定

答案解析：A數(shù)據(jù)的邏輯結(jié)構(gòu)是從面向?qū)嶋H問題的角度出發(fā)的，只采用抽象表達方

式，獨立于存儲結(jié)構(gòu)，數(shù)據(jù)的存儲方式有多種不同的選擇：而數(shù)據(jù)的存儲結(jié)構(gòu)是邏

輯結(jié)構(gòu)在計算機上的映射，它不能獨立于邏輯結(jié)構(gòu)而存在。數(shù)據(jù)結(jié)構(gòu)包括三個要

素，缺一不可。

38.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且要存儲（）.

［單選題］*

數(shù)據(jù)的操作方法

數(shù)據(jù)元素的類型

數(shù)據(jù)元素之間的關(guān)系

數(shù)據(jù)的存取方法

39.鏈式存儲設(shè)計時，結(jié)點內(nèi)的存儲單元地址（）［單選題］*

一定連續(xù)（正確答案）

一定不連續(xù)

不一定連續(xù)

部分連續(xù)，部分不連續(xù)

答案解析：鏈式存儲設(shè)計時，各個不同結(jié)點的存儲空間可以不連續(xù)，但結(jié)點內(nèi)的存

儲單元地址必須連續(xù)。

40.數(shù)據(jù)的存儲結(jié)構(gòu)有_________________［填空題］*

空1答案：順序存儲

空2答案：鏈式存儲

空3答案：索引存儲

空4答案：散列存儲

41.一個算法應(yīng)該是()*

程序

問題求解步驟的描述

滿足五個基本特征

A和C

42.某算法的時間復(fù)雜度為O(22),表明該算法的().

［單選題］*

問題規(guī)模是nA2

執(zhí)行時間等于22

執(zhí)行時間與22成正比

問題規(guī)模與nA2成正比

答案解析：時間復(fù)雜度為O(22),說明算法的時間復(fù)雜度T(n)滿足T(n)

(c為比例常數(shù))，即T(n)=O(22),時間復(fù)雜度T(n)是問題規(guī)模n

的函數(shù)，其問題規(guī)模仍然是n而不是心2。

4.12011統(tǒng)考A題】設(shè)〃是描述問題規(guī)模的非負整數(shù)，下面的程序片段的時間復(fù)雜度是().

x-2；

while(x<n/2)

xsss2*x；

O(log2n)B.O(n)

5川og?〃)D.0(/)

［單選題］*

A(正確答案)

答案解析：

4.A

在程序中,執(zhí)行頻率以高的語句為x=2*x.設(shè)這一語句共執(zhí)行了/次，則有2^<〃/2,所以

log2(w/2)-1=login-2.得l\n)=O(log2w).

注意是t+1

5.12012統(tǒng)考真題】求整數(shù)〃(〃>0)的階乘的算法如下，其時間復(fù)雜度是().

intfact(intn){

if(n<?l)return1;

returnn*fact(n-1);

D.5〃2)

A.O(log2n)B.5〃)C.5"log2")

［單選題］*

A

B（正1

C

D

答案解析：

5.B

本題是求階乘〃!的遞歸代碼，即〃X(〃-1)x…X1,共執(zhí)行〃次乘法操作，故”〃)=。(〃)?

45.

6.12013統(tǒng)考真題】已知兩個長度分別為，〃和〃的升序徒友，若將它們合并為西!巡勰

一個長度為即+〃的降序性表，則最壞情況下的時間復(fù)雜度是().

A.。(〃)B.O(mn)

C.O(min(/ii,〃))D.O(max(/n,n))

［單選題］*

A

B

C

D(正確答案)

答案解析：

6.D

兩個升序缸表會并，兩兩比較表中的元素，每比較一次，確定一個元素的徒接位置(取較小

元素，頭插法).當個倍表比較結(jié)束后，將另一?個倍衣的剩余元素插入即可.圾壞的情況是兩

個鏈衣中的元素依次進行比較，時間復(fù)雜度為tXmax(m,/?)).

46.

7.【2014統(tǒng)考攵題】下列程序段的時間復(fù)雜度是().

count-0;

for(k=l;k<=n;k*=2)

for(j-1;j<-n;j++)

count++;

A.O(log2〃)B.O(n)

2

C.O(nlog2n)D.O(n)

［單選題］*

A

B

C(I

D

答案解析：

7.C

內(nèi)展循環(huán)條件與外層循環(huán)的變盤無關(guān)，每次循環(huán)/白增1.每次內(nèi)層循環(huán)都執(zhí)行”次.

外層循環(huán)條件為AW〃.增Id定義為k*?2,可知循環(huán)次數(shù)為2*W〃，即大41。區(qū)〃?所以內(nèi)層循環(huán)的

時間攵雜度是0(”)，外層砧環(huán)的時間必雜度是0(1。刎)?對于嵌套循環(huán)，根據(jù)乘法規(guī)則可知，讀

段程序的時間女雜度n〃)-A(〃)xTK〃)-a")xaiogM=0(nl0fe/?).

47.

8.12017統(tǒng)才算題】下列函數(shù)的時間復(fù)雜度是().

intfunc(intn)(

inti?0,sum?0;

while(sum<n)sum+■++i;

return1;

J

A.O(logn)B.O(nia)

C.0(")D.O(nlogn)

［單選題］*

A

B（正1

C

答案解析：

8.B

sum+=++i;相當于++i;sum-sum+i;.進行到第上次循環(huán)，sum-(1+k)*k/2.顯然需

要進行5/c)次循環(huán)，因此這也是該函數(shù)的時間復(fù)雜度.

48.

9.有以下算法，其時間復(fù)雜度為（）.

voidfun（intn）｛

inti"0;

while

2020年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)

i++;

)

A.O(n)B.O(〃logn)

C.5匕)D.5?)

［單選題］*

A(正確答案)

B

C

D

答案解析：

9.C

基本運算是i++,設(shè)其執(zhí)行次數(shù)為1,有nxW”，即故有/W防，則”〃)=5防).

49.

10.程序段如下：

for(i=n-l;i>l;i--)

for(j=l;j<i;j++)

if(A[j]>A[j+lJ)

A[j]與A[j+1]對換;

其中”為正整數(shù)，則最后一行語句的頻度在最壞情況下是().

A.0(/i)B.。(川。部)

C.0(n3)D.0(〃2)

[單選題]*

A

B

C

D(正確答案)

答案解析：

10.D

當所有相鄰元索都為逆序時，則最后一行的語句每次都會執(zhí)行.此時,

T(〃)=￡W】=￡iT=d)("l)/2=°(/)

1■2/■1M

所以在最壞情況下的該語句頻度是。0?)?

11.以下算法中加下畫線的語句的執(zhí)行次數(shù)為().

intmN。，，，j;

for