1朵耕、線性表阎曹、棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)所表達(dá)和處理的數(shù)據(jù)以線性結(jié)構(gòu)為組織形式处嫌。棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作注暗，允許插入和刪除的一端稱為棧頂墓猎，另一端稱為棧底骗卜。一個(gè)新元素只能從棧頂一端進(jìn)入膨俐，刪除時(shí)焚刺，只能刪除棧頂?shù)脑厝橛洌磩倓偙徊迦氲脑夭端洹Ｋ詶Ｓ址Q后進(jìn)先出表（Last In First Out）泄私；隊(duì)列可看作是插入在一端進(jìn)行，刪除在另一端進(jìn)行的線性表咧纠，允許插入的一端稱為隊(duì)尾漆羔，允許刪除的一端稱為隊(duì)頭。在隊(duì)列中鸟顺，只能刪除隊(duì)頭元素诊沪，隊(duì)列的最后一個(gè)元素一定是最新入隊(duì)的元素端姚。因此隊(duì)列又稱先進(jìn)先出表（First In First Out）。

2昏鹃、棧和隊(duì)列都是一種特殊的操作受限的線性表洞渤，只允許在端點(diǎn)處進(jìn)行插入和刪除讯柔。二者的區(qū)別是：棧只允許在表的一端進(jìn)行插入或刪除操作魂迄，是一種"后進(jìn)先出"的線性表；而隊(duì)列只允許在表的一端進(jìn)行插入操作湿酸，在另一端進(jìn)行刪除操作选泻，是一種"先進(jìn)先出"的線性表页眯。

3傀顾、棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作嫉拐，允許插入和刪除的一端稱為棧頂，另一端稱為棧底盖呼。一個(gè)新元素只能從棧頂一端進(jìn)入几晤，刪除時(shí)章钾，只能刪除棧頂?shù)脑兀磩倓偙徊迦氲脑馗Ｋ詶Ｓ址Q先進(jìn)后出表（FILO-First In Last Out）。線性表可以順序存儲(chǔ)报腔，也可以鏈?zhǔn)酱鎯?chǔ)株搔，而棧是一種線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)纯蛾。

4纤房、棧和隊(duì)列都是一種特殊的操作受限的線性表，只允許在端點(diǎn)處進(jìn)行插入和刪除翻诉。二者的區(qū)別是：棧只允許在表的一端進(jìn)行插入或刪除操作炮姨，是一種"后進(jìn)先出"的線性表舒岸；而隊(duì)列只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作壳澳，是一種"先進(jìn)先出"的線性表。

5弃酌、在棧中豌研，棧底指針不變晶衷，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化

top=0表示椢毯空蛇耀，top=50表示棧滿图甜。入棧操作首先將top加1，然后將新元素插入到top指針指向的位置；退棧操作首先將top指針指向的元素賦給一個(gè)指定的變量殖妇，然后將top減1峭梳。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。

6、棧是一種先進(jìn)后出的線性表待榔，棧實(shí)際上也是線性表分瘦，只不過是一種特殊的線性表土陪。隊(duì)列是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表坷檩，隊(duì)列是一種"先進(jìn)先出"或"后進(jìn)后出"的線性表

隊(duì)列是指允許在一端進(jìn)行插入酬土、而在另一端進(jìn)行刪除的線性表叽唱。它又稱為"先進(jìn)先出"或"后進(jìn)后出"的線性表种樱，體現(xiàn)了"先來先服務(wù)"的原則嫩挤。

7、帶鏈的隊(duì)列也是線性鏈表外傅，在線性鏈表中指向線性表中的第一個(gè)結(jié)點(diǎn)的指針稱為頭指針攀细，頭指針為NULL或0時(shí)稱為空表，指向隊(duì)尾元素的指針稱為尾指針锦担。隊(duì)列在隊(duì)尾插入元素俭识，稱為入隊(duì)運(yùn)算；在隊(duì)頭刪除元素洞渔，稱為退隊(duì)運(yùn)算套媚。帶鏈隊(duì)列在開辟存儲(chǔ)空間時(shí)，可以按照存儲(chǔ)空間地址增大的方向開辟磁椒，也可以按照存儲(chǔ)空間地址減少的方向開辟堤瘤。

8、所謂循環(huán)隊(duì)列浆熔，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第1個(gè)位置本辐，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用蘸拔。所以循環(huán)隊(duì)列還是屬于線性結(jié)構(gòu)师郑。循環(huán)隊(duì)列的頭指針front指向隊(duì)列的第一個(gè)元素的前一位置，隊(duì)尾指針rear指向隊(duì)列的最后一個(gè)元素调窍，循環(huán)隊(duì)列的動(dòng)態(tài)變化需要頭尾指針共同反映循環(huán)隊(duì)列的長(zhǎng)度是：(sq.rear-sq.front+maxsize)%maxsize，所以循環(huán)隊(duì)列的長(zhǎng)度是由隊(duì)頭和隊(duì)尾指針共同決定的

?在循環(huán)隊(duì)列中张遭，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素邓萨，用排頭指針front指向排頭元素的前一個(gè)位置。

?循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算缔恳，隊(duì)尾指針就進(jìn)一宝剖。每進(jìn)行一次退隊(duì)運(yùn)算，排頭指針就進(jìn)一歉甚。當(dāng)rear或front的值等于隊(duì)列的長(zhǎng)度+1時(shí)万细，就將rear或front的值置為1。一般情況下纸泄，rear大于front赖钞，因?yàn)槿腙?duì)的元素肯定比出隊(duì)的元素多。特殊的情況是rear到達(dá)數(shù)組的上限之后又從數(shù)組的低端開始聘裁，此時(shí)雪营，rear是小于front的。

循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置衡便，形成邏輯上的環(huán)狀空間献起，供隊(duì)列循環(huán)使用。在實(shí)際應(yīng)用中镣陕，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式谴餐。因此，循環(huán)隊(duì)列不是隊(duì)列的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)呆抑。循環(huán)隊(duì)列是一種存儲(chǔ)結(jié)構(gòu)岂嗓，因此循環(huán)隊(duì)列是一種物理結(jié)構(gòu)，而不是邏輯結(jié)構(gòu)理肺。循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)摄闸，因此循環(huán)隊(duì)列是線性結(jié)構(gòu)。

9妹萨、循環(huán)隊(duì)列不同于循環(huán)鏈表年枕，循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)，循環(huán)鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)乎完。雙向鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)熏兄，其中每個(gè)結(jié)點(diǎn)都有左指針和右指針，不同于二叉樹結(jié)點(diǎn)的左子樹指針和右子樹指針树姨。非線性結(jié)構(gòu)和線性結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)摩桶，順序和鏈?zhǔn)绞菙?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，例如二叉樹是非線性結(jié)構(gòu)帽揪，也可以按照層序進(jìn)行順序存儲(chǔ)硝清。

10、非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)元素可能對(duì)應(yīng)多個(gè)直接前驅(qū)和多個(gè)后驅(qū)转晰。常見的非線性結(jié)構(gòu)有：樹（二叉樹等）芦拿，圖（網(wǎng)等）士飒。

11、由于二叉樹的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域蔗崎，因此酵幕，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表，二叉鏈表屬于非線性結(jié)構(gòu)缓苛。

12芳撒、遍歷是指不重復(fù)的訪問所有結(jié)點(diǎn)。線性單鏈表每個(gè)結(jié)點(diǎn)只有一個(gè)指針域未桥，由這個(gè)指針只能找到后件結(jié)點(diǎn)笔刹，但不能找到前件結(jié)點(diǎn)。雙向鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針钢属，左指針指向其前件結(jié)點(diǎn)徘熔，右指針指向其后件結(jié)點(diǎn)。循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)淆党，循環(huán)鏈表中的所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈酷师。二叉鏈表即二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域染乌，左指針域指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址山孔，右指針域指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址。

13荷憋、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的;（2）線性表中各元素在存儲(chǔ)空間中是按邏輯順序依次存放的台颠。

14、循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：(1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)勒庄，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置串前，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)实蔽。(2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空荡碾，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中局装，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈坛吁。

15、在循環(huán)鏈表中铐尚，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置拨脉，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)宣增。

16玫膀、根據(jù)二叉樹的性質(zhì)：二叉樹第i（i≥1）層上至多有2i-1個(gè)結(jié)點(diǎn)。

17爹脾、所謂滿二叉樹是指這樣的一種二叉樹：除最后一層外匆骗，每層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)劳景。這就是說誉简，在滿二叉樹中碉就，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)闷串，且深度為m的滿二叉樹有2m個(gè)結(jié)點(diǎn)瓮钥。

18、在任意一顆樹中烹吵，結(jié)點(diǎn)總數(shù)=總分支數(shù)目+1

19碉熄、二叉樹的性質(zhì)：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)肋拔。本題中度為2的結(jié)點(diǎn)數(shù)為n锈津，故葉子結(jié)點(diǎn)數(shù)為n+1個(gè)。

二叉樹的性質(zhì)：在任意一棵二叉樹中凉蜂，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)琼梆。

20、在用完全二叉樹表示堆窿吩，樹中所有非葉子結(jié)點(diǎn)值均不小于其左右子樹的根結(jié)點(diǎn)值茎杂，因此，堆頂元素必為序列的n個(gè)元素中的最大項(xiàng)纫雁。

21煌往、作為一個(gè)算法，一般應(yīng)具有以下幾個(gè)基本特征轧邪。

?可行性

?確定性

?有窮性

擁有足夠的情報(bào)

22刽脖、計(jì)算機(jī)算法是指解題方案的準(zhǔn)確而完整的描述

算法的有窮性，是指算法必須在有限的時(shí)間內(nèi)做完忌愚，即算法必須能在執(zhí)行有限個(gè)步驟之后終止曲管。

23、希爾排序法的基本思想是：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序菜循。所以希爾排序法屬于插入類排序翘地，但它對(duì)簡(jiǎn)單插入排序做了很大的改進(jìn)。

24癌幕、快速排序的基本思想是衙耕，通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小勺远，再分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序橙喘，以達(dá)到整個(gè)序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中胶逢，從而得到一個(gè)新的序列厅瞎；選擇排序的基本思想是：掃描整個(gè)線性表饰潜，從中選出最小的元素，將它交換到表的最前面（這是它應(yīng)有的位置）和簸，然后對(duì)剩下的子表采用同樣的方法彭雾，直到表空為止；歸并排序是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表锁保。

25薯酝、在單鏈表中，增加頭結(jié)點(diǎn)的目的是______爽柒。

頭結(jié)點(diǎn)不僅標(biāo)識(shí)了表中首結(jié)點(diǎn)的位置吴菠，而且根據(jù)單鏈表（包含頭結(jié)點(diǎn)）的結(jié)構(gòu)，只要掌握了表頭浩村，就能夠訪問整個(gè)鏈表做葵，因此增加頭結(jié)點(diǎn)目的是為了便于運(yùn)算的實(shí)現(xiàn)。

26心墅、算法分析是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量的分析酿矢，一般計(jì)算出相應(yīng)的數(shù)量級(jí)，常用時(shí)間復(fù)雜度和空間復(fù)雜度表示嗓化。分析算法的目的就是要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度棠涮，提高算法的執(zhí)行效率。

27刺覆、算法是指解題方案的準(zhǔn)確而完整的描述严肪。但算法不等于程序，也不等于計(jì)算方法谦屑。當(dāng)然驳糯，程序也可以作為算法的一種描述，但程序通常還需要考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題氢橙，這是因?yàn)樵诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制酝枢。通常，程序的編制不可能優(yōu)于算法的設(shè)計(jì)悍手。作為一個(gè)算法帘睦，一般應(yīng)具有可行性、確定性坦康、有窮性竣付、擁有足夠情報(bào)四個(gè)基本特征。因此設(shè)計(jì)算法時(shí)不僅僅要考慮結(jié)果的可靠性滞欠，即不僅考慮算法結(jié)果的可行性古胆，還要考慮步驟的確定性，時(shí)間和步驟的有窮性等筛璧。因此逸绎，算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則惹恃，并且每一個(gè)規(guī)則都是有效的，且是明確的棺牧，此順序?qū)⒃谟邢薜拇螖?shù)下終止巫糙。

28、一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作陨帆，二是算法的控制結(jié)構(gòu)曲秉。因此設(shè)計(jì)算法時(shí)不僅需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，還要考慮數(shù)據(jù)的操作和運(yùn)算及各操作之間的執(zhí)行順序疲牵。

29、在有向圖中榆鼠，若任意兩個(gè)頂點(diǎn)都連通纲爸，則稱該圖是強(qiáng)連通圖，這樣的有向圖的形狀是環(huán)狀妆够，因而至少應(yīng)有n條邊识啦。

30、當(dāng)數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)神妹，說明數(shù)據(jù)表A按關(guān)鍵字值基本有序颓哮，在待排序序列基本有序的情況下，采用插入排序所用時(shí)間最少鸵荠。

31冕茅、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。

32蛹找、假設(shè)線性表的長(zhǎng)度為n姨伤，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后掃描和n/2遍的從后往前掃描庸疾，需要比較次數(shù)為n(n-1)/2乍楚。快速排序法的最壞情況比較次數(shù)也是n(n-1)/2

（1）冒泡排序法：是一種最簡(jiǎn)單的交換類排序法届慈，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序徒溪。假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下金顿，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描臊泌，需要比較的次數(shù)為n(n-1)/2次。

?（2）簡(jiǎn)單插入排序法：在簡(jiǎn)單插入排序法中串绩，每一次比較后最多移掉一個(gè)逆序缺虐，因此，這種排序方法的效率與冒泡排序法相同礁凡。在最壞情況下高氮，簡(jiǎn)單插入排序需要n(n-1)/2次比較慧妄。

?（3）簡(jiǎn)單選擇排序法：對(duì)于長(zhǎng)度為n的序列，選擇排序需要掃描n-1遍剪芍，每一遍掃描均從剩下的子表中選出最小的元素塞淹，然后將該最小的元素與子表中的第一個(gè)元素進(jìn)行交換。簡(jiǎn)單選擇排序法在最壞情況下需要比較n(n-1)/2次罪裹。

?（4）堆排序法：堆排序的方法為：①首先將一個(gè)無序序列建成堆饱普。②然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。在最壞情況下状共，堆排序需要比較的次數(shù)為套耕。

?假設(shè)線性表的長(zhǎng)度為16，那么冒泡排序峡继、直接插入排序冯袍、簡(jiǎn)單選擇排序都需要比較120次，而堆排序需要比較64次碾牌。

33康愤、對(duì)于長(zhǎng)度為n的線性表，在最壞的情況下舶吗，快速排序所需要的比較次數(shù)為n(n-1)/2征冷；冒泡排序所需要的比較次數(shù)為n(n-1)/2；直接插入排序所需要的比較次數(shù)為n(n-1)/2誓琼；堆排序所需要的比較次數(shù)為检激。

34、在進(jìn)行順序查找過程中踊赠，如果線性表中的第一個(gè)元素就是被查找元素呵扛，則只需做一次比較就查找成功，查找效率最高筐带；但如果被查找的元素是線性表中的最后一個(gè)元素今穿，或者被查找的元素根本就不在線性表中，則為了查找這個(gè)元素需要與線性表中所有的元素進(jìn)行比較伦籍，這是順序查找的最壞情況蓝晒。所以對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下需要比較n次帖鸦。

35芝薇、二分法查找只適用于順序存儲(chǔ)的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大作儿，但允許相鄰元素值相等）洛二。

二分法檢索要求線性表結(jié)點(diǎn)按關(guān)鍵值排序且以順序方式存儲(chǔ)。在查找時(shí)，首先與表的中間位置上結(jié)點(diǎn)的關(guān)鍵值比較晾嘶，若相等則檢索成功妓雾；否則根據(jù)比較結(jié)果確定下一步在表的前半部分或后半部分繼續(xù)進(jìn)行。二分法檢索的效率比較高垒迂，設(shè)線性表有n個(gè)元素械姻，則最多的檢索次數(shù)為大于log2n(2為底數(shù))的最小整數(shù)，最少的檢索次數(shù)為1机断。

36楷拳、一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)吏奸，常用的存儲(chǔ)結(jié)構(gòu)有順序欢揖、鏈接、索引等存儲(chǔ)結(jié)構(gòu)苦丁。而采用不同的存儲(chǔ)結(jié)構(gòu)浸颓，其數(shù)據(jù)處理的效率是不同的。

37旺拉、順序存儲(chǔ)結(jié)構(gòu)就是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)該線性表中的各個(gè)元素，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的棵磷，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致蛾狗。兩者都可以存儲(chǔ)線性的、有序的邏輯結(jié)構(gòu)仪媒，順序結(jié)構(gòu)使用的是連續(xù)物理空間沉桌，鏈?zhǔn)浇Y(jié)構(gòu)可以使用零散的物理空間存儲(chǔ)，鏈?zhǔn)浇Y(jié)構(gòu)更靈活算吩，不存在誰節(jié)約空間的說法

38留凭、順序存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)元素存放在一組地址連續(xù)的存儲(chǔ)單元中偎巢，每個(gè)數(shù)據(jù)元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計(jì)算得到蔼夜，從而實(shí)現(xiàn)了隨機(jī)存取。對(duì)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)压昼，要對(duì)某結(jié)點(diǎn)進(jìn)行存取求冷，都得從鏈的頭指針指向的結(jié)點(diǎn)開始，這是一種順序存取的存儲(chǔ)結(jié)構(gòu)窍霞。

39匠题、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示但金，不需要移動(dòng)數(shù)據(jù)元素韭山。故鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表便于插入和刪除操作。

40、線性表的順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間只用于存放結(jié)點(diǎn)數(shù)據(jù)钱磅，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不僅要存放結(jié)點(diǎn)數(shù)據(jù)梦裂，還要存放數(shù)據(jù)的指針，所以線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)

41续搀、在進(jìn)行順序查找過程中塞琼，如果線性表中的第1個(gè)元素就是被查找元素，則只需做一次比較就查找成功禁舷，查找效率最高彪杉；但如果被查找的元素是線性表中的最后一個(gè)元素，或者被查找的元素根本就不在線性表中牵咙，則為了查找這個(gè)元素需要與線性表中所有的元素進(jìn)行較派近，這是順序查找的最壞情況。所以對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找洁桌，在最壞情況下需要比較n次

42渴丸、對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下另凌，二分查找只需要比較 次谱轨，而順序查找需要比較n次。二分法查找只適用于順序存儲(chǔ)的有序表吠谢，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)土童，也只能用順序查找,所以，對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找工坊，最壞情況下需要的比較次數(shù)為n

43献汗、根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)王污。

44罢吃、如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件昭齐，也最多有一個(gè)后件尿招。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱線性表司浪。

45泊业、有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)肯定是非線性結(jié)構(gòu)，循環(huán)鏈表啊易、雙向鏈表是線性結(jié)構(gòu)槽惫；線性表峡竣、棧與隊(duì)列沈跨、線性鏈表都是線性結(jié)構(gòu)展氓，而二叉樹是非線性結(jié)構(gòu)捆愁。

46、在鏈表中窟却，如果有兩個(gè)結(jié)點(diǎn)的同一個(gè)指針域的值相等昼丑，則該鏈表一定是非線性結(jié)構(gòu)

47、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表夸赫，為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)菩帝，計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊，每一小塊占若干字節(jié)茬腿，通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)呼奢。每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域切平；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)握础，即指向后件的結(jié)點(diǎ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)系可以不一致苔严。為了要在線性鏈表中插入一個(gè)新元素定枷，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便用于存儲(chǔ)該元素的值届氢，然后將存放新元素值的結(jié)點(diǎn)鏈接到線性表中指定的位置依鸥。在線性鏈表的插入過程中不發(fā)生數(shù)據(jù)無素移動(dòng)的現(xiàn)象，只需改變有關(guān)結(jié)點(diǎn)的指針即可悼沈，從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)姐扮，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)絮供，然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。在線性鏈表中刪除一個(gè)元素后茶敏，不需要移動(dòng)表的數(shù)據(jù)元素壤靶，只需改變被刪元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針域即可。因此惊搏，進(jìn)行插入與刪除時(shí)贮乳，不需要移動(dòng)表中的元素。

48恬惯、在先左后右的原則下向拆，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為3種：前序遍歷酪耳、中序遍歷和后序遍歷浓恳。

前序遍歷是指在訪問根結(jié)點(diǎn)刹缝、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)颈将，然后遍歷左子樹梢夯，最后遍歷右子樹；并且遍歷左晴圾、右子樹時(shí)颂砸，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹死姚，最后遍歷右子樹人乓。

后序遍歷指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中知允，首先遍歷左子樹撒蟀，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)温鸽；并且遍歷左保屯、右子樹時(shí)，仍然先遍歷左子樹涤垫，然后遍歷右子樹姑尺，最后訪問根結(jié)點(diǎn)。

二叉樹的中序遍歷指在訪問根結(jié)點(diǎn)蝠猬、遍歷左子樹與遍歷右子樹這三者中切蟋，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)榆芦，最后遍歷右子樹柄粹；并且遍歷左、右子樹時(shí)匆绣，仍然先遍歷左子樹驻右，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹崎淳。

49堪夭、鏈表有線性鏈表，也有非線性鏈表拣凹。線性鏈表和二叉樹鏈表的結(jié)點(diǎn)都有兩個(gè)指針域森爽，前者是線性結(jié)構(gòu)，后者是非線性結(jié)構(gòu)嚣镜。線性單鏈表中的結(jié)點(diǎn)只有一個(gè)指針爬迟，葉子結(jié)點(diǎn)一般是對(duì)樹結(jié)構(gòu)而言，樹結(jié)構(gòu)是非線性結(jié)構(gòu)祈惶，不是線性表雕旨。

50扮匠、算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度：算法在運(yùn)行過程中需輔助存儲(chǔ)空間的大小稱為算法的空間復(fù)雜度；算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量凡涩，即算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)棒搜，為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)活箕，不僅應(yīng)該與所使用的計(jì)算機(jī)力麸、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)育韩。為此克蚂，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。二者沒有直接關(guān)系筋讨。

51埃叭、一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間悉罕。一個(gè)算法所占用的存儲(chǔ)空間包括程序所占的空間赤屋、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間壁袄。如果額外空間相對(duì)于問題規(guī)模來說是常數(shù)类早，則稱該算法是原地(in place)工作的。

52嗜逻、我們通常用時(shí)間復(fù)雜度和空間復(fù)雜度來衡量算法效率涩僻，算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；算法所執(zhí)行的基本運(yùn)算次數(shù)與問題的規(guī)模有關(guān)栈顷，而一個(gè)算法的空間復(fù)雜度逆日，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間；一般來說萄凤，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)屏富。

所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量蛙卤。為了能夠比較客觀地反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)噩死，不僅應(yīng)該與所使用的計(jì)算機(jī)颤难、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)已维。為此行嗤，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。

53垛耳、子程序調(diào)用是一種層次關(guān)系栅屏，子程序調(diào)用功能模塊飘千，調(diào)用功能模塊的個(gè)數(shù)也不確定，可以是一個(gè)栈雳，也可以是多個(gè)护奈。二叉樹是一種很有用的非線性結(jié)構(gòu)，二叉樹不同于樹形結(jié)構(gòu)哥纫。二叉樹具有以下兩個(gè)特點(diǎn)：①非空二叉樹只有一個(gè)根結(jié)點(diǎn)霉旗；②每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹蛀骇。選項(xiàng)D規(guī)定每個(gè)結(jié)點(diǎn)只能有兩個(gè)后件厌秒。在子程序調(diào)用中，調(diào)用的功能模塊可以是多個(gè)擅憔，可以調(diào)用超過兩個(gè)功能模塊鸵闪。

54、結(jié)構(gòu)圖的深度表示控制的層數(shù)結(jié)構(gòu)圖的深度表示控制的層數(shù)

55暑诸、數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示蚌讼。更通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合屠列。所謂結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系啦逆。線性結(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ī)則來處理的，則屬于線性結(jié)構(gòu)苛让；否則屬于非線性結(jié)構(gòu)沟蔑。