全國計算機等級考試二級公共基礎知識課件版.ppt

2003.11.,全國計算機等級考試 二級公共基礎知識 (2),2004.2,.程序設計基本概念,1.1 計算機工作原理,通過工作原理了解，熟悉計算機內部執(zhí)行功能的基本意義。為理解程序打下基礎，特別理解計算機是機器。,1.2 程序概念,什么是程序？ 指令的集合。（解釋指令） 通過硬件控制系統(tǒng)自動完成某一功能。 通過一系列代碼實現(xiàn)。,1.3 程序怎樣執(zhí)行？怎樣編寫？, 計算機本身僅能識別二進制代碼“0”、“1”。 編程最直接、最低級的就是機器語言。 為解決機器語言難理解、記憶等問題。出現(xiàn)符號語言。 為使編程接近自然語言，出現(xiàn)高級語言。如C、PASCAL、FORTRAN, 為配合高級語言編程，出現(xiàn)了開發(fā)工具，提高效率、減輕勞動量。如VB、VC、PB、Dephi、VFP等。因此VFP不是編程語言。 不管什么形式編寫代碼，最終都應將代碼翻譯成機器語言，這就是編譯程序的工作。不同的語言有不同的編譯器。 程序控制是一種邏輯控制。因此，嚴謹?shù)倪壿嬎季S是一個程序員必備的基本素質。, 用程序實現(xiàn)某一功能。有許多方法。具體用哪種完全取決于程序員個人的思維方式。因此，程序是腦力勞動的結晶，從某種意義上，編程又是一門藝術。 程序的特殊性決定了程序的復雜性，且與實現(xiàn)功能的復雜性密切相關成正比。因此為使復雜的、智力的編程工作規(guī)范化、科學化，便出現(xiàn)了各種編程設計方法。如結構化編程方法、面向對象的程序設計方法等。, 不管用什么方法編程，不管編程者智力程度如何，不管采用什么樣的編程語言和方法，程序最終完成的功能穩(wěn)定、可靠、實用、易維護和安全等是程序的最終目標，也是程序員的追求。 程序設計是一個復雜艱巨的過程。編寫代碼僅是程序設計的一部分。必須先有思想，再有方法，然后才是編寫代碼，且要經(jīng)過許多反復，不可急功近利。,1.4 程序設計語言或工具, 程序設計語言指的是用來編寫程序的語言。 人與計算機交流要使用語言，以便讓計算機工作，計算機也通過語言把結果告訴用計算機的人“人機對話”。 人與計算機交流的語言非平常人與人之間交流的語言，是專門的語言程序設計語言。, 程序設計語言是計算機系統(tǒng)軟件的重要組成部分。 執(zhí)行程序設計的語言有很多，可分高級語言和低級語言，區(qū)別在于接近自然語言的程度 高級語言一般與具體的計算機硬件無關，比較接近人類自然語言的語法習慣及數(shù)學表達形式。 用高級語言編寫的源程序不能被機器直接執(zhí)行，需通過編譯成解釋程序的翻譯才可被機器執(zhí)行（機器語言）。,2. 基本數(shù)據(jù)結構與算法,2.1 算法,2.1.1 算法(algorithm)基本概念 對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序將在有限的次數(shù)下終止。 算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報）等個重要特性。,2.1.2 算法的基本要素 1、對數(shù)據(jù)對象的運算和操作 算術運算 邏輯運算 關系運算 數(shù)據(jù)傳輸 2、算法的控制結構 算法中各操作之間的執(zhí)行順序 描述算法的工具通常有傳統(tǒng)流程圖、N-S結構化流程圖、算法描述語言等 一個算法一般可以用順序、選擇、循環(huán)三種基本機構組合而成。,2.1.3 算法設計基本方法 列舉法 歸納法 遞推 遞歸（以簡潔的形式設計和描述算法） 減半遞推技術 回溯法,2.2 算法復雜度,2.2.1 時間復雜度 依據(jù)算法算法編制的程序在計算機上運行時所消耗的時間來度量。通常有事后統(tǒng)計法和事前分析估算法。 一個算法是由控制結構（順序、分支和循環(huán)）和原操作構成的，算法時間取決于兩者的綜合效果。 算法中基本操作重復執(zhí)行次數(shù)n和算法執(zhí)行時間同步增長，稱作算法的時間復雜度。,2.2.2 算法的空間復雜度 一般是指執(zhí)行這個算法所需要的內存空間 一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結構所需要的附加存儲空間 一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。,例題講解,算法的時間復雜度是指 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數(shù) D) 算法程序中的指令條數(shù) 算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報。 算法的空間復雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間 在計算機中，算法是指 A) 加工方法 B) 解題方案的準確而完整的描述 C) 排序方法 D) 查詢方法,算法分析的目的是 A) 找出數(shù)據(jù)結構的合理性 B) 找出算法中輸入和輸出之間的關系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進 算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的 【1】 。,2.2 數(shù)據(jù)結構,數(shù)據(jù)結構的定義 數(shù)據(jù)的邏輯結構和存儲結構 數(shù)據(jù)結構的圖形表示 線性結構與非線性結構,2.2.1 數(shù)據(jù)結構研究的主要內容,當今計算機應用的特點： 所處理的數(shù)據(jù)量大且具有一定的關系； 對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。 應用舉例1學籍檔案管理 假設一個學籍檔案管理系統(tǒng)應包含如下表1-1所示的學生信息。,特點： l 每個學生的信息占據(jù)一行，所有學生的信息按學號順序依次排列構成一張表格； l 表中每個學生的信息依據(jù)學號的大小存在著一種前后關系，這就是我們所說的線性結構； l 對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。 應用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。,圖 1-1 3個對象的全排列過程,特點： l 在求解過程中，所處理的數(shù)據(jù)之間具有層次關系，這是我們所說的樹形結構； l 對它的操作有：建立樹形結構，輸出最低層結點內容等等。 應用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先導課程。比如，計算機專業(yè)課程的開設情況如下表1-2所示：,課程先后關系的圖形描形式：,圖 1-2 計算機專業(yè)必修課程開設先后關系,特點 l 課程之間的先后關系用圖結構描述； l 通過實施創(chuàng)建圖結構，按要求將圖結構中的頂點進行線性排序。 結論： 數(shù)據(jù)結構主要研究以下三個方面的問題： 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 對各種數(shù)據(jù)結構進行的運算,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,2.2.2 基本概念和術語,能輸入到計算機中 并能被計算機程序處理的 符號的集合。,整數(shù)(1,2)、實數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,2.2.2 基本概念和術語,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,2.2.2 基本概念和術語,計算機管理圖書問題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的、有按分類編排 如何將查詢圖書的這些信息存入計算機中 既要考慮查詢時間短，又要考慮節(jié)省空間,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,最簡單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,2.2.2 基本概念和術語,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在 計算機中能最快地達到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計算機中的表示,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,2.2.2 基本概念和術語,對數(shù)據(jù)結構中的節(jié)點進行 操作處理 (插入、刪除、修改、查找、排序),2.2.2 基本概念和術語,數(shù)據(jù)結構是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。,數(shù)據(jù)元素(Data Element),數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱節(jié)點或記錄。,數(shù)據(jù)結構可描述為 Group=（D，R）,有限個數(shù)據(jù)元素的集合,有限個節(jié)點間關系的集合,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,數(shù)據(jù)結構可描述為 Group=（D，R）,線性結構,A , B , C , ，X ,Y , Z,學 生 成 績 表,線性表結點間是以線性關系聯(lián)結,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,數(shù)據(jù)結構可描述為 Group=（D，R）,樹形結構,全校學生檔案管理的組織方式,計算機程序管理系統(tǒng)也是典型的樹形結構,樹形結構 結點間具有分層次的連接關系,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,(亦稱物理結構),D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) ,D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) ,圖形結構節(jié)點間的連結是任意的,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,(亦稱物理結構),元素n,元素i,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存儲地址,存儲內容,Loc(a)=Lo+（i-1)*m,順序存儲,每個元素所占用 的存儲單元個數(shù),元素n,元素i,元素2,元素1,存儲內容,順序存儲結構常用于線性數(shù)據(jù)結構，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。,順序存儲結構的三個弱點： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴充。,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,(亦稱物理結構),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈式存儲,每個節(jié)點都由兩部分組成：數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放元素本身的數(shù)據(jù)， 指針域存放指針。 數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。,1536,元素2,1400,元素1,1346,元素3,元素4,head,鏈式存儲,1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈式存儲,1.比順序存儲結構的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針愈組成)。 2.邏輯上相鄰的節(jié)點物理上不必相鄰。 3.插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。,鏈接存儲結構特點：,1數(shù)據(jù)的邏輯結構,2、數(shù)據(jù)的存儲結構,3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數(shù)據(jù)結構的三個方面,(亦稱物理結構),線性結構和非線性結構,如果一個非空的數(shù)據(jù)結構滿足下列兩個條件： 有且只有一個根結點； 每一個結點最多有一個前件，也最多有一個后件 則稱該數(shù)據(jù)結構為線性結構（線性表）。 如果一個數(shù)據(jù)結構不是線性結構，則稱之為非線性結構。,例題講解,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 數(shù)據(jù)結構分為邏輯結構與存儲結構，線性鏈表屬于 【1】 。 數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的 A) 存儲結構 B) 物理結構 C) 邏輯結構 D) 物理和存儲結構 數(shù)據(jù)的邏輯結構有線性結構和 【1】 兩大類。,順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【2】 的存儲單元中。 數(shù)據(jù)處理的最小單位是 A) 數(shù)據(jù) B) 數(shù)據(jù)元素 C) 數(shù)據(jù)項 D) 數(shù)據(jù)結構 數(shù)據(jù)結構作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結構、對各種數(shù)據(jù)結構進行的運算，以及 A) 數(shù)據(jù)的存儲結構 B) 計算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲 線性表的順序存儲結構和線性表的鏈式存儲結構分別是 A) 順序存取的存儲結構、順序存取的存儲結構 B) 隨機存取的存儲結構、順序存取的存儲結構 C) 隨機存取的存儲結構、隨機存取的存儲結構 D) 任意存取的存儲結構、任意存取的存儲結構,根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分成 A) 動態(tài)結構和靜態(tài)結構 B) 緊湊結構和非緊湊結構 C) 線性結構和非線性結構 D) 內部結構和外部結構 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的 【2】 以及對數(shù)據(jù)的操作運算。 數(shù)據(jù)的基本單位是 【5】 。,下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率密切相關 B) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率無關 C) 數(shù)據(jù)的存儲結構在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結構可以有多種存儲結構 數(shù)據(jù)的存儲結構是指 A）數(shù)據(jù)所占的存儲空間 B）數(shù)據(jù)的邏輯結構在計算機中的表示 C）數(shù)據(jù)在計算機中的順序存儲方式 D）存儲在外存中的數(shù)據(jù),2.3 線性表,2.3.1 線性表的定義 線性表是n個元素的有限序列，它們之間的關系可以排成一個線性序列： a1，a2， ，ai， ，an 其中n稱作表的長度，當n=0時，稱作空表。,線性表的特點： 1.線性表中所有元素的性質相同。 2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅和一個后繼。第一個數(shù)據(jù)元素無前驅，最后一個數(shù)據(jù)元素無后繼。 3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。 在線性表上常用的運算有： 初始化、求長度、取元素、修改、 前插、刪除、檢索、排序。,2.3.2 線性表的順序存儲結構及其插入與刪除操作,特點： 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。 2、所有元素所占的存儲空間是連續(xù)的 3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 2. 做插入、刪除時需移動大量元素。 3. 空間估計不明時，按最大空間分配。,元素an,元素ai,元素a2,元素a1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存儲地址,內存狀態(tài),Loc(元素i)=b +（i-1)*m,順序存儲結構示意圖(順序表)：,首地址 起始地址 基地址,每個元素所占用 的存儲單元個數(shù),0,1,i,線性表的順序存儲結構可用VB語言中的一維數(shù)組來描述. Dim VM As integer; /*V是數(shù)組的名字，M是數(shù)組大小，假設數(shù)組中的元素是整型類型*/,第i個元素的ai存儲地址： Loc(ai)=Loc(a1)+(i-1)*m,V,V,Vi,Vm-1,a2,a1,an,ai+1,ai,0,1,i-1,i,n-1,1- 1插入運算,ai-1,a2,a1,alength,ai+1,ai,x,x,Option Base 0 Function int insq( i As Integer，x As Integer , V( ) As Integer,M As Integer,） / *順序表插入函數(shù)*/ /*在線性表V中第i 個元素之前插入x，i 的合法值為 1 i n */ Dim n As Integer，j As Integer n=UBound(V) / *獲取表長*/ If n=M Then / *M是存儲空間的大小*/ print “overflown“ Exit Function End If If (in+1) Then print “i is error“ Exit Function /*i值不合法 */ Else for j=n To i Step -1 V(j)=V(j-1) /*插入位置后的元素依次右移*/ Next J V(j)=x /* 插入x */ End If End Function,注意數(shù)組元素從0開始,1- 2刪除運算 Option Base o Function delsq( i As Integer ,V( ) As Integer） /*在線性表V中刪除第i 個元素*/ Dim n As Integer,j As Integer n=UBound(V) If in Then print “This element is not in the list“ Exit Function else For j=I To n V(j-1)=V(j) /*被刪除元素之后的元素左移*/ Next J End if End Function,插入算法的分析 假設線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：,刪除算法的分析 在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 分析結論 順序存儲結構表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。,例題講解,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【2】 的存儲單元中。 長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。,線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 線性表的順序存儲結構和線性表的鏈式存儲結構分別是 A) 順序存取的存儲結構、順序存取的存儲結構 B) 隨機存取的存儲結構、順序存取的存儲結構 C) 隨機存取的存儲結構、隨機存取的存儲結構 D) 任意存取的存儲結構、任意存取的存儲結構,根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分成 A) 動態(tài)結構和靜態(tài)結構 B) 緊湊結構和非緊湊結構 C) 線性結構和非線性結構 D) 內部結構和外部結構 當線性表采用順序存儲結構實現(xiàn)存儲時，其主要特點是 【1】 。 線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以,下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率密切相關 B) 數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率無關 C) 數(shù)據(jù)的存儲結構在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結構可以有多種存儲結構,2.4 棧和隊列,2.4.1 棧和隊列的定義 棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結構。,2.4.1.1棧的定義 棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結構稱為后進先出 設棧s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是棧底元素， an是棧頂元素。 棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放的位置。 棧底（bottom):不允許插入和刪除的一端。,隊列的主要運算,（1）設置一個空隊列； （2）插入一個新的隊尾元素，稱為進隊； （3）刪除隊頭元素，稱為出隊； （4）讀取隊頭元素；,2.4.1.2 隊列的定義 定義：一種特殊的線性結構，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表 。此種結構稱為先進先出（FIFO）表。,a1 , a2 , a3 , a4 , an-1 , an,隊 列 示 意 圖,隊頭,隊尾,2.4.2 棧的順序存儲結構及其基本運算,用順序存儲結構表示的棧。 順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。,基本運算： 壓（進）棧：PUSH 出棧：POP,隊空時， 令rear=front=-1，當有新元素入隊時，尾指針加1，當有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置,2.4.3 隊列的順序存儲結構及其基本運算,例題講解,棧和隊列的共同特點是 A)都是先進先出 B) 都是先進后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點 如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意順序 一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調用。而實現(xiàn)遞歸調用中的存儲分配通常用 A) 棧 B) 堆 C) 數(shù)組 D) 鏈表,棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 棧通常采用的兩種存儲結構是 A) 線性存儲結構和鏈表存儲結構 B) 散列方式和索引方式 C) 鏈表存儲結構和數(shù)組 D) 線性存儲結構和非線性存儲結構 棧和隊列通常采用的存儲結構是 【1】 。 下列數(shù)據(jù)結構中，按先進后出原則組織數(shù)據(jù)的是 A) 線性鏈表 B) 棧 C) 循環(huán)鏈表 D) 順序表,當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 【2】 。 由兩個棧共享一個存儲空間的好處是 A) 減少存取時間，降低下溢發(fā)生的機率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機率 C) 減少存取時間，降低上溢發(fā)生的機率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機率 下列關于棧的敘述中正確的是 ）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù) C）棧是先進先出的線性表 D）棧是后進先出的線性表 下列關于隊列的敘述中正確的是 ）在隊列中只能插入數(shù)據(jù) B）在隊列中只能刪除數(shù)據(jù) C）隊列是先進先出的線性表 D）隊列是后進先出的線性表,2.5 鏈表,線性單鏈表 雙向鏈表 循環(huán)鏈表,結構及其基本運算,2.5.1 線性表的鏈式存儲結構,將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結點包含數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結點的地址，最后一個結點的指針域為空。邏輯上相鄰的數(shù)據(jù)元素在內存中的物理存儲空間不一定相鄰。,上圖的線性表為 ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG,線性鏈表表示法:,鏈式存儲結構的特點,插入、刪除靈活方便，不需要移動結點，只要改變結點中指針域的值即可。 適合于線性表是動態(tài)變化的,不進行頻繁查找操作、但經(jīng)常進行插入刪除時使用。 鏈表的查找只能從頭指針開始順序查找。,L,線性表的鏈式存儲結構可用C語言中的“結構指針”來描述,帶頭結點的線性鏈表,data,next,typedef struct LNode int data; Struct LNode *next; JD;,P,P,單鏈表的插入運算,S,在P所指向的結點之后插入新的結點,P,P,L,單鏈表的插入運算,S,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,P,L,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,P,L,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,S,P,L,單鏈表的插入運算,void lbcr (JD *p, int x) / * 在P所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; ,void lbsc(JD *p) /* 刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,L,p,void lbsc(JD *p) /* 刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,L,p,void lbsc(JD *p) /* 刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,q,L,p,q,void lbsc(JD *p) /*刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,L,p,q,void lbsc(JD *p) /*刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,L,p,void lbsc(JD *p) /*刪除p指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向p的后繼結點 */ p-next=q-next; /* 修改p結點的指針域 */ free(q); /* 刪除并釋放結點 */ ,單鏈表的刪除運算,線性鏈表的查找操作： 設無表頭結點的線性鏈表的頭指針為h, 沿著鏈表的開始往后找結點x，若找到，則返回該結點在鏈表中的位置，否則返回空地址。 JD *lbcz (JD *h,int x) JD *p; p=h; while (p!=NULL ,2.5.2 循環(huán)鏈表: 首尾相接的鏈表。 將最后一個結點的空指針改為指向頭結點，從任一結點出發(fā)均可找到其它結點。,L,帶頭結點的單鏈表,L,循環(huán)單鏈表,2.5.3 雙向鏈表 在每個結點中設置兩個指針，一個指向后繼，一個指向前驅?？芍苯哟_定一個結點的前驅和后繼結點?？商岣咝省?data,next,before,線性表的應用：應用最廣的數(shù)據(jù)結構。 高級語言中的數(shù)組； 計算機的文件系統(tǒng)； 計算機的目錄系統(tǒng)； 電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結構）； 各種事務處理（各種表格均采用順序表和線性鏈表結構）,(1) L=P-link;,例題 對以下單鏈表分別執(zhí)行下列各程序段,并畫出結果示意圖.,(2) R-data=P-data;,(3) R-data=P-link-data;,(4) P-link-link-link-data=P-data;,(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-link; ,(6) T=P; while(T-link!=NULL) T-data=(T-data)*2; T=T-link; ,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;,P,10,(8) T=L; T-link=P-link; free(P);,(9) S-link=L;,如果 S-link= =L 則S所指向的結點為尾結點.,例題講解,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 用鏈表表示線性表的優(yōu)點是 A) 便于隨機存取 B) 花費的存儲空間較順序存儲少 C) 便于插入和刪除操作 D) 數(shù)據(jù)元素的物理順序與邏輯順序相同 長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。,線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 在單鏈表中，增加頭結點的目的是 A) 方便運算的實現(xiàn) B) 使單鏈表至少有一個結點 C) 標識表結點中首結點的位置 D) 說明單鏈表是線性表的鏈式存儲實現(xiàn),非空的循環(huán)單鏈表head的尾結點(由p所指向) ，滿足 A) p-next=NULL B) p=NULL C) p-next=head D) p=head 循環(huán)鏈表的主要優(yōu)點是 A) 不再需要頭指針了 B) 從表中任一結點出發(fā)都能訪問到整個鏈表 C) 在進行插入、刪除運算時，能更好的保證鏈表不斷開 D) 已知某個結點的位置后，能夠容易的找到它的直接前件,線性表的順序存儲結構和線性表的鏈式存儲結構分別是 A) 順序存取的存儲結構、順序存取的存儲結構 B) 隨機存取的存儲結構、順序存取的存儲結構 C) 隨機存取的存儲結構、隨機存取的存儲結構 D) 任意存取的存儲結構、任意存取的存儲結構 當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 【2】 。 用鏈表表示線性表的突出優(yōu)點是 【1】 。,2.6 樹,樹的基本概念 二叉樹的定義及其存儲結構 二叉樹的前序、中序和后序遍歷,2.6.1 樹的定義 由一個或多個結點組成的有限集合。僅有一個根結點，結點間有明顯的層次結構關系。,現(xiàn)實世界中，能用樹的結構表示的例子： 學校的行政關系、書的層次結構、人類的家族血緣關系等。,介紹幾個概念： 結點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。 結點的度（Degree）：結點擁有的子樹數(shù)。 結點的層次：從根結點開始算起，根為第一層。 葉子（Leaf）：度為零的結點，也稱端結點。 孩子（Child）：結點子樹的根稱為該結點的孩子結點。 兄弟（Sibling）：同一雙親的孩子。 雙親（Parent）：孩子結點的上層結點，稱為這些結點的雙親。 深度（Depth)： 樹中結點的最大層次數(shù)。 森林（Forest）：M棵互不相交的樹的集合。,2.6.2 二叉樹 （Binary Tree）,1 、二叉樹的定義及其性質 (1) 二叉樹的定義,二叉樹的五種基本形態(tài),二叉樹一種特殊的樹型結構，特點是樹中每個結點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。,因為樹的每個結點的度不同，存儲困難，使對樹的處理算法很復雜。所以引出二叉樹的討論。,二叉數(shù)是n(n0)個結點的有限集合。它或為空數(shù)(n=0),或由一個根結點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。,特別要注意：二叉數(shù)不是樹的特殊情況。,a,a,b,b,兩棵不同的二叉數(shù),A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。,(2) 二叉樹的基本性質,第三層上(i=3)，有23-1=4個節(jié)點。 第四層上(i=4)，有24-1=8個節(jié)點。,A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。 B、 深度為h的二叉樹中至多含有2h-1個結點。,(2) 二叉樹的基本性質,此樹的深度h=4，共有24-1=15個節(jié)點。,A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。 B、 深度為h的二叉樹中至多含有2h-1個結點。 C、 若在任意一棵二叉樹中，有n0個葉子結點， 有n2個度為2的結點，則：n0=n2+1,(2) 二叉樹的基本性質,n0=8 n2=7,（3）滿二叉樹,特點：每一層上都含有最大結點數(shù)。,（4）完全二叉樹,特點：除最后一層外，每一層都取最大結點數(shù)， 最后一層結點都集中在該層最左邊的若干位置。,（5）樹與二叉樹的區(qū)別,A樹的結點個數(shù)至少為1，而二叉樹的結點個數(shù)可以為0。 B樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為2。 C樹的結點無左、右之分，二叉樹的結點子樹有明確的左、右之分。,樹,二叉樹,2、二叉樹的存儲結構,(2) 鏈式存儲結構,T16,若父結點在數(shù)組中i下標處，其左孩子在2*i處，右孩子在2*i+1處。,(1) 順序存儲結構,(1) 順序存儲結構,2h-1=,24-1 = 15,用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結點在數(shù)組中的相對位置蘊含著結點之間的關系。,一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。,2.6.3 二叉樹的遍歷 查找某個結點，或對二叉樹中全部結點進行某種處理，就需要遍歷。 （1）遍歷定義及遍歷算法 遍歷是指按某條搜索路線尋訪樹中每個結點，且每個結點只被訪問一次。 按先左后右的原則，一般使用三種遍歷： 先序遍歷(D L R): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。 中序遍歷(L D R): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。 后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。,（2）遍歷算法,先序遍歷：D L R 中序遍歷：L D R 后序遍歷：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍歷D L R為例演示遍歷過程,ABDC,BDAC,DBCA,例題講解,已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 A) acbed B) decab C) deabc D) cedba 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 樹是結點的集合，它的根結點數(shù)目是 A) 有且只有1 B) 1或多于1 C) 0或1 D) 至少2,在深度為5的滿二叉樹中，葉子結點的個數(shù)為 A) 32 B) 31 C) 16 D) 15 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 在樹結構中，樹根結點沒有 【1】 。 下列敘述中正確的是 A) 線性表是線性結構 B) 棧與隊列是非線性結構 C) 線性鏈表是非線性結構 D) 二叉樹是線性結構,具有3個結點的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) 設有下列二叉樹： 對此二叉樹前序遍歷的結果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT,設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數(shù)為 A) 12 B) 13 C) 14 D) 15 設有下列二叉樹： 對此二叉樹的中序遍歷的結果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,設樹T的深度為4,其中度為1、2、3、4的結點個數(shù)分別為4、2、1、1。則T中的葉子結點數(shù)為 A）8 B）7 C）6 D）5 設一棵完全二叉樹共有700個結點，則該二叉樹中有（ ）個葉子結點。 在一個容量為15的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中共有（ ）個元素。 設一棵二叉樹的中序遍歷結果為DBEAFC，前序遍歷結果為ABDECF，則后序遍歷結果為（ ）。,2.7 查找和排序,順序查找與二分查找算法 基本排序算法（交換類排序、選擇類排序、插入類排序）,2.7.1 查找,查找是在一個給定的數(shù)據(jù)結構中，根據(jù)給定的條件查找滿足條件的結點。不同的數(shù)據(jù)結構采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 查找的結果： 查找成功：找到滿足條件的結點 查找失?。赫也坏綕M足條件的結點。,2.7.1.1 順序查找（線性查找）,查找過程： 對給定的一關鍵字K，從線性表的一端開始，逐個進行記錄的關鍵字和K的比較，直到找到關鍵字等于K的記錄或到達表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進行比較