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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、是()。2014年9月真題A.算法程序的長度B.算法所處理的數(shù)據(jù)量C.執(zhí)行算法所需要的工作單元D.執(zhí)行算法所需要的存儲空間【答案】D【解析】算法的空間復(fù)雜度包括：輸入數(shù)據(jù)所占的存儲空間；程序本身所占的存儲空間；算法執(zhí)行過程中所需要的額外空間，是指執(zhí)行這個算法所需要的內(nèi)存空間，4 .2數(shù)據(jù)結(jié)構(gòu)的基本概念考點1概述(1)數(shù)據(jù)處理概述定義數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數(shù)據(jù)元素進行分析。關(guān)鍵問題大量數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省計算機的存儲空間，這是進行數(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.在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；c.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。研究目的數(shù)據(jù)結(jié)構(gòu)研究和討論上述3個問題的主要目的在于提高數(shù)據(jù)處理效率，包括：a.提高數(shù)據(jù)處理的速度；b.盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間?？键c2數(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)系。一個數(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)系。表示一個數(shù)據(jù)結(jié)構(gòu)B可表示為：B=(D,R)為反映D中個數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。(3)數(shù)據(jù)的存儲結(jié)構(gòu)定義數(shù)據(jù)的存儲結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)，是指數(shù)據(jù)邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，而且要存放各數(shù)據(jù)元素之間的前后件信息。常用的存儲結(jié)構(gòu)：a.順序；b.鏈接；c.索引。采用不同的存儲結(jié)構(gòu)，數(shù)據(jù)處理的效率是不同的?！菊骖}演練】下

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

20、的圖形表示中，數(shù)據(jù)集合D中每個元素用中間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點(簡稱結(jié)點)；對關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。(2)在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點，沒有后件的結(jié)點稱為終端結(jié)點(也稱葉子結(jié)點)，其余結(jié)點都稱為內(nèi)部結(jié)點。(3)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點可能是在動態(tài)變化的，這種變化體現(xiàn)在結(jié)點數(shù)量的增減以及各結(jié)點之間的前后件關(guān)系的動態(tài)變化上。考點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)(線性表)一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件時，稱其為線性結(jié)構(gòu)：有且只有一個根結(jié)點；每個結(jié)點最多只有一個前件，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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