一、填空題
01、當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用順序儲存結構。
02、線性表l=（a1,a2,…,an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是(n-1)/2。
03、在有n個元素的順序表中插入乙個新元素，需要平均移動n/2元素，具體移動的元素個數與表長和該元素在表中的位置有關。
04、線性表中結點的集合是有限的，結點間的關係是一對一的。
05、向乙個長度為n的順序表的第i個元素(1≤i≤n+1)之前插入乙個元素時，需向後移動n-i+1個元素。
06、向乙個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動n-i個元素。
07、在順序表中訪問任意一結點的時間複雜度均為o(1)，因此，順序表也稱為隨機訪問的資料結構。
08、順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置未必相鄰。
09、在單鏈表中，除了首結點外，任一結點的儲存位置由其直接前驅結點的鏈域值指示。
10、在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o(n)。
11、設單鏈表的結點結構為(data,next)，next 為指標域，已知指標px指向單鏈表中data域為x的結點，指標py 指向data域為y的新結點，若將結點y插入結點x之後，則需要執行以下語句：py->next=px->next; px->next=py;
12、在單鏈表中設定頭結點的作用是使插入和刪除等操作統一，在第乙個元素之前插入元素和刪除第乙個結點不必另作判斷。
13、對於乙個具有n 個結點的單鏈表，在已知的結點*p後插入乙個新結點的時間複雜度為o(1)，在給定值為x 的結點後插入乙個新結點的時間複雜度為o(n)。
14、在雙向迴圈鍊錶中，向p所指的結點之後插入指標f所指的結點，其操作是：f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
15、在雙向鍊錶結構中，若要求在p指標所指的結點之前插入指標為s所指的結點，則需執行下列語句：s->next=p; s->prior= p->prior; p->prior=s; s->prior->next =s;
16、鏈結儲存的特點是利用指標來表示資料元素之間的邏輯關係。
17、對於雙向鍊錶，在兩個結點之間插入乙個新結點需修改的指標共4個，單鏈表為2個。
18、迴圈單鏈表的最大優點是從任一結點出發都可訪問到鍊錶中每乙個元素。
19、已知指標p指向單鏈表l中的某結點，則刪除其後繼結點的語句是 u=p->next; p->next=u->next; free(u);
20、帶頭結點的雙迴圈鍊錶l中只有乙個元素結點的條件是 l->next->next==l
21、在單鏈表l 中，指標p 所指結點有後繼結點的條件是 p->next!=null
22、帶頭結點的雙迴圈鍊錶l為空表的條件是 l->next==l && l->prior==l
23、在單鏈表p結點之後插入s結點的操作是 s->next=p->next; p->next=s;
二、判斷題
×01、鍊錶的每個結點中都恰好包含乙個指標。
×02、鍊錶的物理儲存結構具有同煉表一樣的順序。
×03、鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。
×04、線性表的每個結點只能是乙個簡單型別，而鍊錶的每個結點可以是乙個複雜型別。
×05、順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
×06、順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
×07、線性表在物理儲存空間中也一定是連續的。
×08、線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
×09、順序儲存方式只能用於儲存線性結構。
×10、線性表的邏輯順序與儲存順序總是一致的。
×11、鍊錶中的頭結點僅起到標識的作用。
√12、順序儲存結構的主要缺點是不利於插入或刪除操作。
√13、線性表採用鍊錶儲存時，結點和結點內部的儲存空間可以是不連續的。
×14、對任何資料結構鏈式儲存結構一定優於順序儲存結構。
×15、集合與線性表的區別在於是否按關鍵字排序。
×16、所謂靜態鍊錶就是一直不發生變化的鍊錶。
×17、線性表的特點是每個元素都有乙個前驅和乙個後繼。
×18、取線性表的第i個元素的時間同i的大小有關。
×19、迴圈鍊錶不是線性表。
√20、鍊錶是採用鏈式儲存結構的線性表,進行插入、刪除操作時，在鍊錶中比在順序儲存結構中效率高。
三、單項選擇題
c01、資料在計算機儲存器內表示時，實體地址與邏輯位址相同並且是連續的，稱之為___。
a) 儲存結構 b) 邏輯結構
c) 順序儲存結構 d) 鏈式儲存結構
b02、乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是 。
a) 110 b) 108 c) 100 d) 120
a03、在n個結點的順序表中，演算法的時間複雜度是o(1)的操作是___。
a) 訪問第i個結點(1≤i≤n)和求第i個結點的直接前驅(2≤i≤n)
b) 在第i個結點後插入乙個新結點(1≤i≤n)
c) 刪除第i個結點(1≤i≤n)
d) 將n個結點從小到大排序
b04、向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動 _ 個元素。
a) 8 b) 63.5 c) 63 d) 7
a05、鏈式儲存的儲存結構所佔儲存空間___。
a) 分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指標
b) 只有一部分，存放結點值
c) 只有一部分，儲存表示結點間關係的指標
d) 分兩部分，一部分存放結點值，另一部分存放結點所佔單元數
a06、下述___是順序儲存結構的優點。
a) 儲存密度大 b) 插入運算方便
c) 刪除運算方便 d)可方便地用於各種邏輯結構的儲存表示
d07、線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址___。
a) 必須是連續的 b) 部分位址必須是連續的
c) 一定是不連續的 d) 連續或不連續都可以
b08、線性表l在情況下適用於使用鏈式結構實現。
a) 需經常修改l中的結點值
b) 需不斷對l進行刪除插入
c) l中含有大量的結點
d) l中結點結構複雜
c09、單鏈表的儲存密度___。
a) 大於1 b) 等於1 c) 小於1 d) 不能確定
d10、若某鍊錶中最常用的操作是在最後乙個結點之後插入乙個結點和刪除最後乙個結點，則採用___儲存方式最節省運算時間。
a) 單向鍊錶 b) 雙向鍊錶
c) 單向迴圈鍊錶 d) 帶頭結點的雙向迴圈鍊錶
d11、若線性表最常用的操作是訪問第i個元素及其前趨的值，則採用___儲存方式最節省時間。
a) 單向鍊錶 b) 雙向鍊錶
c) 單向迴圈鍊錶 d) 順序表
a12、鍊錶不具有的特點是___。
a) 可隨機訪問任一元素
b) 插入刪除操作不需要移動元素
c) 不必事先估算儲存空間
d) 所需空間與線性表長度成正比
b13、在單向鍊錶的指標p所指結點後插入結點*s(*p不是尾結點)，則應執行___操作。
a) s->next=p; p->next=s;
b) s-next=p->next; p->next=s;
c) s-next=p->next; p=s;
d) p->next=s; s->next=p;
c14、非空的迴圈單向鍊錶first的尾結點(由p指向)滿足___。
a) p->next==null b) p==null
c) p->next==first d) p=first
c15、下列關於線性表的敘述中，不正確的是___。
a) 線性表是n個結點的有窮序列
b) 線性表可以為空表
c) 線性表的每乙個結點有且僅有乙個前趨和乙個後繼
d) 線性表結點間的邏輯關係是1:1的聯絡
a16、在雙向鍊錶儲存結構中刪除p所指的結點時，需要按___修改指標的鏈結。
a) p->prior->next=p->next; p->next->prior=p->prior;
b) p->prior=p->prior->next; p->prior->prior->next=p;
c) p->prior->prior->next=p; p->prior=p->prior->prior;
d) p->next->next->prior=p; p->next=p->next->next;
a17、在單迴圈鍊錶中指標p指向結點a，若要刪除a之後的結點(存在)，則其中指標的鏈結操作為___。
a) p->next=p->next->next b) p=p->next
c) p=p->next->next d) next=p
b18、帶頭結點的單鏈表head為空的判定條件是___。
a) head=null b) head->next==null
c) head->next=head d) head!=null
d19、從乙個具有n個結點的單鏈表中查詢其值等於x的結點時，在查詢成功的情況下，需平均比較___個結點。
a) n b) n/2 c) (n-1)/2 d) (n+1)/2
b20、在乙個具有n個結點的有序單鏈表中插入乙個新結點，並仍然有序的時間複雜度為___。
a) o(1) b) o(n) c) o() d) o()
資料結構第2章習題答案
一 填空 1.嚴題集2.2 在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。2.線性表中結點的集合是有限的，結點間的關係是一對一的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動 n i 1 個元素。4....
資料結構第2章
第2章 線性表 1.理解線性表的定義和邏輯結構特性 填空題 1 線性表中結點的集合是有限的，結點間的關係是一對一的。2 線性表的儲存方式分為順序儲存和鏈式儲存 判斷題 1 線性表的每個結點只能是乙個簡單型別，而鍊錶每個結點可以是乙個複雜型別。錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序...
資料結構第45章答案
第4 5章串和陣列答案 一 填空題 每空1分，共20分 1.不包含任何字元 長度為0 的串稱為空串 由乙個或多個空格 僅由空格符 組成的串稱為空白串。對應嚴題集4.1 簡答題 簡述空串和空格串的區別 2.設s a document mary.doc 則strlen s 20的字元定位的位置為 3 4...