全國計(jì)算機(jī)等級(jí)考試《二級(jí)Java語言程序設(shè)計(jì)》專用教材【考綱分析+考點(diǎn)精講+真題演練+強(qiáng)化習(xí)題】

1、全國計(jì)算機(jī)等級(jí)考試二級(jí)Java語言程序設(shè)計(jì)專用教材【考綱分析+考點(diǎn)精講+真題演練+強(qiáng)化習(xí)題】最新資料，WORD式，可編輯修改！目錄第一部分公共基礎(chǔ)知識(shí)第1章數(shù)據(jù)結(jié)構(gòu)與算法考綱分析考點(diǎn)精講1.1 算法1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)1.4 棧和隊(duì)列1.5 線性鏈表1.6 樹與二叉樹1.7 查找技術(shù)1.8 排序技術(shù)強(qiáng)化習(xí)題第2章程序設(shè)計(jì)基礎(chǔ)考綱分析考點(diǎn)精講2.1 程序設(shè)計(jì)方法與風(fēng)格2.2 結(jié)構(gòu)化程序設(shè)計(jì)2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)強(qiáng)化習(xí)題第3章軟件工程基礎(chǔ)考綱分析考點(diǎn)精講3.1 軟件工程基本概念3.2 結(jié)構(gòu)化分析方法3.3 結(jié)構(gòu)化設(shè)計(jì)方法3.4 軟件測試3.5 程序的調(diào)試強(qiáng)化

2、習(xí)題第4章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)考綱分析考點(diǎn)精講4.1 數(shù)據(jù)庫系統(tǒng)的基本概念4.2 數(shù)據(jù)模型4.3 關(guān)系代數(shù)4.4 數(shù)據(jù)庫設(shè)計(jì)與管理強(qiáng)化習(xí)題第二部分Java語言程序設(shè)計(jì)第1章Java語言概論考綱分析考點(diǎn)精講1.1 Java語言簡介1.2 Java語言面向?qū)ο缶幊虖?qiáng)化習(xí)題第2章基本數(shù)據(jù)類型考綱分析考點(diǎn)精講2.1 概述2.2 基本數(shù)據(jù)類型2.3 引用數(shù)據(jù)類型2.4 Java類庫中對(duì)基本數(shù)據(jù)類型的對(duì)象包裝器（wrapper）類強(qiáng)化習(xí)題第3章運(yùn)算符和表達(dá)式考綱分析考點(diǎn)精講3.1 概述3.2 算術(shù)運(yùn)算符和算術(shù)表達(dá)式3.3 關(guān)系運(yùn)算符和關(guān)系表達(dá)式3.4 布爾邏輯運(yùn)算符和布爾邏輯表達(dá)式3.5 位運(yùn)算符和位運(yùn)算表達(dá)式

3、3.6 賦值運(yùn)算符和賦值表達(dá)式3.7 條件運(yùn)算符與條件表達(dá)式3.8 運(yùn)算符的優(yōu)先級(jí)和復(fù)雜表達(dá)式3.9 表達(dá)式語句強(qiáng)化習(xí)題第4章流程控制考綱分析考點(diǎn)精講4.1 概述4.2 分支（選擇）語句4.3 循環(huán)語句4.4 跳轉(zhuǎn)語句4.5 循環(huán)語句與分支語句的嵌套4.6 遞歸強(qiáng)化習(xí)題第5章Java的繼承、多態(tài)、高級(jí)類特性和數(shù)組考綱分析考點(diǎn)精講5.1 概述5.2 覆蓋方法5.3 重載方法5.4 高級(jí)類特性5.5 內(nèi)部類5.6 數(shù)組強(qiáng)化習(xí)題第6章異常和斷言考綱分析考點(diǎn)精講6.1 概述6.2 異常處理類型6.3 異常處理編程的提醒6.4 斷言強(qiáng)化習(xí)題第7章輸入輸出及文件操作考綱分析考點(diǎn)精講7.1 概述7.2 文件

4、7.3 字節(jié)流7.4 字符流7.5 對(duì)象流7.6 過濾流7.7 管道流7.8 不同流的速度比較7.9 輸入輸出流和正則表達(dá)式7.10 JavaI/O流的其他應(yīng)用強(qiáng)化習(xí)題第8章線程考綱分析考點(diǎn)精講8.1 概述8.2 線程的創(chuàng)建8.3 線程的調(diào)度與控制8.4 線程同步8.5 線程狀態(tài)與生命周期8.6 線程相關(guān)的其他類與方法強(qiáng)化習(xí)題第9章編寫圖形用戶界面考綱分析考點(diǎn)精講9.1 概述9.2 用AWTS寫圖形用戶界面9.3 AWW件處理模型9.4 AWT1件庫9.5 用Swing編寫圖形用戶界面9.6 Swing組件和容器9.7 Swing的事件處理機(jī)制強(qiáng)化習(xí)題第10章Applet程序設(shè)計(jì)考綱分析考點(diǎn)精

5、講10.1 Applet的基本概念10.2 Applet的編寫10.3 Applet中的圖形化用戶界面GUI10.4 Applet的多媒體支持10.5 Applet與工作環(huán)境的通信強(qiáng)化習(xí)題第11章集合與泛型考綱分析考點(diǎn)精講11.1 概述11.2 集合框架11.3 簡單集合類11.4 泛型強(qiáng)化習(xí)題第12章JavaSDK6.0的下載和操作考綱分析考點(diǎn)精講12.1 JavaSDK6.0的下載與安裝12.2 JavaSDK6.0的操作命令12.3 Java編程規(guī)范強(qiáng)化習(xí)題第一部分公共基礎(chǔ)知識(shí)第1章數(shù)據(jù)結(jié)構(gòu)與算法考綱分析1 .算法的基本概念，算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）2 .數(shù)據(jù)結(jié)構(gòu)

6、的定義，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3 .線性表的定義，線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4 .棧和隊(duì)列的定義，棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5 .線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6 .樹的基本概念，二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。7 .順序查找與二分法查找算法，基本排序算法（交換類排序，選擇類排序,插入類排序）。考點(diǎn)精講1.1算法考點(diǎn)1算法的基本概念（1）算法的定義算法是指解題方案的準(zhǔn)確而完整的描述，即算法是對(duì)特定問題求解步驟的一種描述。它是一組嚴(yán)謹(jǐn)定義運(yùn)算順序的規(guī)則，且每個(gè)規(guī)則都是明確有效的

7、，此順序?qū)⒃谟邢薜拇螖?shù)下終止。需要注意的是：算法不等于程序，也不等于計(jì)算方法。（2）算法的基本特征可行性a.算法中的每一步驟都必須能夠?qū)崿F(xiàn)；b.算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。確定性確定性是指算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋，也不允許有多義性。有窮性有窮性是指算法必須能在有限的時(shí)間內(nèi)做完，即必須能在執(zhí)行有限個(gè)步驟之后終止，且必須有合理的執(zhí)行時(shí)間。擁有足夠的情報(bào)算法是否有效，取決于為算法所提供的情報(bào)是否足夠。一般而言，當(dāng)算法有足夠的情報(bào)時(shí)，此算法有效，而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效?！菊骖}演練】算法的有窮性是指（）。2013年9月真題A.算法程序的運(yùn)行時(shí)間是有

8、限的B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長度是有限的D.算法只能被有限的用戶使用【答案】A【解析】算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長時(shí)間得到的正確結(jié)果是沒有意義的?？键c(diǎn)2算法設(shè)計(jì)基本方法(1)列舉法基本思想根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗(yàn)?zāi)男┦切枰模男┦遣恍枰?。常用于解決“是否存在”或“有多少種可能”等類型的問題。主要特點(diǎn)算法比較簡單，但列舉情況較多時(shí)，算法工作量很大。注意事項(xiàng)例舉算法時(shí)，通過對(duì)實(shí)際問題進(jìn)行詳細(xì)分析，將與問題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，并從中找出規(guī)律，或?qū)λ锌赡艿那闆r進(jìn)行分類，從而引出一些有用的信

9、息，減少列舉量。(2)歸納法基本思想通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。主要特點(diǎn)a.比列舉法更能反映問題的本質(zhì)，可解決列舉量為無限的問題；b.可操作性低，不易歸納出一個(gè)具體數(shù)學(xué)模型；c.歸納得出的結(jié)論只是一種猜測，須對(duì)這種猜測加以必要的證明。(3)遞推基本思想從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。主要特點(diǎn)a.初始條件或問題本身已給定，或通過對(duì)問題的分析化簡得到；b.遞推本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果；c.數(shù)值型遞推算法計(jì)算過程中必須注意數(shù)值計(jì)算的穩(wěn)定性問題。(4)遞歸基本思想將復(fù)雜問題逐層分解，歸結(jié)為一些簡單的問題，將簡單問題解決掉，再沿著

10、原來分解的逆過程逐步進(jìn)行綜合。主要特點(diǎn)a.遞歸的基礎(chǔ)是歸納，對(duì)問題逐層分解的過程實(shí)際上并沒有對(duì)問題進(jìn)行求解；b.在可計(jì)算性理論和算法設(shè)計(jì)中占有重要地位；c.遞歸算法比遞推算法清晰易讀，結(jié)構(gòu)簡練；d.設(shè)計(jì)遞歸算法比遞推算法容易，但是其執(zhí)行效率較低。分類a.直接遞歸。一個(gè)算法P顯式地調(diào)用自己。b.間接遞歸。算法P調(diào)用另一個(gè)算法Q,而算法Q又調(diào)用算法P。遞歸與遞推的區(qū)別遞歸與遞推的區(qū)別主要在于二者實(shí)現(xiàn)方法的不同，表現(xiàn)為：a.遞歸是從算法本身到達(dá)遞歸的邊界的；b.遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果。(5)減半遞推技術(shù)減半遞推技術(shù)是工程上常用的分治法，其中，“減半”指將問題的規(guī)模減半，而問題的性

11、質(zhì)不變；“遞推”指重復(fù)“減半”的過程。(6)回溯法回溯法是指通過對(duì)問題的分析，找出一個(gè)解決問題的線索，然后沿著這個(gè)線索逐步試探，若試探成功，則問題得到解決，若試探失敗，則逐步回退換別的路線再進(jìn)行試探?！菊骖}演練】1.下列敘述中正確的是()。2013年9月真題A.所謂算法就是計(jì)算方法B.程序可以作為算法的一種描述方法C.算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果D.算法設(shè)計(jì)可以忽略算法的運(yùn)算時(shí)間【答案】B【解析】程序可以作為算法的一種描述方法，算法在實(shí)現(xiàn)時(shí)需要用具體的程序設(shè)計(jì)語言描述。A項(xiàng)錯(cuò)誤，算法并不等同于計(jì)算方法，是指對(duì)解題方案的準(zhǔn)確而完整的描述；C項(xiàng)錯(cuò)誤，算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情

12、報(bào)；D項(xiàng)錯(cuò)誤，算法設(shè)計(jì)有窮性要求操作步驟有限且必須在有限時(shí)間內(nèi)完成，耗費(fèi)太長時(shí)間得到的正確結(jié)果是沒有意義的。2.下列關(guān)于算法的描述中錯(cuò)誤的是()。2014年3月真題A.算法強(qiáng)調(diào)動(dòng)態(tài)的執(zhí)行過程，不同于靜態(tài)的計(jì)算公式B.算法必須能在有限個(gè)步驟之后終止C.算法設(shè)計(jì)必須考慮算法的復(fù)雜度D.算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境【答案】D【解析】算法是指對(duì)解題方案的準(zhǔn)確而完整的描述。A項(xiàng)正確，算法強(qiáng)調(diào)實(shí)現(xiàn)，不同于數(shù)學(xué)上的計(jì)算方法；B項(xiàng)正確，算法的有窮性是指，算法中的操作步驟為有限個(gè)，且每個(gè)步驟都能在有限時(shí)間內(nèi)完成；C項(xiàng)正確，算法設(shè)計(jì)必須考慮執(zhí)行算法所需要的資源，即時(shí)間復(fù)雜度與空間復(fù)雜度；D項(xiàng)錯(cuò)誤，算法的優(yōu)劣

13、取決于算法復(fù)雜度，只有當(dāng)算法被編程實(shí)現(xiàn)運(yùn)行時(shí)才會(huì)受到運(yùn)行環(huán)境影響。考點(diǎn)3算法復(fù)雜度(1)時(shí)間復(fù)雜度定義算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)其中，n是問題的規(guī)模。在同一問題規(guī)模下，若算法的基本運(yùn)算次數(shù)取決于某一特定輸入，可用以下兩種方法來分析算法的工作量：a.平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。算法的平均性態(tài)定義為：其中，x是所有可能輸入中的某個(gè)特定輸入，p(x)是x出現(xiàn)的概率，即輸入為x的概率，t(x)是算法在輸入為x時(shí)

14、所執(zhí)行的基本運(yùn)算次數(shù)，D表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。b.最壞情況復(fù)雜性最壞情況分析是指規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。其定義為：(2)空間復(fù)雜度定義算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。存儲(chǔ)空間組成一個(gè)算法的存儲(chǔ)空間包括以下幾種：a.算法程序占用的空間；b.輸入的初始數(shù)據(jù)占用的存儲(chǔ)空間；c.算法執(zhí)行過程中所需要的額外空間。額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間，若額外空間相對(duì)于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的?！菊骖}演練】1 .下列敘述中正確的是()。2015年3月真題A.算法的效率只與問題的規(guī)模有

15、關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)B.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量C.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的D.算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)【答案】B【解析】算法的時(shí)間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需時(shí)間的度量；與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。2 .算法的空間復(fù)雜度是指()。2013年9月真題A.算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)【答案】A【解析】空間復(fù)雜度是是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。3 .算法空間復(fù)雜度的度量方法

16、是()。2014年9月真題A.算法程序的長度B.算法所處理的數(shù)據(jù)量C.執(zhí)行算法所需要的工作單元D.執(zhí)行算法所需要的存儲(chǔ)空間【答案】D【解析】算法的空間復(fù)雜度包括：輸入數(shù)據(jù)所占的存儲(chǔ)空間；程序本身所占的存儲(chǔ)空間；算法執(zhí)行過程中所需要的額外空間，是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，4 .2數(shù)據(jù)結(jié)構(gòu)的基本概念考點(diǎn)1概述(1)數(shù)據(jù)處理概述定義數(shù)據(jù)處理是指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算，也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。關(guān)鍵問題大量數(shù)據(jù)元素在計(jì)算機(jī)中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省計(jì)算機(jī)的存儲(chǔ)空間，這是進(jìn)行數(shù)據(jù)結(jié)構(gòu)處理的關(guān)鍵問題。(2)數(shù)據(jù)結(jié)構(gòu)研究概述研究問題a

17、.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；b.在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；c.對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。研究目的數(shù)據(jù)結(jié)構(gòu)研究和討論上述3個(gè)問題的主要目的在于提高數(shù)據(jù)處理效率，包括：a.提高數(shù)據(jù)處理的速度；b.盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空間。考點(diǎn)2數(shù)據(jù)結(jié)構(gòu)的概念(1)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即它是反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。簡言之，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，這里的“結(jié)構(gòu)”指數(shù)據(jù)元素之間的前后件關(guān)系。一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面內(nèi)容：表述數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元

18、素之間的前后件關(guān)系。(2)數(shù)據(jù)的邏輯結(jié)構(gòu)定義數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。要素：a.數(shù)據(jù)元素的集合，通常記為D;b.D上的關(guān)系，通常記為R,它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系。表示一個(gè)數(shù)據(jù)結(jié)構(gòu)B可表示為：B=(D,R)為反映D中個(gè)數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。(3)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)定義數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)，是指數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，而且要存放各數(shù)據(jù)元素之間的前后件信息。常用的存儲(chǔ)結(jié)構(gòu)：a.順序；b.鏈接；c.索引。采用不同的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)處理的效率是不同的?！菊骖}演練】下

19、列敘述中正確的是()。2014年3月真題A.有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)B.每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)C.有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)D.有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)【答案】D【解析】邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，線性結(jié)構(gòu)的特征有：集合中必存在唯一的一個(gè)“第一個(gè)元素”；集合中必存在唯一的一個(gè)“最后的元素”；除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前驅(qū)”；除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”。D項(xiàng)正確，如樹形結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，為非線性結(jié)構(gòu)?？键c(diǎn)3數(shù)據(jù)結(jié)構(gòu)的圖形表示(1)在數(shù)據(jù)結(jié)構(gòu)

20、的圖形表示中，數(shù)據(jù)集合D中每個(gè)元素用中間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點(diǎn)(簡稱結(jié)點(diǎn))；對(duì)關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。(2)在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱葉子結(jié)點(diǎn))，其余結(jié)點(diǎn)都稱為內(nèi)部結(jié)點(diǎn)。(3)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是在動(dòng)態(tài)變化的，這種變化體現(xiàn)在結(jié)點(diǎn)數(shù)量的增減以及各結(jié)點(diǎn)之間的前后件關(guān)系的動(dòng)態(tài)變化上?？键c(diǎn)4線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分為：(1)線性結(jié)構(gòu)(線性表)一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件時(shí)，稱其為線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，

21、也最多只有一個(gè)后件。線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)還應(yīng)是線性結(jié)構(gòu)，如果不滿足這個(gè)條件就不能稱之為線性結(jié)構(gòu)。(2)非線性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。注：線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個(gè)空的數(shù)據(jù)結(jié)構(gòu)屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)，需要根據(jù)對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是否按照線性結(jié)構(gòu)的規(guī)則來處理進(jìn)行判斷。1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)考點(diǎn)1線性表的基本概念(1)線性表是一種最常見最簡單的數(shù)據(jù)結(jié)構(gòu)，由一組數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素在線性表中的位置值只取決于它們自己的序號(hào)，即數(shù)據(jù)元素之間的相對(duì)位置是線性的。(2)非空線性表的結(jié)構(gòu)特征：有且只有一個(gè)根結(jié)點(diǎn)ai,它無前件；有且只有一個(gè)終

22、端結(jié)點(diǎn)an,它無后件；除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有*個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表?！菊骖}演練】下列敘述中正確的是()。2014年9月真題A.結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B.結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C.二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.循環(huán)鏈表是非線性結(jié)構(gòu)【答案】B【解析】A項(xiàng)錯(cuò)誤，具有兩個(gè)指針域的鏈表可能是雙向鏈表；B項(xiàng)正確，如雙向鏈表是線性結(jié)構(gòu)，二叉樹為非線性結(jié)構(gòu)，兩者結(jié)點(diǎn)中均有兩個(gè)指針域；C項(xiàng)錯(cuò)誤，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也可采用其他結(jié)構(gòu)；D項(xiàng)錯(cuò)誤，循環(huán)鏈表是線性結(jié)構(gòu)，邏

23、輯概念線性非線性與實(shí)際存儲(chǔ)結(jié)構(gòu)無關(guān)。考點(diǎn)2線性表的順序存儲(chǔ)結(jié)構(gòu)(1)概述順序存儲(chǔ)是一種最簡單的在計(jì)算機(jī)中存放線性表的方法，也稱順序分配。(2)特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面。(3)運(yùn)算在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可對(duì)線性表進(jìn)行以下運(yùn)算：插入：在線性表的指定位置處加入一個(gè)新的元素；刪除：在線性表中刪除指定的元素；查找：在線性表中查找某個(gè)(或某些)特定的元素；排序：對(duì)線性表中的元素進(jìn)行整序；分解：按要求將一個(gè)線性表分解成多個(gè)線性表；合

24、并：按要求將多個(gè)線性表合并成一個(gè)線性表；復(fù)制：復(fù)制一個(gè)線性表；逆轉(zhuǎn)：逆轉(zhuǎn)一個(gè)線性表等?！菊骖}演練】在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間連續(xù)，各個(gè)元素所占的字節(jié)數(shù)()02014年3月真題A.相同，元素的存儲(chǔ)順序與邏輯順序一致B.相同，但其元素的存儲(chǔ)順序可以與邏輯順序不一致C.不同，但元素的存儲(chǔ)順序與邏輯順序一致D.不同，且其元素的存儲(chǔ)順序可以與邏輯順序不一致【答案】A【解析】在順序表中，每個(gè)元素占有相同的存儲(chǔ)單元。順序表具有特征：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的?？键c(diǎn)3順序表的插入運(yùn)算假設(shè)線性表的存儲(chǔ)空間為V(1:m),線性表的長度為n

25、(n<mj),插入的位置為i(表示在第i個(gè)位置插入元素)，則順序表插入新元素過程如下：(1)首先處理以下三種異常情況：當(dāng)存儲(chǔ)空間已滿(即n=m)時(shí)為“上溢”錯(cuò)誤，不能進(jìn)行插入，算法結(jié)束；當(dāng)i>n時(shí)，認(rèn)為在最后一個(gè)元素之后(即第n+1個(gè)元素之前)插入；當(dāng)i<1時(shí)，認(rèn)為在第1個(gè)元素之前插入。(2)從最后一個(gè)元素開始，直到第i個(gè)元素，其中每一個(gè)元素均往后移動(dòng)一，個(gè)位置。(3)最后將新元素插入到第i個(gè)位置，并且將線性表的長度增加1。考點(diǎn)4順序表的刪除運(yùn)算假設(shè)線性表的存儲(chǔ)空間為V(1:m),線性表的長度為n(n&m),刪除的位置為i(表示刪除第i個(gè)元素)，則順序表刪除元素的過程

26、如下：(1)首先處理以下兩種異常情況：當(dāng)線性表為空(即n=0)時(shí)為“上溢”錯(cuò)誤，不能進(jìn)行插入，算法結(jié)束；當(dāng)i<1或i>n時(shí)，認(rèn)為在最后一個(gè)元素之后(即第n+1個(gè)元素之前)插入。(2)然后從第i+1個(gè)元素開始，直到最后一個(gè)元素，其中每一個(gè)元素均依次往前移動(dòng)一個(gè)位置。(3)最后將線性表的長度減小1。1.4棧和隊(duì)列考點(diǎn)1棧及其基本運(yùn)算(1)棧的定義棧是限定在一端進(jìn)行插入與刪除的線性表。（2）棧的特點(diǎn)：允許插入和刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入也是最后被刪除的。棧遵循“先進(jìn)后出”或“后進(jìn)先出”的原

27、則，具有記憶功能。通常用指針top來指示棧頂位置，用指針bottom指向棧底，棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。（3）棧的順序存儲(chǔ)及其運(yùn)算在棧的順序存儲(chǔ)空間S（1:m）中，top=0表示棧空；top=m表示棧滿。棧的三種運(yùn)算：入棧運(yùn)算人棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。操作過程如下：a.首先判斷棧頂指針是否已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置。如果是，則說明?？臻g已滿，不可能再進(jìn)行入棧操作（這種情況稱為棧“上溢”錯(cuò)誤），算法結(jié)束。b.然后將棧頂指針進(jìn)一（即top加1）。c.最后將新元素x插入棧頂指針指向的位置。退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。操作過程如下：a.首先判

28、斷棧頂指針是否為00如果是，則說明?？眨豢赡苓M(jìn)行退棧操作（這種情況稱為?！跋乱纭卞e(cuò)誤），算法結(jié)束。b.然后將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量。c.最后將棧頂指針退一（即top減1）。讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。操作過程如下：a.首先判斷棧頂指針是否為00如果是，則說明?？眨x不到棧頂元素，算法結(jié)束。b.然后將棧頂元素賦給指定的變量y。這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量，棧頂指針不會(huì)變。【真題演練】1.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）。2013年9月真題A.棧B.樹C.隊(duì)列D.二叉樹【答案】A【解析】棧和隊(duì)列都是受限的線性表，其中棧按照“先

29、進(jìn)后出”的原則組織數(shù)據(jù)，插入與刪除操作被限制在棧頂一端進(jìn)行。棧支持子程序調(diào)用，在主程序調(diào)用子函數(shù)時(shí)，要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，結(jié)束調(diào)用后返回到主程序中調(diào)用子程序的位置，繼續(xù)執(zhí)行，這種調(diào)用符合棧的特點(diǎn)。2.下列與棧結(jié)構(gòu)有關(guān)聯(lián)的是()。2013年3月真題A.數(shù)組的定義域使用B.操作系統(tǒng)的進(jìn)程調(diào)度C.函數(shù)的遞歸調(diào)用D.選擇結(jié)構(gòu)的執(zhí)行【答案】C【解析】遞歸調(diào)用的本質(zhì)就是函數(shù)調(diào)用函數(shù)本身，直到滿足特定條件時(shí)才停止，然后從最后被遞歸調(diào)用處返回。遞歸函數(shù)是通過棧來實(shí)現(xiàn)的，所以調(diào)用原則和棧的實(shí)現(xiàn)相一致。3 .設(shè)棧的順序存儲(chǔ)空間為S(1:50),初始狀態(tài)為top=0。現(xiàn)經(jīng)過一系列入棧與退棧

30、運(yùn)算后，top=20,則當(dāng)前棧中的元素個(gè)數(shù)為()。2014年3月真題A. 30B. 29C. 20D. 19【答案】C【解析】棧按照“先進(jìn)后出”的原則組織數(shù)據(jù)，插入與刪除操作被限制在棧頂一端進(jìn)行，入棧使棧頂位置進(jìn)1,退棧使棧頂退1。top=0表示棧為空，在運(yùn)算過程中，指針始終指向棧頂元素。top=20,說明當(dāng)前棧中有20個(gè)元素。4 .一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是()。2013年9月真題1 .12345ABCDE8 .EDCBA543219 .ABCDE1234510 54321FDCBA【答案】B【解析】棧中數(shù)

31、據(jù)的插入和刪除都在棧頂按照“先進(jìn)后出”的原則進(jìn)行操作?？键c(diǎn)2隊(duì)列及其基本運(yùn)算(1)什么是隊(duì)列隊(duì)列(Queued是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。(2)隊(duì)列的特點(diǎn)允許插入的一端稱為隊(duì)尾，用隊(duì)尾指針指向隊(duì)尾元素；允許刪除的一端稱為隊(duì)頭，用排頭指針指向排頭元素的前一個(gè)位置。最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進(jìn)先出”或“后進(jìn)后出”原則。隊(duì)尾指針rear和排頭指針front共同反映隊(duì)列中元素變動(dòng)情況。入隊(duì)運(yùn)算指只涉及隊(duì)尾指針rear變化，退隊(duì)運(yùn)算只涉及排頭指針front變化。(3)循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上

32、的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，從排頭指針front指向的后一個(gè)位置到隊(duì)尾指針rear指向的位置均是隊(duì)列中元素。隊(duì)列空的條件是s=0;隊(duì)列滿的條件是s=1且front=rear。隊(duì)列的兩種運(yùn)算假設(shè)循環(huán)隊(duì)列的初始狀態(tài)為空，即：s=0,且front=rear=mi入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。操作過程如下：a.首先判斷循環(huán)隊(duì)列是否滿。當(dāng)循環(huán)隊(duì)列非空（S=1）且隊(duì)尾指針等于排頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為“上溢”。此時(shí)算法結(jié)束。b.然后將隊(duì)尾指針進(jìn)一（即rear=

33、rear+1）,并當(dāng)rear=mi+1時(shí)置rear=1oc.最后將新元素x插入隊(duì)尾指針指向的位置，并且置循環(huán)隊(duì)列非空標(biāo)志。退隊(duì)運(yùn)算退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。操作過程如下：a.首先判斷循環(huán)隊(duì)列是否為空。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。這種情況稱為“下溢”。此時(shí)算法結(jié)束。b.然后將排頭指針進(jìn)一（即front=front+1）,并當(dāng)front=mi+1時(shí)置front=1。c.再將排頭指針指向的元素賦給指定的變量。d.最后判斷退隊(duì)后循環(huán)隊(duì)列是否為空。當(dāng)front=rear時(shí)置循環(huán)隊(duì)列空標(biāo)志（即s=0）o【真題演練】11 下列敘述中正確的是（）。2013

34、年9月真題A.棧是“先進(jìn)先出”的線性表B.隊(duì)列是“先進(jìn)后出”的線性表C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)D.有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【答案】D【解析】棧和隊(duì)列都是受限的線性表，其中棧按照“先進(jìn)后出”的原則組織數(shù)據(jù)，插入與刪除操作被限制在棧頂一端進(jìn)行；隊(duì)列采用“先進(jìn)先出”的原則組織數(shù)據(jù)。循環(huán)隊(duì)列是隊(duì)列的一種特殊形式，是線性結(jié)構(gòu)。12 下列敘述中正確的是（）。2014年3月真題A.循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)B.循環(huán)隊(duì)列是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)D.循環(huán)隊(duì)列的插入運(yùn)算不會(huì)發(fā)生溢出現(xiàn)象【答案】A【解析】B項(xiàng)錯(cuò)誤，循環(huán)隊(duì)列是一種順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列；C項(xiàng)錯(cuò)誤，線性結(jié)構(gòu)是一個(gè)非空

35、序列：除第一個(gè)元素外，每個(gè)元素，有且只有一個(gè)前件；除最后一個(gè)元素外，每個(gè)元素有且只有一個(gè)后件，所以循環(huán)隊(duì)列是線性結(jié)構(gòu)；D項(xiàng)錯(cuò)誤，當(dāng)循環(huán)隊(duì)列的元素個(gè)數(shù)等于存儲(chǔ)長度后，入隊(duì)會(huì)發(fā)生溢出現(xiàn)象，覆蓋前面的數(shù)據(jù)。13 對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是()。2013年9月真題A.隊(duì)頭指針是固定不變的B.隊(duì)頭指針一定大于隊(duì)尾指針C.隊(duì)頭指針一定小于隊(duì)尾指針D.隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針【答案】D【解析】循環(huán)隊(duì)列的隊(duì)頭指針與隊(duì)尾指針都不是固定的，每次入隊(duì)操作隊(duì)尾指針要%ma1,每次出隊(duì)操作隊(duì)頭指針要謎1。因?yàn)榇嬖趍g算，所以隊(duì)頭指針與隊(duì)尾指針大小關(guān)系不確定。14 下列敘述中正確的是()。201

36、3年9月真題A.循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)B.在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元索的動(dòng)態(tài)變化情況C.在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況D.循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定【答案】D【解析】在循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定的，入隊(duì)使得隊(duì)尾指針變化，出隊(duì)使得隊(duì)頭指針變化。1.5線性鏈表考點(diǎn)1線性鏈表的基本概念(1)線性表的順序存儲(chǔ)結(jié)構(gòu)存在的缺陷：在插入或刪除元素時(shí)，為保證操作后的線性表仍然是順序存儲(chǔ)，需要大量移動(dòng)數(shù)據(jù)元素，效率很低。在順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充，易產(chǎn)生上溢現(xiàn)象。線

37、性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。(2)鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)組成：數(shù)據(jù)域：用于存放數(shù)據(jù)元素值；指針域：用于存放指針。指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。在用鏈?zhǔn)浇Y(jié)構(gòu)表示較復(fù)雜的非線性結(jié)構(gòu)時(shí)，其指針域的個(gè)數(shù)要多一些。(3)線性鏈表定義：線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。特點(diǎn)a.各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致；b.各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針

38、域來指示的；c.每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后件結(jié)點(diǎn)，不能找到前件結(jié)點(diǎn)，只能順指針向鏈尾進(jìn)行掃描。為了彌補(bǔ)線性單鏈表的缺陷，在某些應(yīng)用中為線性鏈表每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，左指針用以指向其前件結(jié)點(diǎn)，右指針指向其后件結(jié)點(diǎn)。(4)帶鏈的棧帶鏈的棧可以用來收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)。與順序棧一樣，帶鏈棧的基本操作有以下幾個(gè)：棧的初始化：建立一個(gè)空棧的順序存儲(chǔ)空間；入棧運(yùn)算：在棧頂位置插入一個(gè)新元素；退棧運(yùn)算：取出棧頂元素并賦給一個(gè)指定的變量；讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。(5)帶鏈的隊(duì)列與順序隊(duì)列一樣，帶鏈隊(duì)列的基本操作有以下幾個(gè)：隊(duì)列的初始化：建立一個(gè)空隊(duì)列的順

39、序存儲(chǔ)空間；入隊(duì)運(yùn)算：在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素；退隊(duì)運(yùn)算：在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。【真題演練】1.下列敘述中正確的是()。2014年9月真題A.所謂有序表是指在順序存儲(chǔ)空間內(nèi)連續(xù)存放的元素序列B.有序表只能順序存儲(chǔ)在連續(xù)的存儲(chǔ)空間內(nèi)C.有序表可以用鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)在不連續(xù)的存儲(chǔ)空間內(nèi)D.任何存儲(chǔ)方式的有序表均能采用二分法進(jìn)行查找【答案】C【解析】“有序”是指線性表中的元素按照升序或降序(允許相鄰元素相同)的方式排列。有序是一個(gè)邏輯概念，與物理存儲(chǔ)無關(guān)。二分法查找時(shí)涉及下標(biāo)運(yùn)算，要求有序表必須順序存儲(chǔ)。2.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)

40、有()。2014年9月真題A.節(jié)省存儲(chǔ)空間B.插入與刪除運(yùn)算效率高C.便于查找D.排序時(shí)減少元素的比較次數(shù)【答案】B【解析】線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)比較如下：優(yōu)點(diǎn)缺點(diǎn)順序表方便隨機(jī)存取無需額外的存儲(chǔ)空間來表示結(jié)點(diǎn)間的邏輯關(guān)系插入和刪除運(yùn)算效率很低存儲(chǔ)空間不便于擴(kuò)充不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配在進(jìn)行插入和刪除操作時(shí)，只需要改變指針鏈表的存儲(chǔ)空間易于擴(kuò)充，容易實(shí)現(xiàn)空間的動(dòng)態(tài)分配需要額外的空間來表示數(shù)據(jù)元素之間的邏輯關(guān)系，存儲(chǔ)密度低3.下列敘述中正確的是()。2013年9月真題A順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的B.順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱?/p>

41、儲(chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間【答案】A【解析】BC兩項(xiàng)錯(cuò)誤，邏輯概念上的線性非線性是否有序與存儲(chǔ)結(jié)構(gòu)為順序還是鏈?zhǔn)經(jīng)]有直接關(guān)系；D項(xiàng)錯(cuò)誤，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)更耗費(fèi)存儲(chǔ)空間，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)中除了要存儲(chǔ)順序結(jié)構(gòu)中的數(shù)據(jù)外還要存儲(chǔ)指針。考點(diǎn)2線性鏈表的基本運(yùn)算(1)常見的線性表的運(yùn)算線性鏈表的運(yùn)算主要有以下幾個(gè)：在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素；在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)；將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表；將一個(gè)線性鏈表按要求進(jìn)行分解；逆轉(zhuǎn)線性鏈表；復(fù)制線性鏈表；線性鏈

42、表的排序；線性鏈表的查找。(2)在線性鏈表中查找指定元素非空線性鏈表中尋找包含指定元素值x的前一個(gè)結(jié)點(diǎn)p的基本方法：從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止。因此，由這種方法找到的結(jié)點(diǎn)p有兩種可能：當(dāng)線性鏈表中存在包含元素x的結(jié)點(diǎn)時(shí)，則找到的p為第一次遇到的包含元素x的前一個(gè)結(jié)點(diǎn)序號(hào)；當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí)，則找到的p為線性鏈表中的最后一個(gè)結(jié)點(diǎn)號(hào)。(3)線性鏈表的插入定義：線性鏈表的插入是指在鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)下的線性表中插入一個(gè)新元素。插入過程：在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入一個(gè)新元素boa.從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p

43、,并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲ob.在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。c.最后將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。為了實(shí)現(xiàn)這一步，只要改變以下兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容：第一，使結(jié)點(diǎn)P指向包含元素x的結(jié)點(diǎn)；第二，使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p。插入特點(diǎn)：a.不會(huì)發(fā)生上溢現(xiàn)象；b.可方便實(shí)現(xiàn)存儲(chǔ)空間動(dòng)態(tài)分配；c.不發(fā)生數(shù)據(jù)元素移動(dòng)現(xiàn)象，只改變結(jié)點(diǎn)指針，提高插入效率。(4)線性鏈表的刪除定義：線性鏈表的刪除是指在鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。刪除過程：在線性鏈表中刪除包含元素x的結(jié)點(diǎn)。a.在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)序號(hào)為q;b.將結(jié)點(diǎn)

44、q后的結(jié)點(diǎn)p從線性鏈表中刪除，即讓結(jié)點(diǎn)q的指針指向包含元素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn)；c.將包含元素x的結(jié)點(diǎn)p送回可利用棧。在線性鏈表中刪除一個(gè)元素后，不需要移動(dòng)表的數(shù)據(jù)元素，只需改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針域即可?？键c(diǎn)3循環(huán)鏈表(1)與線性鏈表相比，循環(huán)鏈表具有的特點(diǎn)：在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。(2)與線性單鏈表相比，循環(huán)鏈表具有兩方面優(yōu)點(diǎn)：在循環(huán)鏈表中，只要指出表中任何一

45、個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)。而線性單鏈表做不到這一點(diǎn)。由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何情況下循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。循環(huán)鏈表的插入與刪除運(yùn)算要比一般單鏈表簡單，不用考慮在空鏈表和在第一個(gè)結(jié)點(diǎn)前插入以及空鏈表的刪除等特殊情況，從而實(shí)現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一?！菊骖}演練】下列敘述中錯(cuò)誤的是()。2014年3月真題A.在雙向鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)B.在循環(huán)鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)C.在線性單鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)D.在二叉鏈表中，可以從根結(jié)點(diǎn)開始

46、遍歷到所有結(jié)點(diǎn)【答案】C【解析】C項(xiàng)錯(cuò)誤，在線性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，從一個(gè)結(jié)點(diǎn)出發(fā)只能遍歷到其后的節(jié)點(diǎn)，不能遍歷其前的結(jié)點(diǎn)。A項(xiàng)正確，雙向鏈表的結(jié)點(diǎn)包含前驅(qū)和后繼的兩個(gè)指針；B項(xiàng)正確，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)；D項(xiàng)正確，二叉鏈表中所有的結(jié)點(diǎn)都是根結(jié)點(diǎn)的分支。1.6樹與二叉樹考點(diǎn)1樹的基本概念(1)樹是一種簡單的非線性結(jié)構(gòu)，在這種結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。在樹的圖形表示中，上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件。(2)在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)只有一個(gè)前件(父結(jié)點(diǎn))，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)都可以有多個(gè)后件(子結(jié)點(diǎn))，沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。

47、(3)一個(gè)結(jié)點(diǎn)擁有的后件個(gè)數(shù)稱為i結(jié)點(diǎn)的度。某結(jié)點(diǎn)的度為n,表示該結(jié)點(diǎn)有n個(gè)分支，每個(gè)分支指向一個(gè)后件，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有一個(gè)唯一的分支指向它。樹中的結(jié)點(diǎn)數(shù)為樹中所有結(jié)點(diǎn)的度之和再加1。(4)根結(jié)點(diǎn)在第1層，同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層，樹的最大層次稱為樹的深度(5)在樹中，葉子結(jié)點(diǎn)沒有子樹。(6)用樹來表示算術(shù)表達(dá)式的原則：表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)；運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹(在樹中的順序?yàn)閺淖蟮接?；運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。在樹中，葉子結(jié)點(diǎn)沒有子樹。【真題演練】1.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是()。2013

48、年3月真題A.循環(huán)隊(duì)列B.帶鏈隊(duì)列C.二叉樹D.帶鏈?！敬鸢浮緾【解析】線性結(jié)構(gòu)要求有唯一的根結(jié)點(diǎn)和葉子結(jié)點(diǎn)，且除了根結(jié)點(diǎn)任何一個(gè)元素只有唯一的前件，除了葉子結(jié)點(diǎn)任何一個(gè)元素只有唯一的后件。二叉樹的后繼結(jié)點(diǎn)可能不唯一，屬于非線性結(jié)構(gòu)。2.某二叉樹的中序序列為DCBAEFG后序序列為DCBGFEA則該二叉樹的深度(根節(jié)點(diǎn)在第1層)為()。2015年3月真題A. 5B. 4C. 3D. 2【答案】B【解析】題干中二叉樹的后序序列為DCBGFEAA為根節(jié)點(diǎn)。中序序列為DCBAEFG可知DCB為左子樹節(jié)點(diǎn)，EFG為右子樹節(jié)點(diǎn)。同理B為C父節(jié)點(diǎn)，C為D父節(jié)點(diǎn)。根據(jù)分析，可畫出左子樹，同理E為F根節(jié)點(diǎn)，F(xiàn)

49、為G根節(jié)點(diǎn)。根據(jù)分析，可畫出右子樹，觀察得，樹的深度為4,故二叉樹深度為4層?？键c(diǎn)2二叉樹及其基本性質(zhì)(1)二叉樹定義二叉樹是一種很有用的非線性結(jié)構(gòu)，與樹結(jié)構(gòu)很相似，樹結(jié)構(gòu)的所有術(shù)語都可以用到叉樹這種數(shù)據(jù)結(jié)構(gòu)上。(2)二叉樹的兩個(gè)特點(diǎn)非空二叉樹只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。(3)二叉樹的基本性質(zhì)在二叉樹的第k層上，最多有2k-1(k>1)個(gè)結(jié)點(diǎn)。深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n十1,其中l(wèi)og2n表示取log2n的整數(shù)部分

50、。(4)滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹a.除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。b.更確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行連續(xù)編號(hào)，則深度為m且有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為P,則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)镻,或?yàn)閜+1oc.

51、滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹具有以下兩個(gè)性質(zhì)：a.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。b.設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序(每一層從左到右)用自然數(shù)1,2,，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k(k=1,2,n)的結(jié)點(diǎn)有以下結(jié)論：第一，若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT（k/2）。第二，若2k<n,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。第三，若2k+1<n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。根據(jù)完

52、全二叉樹的這個(gè)性質(zhì)，如果按從上到下、從左到右順序存儲(chǔ)完全二叉樹的各結(jié)點(diǎn)，則很容易確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置?！菊骖}演練】1 .某二叉樹共有13個(gè)結(jié)點(diǎn)，其中有4個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為（）o2014年3月真題A. 5B. 4C. 3D. 2【答案】A【解析】對(duì)任何一棵二叉樹來說，度為0的節(jié)點(diǎn)，即葉子節(jié)點(diǎn)，總是比度為2的節(jié)點(diǎn)多一個(gè)。所以可設(shè)葉子節(jié)點(diǎn)個(gè)數(shù)為n,則度為2的節(jié)點(diǎn)個(gè)數(shù)為n-1,13=n+4+n-1,得n=5。2 .某二叉樹中有15個(gè)度為1的結(jié)點(diǎn)，16個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（）。2014年9月真題A. 32B. 46C. 48D. 49【答案】C

53、【解析】在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后繼個(gè)數(shù)稱為該結(jié)點(diǎn)的度。由二叉樹的基本性質(zhì)可得，對(duì)于任何的二叉樹，葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。因?yàn)槎葹?的結(jié)點(diǎn)有16個(gè)，所以葉子結(jié)點(diǎn)個(gè)數(shù)為17,因此結(jié)點(diǎn)總數(shù)為16+17+15=48o3 .某二叉樹中共有935個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有435個(gè)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。2014年3月真題A. 64B. 66C. 436D. 434【答案】D【解析】在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。對(duì)于任何一棵二叉樹來說，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。葉子結(jié)點(diǎn)有435個(gè)，則度為2的結(jié)點(diǎn)為434。4 .深度為7的完全二叉樹中共有125個(gè)結(jié)點(diǎn)

54、，則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為()。2014年9月真題A. 62B. 63C. 64D. 65【答案】B【解析】定義一棵樹的根結(jié)點(diǎn)所在的層次為1,其他結(jié)點(diǎn)所在的層次等于它的父結(jié)點(diǎn)所在的層次加1,樹的最大層次稱為樹的深度。完全二叉樹指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。本題中，前6層是滿二叉樹，結(jié)點(diǎn)個(gè)數(shù)為26-1=63,所以第7層有125-63=62個(gè)葉子結(jié)點(diǎn)，分別掛在第6層的左邊62個(gè)結(jié)點(diǎn)上，所以第6層的最后1個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)，該完全二叉樹共有62+1=63個(gè)葉子結(jié)點(diǎn)?？键c(diǎn)3二叉樹的存儲(chǔ)結(jié)構(gòu)(1)在計(jì)算機(jī)中，二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(2)用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域指針域a.左指針：用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址；b.右指針：指向該結(jié)點(diǎn)的右指結(jié)點(diǎn)的存儲(chǔ)地址?！菊骖}演練】下列敘述中正確的是()。2014年9月真題A.結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B.結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C.二叉樹只能采用鏈?zhǔn)?/p>