數(shù)據(jù)結(jié)構(gòu)作業(yè)：第2章 線性表作業(yè)題目

第2章線性表

-選擇題

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

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

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

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

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

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

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

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

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

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

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

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

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

鏈表

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

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

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

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

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

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

A.線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比

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

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

8.線性表的表元存儲方式有（順序）和鏈接兩種。試指出下列各表中使用的是何種存儲方式:

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

方式…

表元編數(shù)表元間聯(lián)

貨號

號量系

1618-402

220523

3103154

4501205

5781176

6901240

表1:頭結(jié)點指向1

表元編數(shù)表元間聯(lián)

貨號

量系

1618-405

220521

3103154

4501202

5781176

6901243

表2：頭結(jié)點指向1

表元編數(shù)表元間聯(lián)

貨號

號量系

1618-405

220521

3103156

4501200

5781174

6901242

表3：頭結(jié)點指向3

表元間聯(lián)

表元編數(shù)

貨號系

號量

12

1618-4052

2205210

31031546

45012003

57811761

69012435

表4：頭結(jié)點指向4

供選擇的答案：

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

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

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

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

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

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

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

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

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

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

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

二、判斷

1.順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。（）

2.線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（）

3.順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（）

4,對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（）

5.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）

6.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（）

7.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。（）

8.取線性表的第i個元素的時間同i的大小有關(guān).（）

9.循環(huán)鏈表不是線性表.（）

10.線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。（）

11.線性表就是順序存儲的表。（）

12.為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（）

13.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）

14.鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)

構(gòu)中效率高。（）

三、填空

1.當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取

線性表中的元素時，應(yīng)采用存儲結(jié)構(gòu)。

2.線性表L=（al,a2,...,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一

個元素平均需要移動元素的個數(shù)是O

3.在一個長度為n的順序表中第i個元素（l<=i<=n）之前插入一個元素時，需向后移

動個元素。

5.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為

，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為。

6.鏈接存儲的特點是利用來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

7.順序存儲結(jié)構(gòu)是通過表示元素之間的關(guān)系的;鏈式存儲結(jié)構(gòu)是通過

表示元素之間的關(guān)系的。

8.對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共個，單鏈表為

個。

9,循環(huán)單鏈表的最大優(yōu)點是：