版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
二級公共基礎(chǔ)知識(shí)授課時(shí)間:2019年4月1二級公共基礎(chǔ)知識(shí)授課時(shí)間:2019年4
一、涉及面廣,但難度小你應(yīng)該知道
公共基礎(chǔ)知識(shí)考題特點(diǎn)計(jì)算機(jī)等級二級理論考試中有關(guān)公共知識(shí)部分的題目共有15道,涉及算法及數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)基礎(chǔ)、軟件工程基礎(chǔ)和數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)等四門學(xué)科,但是從整體上分析,考試中的考核內(nèi)容的難度不大,考點(diǎn)也相對集中些。2一、涉及面廣,但難度小你應(yīng)該知道公共基礎(chǔ)知識(shí)考題特點(diǎn)二、考核重點(diǎn)為基本概念、基本方法和基本運(yùn)算你應(yīng)該知道
計(jì)算機(jī)等級二級理論考試中涉及的題目都是基本概念、基本方法和基本運(yùn)算,考核以概念和認(rèn)識(shí)性內(nèi)容為主,理解性、應(yīng)用性內(nèi)容極少。
3二、考核重點(diǎn)為基本概念、基本方法你應(yīng)該知道計(jì)三、考核重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法你應(yīng)該知道
以下是對以往二級理論考試的大概統(tǒng)計(jì):
算法及數(shù)據(jù)結(jié)構(gòu):50%程序設(shè)計(jì)基礎(chǔ):12.5%軟件工程基礎(chǔ):18.75%數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ):18.75%4三、考核重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法你應(yīng)該知道以下是你應(yīng)該知道共講授
12個(gè)學(xué)時(shí),具體安排如下:數(shù)據(jù)結(jié)構(gòu)與算法(4學(xué)時(shí)
)程序設(shè)計(jì)基礎(chǔ)、軟件工程基礎(chǔ)(4學(xué)時(shí))
數(shù)據(jù)庫系統(tǒng)、真題講解(4學(xué)時(shí))
本課程授課安排5你應(yīng)該知道共講授12個(gè)學(xué)時(shí),具體安排如下:本課1、了解算法的基本概念和一些常用的算法,學(xué)會(huì)計(jì)算算法的時(shí)間復(fù)雜度;2、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念,并了解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu),學(xué)會(huì)利用圖形的方式表示數(shù)據(jù)結(jié)構(gòu);學(xué)習(xí)目標(biāo)與要求算法與數(shù)據(jù)結(jié)構(gòu):3、了解線性表的基本概念,并掌握線性表的順序存儲(chǔ)結(jié)構(gòu)以及順序存儲(chǔ)的線性表的基本運(yùn)算;4、了解棧和隊(duì)列的基本概念,并掌握它們的基本運(yùn)算;5、了解線性鏈表的基本概念,并掌握線性鏈表的基本運(yùn)算,同時(shí),了解循環(huán)鏈表的基本概念和基本操作;
6、理解樹的概念,尤其是二叉樹的基本概念和相關(guān)性質(zhì),掌握二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷技術(shù);7、掌握查找技術(shù),學(xué)會(huì)利用順序查找和二分查找在數(shù)列中查找指定的數(shù)據(jù);8、學(xué)會(huì)利用相關(guān)的排序技術(shù)實(shí)現(xiàn)無序數(shù)列的排序操作。61、了解算法的基本概念和一些常用的算法,學(xué)會(huì)計(jì)算算法的時(shí)間復(fù)數(shù)據(jù)結(jié)構(gòu)與算法一、算法(algorithm)1、算法的基本概念
算法是指解題方案的準(zhǔn)確而完整的描述。它是指令的有限序列,其中每一條指令表示一個(gè)或多個(gè)操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的,且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性、確定性、可行性、輸入和輸出(擁有足夠的情報(bào))等5個(gè)重要特性。7數(shù)據(jù)結(jié)構(gòu)與算法一、算法(algorithm)1、算法的基本2、算法的基本要素對數(shù)據(jù)對象的運(yùn)算和操作:算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸算法中各操作之間的執(zhí)行順序;描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等;一個(gè)算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成。算法的控制結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)與算法82、算法的基本要素對數(shù)據(jù)對象的運(yùn)算和操作:算法中各操作之3、算法設(shè)計(jì)的基本方法列舉法歸納法遞推遞歸(以簡潔的形式設(shè)計(jì)和描述算法)減半遞推技術(shù)回溯法數(shù)據(jù)結(jié)構(gòu)與算法93、算法設(shè)計(jì)的基本方法列舉法數(shù)據(jù)結(jié)構(gòu)與算法9二、算法的復(fù)雜度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ù)雜度。數(shù)據(jù)結(jié)構(gòu)與算法10二、算法的復(fù)雜度1、時(shí)間復(fù)雜度依據(jù)算法編制的程序在計(jì)算機(jī)上二、算法的復(fù)雜度1、時(shí)間復(fù)雜度在同一問題規(guī)模下,如果算法執(zhí)行所需要的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí),可以用以下方法分析工作量:平均性態(tài)和最壞情況復(fù)雜性。數(shù)據(jù)結(jié)構(gòu)與算法11二、算法的復(fù)雜度1、時(shí)間復(fù)雜度在同一問題規(guī)模下,如果算法執(zhí)算法與數(shù)據(jù)結(jié)構(gòu)2、空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、
輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外,也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。12算法與數(shù)據(jù)結(jié)構(gòu)2、空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)算法與數(shù)據(jù)結(jié)構(gòu)3、例題講解算法的時(shí)間復(fù)雜度是指(C)A、執(zhí)行算法程序所需要的時(shí)間B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D、算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、
【1】和擁有足夠的情報(bào)。【答案】:有窮性算法的空間復(fù)雜度是指(D)
A)算法程序的長度 B)算法程序中的指令條數(shù)
C)算法程序所占的存儲(chǔ)空間
D)執(zhí)行過程中所需要的存儲(chǔ)空間√
√
13算法與數(shù)據(jù)結(jié)構(gòu)3、例題講解算法的時(shí)間復(fù)雜度是指(C)√算法與數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中,算法是指(B)
A)加工方法 B)解題方案的準(zhǔn)確而完整的描述
C)排序方法 D)查詢方法算法分析的目的是(D)
A)找出數(shù)據(jù)結(jié)構(gòu)的合理性
B)找出算法中輸入和輸出之間的關(guān)系
C)分析算法的易懂性和可靠性
D)分析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少分別稱為算法的【1】
?!敬鸢浮?時(shí)間復(fù)雜度和空間復(fù)雜度√
√
14算法與數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中,算法是指(B)算法分析的目算法與數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)(DataStructure)1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn):1、所處理的數(shù)據(jù)量大且具有一定的關(guān)系;2、對其操作不再是單純的數(shù)值計(jì)算,而更多地是需要對其進(jìn)行組織、管理和檢索。對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身,還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。15算法與數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)(DataStructure)特點(diǎn):每個(gè)學(xué)生的信息占據(jù)一行,所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格;表中每個(gè)學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系,這就是我們所說的線性結(jié)構(gòu);對它的操作通常是插入某個(gè)學(xué)生的信息,刪除某個(gè)學(xué)生的信息,更新某個(gè)學(xué)生的信息,按條件檢索某個(gè)學(xué)生的信息等等。應(yīng)用舉例1——學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。16特點(diǎn):應(yīng)用舉例1——學(xué)籍檔案管理16應(yīng)用舉例2——家庭血緣關(guān)系圖
表示家庭成員的輩分關(guān)系,使用下圖1-1所示的形式描述。圖1-1家庭血緣關(guān)系圖特點(diǎn):
在求解過程中,所處理的數(shù)據(jù)之間具有層次關(guān)系,這是我們所說的樹形結(jié)構(gòu);對它的操作有:建立樹形結(jié)構(gòu),輸出結(jié)點(diǎn)內(nèi)容等等。17應(yīng)用舉例2——家庭血緣關(guān)系圖圖1-1家庭血緣關(guān)應(yīng)用舉例3——制定教學(xué)計(jì)劃在制定教學(xué)計(jì)劃時(shí),需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程,有些課程則不需要,而有些課程又是其他課程的先導(dǎo)課程。比如,計(jì)算機(jī)專業(yè)課程的開設(shè)情況如下表所示:18這種數(shù)據(jù)可以用下面的圖來表示:18應(yīng)用舉例3——制定教學(xué)計(jì)劃18這種數(shù)據(jù)可以用下面的圖來表示課程先后關(guān)系的圖形描形式:c1c9c4c2c12c10c11c5c3c6c7c8圖1-2計(jì)算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系1919課程先后關(guān)系的圖形描形式:c1c9c4c2c12c10c11、數(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ǔ)線性表?xiàng)j?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面(亦稱物理結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)的主要研究問題:20201、數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算:2、基本概念和術(shù)語
數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。例:整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。計(jì)算機(jī)管理圖書問題:在圖書館里有各種卡片:有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短,又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表,每一本書的信息在表中占一行,如:21212、基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)數(shù)據(jù)元素在計(jì)算機(jī)中的表示
數(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ù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理(插入、刪除、修改、查找、排序)2222數(shù)據(jù)元素在計(jì)算機(jī)中的表示數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位,即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(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)系的集合2323數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)可描述為Group=(D,R)例1:一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成
B=(D,R) D={春,夏,秋,冬} R={(春,夏),(夏,秋),(秋,冬)}
例2:家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成 B=(D,R) D={父親,兒子,女兒} R={(父親,兒子),(父親,女兒)}冬春夏秋父親兒子女兒24數(shù)據(jù)結(jié)構(gòu)可描述為Group=(D,R)例1:一年四季的數(shù)數(shù)據(jù)結(jié)構(gòu)也可用圖形表示一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬春夏秋父親兒子女兒(概念:結(jié)點(diǎn)、前件、后件、根結(jié)點(diǎn)、葉子)25數(shù)據(jù)結(jié)構(gòu)也可用圖形表示一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成冬春夏秋父親樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)。26樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典HGFECDBA樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA27HGFEDA樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBC1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}
213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}
圖形結(jié)構(gòu)——節(jié)點(diǎn)間的連結(jié)是任意的281423D={1,2,3,4}213D={3、例題講解數(shù)據(jù)處理的最小單位是(C)
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)
A)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
B)計(jì)算方法
C)數(shù)據(jù)映象D)邏輯存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的
【4】
以及對數(shù)據(jù)的操作運(yùn)算?!敬鸢浮课锢斫Y(jié)構(gòu)(或存儲(chǔ)結(jié)構(gòu))293、例題講解數(shù)據(jù)處理的最小單位是(C)29線性結(jié)構(gòu)與非線性結(jié)構(gòu):線性結(jié)構(gòu):有且只有一個(gè)根結(jié)點(diǎn);每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件。如:一年四季,26個(gè)英文字母非線性結(jié)構(gòu):線性以外的數(shù)據(jù)結(jié)構(gòu)。如:反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)
算法與數(shù)據(jù)結(jié)構(gòu)30線性結(jié)構(gòu)與非線性結(jié)構(gòu):算法與數(shù)據(jù)結(jié)構(gòu)304、線性表(LinearList)學(xué)生成績表(按成績排列)86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號
線性表——結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié):線性表:具有線性結(jié)構(gòu)的有限序列。數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號,即數(shù)據(jù)元素之間的相對位置是線性的。314、線性表(LinearList)學(xué)生成績線性表的定義:
線性表是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ù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運(yùn)算有:初始化、求長度、取元素、修改、前插、刪除、檢索、排序3232線性表的定義:線性表的特點(diǎn):3232線性表的順序存儲(chǔ)結(jié)構(gòu)
及其插入
與刪除
操作特點(diǎn):
1、線性表中數(shù)據(jù)元素類型一致,只有數(shù)據(jù)域,存儲(chǔ)空間利用率高。2、所有元素所占的存儲(chǔ)空間是連續(xù)的。3、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的(a)做插入、刪除時(shí)需移動(dòng)大量元素。(b)空間估計(jì)不明時(shí),按最大空間分配。算法與數(shù)據(jù)結(jié)構(gòu)33線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除操作特點(diǎn):算順序存儲(chǔ)存儲(chǔ)地址存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)×mLo+(n-1)×mLoc(元素i)=Lo+(i-1)×m每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)
線性表的順序存儲(chǔ)結(jié)構(gòu):首地址起始地址基地址34順序存儲(chǔ)存儲(chǔ)地址存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元元素a1元素a2……..元素ai+1……..01i線性表的順序存儲(chǔ)結(jié)構(gòu)——可用C語言中的一維數(shù)組來描述.第i個(gè)元素的ai存儲(chǔ)地址:Loc(ai)=Loc(a1)+(i-1)*mV[0]V[1]V[i]V[m-1]intV[M];
其中:V是數(shù)組的名字,M是數(shù)組大小,假設(shè)數(shù)組中的元素是整型類型算法與數(shù)據(jù)結(jié)構(gòu)35元素a1元素a2……..元素ai+1……..01i線性插入運(yùn)算…..a2a1an…..ai+1ai01i-1in-1ai-1…..a2a1alength
…ai+1ai
x
ai-1…..
a2
a1
X
aiai+1…..alength插入算法的分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素,在進(jìn)行插入操作時(shí),若假定在n+1個(gè)位置上插入元素的可能性均等,則平均移動(dòng)元素的個(gè)數(shù)為:3636插入運(yùn)算…..a2a1an…..ai+1ai01i-1in-在進(jìn)行刪除操作時(shí),若假定刪除每個(gè)元素的可能性均等,則平均移動(dòng)元素的個(gè)數(shù)為:分析結(jié)論順序存儲(chǔ)結(jié)構(gòu)表示的線性表,在做插入或刪除操作時(shí),平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大,并且經(jīng)常要對其做插入或刪除操作時(shí),這一點(diǎn)需要值得考慮。刪除算法的分析3737在進(jìn)行刪除操作時(shí),若假定刪除每個(gè)元素的可能性均等,刪除算法的線性表的例題講解順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置
【1】
的存儲(chǔ)單元中?!敬鸢浮肯噜忛L度為n的順序存儲(chǔ)線性表中,當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí),插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為【2】?!敬鸢浮?/p>
n/2線性表L=(a1,a2,a3,…ai,…an),下列說法正確的是(D)
A)每個(gè)元素都有一個(gè)直接前件和直接后件
B)線性表中至少要有一個(gè)元素
C)表中諸元素的排列順序必須是由小到大或由大到小
D)除第一個(gè)元素和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件√
3838線性表的例題講解順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(C)
A)存儲(chǔ)結(jié)構(gòu) B)物理結(jié)構(gòu)
C)邏輯結(jié)構(gòu)
D)物理和存儲(chǔ)結(jié)構(gòu)下列敘述中,錯(cuò)誤的是(B)
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)是指(B)A)數(shù)據(jù)所占的存儲(chǔ)空間B)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C)數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D)存儲(chǔ)在外存中的數(shù)據(jù)39數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(C)39根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度,一般將數(shù)據(jù)結(jié)構(gòu)分成(C)
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)有線性結(jié)構(gòu)和【2】兩大類。非線性結(jié)構(gòu)當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí),其主要特點(diǎn)是【1】?!敬鸢浮窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰。404040405、堆棧和隊(duì)列堆棧和隊(duì)列的定義棧和隊(duì)列是兩種特殊的線性表,它們是運(yùn)算時(shí)要受到某些限制的線性表,故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。堆棧的定義堆棧:限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出。設(shè)棧s=(a1,a2,…ai,…,an),其中a1是棧底元素,an是棧頂元素。棧頂(top):允許插入和刪除的一端;約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底(bottom):不允許插入和刪除的一端。
a1
a2….
an進(jìn)棧出棧棧頂棧底41415、堆棧和隊(duì)列堆棧和隊(duì)列的定義棧和隊(duì)列是兩種隊(duì)列的定義隊(duì)列:一種特殊的線性結(jié)構(gòu),限定只能在表的一端進(jìn)行插入,在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出(FIFO)表。
a1,
a2,
a3,
a4,…………
an-1,
an隊(duì)列示意圖隊(duì)頭隊(duì)尾隊(duì)列的主要運(yùn)算(1)設(shè)置一個(gè)空隊(duì)列;(2)插入一個(gè)新的隊(duì)尾元素,稱為進(jìn)隊(duì);(3)刪除隊(duì)頭元素,稱為出隊(duì);(4)讀取隊(duì)頭元素;4242隊(duì)列的定義隊(duì)列:一種特殊的線性結(jié)構(gòu),限定只能在表的一端進(jìn)行堆棧和隊(duì)列的例題講解棧和隊(duì)列的共同特點(diǎn)是(C)
A)都是先進(jìn)先出
B)都是先進(jìn)后出
C)只允許在端點(diǎn)處插入和刪除元素
D)沒有共同點(diǎn)如果進(jìn)棧序列為e1,e2,e3,e4,則可能的出棧序列是(B)
A)e3,e1,e4,e2B)e4,e3,e2,e1
C)e3,e4,e1,e2 D)任意順序一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用(A)
A)棧
B)堆C)數(shù)組 D)鏈表√
√
√
4343堆棧和隊(duì)列的例題講解棧和隊(duì)列的共同特點(diǎn)是(C)√√棧底至棧頂依次存放元素A、B、C、D,在第五個(gè)元素E入棧前,棧中元素可以出棧,則出棧序列可能是(B)
A)ABCED B)DCBEA
C)DBCEA D)CDABE棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是(A)
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】。【答案】鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)下列數(shù)據(jù)結(jié)構(gòu)中,按先進(jìn)后出原則組織數(shù)據(jù)的是(B)
A)線性鏈表B)棧
C)循環(huán)鏈表 D)順序表√
√
√
4444棧底至棧頂依次存放元素A、B、C、D,在第五個(gè)元素E√√當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【2】。答案:上溢由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是(B)
A)減少存取時(shí)間,降低下溢發(fā)生的機(jī)率
B)節(jié)省存儲(chǔ)空間,降低上溢發(fā)生的機(jī)率
C)減少存取時(shí)間,降低上溢發(fā)生的機(jī)率
D)節(jié)省存儲(chǔ)空間,降低下溢發(fā)生的機(jī)率下列關(guān)于棧的敘述中正確的是(
D)A)在棧中只能插入數(shù)據(jù)B)在棧中只能刪除數(shù)據(jù)C)棧是先進(jìn)先出的線性表D)棧是后進(jìn)先出的線性表下列關(guān)于隊(duì)列的敘述中正確的是(C)A)在隊(duì)列中只能插入數(shù)據(jù)B)在隊(duì)列中只能刪除數(shù)據(jù)C)隊(duì)列是先進(jìn)先出的線性表
D)隊(duì)列是后進(jìn)先出的線性表√
√
√
4545當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不順序存儲(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ò)充。存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元素14646順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu),將邏輯上相鄰的數(shù)據(jù)元6、線性鏈表線性鏈表的基本概念:
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊,每一小塊占若干字節(jié),通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)。算法與數(shù)據(jù)結(jié)構(gòu)476、線性鏈表線性鏈表的基本概念:算法與數(shù)據(jù)結(jié)構(gòu)47將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部:一部分稱為數(shù)據(jù)域,用于存儲(chǔ)數(shù)據(jù)元素的值;另一部分稱為指針域,用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(即存儲(chǔ)結(jié)點(diǎn)的地址),也就是指向后件結(jié)點(diǎn).線性鏈表中存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)如圖2.20所示4848將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部:線性鏈表中存儲(chǔ)結(jié)點(diǎn)的結(jié)1、比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小(每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成,所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯?chǔ)更多)。2、邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3、插入、刪除靈活(不必移動(dòng)節(jié)點(diǎn),只要改變節(jié)點(diǎn)中的指針)。4、查找結(jié)點(diǎn)時(shí)鏈?zhǔn)酱鎯?chǔ)要比順序存儲(chǔ)慢。鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn):算法與數(shù)據(jù)結(jié)構(gòu)491、比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn):算法與數(shù)據(jù)指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針。當(dāng)HEAD=NULL(或0)時(shí)稱為空表。對于線性鏈表,可以從頭指針開始,沿著各個(gè)結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。線性鏈表的邏輯結(jié)構(gòu)圖所示50指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為線性鏈表的邏輯結(jié)構(gòu)51515151線性鏈表的基本運(yùn)算:線性鏈表的運(yùn)算主要有以下幾個(gè):①在線性鏈表中包含指定元素的結(jié)點(diǎn)之前
插入一個(gè)新元素。②在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。③將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。52線性鏈表的基本運(yùn)算:線性鏈表的運(yùn)算主要有以下幾個(gè):52線性鏈表的插入
運(yùn)算:線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。為了要在線性鏈表中插入一個(gè)新元素,首先要給該元素分配一個(gè)新結(jié)點(diǎn),然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。算法與數(shù)據(jù)結(jié)構(gòu)53線性鏈表的插入運(yùn)算:線性鏈表的插入是指在鏈?zhǔn)酱?4545454
線性鏈表的刪除指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn),首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn),然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。線性鏈表的刪除運(yùn)算:算法與數(shù)據(jù)結(jié)構(gòu)55線性鏈表的刪除指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表的刪除56565656循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比,具有以下兩個(gè)特點(diǎn):①循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。②在循環(huán)鏈表中,所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。
循環(huán)鏈表:5757循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比,具有以下循在實(shí)際應(yīng)用中,循環(huán)鏈表與線性單鏈表相比主要有以下兩個(gè)方面的優(yōu)點(diǎn):①在循環(huán)鏈表中,只要指出表中任何一個(gè)結(jié)點(diǎn)的位置,就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)。②由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn),因此,在任何情況下,循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在,從而使空表與非空表的運(yùn)算統(tǒng)一。算法與數(shù)據(jù)結(jié)構(gòu)58在實(shí)際應(yīng)用中,循環(huán)鏈表與線性單鏈表相算法與數(shù)據(jù)結(jié)構(gòu)5鏈表不具有的特點(diǎn)是(B)A)不必事先估計(jì)存儲(chǔ)空間B)可隨機(jī)訪問任一元素C)插入刪除不需要移動(dòng)元素
D)所需空間與線性表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu),線性鏈表屬于【1】?!敬鸢浮看鎯?chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是(B)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)線性鏈表的例題講解5959鏈表不具有的特點(diǎn)是(B)線性鏈表的例題講解59591.6、樹與二叉樹:樹的基本概念:前面我們討論的線性表,棧、隊(duì)列和數(shù)組等都是線性結(jié)構(gòu)。而樹是一種非線性數(shù)據(jù)結(jié)構(gòu),它的每一個(gè)結(jié)點(diǎn),都可以有不止一個(gè)直接后繼,除根外的所有結(jié)點(diǎn),都有且只有一個(gè)直接前趨。這些數(shù)據(jù)結(jié)點(diǎn)按分支關(guān)系組織起來,清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。601.6、樹與二叉樹:樹的基本概念:60算法與數(shù)據(jù)結(jié)構(gòu)現(xiàn)實(shí)世界中,能用樹的結(jié)構(gòu)表示的例子:學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。61算法與數(shù)據(jù)結(jié)構(gòu)現(xiàn)實(shí)世界中,能用樹的結(jié)構(gòu)表示的例子:616262626263636363有關(guān)樹的幾個(gè)概念根結(jié)點(diǎn)、葉子結(jié)點(diǎn)、結(jié)點(diǎn)的孩子與父結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層次、樹的深度、子樹、森林等。6464有關(guān)樹的幾個(gè)概念根結(jié)點(diǎn)、葉子結(jié)點(diǎn)、結(jié)點(diǎn)的孩子與父結(jié)點(diǎn)、結(jié)點(diǎn)
二叉樹(binarytree)是一種很有用的非線性結(jié)構(gòu)。二叉樹具有以下兩個(gè)特點(diǎn):(1)非空二叉樹只有一個(gè)根結(jié)點(diǎn);(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹,且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹(BinaryTree):因?yàn)闃涞拿總€(gè)結(jié)點(diǎn)的度不同,存儲(chǔ)困難,使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論6565二叉樹(binarytree)是一種很有用的非線二叉樹66666666性質(zhì)1:二叉樹的第k層上至多有2k-1(i1)個(gè)結(jié)點(diǎn)二叉樹的性質(zhì):423167891011121314155第三層上(i=3),有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4),有24-1=8個(gè)節(jié)點(diǎn)。67性質(zhì)1:二叉樹的第k層上至多有2k-1(i1)個(gè)結(jié)點(diǎn)二二叉樹的性質(zhì):性質(zhì)2:深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)423167891011121314155此樹的深度h=4,共有24-1=15個(gè)節(jié)點(diǎn)。68二叉樹的性質(zhì):性質(zhì)2:深度為h的二叉樹中至多含有2h-1個(gè)結(jié)性質(zhì)3:在任意一棵二叉樹中,度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。例1:某二叉樹中度為2的結(jié)點(diǎn)有18個(gè),則該二叉樹中有
19個(gè)葉子結(jié)點(diǎn)。二叉樹的性質(zhì):6969性質(zhì)3:在任意一棵二叉樹中,度為0的結(jié)點(diǎn)二叉樹的性質(zhì):69滿二叉樹與完全二叉樹滿二叉樹是指除最后一層外,每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹是指這樣的二叉樹:除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)。注意:滿二叉樹是完全二叉樹,完全二叉樹不一定是滿二叉樹。算法與數(shù)據(jù)結(jié)構(gòu)70滿二叉樹與完全二叉樹滿二叉樹是指除最后一層外,每一層上滿二叉樹的特點(diǎn):每一層上都含有最大結(jié)點(diǎn)數(shù)。7171滿二叉樹的特點(diǎn):7171完全二叉樹的特點(diǎn):除最后一層外,每一層都取最大結(jié)點(diǎn)數(shù),最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置7272完全二叉樹的特點(diǎn):除最后一層外,每一層都取最大結(jié)點(diǎn)數(shù),最對于完全二叉樹而言如果它的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù),則該二叉樹中:
葉子結(jié)點(diǎn)的個(gè)數(shù)=非葉子結(jié)點(diǎn)的個(gè)數(shù)如果它的結(jié)點(diǎn)個(gè)數(shù)為奇數(shù),則該二叉樹中:
葉子結(jié)點(diǎn)的個(gè)數(shù)=非葉子結(jié)點(diǎn)的個(gè)數(shù)+1
(即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù)多一個(gè))規(guī)律總結(jié):算法與數(shù)據(jù)結(jié)構(gòu)73對于完全二叉樹而言規(guī)律總結(jié):算法與數(shù)據(jù)結(jié)構(gòu)73例題講解1、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn),則在該二叉樹中有
350個(gè)葉子結(jié)點(diǎn)。2、在深度為5的滿二叉樹中,葉子結(jié)點(diǎn)的個(gè)數(shù)為(C
)A)32B)31C)16D)15算法與數(shù)據(jù)結(jié)構(gòu)√
74例題講解1、設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn),則在該二叉樹二叉樹的存儲(chǔ)
二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)點(diǎn)由兩部分組成:數(shù)據(jù)域、指針域。其中指針域有兩個(gè):左指針域、右指針域因此二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表7575二叉樹的存儲(chǔ)二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。7575二叉樹的遍歷
二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為三種:前序遍歷、中序遍歷、后序遍歷。設(shè)訪問根結(jié)點(diǎn)記作V;遍歷根的左子樹記作L;遍歷根的右子樹記作R;
前序:
VLR(即根左右)
中序:
LVR(即左根右)后序:
LRV(即左右根)7676二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)777777771、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,
前序遍歷結(jié)果為ABDECF,則后序遍歷結(jié)果為:
DEBFCA
例題講解2、已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF,則該二叉樹的后序遍歷為(B)
A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG√
781、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,例題講解2、3、具有3個(gè)結(jié)點(diǎn)的二叉樹有(D)
A)2種形態(tài)B)4種形態(tài)
C)7種形態(tài)D)5種形態(tài)
4、設(shè)有下列二叉樹:
對此二叉樹前序遍歷的結(jié)果為(B)A)ZBTTCPXA B)ATBZXCTP
C)ZBTACTXPD)ATBZXCPT√
√
79793、具有3個(gè)結(jié)點(diǎn)的二叉樹有(D)√√79791.7、查找和排序:查找——又稱為檢索
查找算法的評價(jià)主要考慮算法的時(shí)間復(fù)雜性,既可以采用數(shù)量級的形式表示,也可以采用平均檢索(查找)長度,即在查找成功情況下的平均比較次數(shù)來表示。查找可分為順序查找和二分法查找兩種。算法與數(shù)據(jù)結(jié)構(gòu)801.7、查找和排序:查找——又稱為檢索算法與數(shù)據(jù)結(jié)構(gòu)80(a)順序查找:
順序查找又稱線性查找。它是一種最簡單、最基本的查找方法?;舅枷胧牵簭谋碇械谝粭l記錄開始,逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。若某個(gè)記錄的關(guān)鍵字和給定值相等,則查找成功;否則,若直至最后一個(gè)記錄,其關(guān)鍵字和給定值都不相等,則表明表中沒有所查記錄,查找不成功。算法與數(shù)據(jù)結(jié)構(gòu)81(a)順序查找:順序查找又稱線性查找。它是一種
二分查找又稱折半查找。作為二分查找對象的表必須是順序存儲(chǔ)的有序表,即各記錄的次序是按其關(guān)鍵字的大小順序(以下假定按從小到大的順序)排列的表。(b)二分查找:算法與數(shù)據(jù)結(jié)構(gòu)82二分查找又稱折半查找。作為二分查找對(b)二分查找:算
二分查找的具體做法是:先取表中間位置的記錄關(guān)鍵字與給定值比較。若相等,則查找成功;否則,若給定值比該記錄的關(guān)鍵字小,則給定值必在表的前半部分。在這前半部分中再取中間位置記錄的關(guān)鍵字進(jìn)行比較,就又可以排除這部分的一半。依次反復(fù)進(jìn)行,直到找到給定值或找完全表而找不到為止。
算法與數(shù)據(jù)結(jié)構(gòu)83二分查找的具體做法是:先取表中間位置的記錄關(guān)算法與
排序是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。通常數(shù)據(jù)對象有多個(gè)屬性域,即由多個(gè)數(shù)據(jù)成員組成,其中有一個(gè)屬性域可用來區(qū)分對象,作為排序依據(jù)。該域稱為關(guān)鍵字(key)。
排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。1.8排序(sort)84排序是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)1.8排序(a)交換類排序:交換類排序法:冒泡排序法:需要比較的次數(shù)為n(n-1)/2快速排序法:是對冒泡排序的改進(jìn),是目前內(nèi)部排序中速度最快的一種。算法與數(shù)據(jù)結(jié)構(gòu)85(a)交換類排序:交換類排序法:算法與數(shù)據(jù)結(jié)構(gòu)85(b)插入類排序:插入類排序的基本方法是:每步將一個(gè)待排序的對象,按其關(guān)鍵字大小,插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上,直到對象全部插入為止。簡單插入排序法:最壞情況需要n(n-1)/2次比較;希爾排序法:最壞情況需要O(n)次比較。算法與數(shù)據(jù)結(jié)構(gòu)86(b)插入類排序:插入類排序的基本方法是:每步將一(c)選擇類排序:選擇類排序的思想是:每一趟(例如,第i趟,i=0,1,…,n?2)在后面n?i個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最?。ㄉ?,若為降序,選出最大關(guān)鍵字)的對象,作為有序?qū)ο笮蛄械牡趇個(gè)對象。待到第n?2趟作完,待排序?qū)ο笾皇O?個(gè),不用再選了,結(jié)束排序。簡單選擇排序法,最壞情況需要n(n-1)/2次比較;堆排序法,最壞情況需要O(nlog2n)次比較。87(c)選擇類排序:選擇類排序的思想是:每一趟(例如,二級公共基礎(chǔ)知識(shí)授課時(shí)間:2019年4月88二級公共基礎(chǔ)知識(shí)授課時(shí)間:2019年4
一、涉及面廣,但難度小你應(yīng)該知道
公共基礎(chǔ)知識(shí)考題特點(diǎn)計(jì)算機(jī)等級二級理論考試中有關(guān)公共知識(shí)部分的題目共有15道,涉及算法及數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)基礎(chǔ)、軟件工程基礎(chǔ)和數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)等四門學(xué)科,但是從整體上分析,考試中的考核內(nèi)容的難度不大,考點(diǎn)也相對集中些。89一、涉及面廣,但難度小你應(yīng)該知道公共基礎(chǔ)知識(shí)考題特點(diǎn)二、考核重點(diǎn)為基本概念、基本方法和基本運(yùn)算你應(yīng)該知道
計(jì)算機(jī)等級二級理論考試中涉及的題目都是基本概念、基本方法和基本運(yùn)算,考核以概念和認(rèn)識(shí)性內(nèi)容為主,理解性、應(yīng)用性內(nèi)容極少。
90二、考核重點(diǎn)為基本概念、基本方法你應(yīng)該知道計(jì)三、考核重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法你應(yīng)該知道
以下是對以往二級理論考試的大概統(tǒng)計(jì):
算法及數(shù)據(jù)結(jié)構(gòu):50%程序設(shè)計(jì)基礎(chǔ):12.5%軟件工程基礎(chǔ):18.75%數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ):18.75%91三、考核重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法你應(yīng)該知道以下是你應(yīng)該知道共講授
12個(gè)學(xué)時(shí),具體安排如下:數(shù)據(jù)結(jié)構(gòu)與算法(4學(xué)時(shí)
)程序設(shè)計(jì)基礎(chǔ)、軟件工程基礎(chǔ)(4學(xué)時(shí))
數(shù)據(jù)庫系統(tǒng)、真題講解(4學(xué)時(shí))
本課程授課安排92你應(yīng)該知道共講授12個(gè)學(xué)時(shí),具體安排如下:本課1、了解算法的基本概念和一些常用的算法,學(xué)會(huì)計(jì)算算法的時(shí)間復(fù)雜度;2、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念,并了解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu),學(xué)會(huì)利用圖形的方式表示數(shù)據(jù)結(jié)構(gòu);學(xué)習(xí)目標(biāo)與要求算法與數(shù)據(jù)結(jié)構(gòu):3、了解線性表的基本概念,并掌握線性表的順序存儲(chǔ)結(jié)構(gòu)以及順序存儲(chǔ)的線性表的基本運(yùn)算;4、了解棧和隊(duì)列的基本概念,并掌握它們的基本運(yùn)算;5、了解線性鏈表的基本概念,并掌握線性鏈表的基本運(yùn)算,同時(shí),了解循環(huán)鏈表的基本概念和基本操作;
6、理解樹的概念,尤其是二叉樹的基本概念和相關(guān)性質(zhì),掌握二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷技術(shù);7、掌握查找技術(shù),學(xué)會(huì)利用順序查找和二分查找在數(shù)列中查找指定的數(shù)據(jù);8、學(xué)會(huì)利用相關(guān)的排序技術(shù)實(shí)現(xiàn)無序數(shù)列的排序操作。931、了解算法的基本概念和一些常用的算法,學(xué)會(huì)計(jì)算算法的時(shí)間復(fù)數(shù)據(jù)結(jié)構(gòu)與算法一、算法(algorithm)1、算法的基本概念
算法是指解題方案的準(zhǔn)確而完整的描述。它是指令的有限序列,其中每一條指令表示一個(gè)或多個(gè)操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的,且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性、確定性、可行性、輸入和輸出(擁有足夠的情報(bào))等5個(gè)重要特性。94數(shù)據(jù)結(jié)構(gòu)與算法一、算法(algorithm)1、算法的基本2、算法的基本要素對數(shù)據(jù)對象的運(yùn)算和操作:算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸算法中各操作之間的執(zhí)行順序;描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等;一個(gè)算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)組合而成。算法的控制結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)與算法952、算法的基本要素對數(shù)據(jù)對象的運(yùn)算和操作:算法中各操作之3、算法設(shè)計(jì)的基本方法列舉法歸納法遞推遞歸(以簡潔的形式設(shè)計(jì)和描述算法)減半遞推技術(shù)回溯法數(shù)據(jù)結(jié)構(gòu)與算法963、算法設(shè)計(jì)的基本方法列舉法數(shù)據(jù)結(jié)構(gòu)與算法9二、算法的復(fù)雜度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ù)雜度。數(shù)據(jù)結(jié)構(gòu)與算法97二、算法的復(fù)雜度1、時(shí)間復(fù)雜度依據(jù)算法編制的程序在計(jì)算機(jī)上二、算法的復(fù)雜度1、時(shí)間復(fù)雜度在同一問題規(guī)模下,如果算法執(zhí)行所需要的基本運(yùn)算次數(shù)取決于某一特定輸入時(shí),可以用以下方法分析工作量:平均性態(tài)和最壞情況復(fù)雜性。數(shù)據(jù)結(jié)構(gòu)與算法98二、算法的復(fù)雜度1、時(shí)間復(fù)雜度在同一問題規(guī)模下,如果算法執(zhí)算法與數(shù)據(jù)結(jié)構(gòu)2、空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、
輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外,也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。99算法與數(shù)據(jù)結(jié)構(gòu)2、空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)算法與數(shù)據(jù)結(jié)構(gòu)3、例題講解算法的時(shí)間復(fù)雜度是指(C)A、執(zhí)行算法程序所需要的時(shí)間B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)D、算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、
【1】和擁有足夠的情報(bào)。【答案】:有窮性算法的空間復(fù)雜度是指(D)
A)算法程序的長度 B)算法程序中的指令條數(shù)
C)算法程序所占的存儲(chǔ)空間
D)執(zhí)行過程中所需要的存儲(chǔ)空間√
√
100算法與數(shù)據(jù)結(jié)構(gòu)3、例題講解算法的時(shí)間復(fù)雜度是指(C)√算法與數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中,算法是指(B)
A)加工方法 B)解題方案的準(zhǔn)確而完整的描述
C)排序方法 D)查詢方法算法分析的目的是(D)
A)找出數(shù)據(jù)結(jié)構(gòu)的合理性
B)找出算法中輸入和輸出之間的關(guān)系
C)分析算法的易懂性和可靠性
D)分析算法的效率以求改進(jìn)算法的工作量大小和實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少分別稱為算法的【1】
?!敬鸢浮?時(shí)間復(fù)雜度和空間復(fù)雜度√
√
101算法與數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中,算法是指(B)算法分析的目算法與數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)(DataStructure)1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn):1、所處理的數(shù)據(jù)量大且具有一定的關(guān)系;2、對其操作不再是單純的數(shù)值計(jì)算,而更多地是需要對其進(jìn)行組織、管理和檢索。對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身,還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。102算法與數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)(DataStructure)特點(diǎn):每個(gè)學(xué)生的信息占據(jù)一行,所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格;表中每個(gè)學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系,這就是我們所說的線性結(jié)構(gòu);對它的操作通常是插入某個(gè)學(xué)生的信息,刪除某個(gè)學(xué)生的信息,更新某個(gè)學(xué)生的信息,按條件檢索某個(gè)學(xué)生的信息等等。應(yīng)用舉例1——學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。103特點(diǎn):應(yīng)用舉例1——學(xué)籍檔案管理16應(yīng)用舉例2——家庭血緣關(guān)系圖
表示家庭成員的輩分關(guān)系,使用下圖1-1所示的形式描述。圖1-1家庭血緣關(guān)系圖特點(diǎn):
在求解過程中,所處理的數(shù)據(jù)之間具有層次關(guān)系,這是我們所說的樹形結(jié)構(gòu);對它的操作有:建立樹形結(jié)構(gòu),輸出結(jié)點(diǎn)內(nèi)容等等。104應(yīng)用舉例2——家庭血緣關(guān)系圖圖1-1家庭血緣關(guān)應(yīng)用舉例3——制定教學(xué)計(jì)劃在制定教學(xué)計(jì)劃時(shí),需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程,有些課程則不需要,而有些課程又是其他課程的先導(dǎo)課程。比如,計(jì)算機(jī)專業(yè)課程的開設(shè)情況如下表所示:105這種數(shù)據(jù)可以用下面的圖來表示:105應(yīng)用舉例3——制定教學(xué)計(jì)劃18這種數(shù)據(jù)可以用下面的圖來表示課程先后關(guān)系的圖形描形式:c1c9c4c2c12c10c11c5c3c6c7c8圖1-2計(jì)算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系106106課程先后關(guān)系的圖形描形式:c1c9c4c2c12c10c11、數(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ǔ)線性表?xiàng)j?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面(亦稱物理結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)的主要研究問題:1071071、數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算:2、基本概念和術(shù)語
數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。例:整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。計(jì)算機(jī)管理圖書問題:在圖書館里有各種卡片:有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短,又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表,每一本書的信息在表中占一行,如:1081082、基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)數(shù)據(jù)元素在計(jì)算機(jī)中的表示
數(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ù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理(插入、刪除、修改、查找、排序)109109數(shù)據(jù)元素在計(jì)算機(jī)中的表示數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位,即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(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)系的集合110110數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)可描述為Group=(D,R)例1:一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成
B=(D,R) D={春,夏,秋,冬} R={(春,夏),(夏,秋),(秋,冬)}
例2:家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成 B=(D,R) D={父親,兒子,女兒} R={(父親,兒子),(父親,女兒)}冬春夏秋父親兒子女兒111數(shù)據(jù)結(jié)構(gòu)可描述為Group=(D,R)例1:一年四季的數(shù)數(shù)據(jù)結(jié)構(gòu)也可用圖形表示一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬春夏秋父親兒子女兒(概念:結(jié)點(diǎn)、前件、后件、根結(jié)點(diǎn)、葉子)112數(shù)據(jù)結(jié)構(gòu)也可用圖形表示一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成冬春夏秋父親樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)。113樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典HGFECDBA樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA114HGFEDA樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBC1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3),(3,4),(2,4)}
213D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}
圖形結(jié)構(gòu)——節(jié)點(diǎn)間的連結(jié)是任意的1151423D={1,2,3,4}213D={3、例題講解數(shù)據(jù)處理的最小單位是(C)
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)
A)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
B)計(jì)算方法
C)數(shù)據(jù)映象D)邏輯存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的
【4】
以及對數(shù)據(jù)的操作運(yùn)算?!敬鸢浮课锢斫Y(jié)構(gòu)(或存儲(chǔ)結(jié)構(gòu))1163、例題講解數(shù)據(jù)處理的最小單位是(C)29線性結(jié)構(gòu)與非線性結(jié)構(gòu):線性結(jié)構(gòu):有且只有一個(gè)根結(jié)點(diǎn);每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件。如:一年四季,26個(gè)英文字母非線性結(jié)構(gòu):線性以外的數(shù)據(jù)結(jié)構(gòu)。如:反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)
算法與數(shù)據(jù)結(jié)構(gòu)117線性結(jié)構(gòu)與非線性結(jié)構(gòu):算法與數(shù)據(jù)結(jié)構(gòu)304、線性表(LinearList)學(xué)生成績表(按成績排列)86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號
線性表——結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié):線性表:具有線性結(jié)構(gòu)的有限序列。數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號,即數(shù)據(jù)元素之間的相對位置是線性的。1184、線性表(LinearList)學(xué)生成績線性表的定義:
線性表是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ù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運(yùn)算有:初始化、求長度、取元素、修改、前插、刪除、檢索、排序119119線性表的定義:線性表的特點(diǎn):3232線性表的順序存儲(chǔ)結(jié)構(gòu)
及其插入
與刪除
操作特點(diǎn):
1、線性表中數(shù)據(jù)元素類型一致,只有數(shù)據(jù)域,存儲(chǔ)空間利用率高。2、所有元素所占的存儲(chǔ)空間是連續(xù)的。3、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的(a)做插入、刪除時(shí)需移動(dòng)大量元素。(b)空間估計(jì)不明時(shí),按最大空間分配。算法與數(shù)據(jù)結(jié)構(gòu)120線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除操作特點(diǎn):算順序存儲(chǔ)存儲(chǔ)地址存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)×mLo+(n-1)×mLoc(元素i)=Lo+(i-1)×m每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)
線性表的順序存儲(chǔ)結(jié)構(gòu):首地址起始地址基地址121順序存儲(chǔ)存儲(chǔ)地址存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元元素a1元素a2……..元素ai+1……..01i線性表的順序存儲(chǔ)結(jié)構(gòu)——可用C語言中的一維數(shù)組來描述.第i個(gè)元素的ai存儲(chǔ)地址:Loc(ai)=Loc(a1)+(i-1)*mV[0]V[1]V[i]V[m-1]intV[M];
其中:V是數(shù)組的名字,M是數(shù)組大小,假設(shè)數(shù)組中的元素是整型類型算法與數(shù)據(jù)結(jié)構(gòu)122元素a1元素a2……..元素ai+1……..01i線性插入運(yùn)算…..a2a1an…..ai+1ai01i-1in-1ai-1…..a2a1alength
…ai+1ai
x
ai-1…..
a2
a1
X
aiai+1…..alength插入算法的分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素,在進(jìn)行插入操作時(shí),若假定在n+1個(gè)位置上插入元素的可能性均等,則平均移動(dòng)元素的個(gè)數(shù)為:123123插入運(yùn)算…..a2a1an…..ai+1ai01i-1in-在進(jìn)行刪除操作時(shí),若假定刪除每個(gè)元素的可能性均等,則平均移動(dòng)元素的個(gè)數(shù)為:分析結(jié)論順序存儲(chǔ)結(jié)構(gòu)表示的線性表,在做插入或刪除操作時(shí),平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大,并且經(jīng)常要對其做插入或刪除操作時(shí),這一點(diǎn)需要值得考慮。刪除算法的分析124124在進(jìn)行刪除操作時(shí),若假定刪除每個(gè)元素的可能性均等,刪除算法的線性表的例題講解順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置
【1】
的存儲(chǔ)單元中?!敬鸢浮肯噜忛L度為n的順序存儲(chǔ)線性表中,當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí),插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為【2】?!敬鸢浮?/p>
n/2線性表L=(a1,a2,a3,…ai,…an),下列說法正確的是(D)
A)每個(gè)元素都有一個(gè)直接前件和直接后件
B)線性表中至少要有一個(gè)元素
C)表中諸元素的排列順序必須是由小到大或由大到小
D)除第一個(gè)元素和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件√
125125線性表的例題講解順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(C)
A)存儲(chǔ)結(jié)構(gòu) B)物理結(jié)構(gòu)
C)邏輯結(jié)構(gòu)
D)物理和存儲(chǔ)結(jié)構(gòu)下列敘述中,錯(cuò)誤的是(B)
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)是指(B)A)數(shù)據(jù)所占的存儲(chǔ)空間B)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C)數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式D)存儲(chǔ)在外存中的數(shù)據(jù)126數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(C)39根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度,一般將數(shù)據(jù)結(jié)構(gòu)分成(C)
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)有線性結(jié)構(gòu)和【2】兩大類。非線性結(jié)構(gòu)當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí),其主要特點(diǎn)是【1】?!敬鸢浮窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰。12712740405、堆棧和隊(duì)列堆棧和隊(duì)列的定義棧和隊(duì)列是兩種特殊的線性表,它們是運(yùn)算時(shí)要受到某些限制的線性表,故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。堆棧的定義堆棧:限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出。設(shè)棧s=(a1,a2,…ai,…,an),其中a1是棧底元素,an是棧頂元素。棧頂(top):允許插入和刪除的一端;約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底(bottom):不允許插入和刪除的一端。
a1
a2….
an進(jìn)棧出棧棧頂棧底1281285、堆棧和隊(duì)列堆棧和隊(duì)列的定義棧和隊(duì)列是兩種隊(duì)列的定義隊(duì)列:一種特殊的線性結(jié)構(gòu),限定只能在表的一端進(jìn)行插入,在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出(FIFO)表。
a1,
a2,
a3,
a4,…………
an-1,
an隊(duì)列示意圖隊(duì)頭隊(duì)尾隊(duì)列的主要運(yùn)算(1)設(shè)置一個(gè)空隊(duì)列;(2)插入一個(gè)新的隊(duì)尾元素,稱為進(jìn)隊(duì);(3)刪除隊(duì)頭元素,稱為出隊(duì);(4)讀取隊(duì)頭元素;129129隊(duì)列的定義隊(duì)列:一種特殊的線性結(jié)構(gòu),限定只能在表的一端進(jìn)行堆棧和隊(duì)列的例題講解棧和隊(duì)列的共同特點(diǎn)是(C)
A)都是先進(jìn)先出
B)都是先進(jìn)后出
C)只允許在端點(diǎn)處插入和刪除元素
D)沒有共同點(diǎn)如果進(jìn)棧序列為e1,e2,e3,e4,則可能的出棧序列是(B)
A)e3,e1,e4,e2B)e4,e3,e2,e1
C)e3,e4,e1,e2 D)任意順序一些重要的程序語言(如C語言和Pascal語言)允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用(A)
A)棧
B)堆C)數(shù)組 D)鏈表√
√
√
130130堆棧和隊(duì)列的例題講解棧和隊(duì)列的共同特點(diǎn)是(C)√√棧底至棧頂依次存放元素A、B、C、D,在第五個(gè)元素E入棧前,棧中元素可以出棧,則出棧序列可能是(B)
A)ABCED B)DCBEA
C)DBCEA D)CDABE棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是(A)
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】。【答案】鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)下列數(shù)據(jù)結(jié)構(gòu)中,按先進(jìn)后出原則組織數(shù)據(jù)的是(B)
A)線性鏈表B)棧
C)循環(huán)鏈表 D)順序表√
√
√
131131棧底至棧頂依次存放元素A、B、C、D,在第五個(gè)元素E√√當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【2】。答案:上溢由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是(B)
A)減少存取時(shí)間,降低下溢發(fā)生的機(jī)率
B)節(jié)省存儲(chǔ)空間,降低上溢發(fā)生的機(jī)率
C)減少存取時(shí)間,降低上溢發(fā)生的機(jī)率
D)節(jié)省存儲(chǔ)空間,降低下溢發(fā)生的機(jī)率下列關(guān)于棧的敘述中正確的是(
D)A)在棧中只能插入數(shù)據(jù)B)在棧中只能刪除數(shù)據(jù)C)棧是先進(jìn)先出的線性表D)棧是后進(jìn)先出的線性表下列關(guān)于隊(duì)列的敘述中正確的是(C)A)在隊(duì)列中只能插入數(shù)據(jù)B)在隊(duì)列中只能刪除數(shù)據(jù)C)隊(duì)列是先進(jìn)先出的線性表
D)隊(duì)列是后進(jìn)先出的線性表√
√
√
132132當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí),說明循環(huán)隊(duì)列已滿,不順序存儲(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ò)充。存儲(chǔ)內(nèi)容元素n……..元素i……..元素2元素1133133順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu),將邏輯上相鄰的數(shù)據(jù)元6、線性鏈表線性鏈表的基本概念:
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊,每一小塊占若干字節(jié),通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)。算法與數(shù)據(jù)結(jié)構(gòu)1346、線性鏈表線性鏈表的基本概念:算法與數(shù)據(jù)結(jié)構(gòu)47將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部:一部分稱為數(shù)據(jù)域,用于存儲(chǔ)數(shù)據(jù)元素的值;另一
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 單元檢測九 區(qū)域與區(qū)域發(fā)展
- 2024年MCL(BCL)系列離心壓縮機(jī)項(xiàng)目建議書
- 2024年雙偏振天氣雷達(dá)項(xiàng)目建議書
- 2024年飛行試驗(yàn)地面設(shè)備合作協(xié)議書
- 2024年航天器電源系統(tǒng)項(xiàng)目建議書
- 2024年三聚氰胺甲醛塑料項(xiàng)目合作計(jì)劃書
- 2024年極性微晶玻璃項(xiàng)目發(fā)展計(jì)劃
- 2024年14-丁二醇項(xiàng)目發(fā)展計(jì)劃
- 安徽省合肥市一中2023-2024學(xué)年高一上學(xué)期期末生物試題
- 鮮花店裝飾裝修協(xié)議
- 2024年國家電力投資集團(tuán)公司湖北分公司招聘24人高頻難、易錯(cuò)點(diǎn)500題模擬試題附帶答案詳解
- 第2章 第5節(jié) 科學(xué)探究:電容器2023-2024學(xué)年新教材高二物理必修第三冊同步課堂高效講義配套教學(xué)設(shè)計(jì)(魯科版2019)
- 電動(dòng)汽車充電設(shè)施及場站測試評價(jià)規(guī)范第1部分:總則
- 5.1 法不可違 課件-2024-2025學(xué)年統(tǒng)編版道德與法治八年級上冊
- 3.14 絲綢之路的開通與經(jīng)營西域 課件 2024-2025學(xué)年部編版
- 2023-2024學(xué)年北京西城區(qū)八中高三(上)期中數(shù)學(xué)試題及答案
- 人教版(2024)第一單元-識(shí)字《日月山川》教學(xué)課件
- 弘揚(yáng)民族精神 貢獻(xiàn)青春力量(2022年青海中考語文試卷議論文閱讀題及答案)
- 《大學(xué)美育》 課件 李然 模塊四 社會(huì)審美
- 江蘇省南京市2024-2025學(xué)年高三上學(xué)期第一次學(xué)情調(diào)研英語試題含答案
- 彈性力學(xué)仿真軟件:ANSYS:優(yōu)化設(shè)計(jì)與靈敏度分析技術(shù)教程
評論
0/150
提交評論