全國計(jì)算機(jī)二級公共基礎(chǔ)知識要點(diǎn)

全國計(jì)算機(jī)等級考試

二級公共基礎(chǔ)知識

27十二月2022基本要求1.掌握算法的基本概念。2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3.掌握基本排序和查找算法。4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)。2022/12/27主講人：李書舉3考試內(nèi)容基本數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)內(nèi)容2006/92007/42007/92008/42008/910`10`8`2`12`8`4`6`12`8`4`6`10`2`8`10`10`2`8`10`一、基本數(shù)據(jù)結(jié)構(gòu)與算法

1.算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。

二、程序設(shè)計(jì)基礎(chǔ)1.程序設(shè)計(jì)方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計(jì)。3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象，方法，屬性及繼承與多態(tài)性。三、軟件工程基礎(chǔ)1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計(jì)，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。四、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。4.數(shù)據(jù)庫設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?？荚嚪绞?、公共基礎(chǔ)的考試方式為筆試，與C語言（VisualBASIC、VisualFoxPro、Java、Access、VisualC++）的筆試部分合為一張?jiān)嚲?。公共基礎(chǔ)部分占全卷的30分。2、公共基礎(chǔ)知識有10道選擇題和5道填空題。學(xué)習(xí)方法理解基本概念多做練習(xí)適當(dāng)記憶一些名詞與所學(xué)的VFP\c\Access程序設(shè)計(jì)知識結(jié)合起來，以增加對知識的理解能力2022/12/27主講人：李書舉101.基本數(shù)據(jù)結(jié)構(gòu)與算法2022/12/27主講人：李書舉111.1算法1.1.1算法(algorithm)基本概念

對特定問題求解步驟的一種描述，它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法一級算法:S1:輸入圓的半徑r;S2:求周長2∏r;S3:求面積∏r2;S4:輸出周長和面積;例題:已知圓的半徑,求周長和面積.程序dowhile.t.

input“輸入圓的半徑：”tor

ifr<0?“輸入不能是負(fù)數(shù)，重新輸入！”

loop

elseexit

endifenddoS=pi()*r*rL=2*pi()*r?S,L2022/12/27主講人：李書舉12算法的基本特征:(1)可行性(2)確定性(3)有窮性(4)輸入和輸出（擁有足夠的情報）2022/12/27主講人：李書舉131.1.2算法的基本要素

1、對數(shù)據(jù)對象的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成。2022/12/27主講人：李書舉14input“輸入圓的半徑：”torifr<0?“輸入不能是負(fù)數(shù)，重新輸入！”循環(huán)輸入relse

退出循環(huán)endifS=pi()*r*rL=2*pi()*r輸出S,L算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸順序、選擇、循環(huán)三種基本結(jié)構(gòu)2022/12/27主講人：李書舉151.1.3算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸（以簡潔的形式設(shè)計(jì)和描述算法）減半遞推技術(shù)回溯法2022/12/27主講人：李書舉161.2算法復(fù)雜度1.2.1時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。通常有事后統(tǒng)計(jì)法和事前分析估算法?！锼惴ㄔ趫?zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量.★算法所執(zhí)行的基本運(yùn)算次數(shù)與問題的規(guī)模n有關(guān).執(zhí)行算法所需要的計(jì)算工作量和f(n)同步增長，記為:算法的工作量=f(n)時間復(fù)雜度=O(f(n))2022/12/27主講人：李書舉17例子4：for(i=2;i<=n;++i)for(j=2;j<=i-1;++j)++x;基本運(yùn)算：基本運(yùn)算的執(zhí)行次數(shù)：X增1i=20i=31i=42…i=nn-21+2+3+…+(n-2)=(n-1)(n-2)/2O（）例子2：++x;O（1）例子3：for(i=1;i<=n;++i)++x;O（n）時間復(fù)雜度：O((n*n-3n+2)/2)基本運(yùn)算：基本運(yùn)算的執(zhí)行次數(shù)：時間復(fù)雜度：1X增1基本運(yùn)算：基本運(yùn)算的執(zhí)行次數(shù)：時間復(fù)雜度：X增1n2022/12/27主講人：李書舉181.2.2算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間一個上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。2022/12/27主講人：李書舉19

算法的時間復(fù)雜度是指A)執(zhí)行算法程序所需要的時間B)算法程序的長度C)算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D)算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、

【1】和擁有足夠的情報。算法的空間復(fù)雜度是指

A)算法程序的長度 B)算法程序中的指令條數(shù)

C)算法程序所占的存儲空間D)執(zhí)行過程中所需要的存儲空間在計(jì)算機(jī)中，算法是指

A)加工方法 B)解題方案的準(zhǔn)確而完整的描述

C)排序方法 D)查詢方法例題講解有窮性2022/12/27主講人：李書舉20算法分析的目的是

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)找出算法中輸入和輸出之間的關(guān)系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元多少分別稱為算法的【1】。時間復(fù)雜度和空間復(fù)雜度2022/12/27主講人：李書舉211.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)2022/12/27主講人：李書舉221.2.1數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容(1)數(shù)據(jù)集中數(shù)據(jù)之間的邏輯關(guān)系線性樹圖(2)數(shù)據(jù)的存儲結(jié)構(gòu)(3)各種數(shù)據(jù)結(jié)構(gòu)的運(yùn)算2022/12/27主講人：李書舉23能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號的集合。整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。1.2.2基本概念和術(shù)語

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。2022/12/27主講人：李書舉24計(jì)算機(jī)管理圖書問題

在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排如何將查詢圖書的這些信息存入計(jì)算機(jī)中既要考慮查詢時間短，又要考慮節(jié)省空間

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如2022/12/27主講人：李書舉25如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？目的不同，最佳的存儲方方法就不同。從大到小排列：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ù)組織、存儲和運(yùn)算的一般方法的學(xué)科。對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理(插入、刪除、修改、查找、排序)2022/12/27主講人：李書舉26（1）數(shù)據(jù)元素(DataElement)

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有時一個數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。2022/12/27主講人：李書舉271．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈?zhǔn)酱鎯€性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面2022/12/27主講人：李書舉28數(shù)據(jù)結(jié)構(gòu)可描述為Group=（D，R）（2）邏輯結(jié)構(gòu)有限個數(shù)據(jù)元素的集合有限個數(shù)據(jù)元素間關(guān)系的集合線性樹圖常用數(shù)據(jù)結(jié)構(gòu):2022/12/27主講人：李書舉29A.線性結(jié)構(gòu)(A,B,C,·······，X,Y,Z)例:學(xué)生成績表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號①線性表②?！筮M(jìn)先出③隊(duì)列——先進(jìn)先出例:英文字母表2022/12/27主講人：李書舉30數(shù)據(jù)結(jié)構(gòu)S=(D,R)D={春,夏,秋,冬}R={<春,夏>,<夏,秋>,<秋,冬>}什么型的數(shù)據(jù)結(jié)構(gòu)?用圖形工具春夏秋冬線性結(jié)構(gòu)2022/12/27主講人：李書舉31①樹形結(jié)構(gòu)例:全校學(xué)生檔案管理的組織方式例:計(jì)算機(jī)文件管理系統(tǒng)也是典型的樹形結(jié)構(gòu)B．非線性結(jié)構(gòu)2022/12/27主講人：李書舉321423

例:數(shù)據(jù)結(jié)構(gòu)B(D,R)D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}213例:數(shù)據(jù)結(jié)構(gòu)C(D,R)D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

②圖形結(jié)構(gòu)2022/12/27主講人：李書舉33元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(ai)=Lo+（i-1)*m1、順序存儲每個元素所占用的存儲單元個數(shù)（3）存儲結(jié)構(gòu)2022/12/27主講人：李書舉34例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)

順序存儲結(jié)構(gòu)：存儲地址數(shù)據(jù)7891011121314zhaoqiansunlizhouwuzhengwang7基地址順序存儲結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里,具有以下特點(diǎn):1.隨機(jī)存取。2.作插入或刪除操作時，需移動大量元數(shù)。3.長度變化較大時，需按最大空間分配。4.表的容量難以擴(kuò)充。2022/12/27主講人：李書舉352、鏈?zhǔn)酱鎯γ總€節(jié)點(diǎn)都由兩部分組成：

數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang)鏈?zhǔn)酱鎯Y(jié)構(gòu)：存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針2022/12/27主講人：李書舉36通常我們把鏈表畫成用箭頭相鏈接的結(jié)點(diǎn)的序列，結(jié)點(diǎn)之間的箭頭表示鏈域中的指針。zhaoqiansunlizhouwuzhengwang/H存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針2022/12/27主講人：李書舉371.比順序存儲結(jié)構(gòu)多用空間(存儲密度小)(每個節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成)。2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3.插入、刪除靈活

(不必移動節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。4.非隨機(jī)存取。鏈接存儲結(jié)構(gòu)特點(diǎn)：2022/12/27主講人：李書舉381．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲B鏈?zhǔn)酱鎯€性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面(亦稱物理結(jié)構(gòu))……2022/12/27主講人：李書舉39鏈表不具有的特點(diǎn)是A)不必事先估計(jì)存儲空間B)可隨機(jī)訪問任一元素C)插入刪除不需要移動元素 D)所需空間與線性表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于【1】

。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的

A)存儲結(jié)構(gòu) B)物理結(jié)構(gòu)

C)邏輯結(jié)構(gòu) D)物理和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和【1】

兩大類。數(shù)據(jù)的存儲結(jié)構(gòu)是指A）數(shù)據(jù)所占的存儲空間B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲方式D）存儲在外存中的數(shù)據(jù)例題講解存儲結(jié)構(gòu)非線性結(jié)構(gòu)2022/12/27主講人：李書舉40順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置

【2】的存儲單元中。

數(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)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及

A)數(shù)據(jù)的存儲結(jié)構(gòu) B)計(jì)算方法C)數(shù)據(jù)映象D)邏輯存儲線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是

A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B)隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

C)隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)

D)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)

相鄰2022/12/27主講人：李書舉41根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成

A)動態(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】以及對數(shù)據(jù)的操作運(yùn)算。數(shù)據(jù)的基本單位是

【5】。下列敘述中，錯誤的是

A)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)

B)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)

C)數(shù)據(jù)的存儲結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的

D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)元素2022/12/27主講人：李書舉421.3線性表1.3.1線性表的概念線性表的定義：

線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列：

(a1，a2，……

，ai，……

，an)

其中n稱作表的長度，當(dāng)n=0時，稱作空表。線性表的特點(diǎn)：1.線性表中所有元素的性質(zhì)相同。2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼.第一個數(shù)據(jù)元素?zé)o前驅(qū),最后一個數(shù)據(jù)元素?zé)o后繼。3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運(yùn)算有：初始化、求長度、取元素、修改、前插、刪除、檢索、排序。2022/12/27主講人：李書舉431.4線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作特點(diǎn)：

1.線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。

2.所有元素所占的存儲空間是連續(xù)的

3.各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的

4.做插入、刪除時需移動大量元素。

5.空間估計(jì)不明時，按最大空間分配。

順序存儲結(jié)構(gòu)：存儲地址數(shù)據(jù)7891011121314zhaoqiansunlizhouwuzhengwang7基地址2022/12/27主講人：李書舉44元素an……..元素ai……..元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存儲地址內(nèi)存狀態(tài)Loc(元素i)=b+（i-1)*m順序存儲結(jié)構(gòu)示意圖(順序表)：首地址起始地址基地址每個元素所占用的存儲單元個數(shù)2022/12/27主講人：李書舉451-1插入運(yùn)算ai-1…..a2a1alength…ai+1aixai-1…..a2a1alength…ai+1aiX插入算法的分析:

假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：2022/12/27主講人：李書舉461-2刪除運(yùn)算ai-1…..a2a1alength…ai+1aiai-1…..a2a1alength…ai+1刪除算法的分析:

在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：總結(jié):

順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點(diǎn)需要值得考慮。2022/12/27主講人：李書舉47鏈表不具有的特點(diǎn)是A)不必事先估計(jì)存儲空間B)可隨機(jī)訪問任一元素C)插入刪除不需要移動元素 D)所需空間與線性表長度成正比順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置

【2】的存儲單元中。長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為【1】

。線性表若采用順序存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址

A)必須是連續(xù)的 B)部分地址必須是連續(xù)的

C)一定是不連續(xù)的D)連續(xù)不連續(xù)都可以例題講解相鄰2022/12/27主講人：李書舉48線性表L=(a1,a2,a3,…ai，…an)，下列說法正確的是

A)每個元素都有一個直接前件和直接后件

B)線性表中至少要有一個元素

C)表中諸元素的排列順序必須是由小到大或由大到小

D)除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是

A)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

B)隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)

C)隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)

D)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)下列敘述中，錯誤的是

A)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)

B)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)

C)數(shù)據(jù)的存儲結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的

D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)

2022/12/27主講人：李書舉49根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成

A)動態(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)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時，其主要特點(diǎn)是【1】

。隨機(jī)存取2022/12/27主講人：李書舉501.5線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其插入與刪除操作zhaoqiansunlizhouwuzhengwang/H存儲地址數(shù)據(jù)17131925313743liqiansunwangwuzhaozhengzhou指針43131null377192531頭指針單鏈表2022/12/27主講人：李書舉51baPbaP1-1單鏈表的插入運(yùn)算xS在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)1-2單鏈表刪除運(yùn)算La…aian^…ai-1ai+1要求:刪除結(jié)點(diǎn)ai。2022/12/27主講人：李書舉521-3.循環(huán)鏈表:

首尾相接的鏈表。將最后一個結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。a1a2an∧a3L…..帶頭結(jié)點(diǎn)的單鏈表a1a2ana3L…..循環(huán)單鏈表特點(diǎn):

可以從任何一個結(jié)點(diǎn)開始訪問鏈表的所有結(jié)點(diǎn).2022/12/27主講人：李書舉531-4雙向鏈表在每個結(jié)點(diǎn)中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)?？商岣咝?。datanextbefore1.6線性表的應(yīng)用：應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。.高級語言中的數(shù)組；·計(jì)算機(jī)的文件系統(tǒng)；·計(jì)算機(jī)的目錄系統(tǒng)；·電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結(jié)構(gòu)）；·各種事務(wù)處理（可采用順序表或單鏈表結(jié)構(gòu)）;2022/12/27主講人：李書舉54鏈表不具有的特點(diǎn)是A)不必事先估計(jì)存儲空間B)可隨機(jī)訪問任一元素C)插入刪除不需要移動元素D)所需空間與線性表長度成正比用鏈表表示線性表的優(yōu)點(diǎn)是A)便于隨機(jī)存取B)花費(fèi)的存儲空間較順序存儲少C)便于插入和刪除操作D)數(shù)據(jù)元素的物理順序與邏輯順序相同長度為n的順序存儲線性表中,當(dāng)在任何位置上插入一個元素概率都相等時,插入一個元素所需移動元素的平均個數(shù)為【1】

。在單鏈表中，增加頭結(jié)點(diǎn)的目的是

A)方便運(yùn)算的實(shí)現(xiàn)B)使單鏈表至少有一個結(jié)點(diǎn)

C)標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

D)說明單鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn)例題講解2022/12/27主講人：李書舉55非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)，滿足

A)p->next==NULL B)p==NULLC)p->next=head D)p=head循環(huán)鏈表的主要優(yōu)點(diǎn)是

A)不再需要頭指針了

B)從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表

C)在進(jìn)行插入、刪除運(yùn)算時，能更好的保證鏈表不斷開

D)已知某個結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【2】。用鏈表表示線性表的突出優(yōu)點(diǎn)是【1】。上溢插入、刪除靈活2022/12/27主講人：李書舉561.7棧和隊(duì)列1.7.1棧和隊(duì)列的定義棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。2022/12/27主講人：李書舉571.棧?！窍薅▋H在表尾進(jìn)行插入或刪除操作的線性表。棧頂——表尾。棧底——表頭?？諚！缓氐目毡??！璦1a2an棧底棧頂進(jìn)棧出棧棧s=(a1,a2,…,an)后進(jìn)先出（LIFO）2022/12/27主講人：李書舉582.棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算a2a1a1a2top

用順序存儲結(jié)構(gòu)表示的棧:

順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\(yùn)算：壓（進(jìn)）棧：PUSH出棧：POP讀棧頂元素：gettop2022/12/27主講人：李書舉59例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：top＝base非空桟：top始終在桟頂元素的后一個位置桟的元素個數(shù)：top-base上溢下溢2022/12/27主講人：李書舉603.隊(duì)列定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭隊(duì)尾2022/12/27主講人：李書舉61e3e4(c)e1,e2出隊(duì)，e4入隊(duì)

隊(duì)滿rear=3fronte1e2e3

(b)rearfront(b)e1,e2,e3入隊(duì)4.隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算

3210(a)rear=front=-1(隊(duì)空）rearfront空隊(duì)列:非空隊(duì)列:隊(duì)列元素個數(shù):rear=front=-1front始終指向隊(duì)頭元素前一個位置，而rear始終指向隊(duì)尾元素的位置rear-front2022/12/27主講人：李書舉62循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想為一個循環(huán)的表，臆想elem[0]接在elem[maxsize-1]之后.……frontrearMaxsize-101e3e4

rear=3front2022/12/27主講人：李書舉630012345frontABCDEFrear上溢0012345frontrear下溢front=rear隊(duì)滿front=rear隊(duì)空2022/12/27主講人：李書舉64棧和隊(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,e1C)e3,e4,e1,e2 D)任意順序一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用

A)棧 B)堆C)數(shù)組 D)鏈表例題講解2022/12/27主講人：李書舉65棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE棧通常采用的兩種存儲結(jié)構(gòu)是

A)線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B)散列方式和索引方式

C)鏈表存儲結(jié)構(gòu)和數(shù)組D)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊(duì)列通常采用的存儲結(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ì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為

【2】。鏈表存儲結(jié)構(gòu)和數(shù)組上溢2022/12/27主講人：李書舉66由兩個棧共享一個存儲空間的好處是A)減少存取時間，降低下溢發(fā)生的機(jī)率B)節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率C)減少存取時間，降低上溢發(fā)生的機(jī)率D)節(jié)省存儲空間，降低下溢發(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)先出的線性表2022/12/27主講人：李書舉671.6.1樹的定義由一個或多個結(jié)點(diǎn)組成的有限集合。僅有一個根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。

A

C

GT2D

HIT3J

M

BEL

KT1F現(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。1.6樹2022/12/27主講人：李書舉68介紹幾個概念：結(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ù)。樹的度：結(jié)點(diǎn)所具有的最大的度.森林（Forest）：M棵互不相交的樹的集合。

A

C

GD

HI

J

M

BEL

KT1F2022/12/27主講人：李書舉691.6.2二叉樹（BinaryTree）1、二叉樹的定義及其性質(zhì)

(1)二叉樹的定義二叉樹的五種基本形態(tài)

二叉樹一種特殊的樹形結(jié)構(gòu)，特點(diǎn)是樹中每個結(jié)點(diǎn)最多只能有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn))，且子樹有左右之分，次序不能顛倒。

空二叉樹

僅有根結(jié)點(diǎn)

右子樹為空

左子樹為空左右子樹均非空2022/12/27主講人：李書舉70二叉樹是n(n0)個結(jié)點(diǎn)的有限集合。它或?yàn)榭諗?shù)(n=0),或由一個根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。特別要注意：二叉樹不是一般樹的特殊情況,而是另一種樹形結(jié)構(gòu).aabb兩棵不同的二叉樹ab一棵樹2022/12/27主講人：李書舉71性質(zhì)1:二叉樹的第i層上至多有2i-1（i1）個結(jié)點(diǎn)。(2)二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個節(jié)點(diǎn)。性質(zhì)2:深度為k的二叉樹中至多含有2k-1個結(jié)點(diǎn)。2022/12/27主講人：李書舉72性質(zhì)３：對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。證明：設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)；∵二叉樹中所有結(jié)點(diǎn)的度均小于或等于2∴其結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2∵二叉樹中除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個分支進(jìn)入設(shè)分支總數(shù)為B；則n=B+1;∵二叉樹的分支是由度為1或2的結(jié)點(diǎn)射出的∴B=n1+2*n2

∴n=n1+2*n2+1=n0+n1+n2

n0=n2+1ABFCJM一般樹2022/12/27主講人：李書舉73★滿二叉樹423167891011121314155特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)?！锿耆鏄?23167891011125特點(diǎn)：(1)除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，(2)最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。2022/12/27主講人：李書舉74性質(zhì)４：具有n個結(jié)點(diǎn)的完全二叉樹的深度為112345678910121例：n=2k=2n=6k=3n=7k=3n=8k=4n=12k=42022/12/27主講人：李書舉75性質(zhì)５：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任一結(jié)點(diǎn)i(1=<i=<n)有：(2)如果2i>n,則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));

否則其左孩子Lchild(i)是結(jié)點(diǎn)2i。

(3)如果2i+1>n,則結(jié)點(diǎn)i無右孩子;

否則其右孩子Rchild(i)是結(jié)點(diǎn)2i+1。(1)如果i=1,則結(jié)點(diǎn)i是二叉樹的根,無雙親;

如果i>1,則雙親Parent(i)是結(jié)點(diǎn)|i/2|。

2022/12/27主講人：李書舉76例：112345678910121i=6其雙親為|i/2|=3；其左孩子為2*i=12;i=1是樹的根,無雙親;其左孩子為2*i=2,右孩子為2*i+1=3.∵2*i=18>122*i+1=19>12∴其無左、右孩子?！?*i+1=13>12∴其無右孩子。i=9其雙親為|i/2|=

4

；2022/12/27主講人：李書舉77★樹與二叉樹的區(qū)別A．樹和二叉樹的結(jié)點(diǎn)個數(shù)最少都可為0。B．樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2。C．樹的結(jié)點(diǎn)無左、右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左、右之分。3個結(jié)點(diǎn)的樹3個結(jié)點(diǎn)的二叉樹2022/12/27主講人：李書舉782、二叉樹的存儲結(jié)構(gòu)

(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)T[16]若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。11ABcFED

●●●●●●●●●124

8

910563712131415(1)順序存儲結(jié)構(gòu)(1)順序存儲結(jié)構(gòu)2h-1=24-1=15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費(fèi)。2022/12/27主講人：李書舉79(2)、鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表三叉鏈表二叉鏈表：二叉鏈表的結(jié)點(diǎn)包含三個域：數(shù)據(jù)域、左、右指針域。例：ABCDEFGA^B^C^D^E^F^^G^2022/12/27主講人：李書舉80三叉鏈表：三叉鏈表的結(jié)點(diǎn)包含四個域：數(shù)據(jù)域、左、右、雙親指針域。例：ABCDEFGA^^B^C^D^E^F^^G^鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)：（1）操作便于實(shí)現(xiàn)（2）結(jié)構(gòu)復(fù)雜2022/12/27主講人：李書舉811.6.3二叉樹的遍歷查找某個結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法遍歷是指按某條搜索路線尋訪樹中每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只被訪問一次。按先左后右的原則，一般使用三種遍歷：先序遍歷(DLR):

訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(LDR):

按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。后序遍歷(LRD):

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。2022/12/27主講人：李書舉82

（2）遍歷算法先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCDLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA2022/12/27主講人：李書舉83e-+a*b-cd/fLDRLDRa+LDRb*LDRc-d-LDRe/f中序遍歷示圖2022/12/27主講人：李書舉84已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是

A)acbedB)decabC)deabc D)cedba已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是

A)有且只有1 B)1或多于1C)0或1 D)至少2下列敘述中正確的是

A)線性表是線性結(jié)構(gòu) B)棧與隊(duì)列是非線性結(jié)構(gòu)

C)線性鏈表是非線性結(jié)構(gòu) D)二叉樹是線性結(jié)構(gòu)例題講解2022/12/27主講人：李書舉85在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為

A)32 B)31C)16 D)15若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是

A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有【1】。具有3個結(jié)點(diǎn)的二叉樹有

A)2種形態(tài)B)4種形態(tài)C)7種形態(tài)D)5種形態(tài)設(shè)一棵二叉樹中有3個葉子結(jié)點(diǎn)，有8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為

A)12 B)13C)14 D)15雙親結(jié)點(diǎn)2022/12/27主講人：李書舉86設(shè)有下列二叉樹：

對此二叉樹前序遍歷的結(jié)果為A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPT設(shè)有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA2022/12/27主講人：李書舉87設(shè)樹T的度為4,其中度為1、2、3、4的結(jié)點(diǎn)個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點(diǎn)數(shù)為A）8B）7C）6D）5設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則該二叉樹中有（）個葉子結(jié)點(diǎn)。

在一個容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有（）個元素。設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（）。3503DEBFCA2022/12/27主講人：李書舉881.7查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）2022/12/27主講人：李書舉891.7.1查找查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點(diǎn)查找失敗：找不到滿足條件的結(jié)點(diǎn)。2022/12/27主講人：李書舉901.7.1.1順序查找（線性查找）◆查找過程：

對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。◆可以采用從前向后查，也可采用從后向前查的方法?！粼谄骄闆r下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長度較大。最好情況：1最壞情況：n◆在下面兩種情況下只能采取順序查找：

a.線性表為無序表（元素排列是無序的）；

b.即使是有序線性表，但采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。2022/12/27主講人：李書舉911.7.1.2折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。分三種情況：

1）若中間項(xiàng)的值等于x,則說明已查到。

2）若x小于中間項(xiàng)的值,則在線性表的前半部分查找；

3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。2022/12/27主講人：李書舉921.7.2排序1.7.2.1概述

1、排序的功能：

將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個按關(guān)鍵字有序的序列。

2、排序過程的組成步驟：首先比較兩個關(guān)鍵字的大?。蝗缓髮⒂涗洀囊粋€位置移動到另一個位置。2022/12/27主講人：李書舉93排序方法插入排序選擇排序交換排序歸并排序簡單插入排序希爾排序簡單選擇排序堆排序起泡排序快速排序2022/12/27主講人：李書舉941.7.2.2插入排序

簡單插入、希爾排序1、簡單插入排序:

基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。2022/12/27主講人：李書舉95該算法適合于n較小的情況，時間復(fù)雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例對于有n個數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1趟最壞情況下：需要n(n-1)/2次比較最好：

n-1次比較2022/12/27主講人：李書舉96希爾排序：希爾排序的基本思想:

先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個序列中的記錄“基本有序”時,再對全體記錄進(jìn)行一次直接插入排序.最壞情況下：需要O(n1.5)次比較2022/12/27主講人：李書舉971、簡單選擇排序思想：首先從1~n個元素中選出關(guān)鍵字最小的記錄交換到第一個位置上。然后再從第2個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。1.7.2.3選擇排序

簡單選擇排序、堆排序2022/12/27主講人：李書舉98初態(tài)83916839168391683916ijkijkijkijk1

3986互換ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟時間復(fù)雜度為O(n2)，適用于待排序元素較少的情況。比較次數(shù)：

n(n-1)/2次2022/12/27主講人：李書舉99

2、堆排序（也是一種選擇排序）堆是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。897624331510112536497856(a):堆頂元素取最大值(b):堆頂元素取最小值堆排序需要比較的次數(shù)為O(nlog2n)

(1)堆的示例

2022/12/27主講人：李書舉1001.7.2.4交換排序交換排序的特點(diǎn)在于交換。有冒泡和快速排序兩種。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較，大則交換，……關(guān)鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換到第n-1個位置上；依次類推，則完成排序。2022/12/27主講人：李書舉101第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字思想：小的浮起，大的沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252525排序n個記錄最多需要n-1趟冒泡排序正序：比較次數(shù)為O(n-1)

逆序：比較次數(shù)為O(n(n-1)/2)

適合于數(shù)據(jù)較少的情況。

2022/12/27主講人：李書舉1022、快速排序(對冒泡排序的改進(jìn)）思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達(dá)到整個序列有序。時間復(fù)雜度：O(log2n)當(dāng)待排序列逆序時，蛻變成冒泡排序，時間復(fù)雜度:O(n(n-1)/2)2022/12/27主講人：李書舉1031.7.2.5內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點(diǎn)，故在不同情況下可作不同的選擇。通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大??；記錄的鍵值分布情況等。若待排序的記錄個數(shù)n較小時，可采用簡單排序方法。若n較大時，應(yīng)采用快速排序或堆排序。若待排序的記錄已基本有序，可采用簡單插入和起泡排序。2022/12/27主講人：李書舉104方法歸并排序簡單插入希爾排序簡單選擇堆排序起泡排序快速排序插入選擇交換比較次數(shù)使用建議查找:方法順序折半比較次數(shù)log2n最好:1最壞:n平均:(n+1)/2使用條件順序存儲結(jié)構(gòu)的有序表任何表排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2log2nn(n-1)/2正序的表、n小的表與表的初始數(shù)據(jù)無關(guān)、n小的表正序的表、n小的表n大的表,但逆序的表會蛻變?yōu)槠鹋菖判蚪柚o助空間最多的方法n大的表2022/12/27主講人：李書舉105在長度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為

【2】。長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為【1】

。假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為

A)log2n B)n2C)O(n1..5) D)n(n-1)/2已知數(shù)據(jù)表A中每個元素距其最終位置不遠(yuǎn)，為節(jié)省時間，應(yīng)采用的算法是

A)堆排序B)直接插入排序C)快速排序D)直接選擇排序例題講解log2nn/22022/12/27主講人：李書舉106

冒泡排序算法在最好的情況下的元素交換次數(shù)為【1】

。在最壞情況下，堆排序需要比較的次數(shù)為

【2】。最簡單的交換排序方法是

A)快速排序 B)選擇排序C)堆排序 D)冒泡排序排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見的排序方法有插入排序、【1】

和選擇排序等。0nlog2n交換排序2022/12/27主講人：李書舉107在下列幾種排序方法中，要求內(nèi)存量最大的是

A)插入排序B)選擇排序C)快速排序 D)歸并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A)冒泡排序B)選擇排序C)快速排序D)歸并排序

希爾排序?qū)儆?/p>

A)交換排序B)歸并排序C)選擇排序 D)插入排序?qū)﹂L度為n的線性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)為Ａ)n+1B)nC)(n+1)/2D)n/22022/12/27主講人：李書舉1082.程序設(shè)計(jì)基礎(chǔ)2022/12/27主講人：李書舉1092.1程序設(shè)計(jì)方法與風(fēng)格2.1.1程序設(shè)計(jì)方法結(jié)構(gòu)化設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法2022/12/27主講人：李書舉1101.源程序的文檔化符號的命名:見名知意注釋（序言性和功能性注釋）程序的視覺組織:空格、空行、縮進(jìn)。。。。2.數(shù)據(jù)說明數(shù)據(jù)說明的次序應(yīng)該規(guī)范化變量安排有序化對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明3.語句的結(jié)構(gòu)每條語句簡單明了盡量不用或少用GOTO語句盡量只采用3種基本控制結(jié)構(gòu)編程4.輸入和輸出對所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查輸入輸出格式保持一致設(shè)計(jì)良好的輸出報表清晰第一，效率第二2.1.2程序設(shè)計(jì)風(fēng)格2022/12/27主講人：李書舉1112.2結(jié)構(gòu)化程序設(shè)計(jì)2.2.1基本概念★基本思想

對大型的程序設(shè)計(jì)，使用一些基本的結(jié)構(gòu)來設(shè)計(jì)程序，無論多復(fù)雜的程序，都可以使用這些基本結(jié)構(gòu)按一定的順序組合起來。這些基本結(jié)構(gòu)的特點(diǎn)都是只有一個入口、一個出口。由這些基本結(jié)構(gòu)組成的程序就避免了任意轉(zhuǎn)移、閱讀起來需要來回尋找的問題。三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)三種基本結(jié)構(gòu)的特點(diǎn)只有一個入口只有一個出口每一個基本結(jié)構(gòu)中的每一部分都有機(jī)會執(zhí)行到結(jié)構(gòu)內(nèi)不存在“死循環(huán)”2022/12/27主講人：李書舉1122.2.2設(shè)計(jì)原則自頂向下（先總體，后細(xì)節(jié)）逐步求精（設(shè)計(jì)子目標(biāo)過渡）模塊化（分解總目標(biāo)）限制使用goto語句★結(jié)構(gòu)化程序設(shè)計(jì)方法特點(diǎn)要求把程序的結(jié)構(gòu)規(guī)定為順序、選擇和循環(huán)三種基本機(jī)構(gòu)，并提出了自頂向下、逐步求精、模塊化程序設(shè)計(jì)等原則。結(jié)構(gòu)化程序設(shè)計(jì)是把模塊分割方法作為對大型系統(tǒng)進(jìn)行分析的手段，使其最終轉(zhuǎn)化為三種基本結(jié)構(gòu)，其目的是為了解決由許多人共同開發(fā)大型軟件時，如何高效率地完成可靠系統(tǒng)的問題。缺點(diǎn)：程序和數(shù)據(jù)結(jié)構(gòu)松散地耦合在一起。解決此問題的方法就是采用面向?qū)ο蟮某绦蛟O(shè)計(jì)方法(OOP)。2022/12/27主講人：李書舉1132.3面向?qū)ο蟮某绦蛟O(shè)計(jì)方法2.3.1關(guān)于面向?qū)ο蠓椒▽ο到y(tǒng)的復(fù)雜性進(jìn)行概括、抽象和分類，使軟件的設(shè)計(jì)與現(xiàn)實(shí)形成一個由抽象到具體、由簡單到復(fù)雜這樣一個循序漸進(jìn)的過程，從而解決大型軟件研制中存在的效率低、質(zhì)量難以保證、調(diào)試復(fù)雜、維護(hù)困難等問題。結(jié)構(gòu)化的分解突出過程，即如何做(Howtodo)?它強(qiáng)調(diào)代碼的功能是如何實(shí)現(xiàn)的；面向?qū)ο蟮姆纸馔怀霈F(xiàn)實(shí)世界和抽象的對象，即做什么(Whattodo)?主要優(yōu)點(diǎn)與人類習(xí)慣的思維方法一致穩(wěn)定性好可重用性好可維護(hù)性好易于開發(fā)大型軟件產(chǎn)品2022/12/27主講人：李書舉1142.3.2基本概念對象(Object)對象是基本的運(yùn)行時認(rèn)得實(shí)體，它既包括數(shù)據(jù)（屬性），也包括作用于數(shù)據(jù)的操作（行為）。一個對象把屬性和行為封裝為一個整體一個對象通?？捎蓪ο竺?、屬性和操作3部分組成對象的基本特性：（1）標(biāo)識唯一性（對象可區(qū)分）（2）分類性（對象抽象成類）（3）多態(tài)性（同一操作可以是不同對象的行為）（4）封裝性（只能看到對象的外部特性）（5）模塊獨(dú)立性好（對象內(nèi)部各元素結(jié)合緊密、內(nèi)聚性強(qiáng)）2022/12/27主講人：李書舉