數(shù)據(jù)結構 第2章 線性表

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

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

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

4、）8（B）63.5（C）63（D）7（A）5.鏈式存儲的存儲結構所占存儲空間：（A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針（B）只有一部分，存放結點值（C）只有一部分，存儲表示結點間關系的指針（D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)（D）6.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的3Apnext=ssnext=pnextBsnext=

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

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

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