《數(shù)據(jù)結(jié)構(gòu)與算法》習(xí)題集

《數(shù)據(jù)結(jié)構(gòu)與算法》習(xí)題集

一、單項選擇題

第1章概論

1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的(①)以及它們之間的(②)和

運算等的學(xué)科。

①A.數(shù)據(jù)元素B.計算方法C.邏輯存儲D.數(shù)據(jù)映像

②A.結(jié)構(gòu)B.關(guān)系C.運算D.算法

2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K,R),其中K是(①)的有限集，R是K上的(②)的有限集。

①A.數(shù)據(jù)元素B.算法C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)

②A.操作B.映像C.存儲D.關(guān)系

3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上看可以把數(shù)據(jù)結(jié)構(gòu)分成()。

A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

4.數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指()。

A.數(shù)據(jù)的存儲結(jié)構(gòu)B,數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系

5.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。

A.邏輯B.存儲C.邏輯和存儲D.物理

6.算法分析的目的是(①)，算法分析的兩個主要方面是(②)。

①A.研究數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進D.分析算法的易董性和文檔性

②A.空間復(fù)雜度和時間復(fù)雜度B.正確性和簡明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

7.算法指的是(①)，它必須具有輸入、輸出和(②)等5個特性。

①A.計算方法B.排序方法C.解決問題的有限運算序列D.調(diào)度方法

②A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性

8.以下敘述中，正確的是()。

A.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)

B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表

C.棧的操作方式是先進先出

D.隊列的操作方式是先進后出

9.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮()。

A.各結(jié)點的值如何B.結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運算

D.所用編程語言實現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)是否方便

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

A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型

C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲方法

11.下面說法錯誤的是()。

(1)算法原地工作的含義是指不需要任何額外的輔助空間

(2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度0(2,的算法

(3)所謂時間復(fù)雜度是指最壞情況下，估算執(zhí)行時間的一個上界

(4)同一個算法，實現(xiàn)語句的級別越高，執(zhí)行效率越低

A.(1)B.⑴、(2)C.⑴、(4)D.(3)

12.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著()。

A.數(shù)據(jù)元素具有同一■特點

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致

C.每個數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

13.以下說法正確的是()。

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B.數(shù)據(jù)項是數(shù)據(jù)的基本單位

C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的各數(shù)據(jù)項的集合

D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

14.算法的計算量的大小稱為計算的()。

A.效率B.復(fù)雜性C.現(xiàn)實性D.難度

15.算法的時間復(fù)雜度取決于()

A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B

16.計算機算法指的是【1】，它必須具備【2】這三個特性。

(1)A.計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方

法

(2)A.可執(zhí)行性、可移植性、可擴充性B.可執(zhí)行性、確定性、有窮性

C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性

17.?個算法應(yīng)該是()。

A.程序B.問題求解步驟的描述

C.要滿足五個基本特性1).A和C.

18.下面關(guān)于算法說法錯誤的是()

A.算法最終必須由計算機程序?qū)崿F(xiàn)

B.為解決某問題的算法同為該問題編寫的程序含義是相同的

C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的

19.下面說法錯誤的是()

(1)算法原地工作的含義是指不需要任何額外的輔助空間

(2)在相同的規(guī)模n下，復(fù)雜度0(n)的算法在時間上總是優(yōu)于復(fù)雜度0(2”)的算法

(3)所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界

(4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低

A.(1)B.(1),(2)C.(1),(4)D.(3)

20.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。

A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

21.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。

A.循環(huán)隊列B.鏈表C.哈希表D.棧

22.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)()?

A.廣義表B.二叉樹C.稀疏矩陣D.串

23.以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？()

A.棧B.哈希表C.線索樹D.雙向鏈表

24.在下面的程序段中，對x的賦值語句的頻度為（）

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

A.0(2n)B.0(n)C.0(n2)D.O(logJ)

25.程序段FORi:=nTDOWNTO1DO

FORj:=lTOiDO

IFA[j]>A[j+l]

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

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

A.0(n)B.O(nlogn)C.0(n3)D.0(n2)

26.以下哪個數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）

A.棧B.廣義表C.有向圖D.字符串

27.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹B.字符串C.隊D.棧

28.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。

A.棧B.隊列C.完全二叉樹D.堆

29.連續(xù)存儲設(shè)計時，存儲單元的地址（）。

A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)

30.以下屬于邏輯結(jié)構(gòu)的是（）。

A.順序表B.哈希表C.有序表D.單鏈表

31.組成數(shù)據(jù)的基本單位是（

A.數(shù)據(jù)項B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量

32.下列數(shù)據(jù)組織形式中，（）的結(jié)點按邏輯關(guān)系依次排列形成一個“鎖鏈”。

A.集合B.樹形結(jié)構(gòu)

C.線性結(jié)構(gòu)D.圖狀結(jié)構(gòu)

33.數(shù)據(jù)結(jié)構(gòu)可以形式化地定義為（S,△）,其中S指某種邏輯結(jié)構(gòu)，△是指（)

A.S上的算法B.S的存儲結(jié)構(gòu)

C.在S上的一個基本運算集D.在S上的所有數(shù)據(jù)元素

34.算法分析的目的是（）

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入/輸出關(guān)系

C.分析算法的效率以求改進D.分析算法的易讀性

35.數(shù)據(jù)結(jié)構(gòu)是?門研究非數(shù)值計算的程序設(shè)計問題中計算機的⑴以及它們之間的⑵和運算

等的學(xué)科。（

（1）A.操作對象Bo計算方法C。邏輯存儲1）。數(shù)據(jù)映象

（2）A.結(jié)構(gòu)Bo關(guān)系C?運算Do算法

36.數(shù)據(jù)結(jié)構(gòu)被形容地定義為（K,R），其中K是（1）的有限集合，R是K上的（2）有限

集合。

(1)A.算法Bo數(shù)據(jù)元素Co數(shù)據(jù)操作Do邏輯結(jié)構(gòu)

(2)A.操作B。映象Co存儲D?關(guān)系

37.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成

（1）A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)Bo緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D。內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

38.算法分析的目的是（1）,算法分析的兩個主要方面是（2）。

（1）A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進D.分析算法的易懂性和文檔性

（2）A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

39.計算機算法指的是（1）大，它必具備輸入、輸出和（2）等五個特性。

（1）A.計算方法B。排序方法

C.解決問題的有限運算序列D?調(diào)度方法

（2）A.可行性、可移植性和可擴充性B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性

第2章線性表

1.線性表不具備的特點是（）。

A.可隨機訪問任一結(jié)點B.插入刪除不需要移動元素

C.不必事先估計存儲空間D.所需空間與其長度成正比

2.不帶頭結(jié)點的單鏈表head為空的判定條件是（）。

A.head==NULLB.head->next==NULL

C.head->next=headD.head!==NULL

3.帶頭結(jié)點的單鏈表head為空的判定條件是（）。

A.head==NULLB.head->next==NULL

C.head->next=headD.head!==NULL

4.帶頭結(jié)點的雙循環(huán)鏈表L為空的條件是（）。

A.L==NULLB.L->next==NULL

C.L->prior==NULLD.L->next==L

5.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足（）。

A.p->next=NULLB.p==NULL

C.p->next==headD.p==head

6.在循環(huán)雙鏈表的p所指結(jié)點之前插入s所指結(jié)點的操作是()。

A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;

B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;

C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;

D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;

7.若某表最常用的操作是在最后一個結(jié)點之后插入--個結(jié)點或刪除最后一個結(jié)點，在采用

()存儲方式最節(jié)省運算時間。

A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶頭結(jié)點的雙循環(huán)鏈表

8.某線性標(biāo)最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除第一個結(jié)點，故采用

()存儲方式最節(jié)省運算時間。

A.單鏈表B.僅有頭結(jié)點的單循環(huán)鏈表C.雙鏈表D.僅有為指針的單循環(huán)鏈表

9.需要分配不僅大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是()。

A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲結(jié)構(gòu)

10.如果最常用的操作是取第i個結(jié)點及其前驅(qū)，在采用()存儲方式最節(jié)省時間。

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表

11.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是

()。

2

A.O(l)B.O(n)C.O(n)D.O(nlog2n)

12.在一個長度為n(n>l)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行()操作與鏈表的長

度有關(guān)。

A.刪除單鏈表中的第一個元素

B.刪除單鏈表中的最后一個元素

C.在單鏈表第一個元素前面插入一個新元素

D.在單鏈表最后一個元素后插入一個新元素

13.設(shè)線性表有n個元素，以下算法中，()在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。

A.輸出第i(0<=i<=n-l)個元素值

B.交換第0個元素與第1個元素的值

C.順序輸出這n個元素的值

D.輸出與給定值x相等的元素在線性表中的序號

14.設(shè)線性表中有2n個元素，算法(),在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高.

A.輸出所有值為x的元素

B.在最后一個元素的后面插入一個新元素

C.順序輸出前k個元素

D.交換第i個元素和第2n-i-l個元素的值(i=0,l,...,n-l)

15.與單鏈表相比，雙鏈表的優(yōu)點之一是()。

A.插入、輸出操作更簡單B.可以進行隨機訪問

C.可以受理表頭指針或表尾指針D.順序訪問相鄰結(jié)點更靈活

16.如果對線性表的運算只有四種，即刪除第一個元素，刪除最后一個元素，在第一個元素

的前面插入新元素，在最后一個元素的后面插入新元素，則最好使用()。

A.只有表尾指針沒有表頭指針的循環(huán)單鏈表

B.只有表尾指針沒有表頭指針的非循環(huán)雙鏈表

C.只有表頭指針沒有表尾指針的循環(huán)雙鏈表

D.既有表頭指針也有表尾指針的循環(huán)單鏈表

17.如果對線性表的運算只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素,

最最好使用（）o

A.只有表頭指針沒有表尾指針的循環(huán)單鏈表

B.只有表尾指針沒有表頭指針的循環(huán)單鏈表

C.非循環(huán)雙鏈表

D.循環(huán)雙鏈表

18.設(shè)有兩個長度為n的單鏈表，結(jié)點類型相同。若以hl為表頭指針的鏈表是非循環(huán)鏈表,

以h2為表頭指針的鏈表是循環(huán)鏈表，則（）。

A.對應(yīng)兩個鏈表來說，刪除第一個結(jié)點的操作，其時間復(fù)雜度都是0（1）

B.對應(yīng)兩個鏈表來說，刪除最好一個結(jié)點的操作，其時間復(fù)雜度都是0（n）

C循環(huán)鏈表要比非循環(huán)鏈表占用更多的存儲空間

D.hl和h2是不同類型的變量

19.在長度為n的（）上，刪除第一個元素，其算法的時間復(fù)雜度為0（n）。

A.只有表頭指針的不帶表頭結(jié)點的循環(huán)單鏈表

B.只有表尾指針的不帶表頭結(jié)點的循環(huán)單鏈表

C.只有表尾指針的帶表頭結(jié)點的循環(huán)單鏈表

D.只有表頭指針的帶表頭結(jié)點的循環(huán)單鏈表

20.下述哪一?條是順序存儲結(jié)構(gòu)的優(yōu)點？（）

A.存儲密度大B.插入運算方便C.刪除運算方便

D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

21.下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）

A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。

B.線性表采用順序存儲，便于進行插入和刪除操作。

C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。

D.線性表采用鏈接存儲，便于插入和刪除操作。

22.線性表是具有nj（）的有限序列（n>0）。

A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項E.信息項

23.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則

利用（）存儲方式最節(jié)省時間。

A.順序表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表

24.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采

用（）存儲方式最節(jié)省運算時間。

A.單鏈表B.僅有頭指針的單循環(huán)鏈表

C.雙鏈表D.僅有尾指針的單循環(huán)鏈表

25.設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用（）最節(jié)省時間。

A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表

26.若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用

（）存儲方式最節(jié)省運算時間。

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表

27.靜態(tài)鏈表中指針表示的是（）.

A.內(nèi)存地址B.數(shù)組下標(biāo)C.下一元素地址D.左、右孩子地址

28.鏈表不具有的特點是（）。

A.插入、刪除不需要移動元素B.可隨機訪問任一元素

C.不必事先估計存儲空間D.所需空間與線性長度成正比

29.下面的敘述不正確的是（）。

A.線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比

B.線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)

C.線性表在順序存儲時，查找第i個元素的時間同i的值成正比

D.線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)

30.線性表的表元存儲方式有（（1））鏈接兩種。試指出下列各表中使用的是何種存儲方式：

表1是（2）存儲方式；表2是（3）存儲方式；表3是（4）存儲方式；表4是（5）存儲方

式。表左的s指向起始表元。

表1

表元編號貨號數(shù)量表元間聯(lián)系

1618402

220523

3103154

4501205

5781176

6910240

表2

表元編號貝化甘n數(shù)量表元間聯(lián)系

1618405

220521

3103154

4501202

5781176

6910243

表3

表元編號貨號數(shù)量表元間聯(lián)系

1618405

220521

3103154

4501200

5781176

6910243

表4

表元編號貨號數(shù)量表元間聯(lián)系

12

16184052

2205210

31031546

45012003

57811761

69102435

供選擇的答案：

A.連續(xù)B.單向鏈接C.雙向鏈接D.不連接E.循環(huán)鏈接

F.樹狀G.網(wǎng)狀H.隨機I.順序J.順序循環(huán)

31.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素

的時間與i無關(guān)。

(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。

(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。

以上錯誤的是()o

A.(1),(2)B.(1)C.(1),(2),(3)D.(2)

32.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間

復(fù)雜度為()(l<=i〈=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

33.對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為()。

A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)

34.線性表(al,a2,…,an)以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為()

A.0(i)B.0(1)C.0(n)D.0(i-1)

35.非空的循環(huán)單鏈表head的尾結(jié)點指針p滿足()。

A.p->link=headB.p->link二NILC.p=NILD.p=head

36.循環(huán)鏈表H的尾結(jié)點P的特點是()。

A.P->NEXT=HB.P->NEXT=H->NEXTC.P=HD.P=H->NEXT

37.在一個以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是().

A.p->next=hB.p->next=NULLC.p->next->next=hD.p->data=-l

38.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是()。

A.p->Llink=q;q->Rlink=p;p->Llink->R1ink=q;q->Llink=q；

B.p->Llink=q;p->Llink->Rlink=q;q->Rlinkup;q->Llink=p->Llink;

C.q->Rlink=p;q->L1ink=p->L1ink;p->L1ink->Rlink二q;p->Llink=q;

D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

39.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：()。

A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;

C.p->next=s;p->next=s_>next;D.p->next=s->next;p->next=s;

40.對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是()

A.head==NULLB.headnext-NULLC.head-*next-headD.head!=NULL

41.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)，若在p、q之間插入s結(jié)點，則

執(zhí)行(B)操作。

A、s->next=p-next;p->next=s;B、q->next=s;s->next=p;

C、p->next=s->next;s->next=p;p->next=s;s->next=q;

42、使用雙向鏈表存儲數(shù)據(jù)，其優(yōu)點是可以(A)。

A、提高檢索速度B、很方便地插入和刪除數(shù)據(jù)

C、節(jié)約存儲空間D、很快回收存儲空間

43、單鏈表中，增加頭結(jié)點的目的是為了(A)o

A、方便運算的實現(xiàn)B、標(biāo)識單鏈表

C、使單鏈表中至少有一個結(jié)點1)、用于標(biāo)識起始結(jié)點的位置

若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用(D)存

儲方式最節(jié)省時間。

A、單鏈表B、雙鏈表C、單向循環(huán)鏈表D、順序表

44、帶頭結(jié)點的單鏈表h為空的判斷條件是（B

A>h==NULLB、h->next==NULLC、h->next=hD、h!=NULL

45.線性表的鏈接實現(xiàn)有利于（）運算。

A.插入B.讀表元素C.查找D.定位

46.設(shè)單鏈表中指針P指著結(jié)點A,若要刪除A之后結(jié)點（若存在），則需要修改指針的操

作為（

A.p->next=p->next->nextB.p=p->next

C.p=p->next->nextD.P->next=p

47.設(shè)雙鏈表中結(jié)點的前趨指針和后繼指針的域名分別為tl和rl,則刪除雙鏈表中指針s

所指結(jié)點的操作為（）

A.s->tl->rl=s->t1;s->rl->tl=s->rl;B.s->tl->rl=s->rl;s->rl->tl=s->t1;

C.s->rl=s->tl->r1;s->t1=s->r->t1;D.s->tl=s->t1->r1;s->rl=s->r->tl;

48.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點和直接后繼結(jié)點的指針域，現(xiàn)要把一

個指針s所指的新結(jié)點作為非空雙鏈表中q所指地點（中間結(jié)點）的直接后繼結(jié)點插入到該

雙向鏈表中，則下列算法段能正確完成上述要求的是（）

A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;

B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;

C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;

D.以上都不對

49.下列說法正確的是（）

A.線性表的邏輯順序與存儲順序總是一致的

B.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，要求內(nèi)存中可用的存儲單元可以是連續(xù)的，也可以不連續(xù)

C.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)

D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運算

50.設(shè)非空單鏈表的數(shù)據(jù)域為data,指針域為next,指針p指向單鏈表中第i個結(jié)點，s

指向已生成的新結(jié)點，現(xiàn)將s結(jié)點插入到單鏈表中，使其成為第i個結(jié)點，下列算法段

能正確完成上述要求的是（）

A.s->next=p->next;p->next=s；

B.p->next=s;s->next=p->next；

C.s->next=p->next;p->next=s;交換p->data和s->data；

D.p=s;s->next=p；

51.下面關(guān)于線性表的敘述中，錯誤的為（）

A.順序表使用一維數(shù)組實現(xiàn)的線性表B.順序表必須占用一片連續(xù)的存儲單元

C.順序表的空間利用率高于鏈表D.在鏈表中，每個結(jié)點只有一個鏈域

52.帶頭結(jié)點的單鏈表head為空的判斷條件是（）

A.head=NILB.headt.next=NIL

C.headt.next=headD.head<>NIL

53.一個順序表所占用的存儲空間大小與——無關(guān)?

A.表的長度B.元素的存放順序C.元素的類型D。元素中各字段的類型

54.設(shè)存儲分配是從低地址到高地址進行的。若每個元素占用4個存儲單元，則某元素的地

址是指它所占用的單元的

A.第1個單元的地址B.第2個單元的地址

C.第3個單元的地址n第4個單元的地址

55.若線性表采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第1個元素的存儲地址為

100,則第12個元素的存儲地址是o

A.112B.144C.1480.412

56.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在表的第i個位置插入一個數(shù)據(jù)元素，i的合

法值

應(yīng)該是——。

A.i>0B.iWnC.IWiWnD.IWiWn+l

57.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個數(shù)據(jù)元素，i的合法值應(yīng)

該是

A.i>0B.iWnC.IWiWnD。IWiWn十1

58.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個數(shù)據(jù)元素，首先需要移動

表

中——個數(shù)據(jù)元素。

A.n-iB.n+iC.n-i+1D.n-i-1

59.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在表的第i個位置插入一個數(shù)據(jù)元素，需要移

動

表中——個元素。。

A.iB.n+iC.n-i+1D.n-i-1

60.若頻繁地對線性表進行插入和刪除操作，該線性表應(yīng)該采用——存儲結(jié)構(gòu)。

A.散列B.順序C.鏈?zhǔn)紻.索引

61.鏈表中所占用的存儲單元地址一定是。

A.無序的B.連續(xù)的C.不連續(xù)的D.部分連續(xù)的

62.鏈表中的每一個鏈結(jié)點所占用的存儲單元——。

A.不必連續(xù)B.一定連續(xù)C.部分連續(xù)D.連續(xù)與否無所謂

63.與單鏈表相比，雙向鏈表的優(yōu)點之一是。

A.插入、刪除操作更簡單B.可以進行隨機訪問

C.可以省略頭結(jié)點指針I(yè)).順序訪問相鄰結(jié)點更靈活

64.若list是某帶頭結(jié)點的循環(huán)鏈表的頭結(jié)點指針，則該鏈表最后那個鏈結(jié)點的指針域中

存

放的是——?

A.list的地址B.list的內(nèi)容

C.list指的鏈結(jié)點的值I).鏈表第一個鏈結(jié)點的地址

65.若list是某帶頭結(jié)點的循環(huán)鏈表的頭結(jié)點指針，當(dāng)p(p與list同類型)指向鏈表的最

后那

個鏈結(jié)點時，——。

A.該結(jié)點的指針域為空B.p為空

C.p的內(nèi)容與頭結(jié)點的內(nèi)容相同D.該鏈結(jié)點指針域內(nèi)容與list的內(nèi)容相同

66.若listl和list2分別為一個單鏈表與一個雙向鏈表的第一個結(jié)點的指針，則——。

A.Iist2比listl占用更多的存儲單元B.listl與list2占用相同的存儲單元

C.listl和list2應(yīng)該是相同類型的指針變量D.雙向鏈表比單鏈表占用更多的存儲單

元

67.在表達式中，符號p->link表不--。

A.p所指的鏈結(jié)點的指針域(位置)

B.p所指的鏈結(jié)點的指針域的內(nèi)容

C.p所指的鏈結(jié)點的下一個鏈結(jié)點的地址

I),p所指的鏈結(jié)點的下一個鏈結(jié)點的地址(出現(xiàn)在表達式中)

68.在一個具有n個鏈結(jié)點的線性鏈表中查找某個鏈結(jié)點，若查找成功，需要平均比較

——個鏈結(jié)點。

A.nB.n/2C.(n+1)/2D.(n-1)/Q

69.從一個具有n個鏈結(jié)點的有序線性鏈表(即鏈結(jié)點按照數(shù)據(jù)域值有序鏈接)中插入一個

新的鏈結(jié)點，并且仍然保持鏈表有序的時間復(fù)雜度為——。

A.0(1)B.0(n)C.0(n(2))D.0(log2(n))

70.給定具有n個元素的順序表，建立一個有序線性鏈表的時間復(fù)雜度為一一。

A.0(1)B.0(n)C.0(n(2))D.0(log2(n))

71.在非空線性鏈表中由p所指的鏈結(jié)點后面插入一個由q所指的鏈結(jié)點的過程是依次執(zhí)

行----。

A.q->link=p；p->link=q；B.q->link=p->link；p->link=q；

C.q->link=p->link；p=q；D.p->link=q；q->link=p；

72.若刪除非空線性鏈表中由p所指的鏈結(jié)點的直接后繼鏈結(jié)點的過程是依次執(zhí)行

A.r=p->link；p->link=r；free(r)；

B.r=p->link；p->link=r->link；free(r)；

C.r=p->link；p->link=r->link；free(p)；

D.p->link=p->link->link；free(p)；

73.在非空雙向循環(huán)鏈表中由q所指的鏈結(jié)點后面插入一個由p所指的鏈結(jié)點的動作依次

為：p->llink=Q；p->rlink=q->rlink；q->rlink=p；----。(空白處為一條賦值

語句)

A.q->llink=pB.q->rlink->llink=p

C.p->fiink->l1ink=pD.p->l1ink->l1ink=p

74.在非空雙向循環(huán)鏈表中由q所指的那個鏈結(jié)點前面插入一個p所指的鏈結(jié)點的動作對

應(yīng)的語句依次為:p->rlink=Q；p->llink=q->llink；q->[link=p；----,(空白

處為一條賦值語句)

A.q->rlink=p；B.q->llink->rlink=p；

C.p->rlink->rlink=p；D.p->l1ink->rlink=p；

75.在包含有1000個數(shù)據(jù)元素的線性表中實現(xiàn)如下四個操作，所需要的執(zhí)行時間最長的是

—0

A.線性表采用順序存儲結(jié)構(gòu)，在第10個元素后面插入一個新的元素

B.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，在第10個元素后面插入一個新的元素

C.線性表采用順序存儲結(jié)構(gòu)，刪除第990個元素

D.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除p所指的鏈結(jié)點

76.不帶頭結(jié)點的單鏈表head為空的判定條件是3)。

A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL

77.帶頭結(jié)點的單鏈表head為空的判定條件是(1)。

A.head=NULLB.head->next=NULLC.head->next=headD.!=NULL

78.非空的循環(huán)單鏈表head的尾結(jié)點（由P所指向）滿足（1）。

A.p->next=NULLB.p=NULLC.p->next=headD.p=head

79.在循環(huán)雙鏈表的p所指結(jié)點之后插入S所指向的結(jié)點的操作是（1）。

A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;

80.在一個單鏈表中，已知p所指結(jié)點是前驅(qū)結(jié)點，若在q和p之間插入S結(jié)點，則執(zhí)行（1）。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;D.p->next=s;s->next=q;

81.在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入S所指結(jié)點，則執(zhí)行（l）o

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

82.在一個單鏈表中，若刪除P所指結(jié)點的后續(xù)結(jié)點，剛執(zhí)行（1）。

A.p-next=p->next->next;B.p=p->next;p->next=p->next->next;

C.p->next=p->next;D.p=p->next->next;

83.假設(shè)雙鏈表結(jié)點的類型如下：

Typedefstructlinknode

（

Intdata;/*數(shù)據(jù)域*/

Structlinknode*llink;/*llink是指向前驅(qū)結(jié)點的指針域*/

Structlinknode*rlink/*rlink是指向后續(xù)結(jié)點的指針域*/

}bnode

下面給出的算法段是要把一個q所指新結(jié)點作為非空雙向鏈表中的P所指結(jié)點的前驅(qū)結(jié)點插

入到該雙鏈表中，能正確完成要求的算法段是（1）。

A.q->rlink=p;

q->llink=p->llink;

p->llink=q;

p->llink->rlink=q;

B.p->llink=q;

q->rlink=p;

p->Hink->r1ink=q;

q->llink=p->llink;

C.q->Hink=p->llink;

q->rlink=p;

p->Hink->rlink=q;

p->llink=q;

D.以上都不對

第3章棧和隊列

1.棧的特點是（①）列的特點是（②）。

A.先進先出B.先進后出

2.棧和隊列的共同點是（）。

A.都是先進后出B.都是先進先出

C.只允許在端點插入和刪除元素D.沒有共同點

3.?個棧的進棧序列是a,b,c,d,e,則棧不可能的輸出序列是（）o

A.edcbaB.decbaC.dceabD.abcde

4.若已知一個棧的進棧序列是1,2,3,…,n,其輸出序列為pi,p2,p3,…,Pn，若pi=n,則pi（k=ivn）

為（）。

A.iB.n=iC.n-i+1D.不確定

5.若已知一個棧的進棧序列是1,2,3.n,其輸出序列為pi,p2,p3,…,Pn，若Pn=n,則pi（l<=i<n）

為（）。

A.iB.n=iC.n-i+1D.不確定

6.若已知一個棧的進棧序列是1,2,3.n,其輸出序列為P|,P2,P3,…,Pn，若Pl=l，則P2為（）。

A.可能是2B.不一定是2C.可能是1D.一定是1

7.若已知一個棧的進棧序列是1,2,3,其輸出序列為pi,p2,p3,…,p”若p3=l，則Pi為

（）。

A.可能是2B.一定是2C.不可能是2D.不可能是3

8.若已知一個棧的進棧序列是Pl,P2,P3,...,Pn，輸出序列是1,2,3,..,110若Pn=l,則Pi（l<=i<n）

為（）。

A.n-i+1B.n-iC.iD.有多種可能

9.判定一個棧ST（最多元素為MaxSize）為空的條件是（）。

A.ST->top!=-1B.ST->top==-l

C.ST->top!=MaxSize-1D.ST->top=MaxSize-l

10.判定一個棧ST（最多元素為MaxSize）棧滿的條件是（）。

A.ST->top!=-lB.ST->top==-l

C.ST->top!=MaxSize-lD.ST->top==MaxSize-l

11.最不適合用作鏈枝的鏈表是（）0

A.只有表頭指針沒有表尾指針的循環(huán)雙鏈表

B.只有表尾指針沒有表頭指針的循環(huán)雙鏈表

C.只有表尾指針沒有表頭指針的循環(huán)單鏈表

D.只有表頭指針沒有表尾指針的循環(huán)單鏈表

12.向一個棧頂指針為HS的鏈棧中插入一個S所指結(jié)點時，則執(zhí)行（）。

A.HS->next=S；B.S->next=HS->next;HS->next=S;

C.S->next=HS;HS=S;D.S->next=HS;HS=HS->next;

13.從一個棧頂指針為HS的鏈棧中輸出一個結(jié)點時，用x表層被刪除結(jié)點的值，則執(zhí)行

（）。

A.x=HS;HS=HS->next;B.x=HS->data;

C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;

14.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是（）。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1

15.判定一個隊列QU（最多有MaxSize個元素）為空的條件是（）。

A.QU->rear-QU->front==MaxSizeB.QU->rear-QU->front-l==MaxSize

C.QU->front==QU->rearD.QU->front==QU->rear+1

16.判定一個隊列QU（最多有MaxSize個元素）隊滿件是（）。

A.QU->rear-QU->front==MaxSizeB.QU->rear-QU->front-l==MaxSize

C.QU->front==QU->rearD.QU->front==QU->rear+1

17.循環(huán)順序隊列中是否可以插入下一個元素，（）。

A.與對隊頭指針和隊尾指針的值有關(guān)

B.只與隊尾指針的值有關(guān)，與隊頭指針的值無關(guān)

C只與數(shù)組的大小有關(guān)，與隊首指針和隊尾指針的值無關(guān)

D.與曾經(jīng)進行多少次插入操作有關(guān)

18.判定一個循環(huán)隊列QU（最多有MaxSize個元素）為空的條件是（）。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==（QU->rear+1）%MaxSizeD.QU->front!=（QU->rear+1）%MaxSize

19.判定一個循環(huán)隊列QU（最多有MaxSize個元素）隊滿的條件是（）。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==（QU->rear+l）%MaxSizeD.QU->front!=（QU->rear+1）%MaxSize

20.循環(huán)隊列用數(shù)組A[0,m-l]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊

列中的元素個數(shù)是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front

21.若用一個大小為6的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3。

當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是（）。

A.1和5B.2和4C.4和2D.5和1

22.最不適合用作鏈隊的鏈表是（）°

A.只帶隊頭指針的非循環(huán)鏈表B.只帶隊頭指針的循環(huán)雙鏈表

C.只帶隊尾指針的循環(huán)雙鏈表D.只帶隊尾指針的循環(huán)單鏈表

23.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算是（）o

A.f->next=s;f=s;B.r->next=s;r=s;

C.s->next=r;r=s;D.s->next=f;f=s;

24.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算是（）o

A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;

25.用單鏈表表示的鏈隊的隊頭在鏈表的（）位置。

A.鏈頭B.鏈尾C.鏈中

26.對于棧操作數(shù)據(jù)的原則是（）。

A.先進先出B.后進先出C.后進后出D.不分順序

27.在作進棧運算時，應(yīng)先判別棧是否（①），在作退棧運算時應(yīng)先判別棧是否（②）。當(dāng)棧中

元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為（③）。為了增加內(nèi)存空間的

利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的（④）分別設(shè)

在這片內(nèi)存空間的兩端，這樣，當(dāng)（⑤）時，才產(chǎn)生上溢。