全國計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)30248

1、全國計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí) ( 全)第一章數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)過對(duì)部分考生的調(diào)查以及對(duì)近年真題的總結(jié)分析 ?筆試部分經(jīng)常考查的足算法復(fù)雜度、數(shù)據(jù)結(jié)構(gòu)的概念 ?棧?二叉樹的遍歷、二分法直找. 讀者應(yīng)對(duì)此部分進(jìn)行蛋點(diǎn)學(xué)習(xí)。詳細(xì)幣: 點(diǎn)學(xué)習(xí)知識(shí)點(diǎn)：1 ?算法的概念 . 算法時(shí)間復(fù)雜度及空間復(fù)雜度的概念2. 數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)邏輸結(jié)構(gòu)及物理結(jié)構(gòu)的定義3. 棧的定義及其運(yùn)算、線性鏈表的存儲(chǔ)方式4. 樹與二叉樹的概念、二叉樹的基本性質(zhì)、完全二叉樹的概念、二艾樹的遍歷5. 二分查找法6. 冒泡排序法1.1 算法考點(diǎn) I 算法的基本概念考試鏈接：考點(diǎn) 1 在筆試考試中考核的兒率為 30%,主耍是以填空題的形

2、式出現(xiàn)，分值為 2 分，此考點(diǎn)為識(shí)記內(nèi)容 ?讀者還應(yīng)該了牌算法中對(duì)數(shù)據(jù) 的基本運(yùn)算。 il 傅機(jī)解題的過程實(shí)際上足在實(shí)施某種算法，這科算法稱為汁妹機(jī)算法。1. 算法的雄木特征：可行性、確定性 . 有窮性 . 擁有足夠的情報(bào)。2. 算法的基本翌素：(1 算法中對(duì)數(shù)據(jù)的運(yùn)算和操作 一個(gè)算法由兩種基木要索組成：一是對(duì)數(shù)據(jù)對(duì)荻的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。在?般的計(jì)算機(jī)系統(tǒng)中 ?基本的運(yùn)算和操作有以下4 類：算術(shù)運(yùn)克、邏輯運(yùn)算 -關(guān)系運(yùn)算和數(shù)據(jù)傳輸。(2)算法的控制結(jié)構(gòu)：算法中備操作 Z 間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。描述算法的工具通常冇傳統(tǒng)流程圖、 N? S結(jié)構(gòu)化流程圖、算法描述語言等。一個(gè)算

3、法般都可以川順序、選擇、循環(huán)3種基木控制結(jié)構(gòu) 組合而成?？键c(diǎn) 2 算法刃雜度考試鏈接： 考點(diǎn) 2在筆試考試中， 是一個(gè)經(jīng)?？紪说膬?nèi)容 ?在筆試考試中出現(xiàn)的兒率為 70%, 主耍是以選擇的形式出現(xiàn)， 分值為 2分，此考點(diǎn)為重 點(diǎn) 識(shí)記內(nèi)容，讀者還應(yīng)該識(shí)記算法時(shí)間復(fù)雜度及空間復(fù)雜度的概念。1. 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作呈。同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行，效率血不同。這表明使用絕對(duì)的時(shí)間單位衡 J1 算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法運(yùn)行工作咼 的大小，只依賴于問題的

4、 規(guī)模(通常用整數(shù)n 表示)，它是問題規(guī)模的函數(shù)。即算法的工作 ft=f ( n)2?算法的空間口雜度算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包插算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。其中額 外空間包括 算法程序執(zhí)行過程中的工作單元以及某種數(shù)裁結(jié)構(gòu)所需要的附加存儲(chǔ)空間。 如果額外空間量相對(duì)于問題規(guī)模來說是常數(shù)， 則 稱該算法是原地工作的。 在許多實(shí)際問題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)，以便盡雖減少不必要的額外空間。疑難解答：算法的工作地用什么來計(jì)算？算法的工作雖用算法所執(zhí)行的基本運(yùn)算次數(shù)來計(jì)算

5、，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f (n),其中n是問題的規(guī)模。1.2 數(shù)據(jù)結(jié)構(gòu)的基木概念考點(diǎn) 3 數(shù)據(jù)結(jié)構(gòu)的定義考試鏈接：考點(diǎn) 3 在筆試考試中，是一個(gè)經(jīng)?？疾榈膬?nèi)容，在筆試考試中出現(xiàn)的兒率為 70%,主要是以選擇的形式出現(xiàn)，分值為 2 分，此考點(diǎn)為識(shí) 記內(nèi)容，讀 者還應(yīng)該識(shí)記數(shù)據(jù)的邏供結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的概念。數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主耍研究和討論以下三個(gè)方面：(1) 數(shù)據(jù)集合中個(gè)數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；(2) 在對(duì)數(shù)據(jù)元索進(jìn)行處理時(shí)，各數(shù)據(jù)元索在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；(3) 對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 數(shù)據(jù)：是對(duì)客觀

6、事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是扌旨所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元索：是數(shù)據(jù)的基木單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對(duì)彖：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的邏軻結(jié)構(gòu)是對(duì)數(shù)據(jù)元索 Z 間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元索的集介和定義在此集合屮的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：-是數(shù)據(jù)元素的集合，通常記為 D ；二是D上的關(guān)系，它反映了數(shù)據(jù)元索之間的前后件關(guān)系，通常記為Ro ?個(gè)數(shù)據(jù)結(jié)構(gòu)可以後示成B= (D. R)其中 B 表示數(shù)據(jù)結(jié)構(gòu)。為了反映 D 中各數(shù)據(jù)元索之間的前后件關(guān)系，一般用二元組來表示。 數(shù)據(jù)的邏軻結(jié)

7、構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。關(guān)系（即前數(shù)據(jù)處理的由于數(shù)抵元索在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此 . 為了義示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素Z 間的邏輯后件關(guān)系，在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅耍存放各數(shù)據(jù)元素的信息，還需耍存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。- 種數(shù)據(jù)的邏輯結(jié)構(gòu)根弟需?？梢员硎境啥喾N存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)冇順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。而采用不同的存儲(chǔ)結(jié)構(gòu)，其 效率是不同的。因此 . 在進(jìn)行 ?數(shù)據(jù)處理時(shí) . 選擇合適的存儲(chǔ)結(jié)構(gòu)是很重耍的?？键c(diǎn) 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu)考試鏈接：考點(diǎn) 4 在筆試考試中，雖然說不是考試經(jīng)

8、常考査的內(nèi)容，但讀者還是對(duì)此考點(diǎn)有所了解，在筆試考試中出現(xiàn)的兒率為30%, 主要是以填形式出現(xiàn)，分值為 2 分，此考點(diǎn)為識(shí)記內(nèi)容根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度， - 般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果 - 個(gè)非空的數(shù)據(jù)空題出現(xiàn)的結(jié)拘滿足下不是線性結(jié)來處理的，握內(nèi)容，讀素總是后被后進(jìn)先出”列兩個(gè)條件：1） 有且只有一個(gè)根結(jié)點(diǎn)；2） 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件 則稱該數(shù)劣結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果 - 個(gè)數(shù)據(jù)結(jié)構(gòu) 構(gòu). 則稱之為菲線性結(jié)構(gòu)疑難解答：空的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)還是非線

9、性結(jié)構(gòu)？ 一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這耍根據(jù)具體情況來確定。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的算法是按線性結(jié)構(gòu)的規(guī)則 則屬于線性結(jié)構(gòu)；否則屬于菲線性結(jié)構(gòu)。1.3 棧及線性鏈表考點(diǎn) 5 棧及其基本運(yùn)算考試鏈接：考點(diǎn) 5 在筆試考試中，是一個(gè)必考的內(nèi)容，在筆試考試中出現(xiàn)的兒率為100%, 主要是以選擇的形式出現(xiàn)，分值為 2 分，此考點(diǎn)為重點(diǎn)學(xué)若應(yīng)該掌握棧的運(yùn)算，1. 棧的基木概念 棧是限定只在一端進(jìn)行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元索時(shí)稱為空棧。棧頂元 插入的元索， 從而也是嚴(yán)先被刪除的元縈； 棧底元素總是最先彼插入的元素，從而也是最后才能

10、被刪除的元索。棧是按觀 先 進(jìn)后出 或 的原則組織數(shù)據(jù)的2. 棧的順序存儲(chǔ)及其運(yùn)算 用一維數(shù)組 S (1 ： m )作為棧的順序存儲(chǔ)空間，其中 m 為最大容呈。在棧的順序存儲(chǔ)空間 S (1 : m)中，S (bottom )為棧底元索，S (top)為棧頂元索。iop=0表示?？眨籭op-m表示棧滿。 棧的基本運(yùn)算有三種：入棧、退找與讀棧頂元索。(1)入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。首先將棧頂扌旨針加一(即top加I)，然后將新元索插入到棧頂折針指向的位迓。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位迓時(shí)，說明?？臻g已満，不可能再進(jìn)行入棧操作。這種情況稱為棧上滯錯(cuò)誤。(2) 退棧運(yùn)算

11、：退棧是指収出棧頂元索并賦給一個(gè)指定的變就。首先將棧頂元素(棧頂指針指向的元索)賦給一個(gè)指定的變就，然后將棧頂指針減一(即 lop 減 1)。當(dāng)棧頂指針為 0 時(shí)，說明?？?，不可進(jìn)行退找操作。這種悄況稱為棧的 下溢 錯(cuò)誤。(3) 讀棧頂元索：険棧頂元索是指將棧頂元索賦給一個(gè)指定的變量。這個(gè)運(yùn)算不刪除棧頂元素, 只是將它賦給一個(gè)變量，因此棧頂指針 不會(huì)改 變。當(dāng)棧頂扌旨針為 0 時(shí)，說明?？?，讀不到棧頂元素。小技巧：棧是按照 先進(jìn)后出 或”后進(jìn)先出 的原則組織數(shù)據(jù) . 但是出棧方式有多種選擇 . 在考題中經(jīng)?？疾楦鞣N不同的出棧方式。考點(diǎn) 6 線性鏈表的基本概念考試鏈接：考點(diǎn) 6 在筆試考試中出現(xiàn)

12、的幾率為 30%,主翌是以選擇的形式岀現(xiàn)，分值為 2分，此考點(diǎn)為識(shí)記內(nèi)容。重點(diǎn)識(shí)記結(jié)點(diǎn)的組成。在鏈?zhǔn)酱鎯?chǔ)方式中，耍求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)蟹元索值 . 稱為數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。其 中指針用于 指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件。鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。( 1 ) 線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在某些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針 , 一個(gè)稱為左指針 , 用以指向其前件結(jié)點(diǎn) :另-個(gè)稱為右指針 ,用以指向其后件 結(jié)點(diǎn)。這樣的表 稱為雙向鏈表。(2) 帶鏈的棧棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)

13、構(gòu)。 帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)， 這種帶鏈的棧稱為可利用棧。 疑難解答 :在徒式結(jié)構(gòu)中，存儲(chǔ)空間位置關(guān)系與邏輯關(guān)系是什么？在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中 .存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元索Z 間的邏輯關(guān)系是由指針域來確定的。1.4 樹與二叉樹 考點(diǎn) 7 樹與二叉樹及其基本性質(zhì) 考試鏈接：考點(diǎn) 7 在筆試考試中 , 是一個(gè)必考的內(nèi)容，在筆試考試中出現(xiàn)的兒率為 100%, 主要是以選擇的形式出現(xiàn) , 有時(shí)也有出現(xiàn)在填空題中，分 值為 2 分，此 考點(diǎn)為覓點(diǎn)掌握內(nèi)客。重點(diǎn)識(shí)記樹及二叉樹的性質(zhì)。課區(qū)警示：滿二叉樹也是完

14、全二叉樹 . 而完全二叉樹一般不是滿二叉樹。應(yīng)該注意二者的區(qū)別。1、樹的基本概念樹（tree ）是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹結(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)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中， - 個(gè)結(jié)點(diǎn)所擁有 ？的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為0在樹中，所有結(jié)點(diǎn)中的最大的度稱為樹的度。2、二叉樹及其基本性質(zhì)（ 1） 二叉樹的定義二叉樹是 - 種很有用的非線性結(jié)構(gòu)，具有以下兩個(gè)特點(diǎn)： 非空二叉樹只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多冇兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹和右子樹。由以上持點(diǎn)

15、可以看出，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2,即所有子樹（左子樹或右子樹）也均為二叉樹 . 而樹結(jié)構(gòu)中的每一 ？個(gè)結(jié)點(diǎn) 的度可以是任意的。另外，二叉樹中的每個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個(gè)結(jié)點(diǎn)既沒有左子樹也沒有右子樹時(shí)，該結(jié)點(diǎn)即為葉子結(jié)點(diǎn)。（ 2） 二叉樹的基木性質(zhì)二叉樹具有以下兒個(gè)性質(zhì)：性質(zhì) 1：在二叉樹的第 k 層上，最冬有 2k-l （ kl ）個(gè)結(jié)點(diǎn)：性質(zhì) 2：深度為 m 的二叉樹垠多有 2m-1 個(gè)結(jié)點(diǎn)：性質(zhì) 3：在任意 - 棵二叉樹中，度為 0 的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為 2 的結(jié)點(diǎn)多一

16、個(gè)。性質(zhì) 4：具有 n 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 （ log2n ） +1,其中 （Iog2n ）表示取 log2n 的整數(shù)部分。小技巧：在二叉樹的遍歷中 . 無論是前序遍歷 ？中序遍歷還是后序遍歷 ？二義樹的葉子結(jié)點(diǎn)的先后順序都是不變的。3、滿二叉樹與完全二叉樹滿二叉樹是指這樣的一 ？種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在満二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第 k 層上有 2k？ l 個(gè)結(jié)點(diǎn)，且漆度為 m 的滿二叉樹有 2m-1 個(gè)結(jié)點(diǎn)。完全二叉樹是指這樣的二艾樹：除鍛后一層外 . 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在晟后一層上只缺少右邊的若干結(jié)點(diǎn)。

17、對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)：對(duì)于任何一個(gè)結(jié)點(diǎn)，若苴右分支下的子孫結(jié)點(diǎn)的最大層次為p,則瓦左 分支下的子孫結(jié)點(diǎn)的呆大層次或?yàn)镻,或?yàn)閜+l.完全二叉樹具有以下兩個(gè)性質(zhì)：性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為(log2n ) +1。性質(zhì) 6: 設(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=l, 2, n)的結(jié)點(diǎn)有以下結(jié)論: 若k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)：若kl?則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT (k/2)o 若2kn,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k ；否則該結(jié)

18、點(diǎn)無左子結(jié)點(diǎn)(顯然也沒有右子結(jié)點(diǎn))。 若 2k+ln, 則編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2kH； 否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)?？键c(diǎn) 8 二叉樹的遍歷考試鏈接：考點(diǎn) 8在筆試考試中考核兒率為 30%, 分值為 2分,讀者應(yīng)該熟練掌握各種遙歷的具體算法，能由兩種遍歷的結(jié)果推導(dǎo)另 - 種遍歷的結(jié) 果。在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。( 1 ) 前序適歷：先訪問根結(jié)點(diǎn) . 然后遍歷左子樹 . 昴后遍歷右子樹；并且，在遍歷左 . 右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹 . 報(bào)后遍歷 右

19、子樹。( 2) 中庠遍歷：先遍歷左子樹、然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在姻歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn), 最后遍歷右子樹。( 3) 后序遍歷：先遍歷左子樹、然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；并且，在遍歷左. 右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹 , 最后訪問根結(jié)點(diǎn)。疑難解答：樹與二叉樹的不同之處是什么？在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2,即所有子樹(左子樹或右子樹)也均為二叉樹，而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。1.5 査找技術(shù)考點(diǎn) 9 順序查找考試鏈接：考點(diǎn) 9 在筆試考試中考核兒率在 30%, -般岀現(xiàn)選擇題中，分值為 2 分，讀者應(yīng)該具體學(xué)握順序査找

20、的算法。査找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找菜個(gè)指定的元索。從線性表的第一個(gè)元索開始?依次將線性表中的元索與被査找的元索相比較, 若相等則農(nóng)示查找成功；若線性農(nóng)中所有的尤索都 9 被杳找尤索進(jìn)行了比較但都不相等，則農(nóng)爪 ?査找失敗? 在下列兩種情況下也只能采川順序査找：( 1 ) 如果線性農(nóng)為無序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序査找。2) 即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找考點(diǎn) 10 二分法查找考試鏈接：考點(diǎn) 10 在筆試考試中考核幾率為 30%, 般出現(xiàn)填空題中，分值為 2 分 , 考核比較多查找的比較次數(shù)，讀者應(yīng)該具體慕握二分查找法的 二分法只適用于順序存儲(chǔ)的 , 按非遞減排列的有序表 , 其方法如 F：設(shè)有序線性表的長度為n,被査找的元索為i.（1）將 i 與線性表的中間項(xiàng)進(jìn)行比較；（2）若 i 與中間項(xiàng)的值相等，則査找成功；（ 3） 若 i 小于中間項(xiàng)，則在線性表的前半部分以相同的方法査找：（ 4） 若 i 大于中間項(xiàng) ?則在線性表的后半部分以相同的方法査找。疑難解答：二分查找法適用于哪種情況？ 二分査找法只適用于順序存儲(chǔ)的有序表。在此所說的有序表是