自考衝刺資料——資料結構重點章節講解
特別鳴謝：
第二章線性表
線性表是一種最簡單、最常見的資料結構。
一、本章總述
本章主要討論了線性表及它的兩種儲存實現：順序實現和鏈結實現。
線性表是一種最簡單、最常見的資料結構。線性表的邏輯結構特性是資料元素之間存在著線性關係，在計算機中表示這種關係的兩類不同的儲存結構是順序儲存結構和鏈式儲存結構。用前者表示的線性表簡稱為順序表，用後者表示的線性表簡稱為鍊錶。
二、本章重點
熟練掌握順序表和單鏈表上實現的各種基本演算法及相關的時間效能分析。
三、本章難點
使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
四、本章知識點
1、線性表的邏輯結構的基本特徵
圖2-1 線性表
線性結構是乙個資料元素的有序(次序)集
1).集合中必存在唯一的乙個「第一元素」；
2).集合中必存在唯一的乙個「最後元素」
3).除最後元素之外，均有唯一的後繼；
4).除第一元素之外，均有唯一的前驅。
2、線性表的順序儲存實現
順序表是線性表的順序儲存結構。用一組位址連續的儲存單元依次儲存線性表的元素。
順序表特點：
邏輯順序與物理順序一致
屬隨機訪問的儲存結構，即訪問每個元素所花時間相等
假設線性表中每個元素需占用c個儲存單元，計算結點儲存位址公式：
loc(ai+1)=loc(ai)+c (1)
loc(ai)=loc(a1)+(i-1)*c (2)
順序表上實現基本運算及時間複雜度分析。
1)插入演算法：
假設在第 i 個元素之前插入的概率為 pi，則在長度為n的線性表中插入乙個元素所需移動元素次數的期望值為：
若假定**性表中任何乙個位置上進行插入的概率都相等，則移動元素的期望值為：
插入演算法的平均時間複雜性為 ，平均時間複雜性量級為o(n)。
2)刪除演算法：
假設刪除第 i 個元素的概率為qi , 則在長度為n的線性表中刪除乙個元素所需移動元素次數的期望值為：
若假定**性表中任何乙個位置上進行刪除的概率都是相等的，則移動元素的期望值為：
刪除演算法的平均時間複雜性為
，平均時間複雜性量級為o(n)。
3、線性表的鏈式儲存實現
鏈結實現線性表，可以克服順序表的缺點。線性表的常見鏈式儲存結構有：單鏈表、迴圈鍊錶、雙鏈表。
1)單鏈表
用一組位址任意的儲存單元存放線性表中的資料元素。
元素(資料元素的映象)+ 指標(指示後繼元素儲存位置的) = 結點
鏈式儲存特點：
邏輯順序與物理順序有可能不一致
屬順序訪問的儲存結構，即訪問每個資料元素所花費的時間不相等
幾種運算在單鏈表上的實現，包括：建立單鏈表、查詢、插入、刪除等。
2)迴圈鍊錶
表中最後乙個結點的指標域指向頭結點，鍊錶形成乙個環。
特點：從表中任何乙個結點出發可掃瞄整個鍊錶中的所有結點。
3)雙鏈表
特點: 每個結點有兩個指標域,克服單鏈表的單向性
注意：「插入」、「刪除」操作，與單鏈表有很大不同。需要同時修改兩個方向上的指標。
4、順序表和煉表的比較
空間效能比較、時間效能比較。
順序儲存結構：
優點：儲存密度大、簡單。資料元素的位址可以通過公式計算。
缺點：插入、刪除操作效率低，儲存空間需要按最大需求事先分配，且要求一片連續的儲存空間，容易造成浪費。
鏈式儲存結構：
優點：儲存空間按需分配；插入、刪除操作效率高。
缺點：鍊錶中的結點需要儲存指標，構造本身比順序儲存結構大。
時間複雜性量級
定位運算，順序表和單鏈表,均為 o(n)
讀表元：順序表-o(1) (隨機訪問);單鏈表-o(n)
鏈入、刪除：順序表-0(n); 單鏈表-o(1) (插入、刪除方便)
五、相關考題
本章將可能有演算法題出現。
2006.01
三、解答題
28.當將兩個長度均為n的有序表a=(a1，a2，…，an)與b=(b1，b2，…，bn)(ai≠bj,1≤i,j≤n)歸併為乙個有序表c=(c1, c2,…,c2n)時，所需進行的元素比較次數最少可達n,最多可達2n-1。
(1)假設有序表c=(2，4，5，6，7，9)，試舉出兩組a與b的例子，使它們在歸併過程中進行的元素比較次數分別達到最少和最多；
(2)寫出一般情況下，使歸併所需進行的元素比較次數分別達到最少和最多時，a與b中的元素應滿足的條件。
演算法閱讀：
30.已知head為帶頭結點的單迴圈鍊錶的頭指標，鍊錶中的資料元素依次為(a1，a2,a3,a4,…,an),a為指向空的順序表的指標。閱讀以下程式段，並回答問題：
(1)寫出執行下列程式段後的順序表a中的資料元素；
(2)簡要敘述該程式段的功能。
演算法設計題：
34.在帶頭結點的迴圈鍊錶l中，結點的資料元素為整型，且按值遞增有序存放。給定兩個整數a和b，且a
2005.01演算法設計題(本題共10分)
34.假設一元多項式以迴圈鍊錶表示，鍊錶的結點結構為：
2005.10演算法閱讀題
30. 閱讀下列演算法，並回答問題：
(1)設順序表l=(3,7,11,14,20,51)，寫出執行f30(&l,15)之後的l；
(2)設順序表l=(4,7,10,14,20,51)，寫出執行f30(&l,10)之後的l；
(3)簡述演算法的功能。
以上資料由百度貼吧：
自考樂園俱樂部楊尚傑為你精心編輯
資料結構考試重點
資料結構 第一章緒論 1 資料結構的定義 按照某種邏輯關係組織起來的資料集 2 資料主要分為兩大類 數值型資料和非數值型別資料。數值型資料主要包括整數 實數和複數等 非數值型別資料報括字元 字串 文字 聲音 圖形 影象等。3 資料結構的邏輯結構是指資料元素的集合以及定義在該集合上的資料元素之間的一種...
資料結構重點整理
2幾種資料結構 資料結構定義 具有結構的資料元素的集合 邏輯結構 集合 線性結構 線性表 廣義表 堆疊和佇列 非線性結構 樹 圖 儲存結構 順序儲存結構 鏈式儲存結構 索引結構 雜湊結構等 集合和線性結構 1 1樹形結構 1 n圖形結構 n n 3 線性表順序儲存和鏈結儲存的特點 順序儲存 隨機訪問...
資料結構複習重點 全
2011 2012 1資料結構複習重點 第1章緒論 1.資料結構研究的三個方面 2.資料元素 資料項 3.邏輯結構和儲存結構的種類 4.演算法時間複雜度的計算，演算法的5個特性第2章線性表 very important 1.線性表的定義 2.線性表的邏輯結構特點 3.線性表的儲存結構種類 4.順序表...