全國計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)課件版.ppt

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