數(shù)據(jù)結(jié)構(gòu) 第2章 線性表

1、1第2章線性表線性表一、判斷正誤一、判斷正誤（F）1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（F）2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。（F）3.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。（F）4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（F）5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（F）6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算

2、效率高。（F）7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。（T）8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（F）9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（F）10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。二、單項(xiàng)選擇題二、單項(xiàng)選擇題（C）1數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）順序存儲(chǔ)結(jié)構(gòu)（D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（B）2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是

3、100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是（A）110（B）108（C）100（D）120（A）3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：（A）訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）（B）在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）（C）刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）（D）將n個(gè)結(jié)點(diǎn)從小到大排序（B）4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)個(gè)元素（A

4、）8（B）63.5（C）63（D）7（A）5.鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：（A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針（B）只有一部分，存放結(jié)點(diǎn)值（C）只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針（D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（D）6.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的3Apnext=ssnext=pnextBsnext=

5、pnextpnext=sCpnext=spnext=snextDpnext=snextpnext=s（B）18對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）Ahead==NULLBheadnext==NULLCheadnext==headDhead!=NULL（A）19.在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。A(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llin

6、k:=p^.llinkBp^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=pC(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlinkDp^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink三、簡(jiǎn)答題三、簡(jiǎn)答題1線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有n個(gè)線性表同時(shí)并存，并且在處理過

7、程中各表的長度會(huì)動(dòng)態(tài)變化長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地總數(shù)也會(huì)自動(dòng)地改變改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？答：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)殚L度動(dòng)態(tài)變化是因?yàn)橐M(jìn)行插入和刪除操作，而進(jìn)行這些操作，鏈?zhǔn)浇Y(jié)構(gòu)不需要移動(dòng)數(shù)據(jù)元素，效率較高。所以選用鏈?zhǔn)浇Y(jié)構(gòu)。（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？答：順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)可利用起始

8、地址和偏移量在較短時(shí)間內(nèi)完成存取，效率較高。所以選用順序存儲(chǔ)結(jié)構(gòu)。2.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：①對(duì)數(shù)據(jù)進(jìn)行插入、刪除操作時(shí)，可直接通過修改指針完成前驅(qū)和后繼的處理。②表頭指針非空，不需要再判斷是否為空表。四、四、線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L=23，17，47，05，31，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，