算法與基本數(shù)據(jù)結(jié)構(gòu)1

算法與數(shù)據(jù)結(jié)構(gòu)公共根底第一局部本章考核內(nèi)容約占13%，主要包括一下幾個方面：算法復(fù)雜度棧、隊列、線性鏈表的根本概念樹的結(jié)點計算和遍歷排序的最壞次數(shù)計算考點1算法的根本概念1.算法是指解題方案的準(zhǔn)確而完整的描述。對于一個問題，如果可以通過一個計算機程序，在有限的存儲空間內(nèi)運行有限的時間而得到正確的結(jié)果，那么稱這個問題是可解的。2.算法特征：1)可行性2)確定性3)有窮性：即算法必須能在執(zhí)行有限個步驟之后終止4)擁有足夠的情報考點1算法的根本概念【2008年4月】：算法的有窮性是指〔〕A〕算法程序的運行時間是有限的B〕算法程序所處理的數(shù)據(jù)量是有限的C〕算法程序的長度是有限的D〕算法只能被有限的用戶使用答案A考點1算法的根本概念3.算法的根本元素一個算法通常由兩種根本要素組成：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。一般的計算機系統(tǒng)中，根本運算和操作包括以下4類：①算術(shù)運算：加、減、乘、除等運算；②邏輯運算：與、或、非等運算；③關(guān)系運算：等于、不等于、大于、小于等運算；④數(shù)據(jù)傳輸：賦值、輸入、輸出等操作?？键c1算法的根本概念3.算法的根本元素算法的控制結(jié)構(gòu)算法各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)包括：順序、選擇〔分支〕和循環(huán)?？键c1算法的根本概念4.算法設(shè)計的根本方法計算機解題的過程實際上是在實施某種算法,這種算法稱為計算機算法。①列舉法；②歸納法；③遞推；④遞歸；⑤減半遞推技術(shù)；⑥回溯法?？键c2算法的復(fù)雜度☆算法的復(fù)雜度包括算法時間復(fù)雜度和算法空間復(fù)雜度。1.算法時間復(fù)雜度算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。在度量一個算法的工作量時，用算法在執(zhí)行過程中所需根本運算的執(zhí)行次數(shù)來度量算法的工作量。分析算法工作量的方法：平均性態(tài)和最壞情況復(fù)雜性?？键c2算法的復(fù)雜度☆2.算法空間復(fù)雜度一個算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間大小。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的空間以及算法執(zhí)行過程中所需要的額外空間?？键c2算法的復(fù)雜度☆【2005年9月】：算法復(fù)雜度主要包括時間復(fù)雜度和_______復(fù)雜度。

【2006年9月】：以下表達中正確的選項是〔〕A〕一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度也必定大B〕一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度必定小C〕一個算法的時間復(fù)雜度大，那么其空間復(fù)雜度必定小D〕上述三種說法都不對答案D空間考點2算法的復(fù)雜度☆【2007年4月】：以下表達中正確的選項是〔〕A〕算法的效率只與問題的規(guī)模有關(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考點3數(shù)據(jù)結(jié)構(gòu)1.根本概念1)數(shù)據(jù)：描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并被計算機程序加工處理的符號的集合。2)數(shù)據(jù)元素：數(shù)據(jù)的根本單位，即數(shù)據(jù)集合中的個體。有時一個數(shù)據(jù)元素由假設(shè)干個數(shù)據(jù)項組成，在這種情況下，將數(shù)據(jù)元素稱為記錄，由記錄所組成的線性表為文件。3)數(shù)據(jù)項：具有獨立意義的最小數(shù)據(jù)單位。4)數(shù)據(jù)對象：具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。5)結(jié)構(gòu)：指數(shù)據(jù)元素之間的前后件關(guān)系?？键c3數(shù)據(jù)結(jié)構(gòu)1.根本概念6)數(shù)據(jù)結(jié)構(gòu)：指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包含兩方面信息：一是表示數(shù)據(jù)元素的信息；二是表示各數(shù)據(jù)元素之間的前后件關(guān)系。例如，描述一年四季的季節(jié)名春、夏、秋、冬，可以作為季節(jié)的數(shù)據(jù)元素；在考慮一年4個季節(jié)的順序關(guān)系時，那么“春〞是“夏〞的前件，而“夏〞是“春〞的后件等。考點3數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)在以上所述的數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系，而與它們在計算機中的存儲位置無關(guān)。因此，上面所述的數(shù)據(jù)結(jié)構(gòu)實際上是數(shù)據(jù)的邏輯結(jié)構(gòu)。1)概念：

所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)?？键c3數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)2)表示：圖形表示：集合、線性、樹、圖集合線性樹圖考點3數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)2)表示：二元關(guān)系表示數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R，即一個數(shù)據(jù)結(jié)構(gòu)可以表示成：B=(D，R)其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。

考點3數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)2)表示：二元關(guān)系表示例如，一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成：B=〔D，R〕D={春，夏，秋，冬}R={〔春，夏〕，〔夏，秋〕〔秋，冬〕}考點4數(shù)據(jù)的存儲結(jié)構(gòu)1.概念：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)?？键c4數(shù)據(jù)的存儲結(jié)構(gòu)2.存儲形式：數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法：順序映像和非順序映像，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序映像的特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序映像的特點是借助指示元素存儲地址的指針(Pointer)表示數(shù)據(jù)元素之間的邏輯關(guān)系?？键c4數(shù)據(jù)的存儲結(jié)構(gòu)注意：

數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的?？键c4數(shù)據(jù)的存儲結(jié)構(gòu)【2005年4月】：數(shù)據(jù)的存儲結(jié)構(gòu)是指〔〕 A〕存儲在外存中的數(shù)據(jù) B〕數(shù)據(jù)所占的存儲空間量C〕數(shù)據(jù)在計算機中的順序存儲方式 D〕數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示答案D考點4數(shù)據(jù)的存儲結(jié)構(gòu)【2005年9月】以下表達中正確的選項是〔〕A〕一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B〕數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C〕一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D〕一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率答案D考點4數(shù)據(jù)的存儲結(jié)構(gòu)【2007年9月】以下表達中正確的選項是〔〕A〕數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B〕由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C〕程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D〕以上三種說法都不對答案D考點4數(shù)據(jù)的存儲結(jié)構(gòu)【2008年9月】以下表達中正確的選項是〔〕A〕順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的B〕順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(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考點5線性結(jié)構(gòu)與非線性結(jié)構(gòu)☆根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足兩個條件：一是有且只有一個根結(jié)點；二是每一個結(jié)點最多有一個前件，也最多有一個后件，那么稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。注意：在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，那么稱為非線性結(jié)構(gòu)?？键c6線性表的根本概念線性表是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表由一組數(shù)據(jù)元素構(gòu)成的有限序列，如一年的四個季節(jié)。線性表中結(jié)點的個數(shù)n稱為線性表的長度。n=0時，稱為空表。非空線性表有如下一些結(jié)構(gòu)特征：有且只有一個根結(jié)點，它無前件；有且只有一個終端結(jié)點，它無后件；除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件?？键c7線性表的順序存儲在計算機中存放線性表的一種最簡單的方法是順序存儲，也稱為順序分配。用順序存儲結(jié)構(gòu)存儲的線性表稱作順序表。線性表的順序存儲結(jié)構(gòu)具有以下兩個根本特點：1)線性表中所有元素所占的存儲空間是連續(xù)的；2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。注意：在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面?？键c8順序表的操作1.插入向順序表中插入一個新結(jié)點時，由于需要保持運算的結(jié)果仍然是順序存儲，所以可能要移動一系列結(jié)點。假設(shè)順序表中結(jié)點個數(shù)為n，在向每個位置插入的概率相等的情況下，插入一個結(jié)點平均需要移動之結(jié)點個數(shù)為n/2，算法的時間復(fù)雜度是O(n)。2.刪除從順序表中刪除一個結(jié)點可能需要移動一系列結(jié)點。在等概率的情況下，刪除一個結(jié)點平均需移動結(jié)點個數(shù)為(n-1)/2，算法的時間復(fù)雜度也是O(n)?？键c9線性表的鏈?zhǔn)酱鎯Α顬榱诉m應(yīng)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，計算機的內(nèi)存空間被劃分為多個小塊，每個小塊占假設(shè)干個字節(jié)，通常稱這些小塊為存儲結(jié)點。每個存儲結(jié)點分為兩局部：一局部用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；一局部用于存儲下一個數(shù)據(jù)元素的存儲序號〔即存儲結(jié)點的地址〕，稱為指針域?？键c9線性表的鏈?zhǔn)酱鎯Α?.線性鏈表〔單鏈表〕所謂線性鏈表就是鏈?zhǔn)酱鎯Φ木€性表，其結(jié)點中只含有一個指針域，用來指出其后繼結(jié)點的存儲位置。線性鏈表的最后一個結(jié)點無后繼結(jié)點，它的指針域為空(記為NULL或^)。另外還要設(shè)置表頭指針head，指向線性鏈表的第一個結(jié)點。Head指針data1

…Data2

Datan?圖1.3鏈?zhǔn)酱鎯Y(jié)構(gòu)考點9線性表的鏈?zhǔn)酱鎯Α?.線性鏈表〔單鏈表〕對線性鏈表可以進行插入、刪除等運算。注意：做刪除運算時改變的是被刪結(jié)點的前一個結(jié)點中指針域的值。因此，假設(shè)要查找且刪除某一結(jié)點，那么應(yīng)在查找被刪結(jié)點的同時記下它前一個結(jié)點的位置?？键c9線性表的鏈?zhǔn)酱鎯Α?.雙向鏈表線性單鏈表中，每個結(jié)點只有一個指針域，由此指針只能找到后件節(jié)點。為了彌補線性單鏈表的這個缺點，在某些應(yīng)用中，對線性單鏈表的每個結(jié)點設(shè)置兩個指針，一個稱為左指針〔Llink〕用以指向其前件結(jié)點；另一個稱為右指針〔Rlink〕用以指向其后件結(jié)點，這樣的線性鏈表稱為雙向鏈表。Head指針data1

…data2

datan?圖1.7雙向鏈表?

考點9線性表的鏈?zhǔn)酱鎯Α?.循環(huán)鏈表所謂循環(huán)鏈表是指鏈表的最后一個結(jié)點的指針值指向第一個結(jié)點，整個鏈表形成一個環(huán)。data1

…Data2

Datan●圖1.8循環(huán)鏈表考點9線性表的鏈?zhǔn)酱鎯Α?/p>

注意：在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)構(gòu)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。

考點9線性表的鏈?zhǔn)酱鎯Α睢?005年4月】：對于線性鏈表的描述中正確的選項是〔〕A〕存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的B〕存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C〕存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D〕存儲空間必須連續(xù)，且各元素的存儲順序是任意的答案A考點10棧及其根本運算☆1.棧的定義棧是一種特殊的線性表。棧是限定僅在表尾〔表的一端〕進行插入和刪除運算的線性表，表尾稱為棧頂〔top〕，表頭叫做棧底〔bottom〕。棧中無元素時稱為空棧。棧遵守“后進先出〞〔LIFO〕的操作原那么，具有記憶功能。a1a2?an棧頂棧底進棧出棧圖1.9棧結(jié)構(gòu)考點10棧及其根本運算☆2.棧的存儲棧的既可以用順序存儲結(jié)構(gòu)，也可用鏈?zhǔn)酱鎯Y(jié)構(gòu)。在程序設(shè)計語言中，用一維數(shù)組S〔1：m〕作為棧的順序存儲空間，其中m為棧的最大容量。通常，棧底指針指向棧空間的低地址一端〔即數(shù)組的起始地址這一端〕。棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)：帶鏈的棧稱為可利用棧?？键c10棧及其根本運算☆3.棧的運算1)入棧運算：指在棧頂位置插入一個新元素，其方法是先將棧頂指針top進一〔即top加1〕，然后將新元素插入到棧頂指針指向的位置。注意：?！吧弦绋曞e誤。(棧頂指針為m)2)退棧運算：指取出棧頂元素并賦給一個指定的變量。其方法是先將棧頂元素賦給一個指定的變量，然后將棧頂指針top退一〔即top減1〕。注意：?！跋乱绋曞e誤。(棧頂指針為0)3)讀棧頂元素：指將棧頂元素賦給一個指定的變量。注意，此元素不刪除棧頂元素，只是將其賦給一個變量，因此在這個運算中，棧頂指針不會改變。考點10棧及其根本運算☆【2005年4月】：以下關(guān)于棧的描述中錯誤的選項是〔〕A〕棧是先進后出的線性表 B〕棧只能順序存儲C〕棧具有記憶作用 D〕對棧的插入與刪除操作中，不需要改變棧底指針

答案B考點10棧及其根本運算☆【2005年9月】以下關(guān)于棧的描述正確的選項是〔〕A〕在棧中只能插入元素而不能刪除元素B〕在棧中只能刪除元素而不能插入元素C〕棧是特殊的線性表，只能在一端插入或刪除元素D〕棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

答案C考點10棧及其根本運算☆【2006年4月】：按照“后進先出〞原那么組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是〔〕 A〕隊列 B〕棧 C〕雙向鏈表 D〕二叉樹【2006年9月】：按“先進后出〞原那么組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是___。

答案棧B考點10棧及其根本運算☆【2008年4月】：以下關(guān)于棧的表達正確的選項是〔〕A〕棧按“先進先出〞組織數(shù)據(jù) B〕棧按“先進后出〞組織數(shù)據(jù)C〕只能在棧底插入數(shù)據(jù) D〕不能刪除數(shù)據(jù)

答案B考點10棧及其根本運算☆【2008年9月】：一個棧的初始狀態(tài)為空，現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，那么元素出棧的順序是〔〕 A〕12345ABCDE B〕EDCBA54321 C〕ABCDE12345 D〕54321EDCBA答案B考點11隊列及其根本運算☆1.隊列的定義隊列是一種特殊的線性表。隊列是限定所有的插入都在表的一端進行，所有的刪除都在表的另一端進行的線性表。允許插入的一端稱為隊尾，通常用一個稱為尾指針〔rear〕的指針指向隊尾元素；允許刪除的一端稱為隊頭，通常用一個稱為頭指針〔front〕的指針指向排頭元素的前一個位置。考點11隊列及其根本運算☆1.隊列的定義隊列遵守“先進先出〞〔FIFO〕的操作原那么，隊尾指針和隊頭指針共同反映了隊列中元素的動態(tài)變化情況。2.隊列的存儲隊列的既可以用順序存儲結(jié)構(gòu)〔一般采用循環(huán)隊列〕，也可用鏈?zhǔn)酱鎯Y(jié)構(gòu)。3.隊列的運算入隊運算、退隊運算、取隊頭元素、檢查隊列是否為空、去除等?？键c11隊列及其根本運算☆4.循環(huán)隊列〔順序存儲結(jié)構(gòu)〕循環(huán)隊列就是將隊列存儲空間的最后一個位置繞到第1個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用?？键c11隊列及其根本運算☆4.循環(huán)隊列入隊運算：入隊運算是指在循環(huán)隊列的隊尾參加一個新元素，rear加1。當(dāng)rear=m+1時，那么置rear=1。退隊運算：退隊運算是指在循環(huán)隊列的排頭位置退出一個元素，front加1。當(dāng)front=m+1時，那么置front=1。當(dāng)循環(huán)隊列滿時有front=rear，而當(dāng)循環(huán)隊列為空時也有front=rear。為了那個區(qū)分隊列是滿還是隊列空，通常需要增加一個標(biāo)示s，s=0表示隊列空；s=1表示隊列非空。由此可得隊列滿與空的條件：隊列空的條件為s=0；隊列滿的條件為s=1且front=rear?？键c11隊列及其根本運算☆【2008年4月】：設(shè)某循環(huán)隊列的容量為50，頭指針Front=5(指向隊頭元素的前一位置)，尾指針rear=29〔指向隊尾元素〕，那么該循環(huán)隊列中共有個元素。 答案24考點11隊列及其根本運算☆【2008年9月】：以下表達中正確的選項是〔〕A)循環(huán)隊列中有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)B)在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況C)在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D)循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定答案D考點11隊列及其根本運算☆【2005年9月】：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于結(jié)構(gòu)?！?006年9月】：數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于________。 答案存儲線性考點11隊列及其根本運算☆【2007年4月】：以下對隊列的表達正確的選項是〔〕A〕隊列屬于非線性表 B〕隊列按“先進后出〞原那么組織數(shù)據(jù)C〕隊列在隊尾刪除數(shù)據(jù) D〕隊列按“先進先出〞原那么組織數(shù)據(jù)【2007年9月】：線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列是隊列的存儲結(jié)構(gòu)。 答案D順序考點12樹的根本概念1.樹樹是一種簡單的非線性結(jié)構(gòu)。在樹這種結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。一般認為，直線連接起來的兩端結(jié)點中，上端結(jié)點是前件，下端結(jié)點是后件。(具有層次關(guān)系的數(shù)據(jù)都可以用樹來表示)RPEBDHKTONYXQCWZSA考點12樹的根本概念2.常用術(shù)語根結(jié)點：沒有前件的結(jié)點〔只有一個〕。葉子結(jié)點：沒有后件的結(jié)點。父結(jié)點：每一個結(jié)點只有一個前件，該前件結(jié)點稱為父結(jié)點。子結(jié)點：每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。兄弟〔Sibling〕：具有相同親結(jié)點的結(jié)點互為兄弟。結(jié)點的度〔Degree〕：一個結(jié)點所擁有的后件的個數(shù)。樹的度：樹中各結(jié)點的度的最大值?？键c12樹的根本概念2.常用術(shù)語結(jié)點的層數(shù)：根結(jié)點的層數(shù)為1，同一層上所有結(jié)點的所有子結(jié)點都在下一層。樹的深度：樹的最大層次。子樹：以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹〔葉子結(jié)點沒有子樹〕?？键c13二叉樹及其根本性質(zhì)☆1.二叉樹定義二叉樹是一種很有用的非線性結(jié)構(gòu)。二叉樹具有以下兩個特點：1)非空二叉樹只有一個根結(jié)點；2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。二叉樹的5種根本形態(tài)?？键c13二叉樹及其根本性質(zhì)☆2.二叉樹的性質(zhì)①在二叉樹的i層上，最多有2i-1個結(jié)點〔i≥1〕。②深度為k的二叉樹最多有2k-1個結(jié)點〔k≥1〕。③對任何一棵二叉樹T，如果葉子結(jié)點的數(shù)為n0，度為2的結(jié)點數(shù)為n2，那么n0=n2+1。④具有n個結(jié)點的二叉樹的深度至少為。考點13二叉樹及其根本性質(zhì)☆2.二叉樹的性質(zhì)【2005年4月】：某二叉樹中度為2的結(jié)點有18個，那么該二叉樹中有______個葉子結(jié)點?！?005年9月】：一棵二叉樹第六層〔根結(jié)點為第一層〕的結(jié)點數(shù)最多為結(jié)構(gòu)。【2007年4月】：某二叉樹中有n個度為2的結(jié)點，那么該二叉樹中的葉子結(jié)點數(shù)為〔〕。 A〕n+1 B〕n-1 C〕2n D〕n/2答案19A32考點13二叉樹及其根本性質(zhì)☆2.二叉樹的性質(zhì)【2007年9月】：一棵二叉樹共有70個葉子結(jié)點與80個度為1的結(jié)點，那么該二叉樹中的總結(jié)點數(shù)為〔〕。A〕219 B〕221 C〕229 D〕231答案A考點13二叉樹及其根本性質(zhì)☆3.滿二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。所謂滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。在滿二叉樹中，每一層上的結(jié)點數(shù)都到達最大值?？键c13二叉樹及其根本性質(zhì)☆3.滿二叉樹【2006年4月】：在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為〔〕。A〕32 B〕31 C〕64 D〕63【2007年4月】：在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為。

【2008年4月】：深度為5的滿二叉樹有個葉子結(jié)點。答案16C63考點13二叉樹及其根本性質(zhì)☆4.完全二叉樹1)定義：所謂完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均到達最大值；在最后一層上只缺少右邊的假設(shè)干結(jié)點。

考點13二叉樹及其根本性質(zhì)☆4.完全二叉樹2)性質(zhì)：①具有n個結(jié)點的完全二叉樹的深度為。②設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序〔每一層從左到右〕用自然1，2，…，n給結(jié)點進行編號，那么對于編號為k〔k=1，2，…，n〕的結(jié)點有以下結(jié)論：假設(shè)是k=1，那么該結(jié)點為根結(jié)點，它沒有父結(jié)點；假設(shè)k>1，那么該結(jié)點的父結(jié)點編號為INT〔k/2〕；假設(shè)2k<=n，那么編號為k的結(jié)點的左子結(jié)點編號為2k，否那么該結(jié)點無左子結(jié)點；假設(shè)2k+1<=n，那么編號為k的結(jié)點的右子結(jié)點編號為2k+1；否那么該結(jié)點無右子結(jié)點考點14二叉樹的存儲結(jié)構(gòu)二叉樹的存儲通常采用鏈接方式。每個結(jié)點除存儲結(jié)點自身的信息外再設(shè)置兩個指針域llink和rlink，分別指向結(jié)點的左子女和右子女，當(dāng)結(jié)點的某個指針為空時，那么相應(yīng)的指針值為空(NULL)?？键c15二叉樹的遍歷☆遍歷〔或稱周游〕是樹形結(jié)構(gòu)的一種重要運算。不重復(fù)訪問二叉樹中的所有結(jié)點?？梢园炊喾N不同的次序遍歷樹形結(jié)構(gòu)。二叉樹的根本組成局部是：根〔N〕、左子樹〔L〕、右子樹〔R〕，因此可有NLR，LNR，LRN，NRL，RNL，RLN六種遍歷次序。以下著重介紹前序遍歷、中序遍歷、后序遍歷?？键c15二叉樹的遍歷☆遍歷規(guī)那么：前序遍歷：先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。中序遍歷：先訪問左子樹，然后遍歷根結(jié)點，最后遍歷右子樹。后序遍歷：先訪問左子樹，然后遍右子樹，最后遍歷根結(jié)點?？键c15二叉樹的遍歷☆【2007年4月】：對以下二叉樹進行前序遍歷的結(jié)果為〔〕A〕DYBEAFCZXB〕YDEBFZXCAC〕ABDYECFXZD〕ABCDEFXYZ答案C考點15二叉樹的遍歷☆【2006年9月】：對以下二叉樹進行中序遍歷的結(jié)果是〔〕 A〕ACBDFEG B〕ACBDFGEC〕ABDCGEF D〕FCADBEG答案A考點15二叉樹的遍歷☆【2008年9月】：對以下二叉樹進行中序遍歷的結(jié)果是：。答案DBXEAYFZC考點15二叉樹的遍歷☆【2006年4月】：對如下二叉樹進行后序遍歷的結(jié)果為〔〕A〕ABCDEF B〕DBEAFC C〕ABDECF D〕DEBFCA答案D考點16順序查找☆順序查找〔順序搜索〕是指在線性表中查找指定的元素。查找方法：從第一個元素開始，逐個比較，假設(shè)相等那么查找成功，假設(shè)找遍所有結(jié)點都不相等，那么查找失敗。優(yōu)點：對線性表的結(jié)點邏輯次序沒有要求〔不必排序〕，對線性表的存儲結(jié)構(gòu)也沒有要求〔順序存儲、鏈?zhǔn)酱鎯钥伞场Ｈ秉c：平均檢索長度大。

對于長度為n的有序線性表，在最壞的情況下，順序查找需要比較n次；平均查找次數(shù)為n/2?？键c16順序查找☆【2005年4月】：對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為〔〕。 A〕log2n B〕n/2 C〕n D〕n+1【2006年9月】：在長度為64的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為〔〕。A〕63 B〕64 C〕6 D〕7

答案CB考點17二分法查找☆二分法查找是一種效率較高的查找方法。二分法查找只適用于順序存儲的有序表。☆查找方法：首先用要查找的元素與線性表中間項比較，這個中間項把線性表分成了兩個子表，比較相等那么查找完成，不等那么根據(jù)比較結(jié)果確定下一步的查找應(yīng)在哪一個子表中進行，如此進行下去，直到找到滿足條件的結(jié)點，或確定表中沒有這樣的結(jié)點為止。對于長度為n的有序線性表，在最壞的情況下，二分查找需要比較次。考點17二分法查找☆【2005年9月】：能用二分法進行查找的是〔〕 A〕順序存儲的有序線性表 B〕線性鏈表C〕二叉鏈表 D〕有序線性鏈表【2008年9月】：在長度為n的有序線性表