數(shù)據(jù)結(jié)構(gòu)（線性表）練習(xí)題與答案1

1、線性表是()。

A.一個(gè)有限序列，可以為空

B.一個(gè)有限序列，不可以為空

C.一個(gè)無(wú)限序列，可以為空

D.一個(gè)無(wú)限序列，不可以為空

正確答案：A

解析：線性表是具有n(n20)個(gè)數(shù)據(jù)元素的有限序列。

2、線性表的基本運(yùn)算Listinsert(也L,i,e)表示在線性表L中第i

個(gè)位置上插入一個(gè)元素e,若L的長(zhǎng)度為n,則i的合法取值是

()O

A.iWiWn

B.lWiWn+1

C.OWiWnT

D.OWiWn

正確答案：B

解析：線性表的基本運(yùn)算Listinsert(&L,i,e)中，位置i是指

邏輯序號(hào)，可以在L的位置1到位置n+1插入元素。

3、順序表具有隨機(jī)存取特性，指的是()。

A.查找值為x的元素與順序表中元素個(gè)數(shù)n無(wú)關(guān)

B.查找值為x的元素與順序表中元素個(gè)數(shù)n有關(guān)

C.查找序號(hào)為i的元素與順序表中元素個(gè)數(shù)n無(wú)關(guān)

D.查找序號(hào)為i的元素與順序表中元素個(gè)數(shù)n有關(guān)

正確答案：C

解析：一種存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存取特性指的是，對(duì)于給定的序號(hào)

i,在0(1)時(shí)間內(nèi)找到對(duì)應(yīng)元素值。

4、在順序表中刪除一個(gè)元素所需要的時(shí)間()。

A.與刪除元素的位置及順序表的長(zhǎng)度都有關(guān)

B.只與刪除元素的位置有關(guān)

C.與刪除任何其他元素所需要的時(shí)間相等

D.只與順序表的長(zhǎng)度有關(guān)

正確答案：A

解析：當(dāng)從順序表中刪除元素時(shí)，為了保持順序表的邏輯特性，需

要移動(dòng)元素以覆蓋該刪除的元素。因此在順序表中刪除一個(gè)元素與

該元素的位置及順序表的長(zhǎng)度都有關(guān)。

5、在n(n>l)個(gè)運(yùn)算的順序表中，算法時(shí)間復(fù)雜度為0(1)的運(yùn)算

是()。

A.訪問(wèn)第i個(gè)元素(2WiWn)并求其前驅(qū)元素

B.在第i個(gè)元素之后插入一個(gè)新元素

C.刪除第i個(gè)元素

D.將這n個(gè)元素遞增排序

正確答案：A

解析：訪問(wèn)第i個(gè)元素(2WiWn)即L->data[iT]和求其前驅(qū)元

素L->data[i-2]的時(shí)間復(fù)雜度均為0(1)。

6、關(guān)于線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述中，正確的是

()O

I.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

n.順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度高

in.如需要頻繁插入和刪除元素，最好采用順序存儲(chǔ)結(jié)構(gòu)

IV.如需要頻繁插入和刪除元素，最好采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

A.I、II、III

B.II.IV

C.IKIII

D.IlkIV

正確答案：B

解析：線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，不能簡(jiǎn)

單比較好壞，所以I錯(cuò)誤。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用指針表示邏輯關(guān)系，

所以存儲(chǔ)密度比較低，所以n正確。如頻繁使用插入和刪除操作，

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更優(yōu)于順序存儲(chǔ)結(jié)構(gòu)，所以in錯(cuò)誤，w正確。

7、在單鏈表中，增加一個(gè)頭節(jié)點(diǎn)的目的是為了（）。

A.使單鏈表至少有一個(gè)節(jié)點(diǎn)

B.標(biāo)識(shí)鏈表中某個(gè)重要節(jié)點(diǎn)的位置

C.方便插入和刪除運(yùn)算的實(shí)現(xiàn)

D.表示單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

正確答案：C

解析：在單鏈表中增加一個(gè)頭節(jié)點(diǎn)的主要目的是使刪除和插入節(jié)

點(diǎn)操作更簡(jiǎn)單，方便運(yùn)算的實(shí)現(xiàn)。

8、通過(guò)含有n（n21）個(gè)元素的數(shù)組a,采用頭插法建立一個(gè)單鏈

表L,則L中節(jié)點(diǎn)值的次序（）。

A.與數(shù)組a的元素次序相同

B.與數(shù)組a的元素次序相反

C.與數(shù)組a的元素次序無(wú)關(guān)

D.以上都不對(duì)

正確答案：B

解析：采用頭插法建立單鏈表時(shí)，后面的節(jié)點(diǎn)插入到最前端，所以

L的節(jié)點(diǎn)值次序與數(shù)組a的元素次序相反。

9、某算法在含有n(n2l)個(gè)節(jié)點(diǎn)的單鏈表中查找值為x節(jié)點(diǎn)，其

時(shí)間復(fù)雜度是()。

A.0(log2n)

B.0(1)

C.0(n2)

D.0(n)

正確答案：D

解析：需要從首節(jié)點(diǎn)出發(fā)逐一查找每個(gè)節(jié)點(diǎn)。

10、在長(zhǎng)度為n(nNl)的單鏈表中刪除尾節(jié)點(diǎn)的時(shí)間復(fù)雜度為

()O

A.0(1)

B.0(log2n)

C.0(n)

D.0(n2)

正確答案：C

解析：在長(zhǎng)度為n(n2l)的單鏈表中刪除尾節(jié)點(diǎn)時(shí)，需要找倒

數(shù)第2個(gè)節(jié)點(diǎn)，此時(shí)時(shí)間復(fù)雜度為0(n)。

11、關(guān)于線性表的正確說(shuō)法是()。

A.每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼元素

B.線性表中至少有一個(gè)元素

C.表中元素的排序順序必須是由小到大或由大到小

D.除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素有且僅有一個(gè)前

驅(qū)和一個(gè)后繼元素

正確答案：D

解析：線性表屬典型的線性結(jié)構(gòu)。

12、以下關(guān)于順序表的敘述中，正確的是（）。

A.順序表可以利用一維數(shù)組表示，因此順序表與一維數(shù)組在結(jié)構(gòu)上

是一致的，它們可以通用

B.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰

C.順序表和一維數(shù)組一樣，都可以進(jìn)行隨機(jī)存取

D.在順序表中每一個(gè)元素的類型不必相同

正確答案：C

解析：順序表中所有元素必須連續(xù)存放，而一維數(shù)組中所有元素

可以不連續(xù)存放，另外，一維數(shù)組只有按下標(biāo)的存、取兩個(gè)操作，

而順序表可以進(jìn)行線性表的插入、刪除等操作，所以選項(xiàng)A錯(cuò)誤。

在順序表中，邏輯上相鄰的元素在物理位置上也一定相鄰，所以選

項(xiàng)B錯(cuò)誤。順序表中每一個(gè)元素的類型必須相同，所以選項(xiàng)D錯(cuò)誤。

13、以下屬于順序表的優(yōu)點(diǎn)是（）。

A.插入元素方便

B.刪除元素方便

C.存儲(chǔ)密度大

D.以上都不對(duì)

正確答案：C

解析：順序表的存儲(chǔ)密度為1,所以其存儲(chǔ)密度大。

14、設(shè)線性表中有n個(gè)元素，以下運(yùn)算中，（）在單鏈表上實(shí)現(xiàn)要

比在順序表上實(shí)現(xiàn)效率更高。

A.刪除指定位置元素的后一個(gè)元素

B.在尾元素的后面插入一個(gè)新元素

C.順序輸出前k個(gè)元素

D.交換第i個(gè)元素和第n-i+1個(gè)元素的值（i=L2,n）

正確答案：A

解析：在順序表中插入元素和刪除元素時(shí)需要移動(dòng)較多元素，而在

單鏈表上執(zhí)行同樣的操作不需要移動(dòng)元素，只需修改相關(guān)節(jié)點(diǎn)的指

針域。

15、以下關(guān)于單鏈表的敘述中正確的是()。

I.節(jié)點(diǎn)除自身信息外還包括指