1、全國計算機等級考試二級公共基礎知識二級公共基礎知識基本要求 n1. 掌握算法的基本概念。n2. 掌握基本數據結構及其操作。n3. 掌握基本排序和查找算法。n4. 掌握逐步求精的結構化程序設計方法。n5. 掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發的能力。n6. 掌握數據的基本知識，了解關系數據庫的設計。 2考試內容考試內容一、 基本數據結構與算法 1. 算法的基本概念；算法復雜度的概念和意義（時間復雜度算法的基本概念；算法復雜度的概念和意義（時間復雜度與空間復雜度）。與空間復雜度）。2. 數據結構的定義；數據的邏輯結構與存儲結構；數據結構數據結構的定義；數據的邏輯結構與存儲結構；

2、數據結構的圖形表示；線性結構與非線性結構的概念。的圖形表示；線性結構與非線性結構的概念。3. 線性表的定義；線性表的順序存儲結構及其插入與刪除運線性表的定義；線性表的順序存儲結構及其插入與刪除運算。算。4. 棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。棧和隊列的定義；棧和隊列的順序存儲結構及其基本運算。5. 線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。線性單鏈表、雙向鏈表與循環鏈表的結構及其基本運算。6. 樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前樹的基本概念；二叉樹的定義及其存儲結構；二叉樹的前序、中序和后序遍歷。序、中序和后序遍歷。7. 順序查找與二分法查找算法；基本

3、排序算法（交換類排序，順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。選擇類排序，插入類排序）。 3二、 程序設計基礎1. 程序設計方法與風格。2. 結構化程序設計。3. 面向對象的程序設計方法，對象，方法，屬性及繼承與多態性。 4三、 軟件工程基礎1. 軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發環境。2. 結構化分析方法，數據流圖，數據字典，軟件需求規格說明書。3. 結構化設計方法，總體設計與詳細設計。4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統測試。5. 程序的調試，靜態調試與動態調試。5四、數據

4、庫設計基礎1. 數據庫的基本概念：數據庫，數據庫管理系統，數據庫系統。2. 數據模型，實體聯系模型及E-R圖，從E-R圖導出關系數據模型。3. 關系代數運算，包括集合運算及選擇、投影、連接運算，數據庫規范化理論。4. 數據庫設計方法和步驟：需求分析、概念設計、邏輯設計和物理設計的相關策略。6考試方式1、 公共基礎的考試方式為筆試，與C語言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的筆試部分合為一張試卷。公共基礎部分占全卷的30分。2、 公共基礎知識有10道選擇題和5道填空題。 7學習方法n理解基本概念n多做練習n適當記憶一些名詞n與所學的

5、VBA程序設計知識結合起來，以增加對知識的理解能力81. 基本數據結構與算法1.1 算法1.1.1 算法(algorithm)基本概念對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。算法具有有窮性有窮性、確定性確定性、可行性可行性、輸輸入入和輸出（擁有足夠的情報）輸出（擁有足夠的情報）等個重要特性。91.1 算法的基本概念算法的基本概念n算法的定義：一個有窮的指令集，這些算法的定義：一個有窮的指令集，這些指令為解決某一特定問題規定了一個運算指令為解決某一特定問

6、題規定了一個運算序列，即方法和步驟，在計算機學科中，序列，即方法和步驟，在計算機學科中，算法就是計算機解決問題的過程或步驟。算法就是計算機解決問題的過程或步驟。n算法是解題方案的準確而完整的描述。算法是解題方案的準確而完整的描述。n算法等于程序？等于計算方法？算法等于程序？等于計算方法？10n結構化程序算法的特性特性如下。n（1）可行性算法中的操作能夠用已經實現的基本運算執行有限次來實現。n（2）確定性算法中的每一步都有確切的含義。n（3）有窮性一個算法（對任何合法的輸入）在執行有窮步后能夠結束，并且在有限的時間內完成。n（4）擁有足夠的情報當算法擁有足夠的情報，此算法才是有效的。考點考點1：

7、算法的定義：算法的定義例2.1.1問題處理方案的正確而完整的描述稱為_。2005年4月填空第5題例2.1.2算法具有4個特性，以下選項中不屬于算法特性的是（）A有窮性B簡潔性C可行性D確定性111.1.2 算法的基本要素 1、對數據對象的運算和操作n算術運算n邏輯運算n關系運算n數據傳輸2、算法的控制結構n算法中各操作之間的執行順序n描述算法的工具通常有傳統流程圖、N-S結構化流程圖、算法描述語言等n一個算法一般可以用順序、選擇、循環順序、選擇、循環三種基本機構組合而成。121.1.3 算法設計基本方法n列舉法n歸納法n遞推n遞歸（以簡潔的形式設計和描述算法）n減半遞推技術n回溯法131.2

8、算法復雜度1.2.1 時間復雜度n 依據算法算法編制的程序在計算機上運行時所消耗的時間來度量。通常有事后統計法和事前分析估算法。n 一個算法是由控制結構（順序、分支和循環）和原操作構成的，算法時間取決于兩者的綜合效果。n 算法中基本操作重復執行次數n和算法執行時間同步增長，稱作算法的時間復雜度。14n算法的時間復雜度指算法的時間耗費，算法的時間復雜度指算法的時間耗費，算法時間是由控制結構和原操作的決定算法時間是由控制結構和原操作的決定的。的。算法中基本操作重復執行的次數是算法中基本操作重復執行的次數是問題規模問題規模n的某個函數的某個函數f(n)，記作：，記作：nT(n) = O(f(n)n它

9、表示隨問題規模它表示隨問題規模n的增大，算法執的增大，算法執行時間的增長率和行時間的增長率和f(n)的增長率相同。的增長率相同。n算法的時間復雜度用來衡量算法執行算法的時間復雜度用來衡量算法執行過程中所需要的基本運算次數。過程中所需要的基本運算次數。n算法的時間復雜度是指算法所需要的計算法的時間復雜度是指算法所需要的計算工作量。算工作量。 151.2.2 算法的空間復雜度n 一般是指執行這個算法所需要的內存空間n一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的存儲空間以及某種數據結構所需要的附加存儲空間n 一個上機執行的程序除了需要存儲空間來寄存本身所用指令、常數、變量和輸

10、入數據外，也需要一些對數據進行操作的工作單元和存儲一些為實現計算所需信息的輔助空間。16n算法的空間復雜度描述算法的存儲空間需算法的空間復雜度描述算法的存儲空間需求求，運行完一個程序所需要的內存大小是問題，運行完一個程序所需要的內存大小是問題規模規模n的某個函數的某個函數g(n)，記作：，記作：nS(n) = O(g(n)n它表示隨著問題規模它表示隨著問題規模n的增大，算法運行所的增大，算法運行所需存儲空間的增長率需存儲空間的增長率S(n)與與g(n)的增長率相的增長率相同。同。n空間復雜度是指執行這個算法所需要的內存空空間復雜度是指執行這個算法所需要的內存空間。間。2007-4真題真題:17

11、例題講解n 算法的時間復雜度是指A) 執行算法程序所需要的時間 B) 算法程序的長度C) 算法執行過程中所需要的基本運算次數 D) 算法程序中的指令條數n算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報。n算法的空間復雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數 C) 算法程序所占的存儲空間 D) 執行過程中所需要的存儲空間18n在計算機中，算法是指 A) 加工方法 B)解題方案的準確而完整的描述 C) 排序方法 D)查詢方法n算法的工作量大小和實現算法所需的存儲單元多少分別稱為算法的 【1】 。191.2 數據結構n數據結構的定義n數據的邏輯結構和存儲結構n數據結構的

12、圖形表示n線性結構與非線性結構201.2.1 數據結構研究的主要內容數據結構研究的主要內容當今計算機應用的特點：n所處理的數據量大且具有一定的關系；n對其操作不再是單純的數值計算，而更多地是需要對其進行組織、管理和檢索。應用舉例1學籍檔案管理假設一個學籍檔案管理系統應包含如下表1-1所示的學生信息。21 學 生 基本 情 況學 號姓 名性 別出 生 年 月.99070101李 軍男80 12.99070102王 顏 霞女81 2.99070103孫 濤男80 9.99070104單 曉 宏男81 3.22n特點： l每個學生的信息占據一行，所有學生的信息按學號順序依次排列構成一張表格； l表中

13、每個學生的信息依據學號的大小存在著一種前后關系，這就是我們所說的線性結構； l對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。 應用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。233121321231232123121321124n特點： l在求解過程中，所處理的數據之間具有層次關系，這是我們所說的樹形結構； l對它的操作有：建立樹形結構，輸出最低層結點內容等等。 應用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先

14、導課程。比如，計算機專業課程的開設情況如下表1-2所示：25 計 算 機 專 業 學 生 的 必 修 課 程課 程 編 號課 程 名 稱需 要 的 先 導 課 程編 號C 1程 序 設 計 基 礎無C 2離 散 數 學C 1C 3數 據 結 構C 1 ， C 2C 4匯 編 語 言C 1C 5算 法 分 析 與 設 計C 3 ， C 4C 6計 算 機 組 成 原 理C 1 1C 7編 譯 原 理C 5 ， C 3C 8操 作 系 統C 3 ， C 6C 9高 等 數 學無C 1 0線 性 代 數C 9C 1 1普 通 物 理C 9C 1 2數 值 分 析C 9 ， C 1 0 ， C 126

15、n課程先后關系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c827n特點 l 課程之間的先后關系用圖結構描述； l 通過實施創建圖結構，按要求將圖結構中的頂點進行線性排序。n結論：結論：數據結構主要研究以下三個方面的問題：數據結構主要研究以下三個方面的問題：n數據的邏輯結構n數據的存儲結構n對各種數據結構進行的運算 28n數據的邏輯結構：數據的邏輯結構：用來描述數據元素之間用來描述數據元素之間的邏輯關系。的邏輯關系。n數據的存儲結構：數據的存儲結構：用來描述數據元素及數用來描述數據元素及數據元素之間的關系在存儲器中的存儲形式。據元素之間的關系在存儲器中的存儲形式。n*重點提

16、示：重點提示： 同一邏輯結構的數據可以采用不同一邏輯結構的數據可以采用不同存儲結構，但影響數據處理效率。同存儲結構，但影響數據處理效率。n數據的運算：數據的運算：即對數據元素施加的操作。即對數據元素施加的操作。n數據結構的圖形表示：數據結構的圖形表示：用圖形來直觀地表用圖形來直觀地表示數據及其之間的關系。示數據及其之間的關系。 數據結構數據結構包括邏輯結構、存儲結構和數據的包括邏輯結構、存儲結構和數據的運算運算3個方面的內容。個方面的內容。29數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。1.2.2 基本概念和術語30能輸入到計算

17、機中能輸入到計算機中并能被計算機程序處理的并能被計算機程序處理的符號的集合。符號的集合。整數整數(1,2)(1,2)、實數、實數(1.1,1.2)(1.1,1.2)字符串字符串( (Beijing)Beijing)、圖形、聲音。圖形、聲音。1.2.2 基本概念和術語數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。311.2.2 基本概念和術語計算機管理圖書問題計算機管理圖書問題 在圖書館里有各種卡片：有按書名編排的、在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排有按作者編排的、有按分類編排如何將查詢圖書的這些信息

18、存入計算機中如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節省空間既要考慮查詢時間短，又要考慮節省空間數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。32最簡單的辦法之一是建立一張表，最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如每一本書的信息在表中占一行，如 1.2.2 基本概念和術語數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。33如何將如何將0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9這這1010個數

19、存放在個數存放在計算機中能最快地達到你所需要的目的？計算機中能最快地達到你所需要的目的？ 目的不同，目的不同，最佳最佳的存儲方方法就不同的存儲方方法就不同。 從大到小排列：從大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0輸出偶數：輸出偶數：0,2,4,6,8,1,3,5,7,9 0,2,4,6,8,1,3,5,7,9 數據元素在數據元素在計算機中的表示計算機中的表示數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。1.2.2 基本概念和術語34對數據結構中的節點進行對數據結構中的節點進行操作處

20、理操作處理(插入、刪除、修改、查找、排序插入、刪除、修改、查找、排序)1.2.2 基本概念和術語數據結構是一門研究數據結構是一門研究數據數據組織組織、存儲存儲和和運算運算的一般方法的學科。的一般方法的學科。35數據元素數據元素( (Data Element)Data Element) 數據元素是數據的基本單位，即數據數據元素是數據的基本單位，即數據集合中的個體。集合中的個體。 有時一個數據元數可由若干有時一個數據元數可由若干數據項數據項( (Data Item)Data Item)組成。數據項是數據的最小組成。數據項是數據的最小單位。單位。數據元素亦稱數據元素亦稱節點節點或或記錄記錄。36數據

21、結構可描述為數據結構可描述為Group=（D，R）有限個數據元素的集合有限個數據元素的集合有限個節點間關系的集合有限個節點間關系的集合371數據的邏輯結構2、數據的存儲結構3、數據的運算：檢索、排序、插入、刪除、修改等。A線性結構B非線性結構A順序存儲B鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面數據結構可描述為Group=（D，R）38線性結構線性結構A,B,C,，X,Y,Z學生成績表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號線性表線性表結點間是以線性關系聯結結點間是以線性關系聯結39樹形結構樹形結構全校學生檔案管理的組織方式全校學生檔案管理

22、的組織方式計算機程序管理系統也是典型的樹形結構計算機程序管理系統也是典型的樹形結構40ABCDEFGH樹形結構結點間具有分層次的連接關系HBCDEFGA411數據的邏輯結構2、數據的存儲結構3、數據的運算：檢索、排序、插入、刪除、修改等。A線性結構B非線性結構A順序存儲B鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面(亦稱物理結構亦稱物理結構)421423D=1,2,3,4R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)213D=1,2,3R=(1,2),(2,3),(3,2),(1,3)圖形結構圖形結構節點間的連結是任意的節點間的連結是任意的431數據的邏輯結構

23、2、數據的存儲結構3、數據的運算：檢索、排序、插入、刪除、修改等。A線性結構B非線性結構A順序存儲B鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面(亦稱物理結構亦稱物理結構)44元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內容Loc(a)=Lo+（i-1)*m順序存儲每個元素所占用每個元素所占用的存儲單元個數的存儲單元個數45元素n.元素i.元素2元素1存儲內容順序存儲結構常用于線性順序存儲結構常用于線性數據結構，將邏輯上相鄰數據結構，將邏輯上相鄰的數據元素存儲在物理上的數據元素存儲在物理上相鄰的存儲單元里。相鄰的存儲單元里。順序存儲結構的

24、三個弱點：順序存儲結構的三個弱點：1.作插入或刪除操作時，需移動大量元數。作插入或刪除操作時，需移動大量元數。2.長度變化較大時，需按最大空間分配。長度變化較大時，需按最大空間分配。3.表的容量難以擴充。表的容量難以擴充。461數據的邏輯結構2、數據的存儲結構3、數據的運算：檢索、排序、插入、刪除、修改等。A線性結構B非線性結構A順序存儲B鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面(亦稱物理結構亦稱物理結構)471536元素21400元素11346元素3 元素41345h鏈式存儲每個節點都由兩部分組成：每個節點都由兩部分組成：數據域數據域和和指針域指針域。數據域數據域存放元素本身的數

25、據，存放元素本身的數據，指針域指針域存放指針。存放指針。數據元素之間邏輯上的聯系由指針來體現數據元素之間邏輯上的聯系由指針來體現。481536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲內容存儲地址鏈式存儲1345491536元素21400元素11346元素3 元素41345h鏈式存儲1.比順序存儲結構的存儲密度小比順序存儲結構的存儲密度小(每個節點都由數據域和指針愈組成每個節點都由數據域和指針愈組成)。2.邏輯上相鄰的節點物理上不必相鄰。邏輯上相鄰的

26、節點物理上不必相鄰。3.插入、刪除靈活插入、刪除靈活(不必移動節點，只要改變節點中的指針不必移動節點，只要改變節點中的指針)。鏈接存儲結構特點：鏈接存儲結構特點：501數據的邏輯結構2、數據的存儲結構3、數據的運算：檢索、排序、插入、刪除、修改等。A線性結構B非線性結構A順序存儲B鏈式存儲線性表棧隊樹形結構圖形結構數據結構的三個方面(亦稱物理結構亦稱物理結構)51 線性結構和非線性結構n如果一個非空的數據結構滿足下列兩個條件：n有且只有一個根結點；n每一個結點最多有一個前件，也最多有一個后件則稱該數據結構為線性結構（線性表）。n如果一個數據結構不是線性結構，則稱之為非線性結構。52例題講解n數

27、據結構分為邏輯結構與存儲結構，線性鏈表屬于 【1】 。P327 n數據結構中，與所使用的計算機無關的是數據的 A) 存儲結構B) 物理結構 C) 邏輯結構D) 物理和存儲結構 n數據的邏輯結構有線性結構和 【1】 兩大類。 53n順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【2】 的存儲單元中。 P317n數據處理的最小單位是P309 A) 數據 B) 數據元素 C) 數據項 D)數據結構n數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及 A) 數據的存儲結構 B)計算方法 C)數據映象 D) 邏輯存儲54n根據數據結構中各數據元素之間前后件關系的復雜程

28、度，一般將數據結構分成 A) 動態結構和靜態結構 B) 緊湊結構和非緊湊結構 C) 線性結構和非線性結構 D) 內部結構和外部結構 n數據結構包括數據的邏輯結構、數據的 【2】 以及對數據的操作運算。n數據的基本單位是 【5】 。55n下列敘述中，錯誤的是 A) 數據的存儲結構與數據處理的效率密切相關 B) 數據的存儲結構與數據處理的效率無關 C) 數據的存儲結構在計算機中所占的空間不一定是連續的 D) 一種數據的邏輯結構可以有多種存儲結構n數據的存儲結構是指P314A）數據所占的存儲空間B）數據的邏輯結構在計算機中的表示C）數據在計算機中的順序存儲方式D）存儲在外存中的數據 561.3 線性

29、表及其順序存儲結構1.3.1 線性表的定義 線性表是線性表是n個元素的有限序列，它們之間的個元素的有限序列，它們之間的關系可以排成一個線性序列：關系可以排成一個線性序列： a1，a2， ，ai， ，an其中其中n稱作表的長度，當稱作表的長度，當n=0時，稱作空表。時，稱作空表。57 線性表的特點：線性表的特點：1.線性表中所有元素的性質相同。線性表中所有元素的性質相同。2.除第一個和最后一個數據元素之外，其它數據元除第一個和最后一個數據元素之外，其它數據元素有且僅有一個前驅和一個后繼。第一個數據元素有且僅有一個前驅和一個后繼。第一個數據元素無前驅，最后一個數據元素無后繼。素無前驅，最后一個數據

30、元素無后繼。3.數據元素在表中的位置只取決于它自身的序號。數據元素在表中的位置只取決于它自身的序號。n在線性表上常用的運算有：在線性表上常用的運算有：初始化、求長度、取元素、修改、初始化、求長度、取元素、修改、前插、刪除、檢索、排序。前插、刪除、檢索、排序。581.3.2 線性表的順序存儲結構及其插入與刪除操作n特點：特點： 1、線性表中數據元素類型一致，只有數、線性表中數據元素類型一致，只有數據域，存儲空間利用率高。據域，存儲空間利用率高。 2、所有元素所占的存儲空間是連續的、所有元素所占的存儲空間是連續的 3、各數據元素在存儲空間中是按邏輯順、各數據元素在存儲空間中是按邏輯順序依次存放的序

31、依次存放的 2. 做插入、刪除時需移動大量元素。做插入、刪除時需移動大量元素。 3. 空間估計不明時，按最大空間分配。空間估計不明時，按最大空間分配。59元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bb+mb+(i-1)*mb+(maxlen-1)*m存儲地址存儲地址內存狀態內存狀態Loc(元素元素i)=b+（i-1)*m順序存儲結構示意圖順序存儲結構示意圖(順序表順序表)：首地址首地址起始地址起始地址基地址基地址每個元素所占用每個元素所占用的存儲單元個數的存儲單元個數60元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1.01i線性表

32、的順序存儲結構線性表的順序存儲結構可用可用VB語言中的一維數組來描語言中的一維數組來描述述.DimVMAsinteger;/*V是數組的名字，是數組的名字，M是數組大小，假是數組大小，假設數組中的元素是整型類型設數組中的元素是整型類型*/第第i個元素的個元素的ai存儲地址：存儲地址：Loc(ai)=Loc(a1)+(i-1)*mVVViViVm-1Vm-161.a2a1an.ai+1ai01i-1in-11-1插入運算插入運算ai-1.a2a1alength ai+1aix ai-1. a2 a1 ai ai+1 alengthalength ai+1 aix62OptionBase0Func

33、tionintinsq(iAsInteger，xAsInteger,V()AsInteger,MAsInteger,）/*順序表順序表插入函數插入函數*/*在線性表在線性表V中第中第i個元素之前插入個元素之前插入x，i的合法值為的合法值為1 i n*/DimnAsInteger，jAsIntegern=UBound(V)/*獲取表長獲取表長*/Ifn=MThen/*M是存儲空間的大小是存儲空間的大小*/printoverflown“ExitFunctionEndIfIf(in+1)Thenprintiiserror“ExitFunction/*i值不合法值不合法*/Elseforj=nToiS

34、tep-1V(j)=V(j-1)/*插入位置后的元素依次右移插入位置后的元素依次右移*/NextJV(j)=x/*插入插入x*/EndIfEndFunction注意數組元注意數組元素從素從0 0開始開始631-2刪除運算刪除運算OptionBaseoFunctiondelsq(iAsInteger,V()AsInteger）/*在線性表在線性表V中刪除第中刪除第i個元素個元素*/DimnAsInteger,jAsIntegern=UBound(V)IfinThenprintThiselementisnotinthelist“ExitFunctionelseForj=ITonV(j-1)=V(j

35、)/*被刪除元素之后的元素左移被刪除元素之后的元素左移*/NextJEndifEndFunction64 插入算法的分析 假設線性表中含有n個數據元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數為：1n1iis2n1)i(n1n1E65 刪除算法的分析 在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數為： 分析結論 順序存儲結構表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數據元素。當線性表的數據元素量較大，并且經常要對其做插入或刪除操作時，這一點需要值得考慮。n1idl21ni)(nn1E66例題講解n順序存儲方法是把

36、邏輯上相鄰的結點存儲在物理位置 【2】 的存儲單元中。PPT:P4667n線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件P31768n根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分成P316 A) 動態結構和靜態結構 B) 緊湊結構和非緊湊結構 C) 線性結構和非線性結構 D) 內部結構和外部結構69n下列敘述中，錯誤的是 A) 數據的存儲結構與數據處

37、理的效率密切相關 B) 數據的存儲結構與數據處理的效率無關 C) 數據的存儲結構在計算機中所占的空間不一定是連續的 D) 一種數據的邏輯結構可以有多種存儲結構 701.4 棧和隊列1.4.1 棧和隊列的定義 棧和隊列是兩種特殊的線性表，它們是是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也運算時要受到某些限制的線性表，故也稱為稱為限定性的數據結構。711.4.1.11.4.1.1棧的定義棧的定義棧棧：限定只能在表的一端進行插入和刪除的特殊的線性表限定只能在表的一端進行插入和刪除的特殊的線性表, ,此種結構稱為此種結構稱為后進先出后進先出（Last_In_First_Out，簡稱，簡

38、稱LIFO）或先進后出（）或先進后出（FILO）表表設棧設棧s=s=（a a1 1，a a2 2，. . . ,a. . . ,ai i，. . . . . . ，a an n），其中其中a a1 1是棧底元素，是棧底元素， a an n是棧頂元素。是棧頂元素。棧頂（棧頂（top)top)：允許插入和刪除的一端；允許插入和刪除的一端； 約定約定toptop始終指向新數據元素將存放的位置。始終指向新數據元素將存放的位置。棧底（棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。 a1 a2 . an進棧進棧出棧出棧棧頂棧頂棧底棧底72隊列的主要運算隊列的主要運算（1）設置一個空隊列；）設置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；）讀取隊頭元素；1.4.1.2隊列的定義隊列的定義定義：定義：一種特殊的線性結構，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。此種結構稱為先進先出（先進先出（FIFO）表表。a1,a2,a3,a4,an-1,an隊列示