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

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

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

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

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

5、pnextpnext=sCpnext=spnext=snextDpnext=snextpnext=s（B）18對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（）Ahead==NULLBheadnext==NULLCheadnext==headDhead!=NULL（A）19.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。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三、簡答題三、簡答題1線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有n個線性表同時并存，并且在處理過

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

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