數(shù)據(jù)結(jié)構(gòu)復習

*)設(shè)一組初始記錄關(guān)鍵字序列(8，3，6，5，9)，以第一個記錄關(guān)鍵字8為基準進行一趟快速排序的結(jié)果為5,3,6,8,9*)用快速排序法對序列（22，5，8，20，18，10）進行升序排序，寫出每一趟的排序過程。第一趟：{10582018}22第二趟：{85}10{2018}22第三趟：58101820*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為___選擇排序_______*)內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。按照排序過程涉及的存儲設(shè)備的不同，排序通常可分為內(nèi)部排序和外部排序。*)用簡單選擇排序法對關(guān)鍵字序列(46，90，48，30，22，78)進行升序排序，寫出每一趟的排序過程。P247答：第一趟：(22)9048304678第二趟：(2230)48904678 第三趟：(223046)904878第四趟：(22304648)9078第五趟：(2230464878)90堆是完全二叉樹，完全二叉樹不一定是堆正確直接選擇排序是一種穩(wěn)定的排序方法錯誤（它是一種不穩(wěn)定的排序方法）堆的形狀是一棵__完全二叉樹___________*)假設(shè)關(guān)鍵字的輸入順序為(12,2,16,30,28,10,16,20,6,18),畫出堆排序每趟排序結(jié)束后關(guān)鍵字狀態(tài)。P2702(1)題圖片*)簡述快速排序算法思想。設(shè)要排序的\t"/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/_blank"數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個過程稱為一趟快速排序*)在快速排序、堆排序、歸并排序中，____歸并排序_____排序是穩(wěn)定的。快速排序在___被排序的數(shù)據(jù)完全無序___情況下最易發(fā)揮其長處。P246*)希爾排序?qū)嵸|(zhì)上是采用_分組插入___的方法來實現(xiàn)的。設(shè)待排序的關(guān)鍵字序列為{12，26，40，28，30，20，6，18}，試寫出使用直接插入排序，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。答初始化關(guān)鍵字（12）2640283020618i=1 （1226）40283020618i=2 （122640）283020610i=3 （12262840）3020610i=4 （1226283040）20610i=5 （122026283040）610i=6 （6122026283040）10i=7 （610122026283040）*)簡述插入排序的基本思想每一趟講一個待排序的記錄，安其關(guān)鍵字的大小插入到已經(jīng)排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素52，則它將依次與表中（20703050）比較大小，查找結(jié)果是失敗。P231第7題折半查找只適用于有序表，包括有序的順序表和鏈表*）適用于折半查找的表的存儲方式及元素排列要求為順序方式存儲，元素有序*）對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關(guān)鍵字。P230第5題解法：第一次（1+22）/2=11假設(shè)在左邊第二次（1+10）/2=5第三次（1+4）/2=2第四次與第1個位置上的數(shù)進行比較*)散列表的沖突處理方法，按組織形式的不同，分為___開放定址法________和____拉鏈(Chaining)法_________.*)散列表的平均查找長度取決于裝填因子。

*)創(chuàng)建二叉排序樹的時間復雜度為______________*)平衡二叉樹的左子樹和右子樹的深度之差的絕對值不超過1*)已知關(guān)鍵字的輸入序列為（352348824135725），畫出建立平衡排序二叉樹的過程。答：如圖所以（因為不知道我做的對錯，如果錯了和我說下）*）對有序表（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找元素42和80，則需要分別依次與哪些元素比較？答：3063428772*）若有18個元素的有序表存放在一維數(shù)組A[18]中，第一個元素放A[1]中，現(xiàn)進行折半查找，則查找A［3］的比較序列的下標依次為答：這個題有一點點問題，應(yīng)該是A[19]才對答案為：9423在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。答：如圖所示：*）長度20的有序表進行折半查找，則對應(yīng)的判定樹高度為答：5次*）對一個有序表：(13，18，24，35，47，50，62)進行折半查找，畫出折半查找過程的判定樹，并給出查找元素24時，需要依次與哪些元素比較？答：如圖所示*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為插入排序*)由3個結(jié)點可以構(gòu)造出（5）種不同的二叉樹*)一個具有1025個結(jié)點的二叉樹的高h為11至1025之間注：折半折半的計算算出最小的來*)設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（n+1）個。*）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（A）。A．空 B．非空C．指向最左孩子 D．指向最右孩子注意：二叉鏈表：

左孩子右兄弟根節(jié)點沒有兄弟，所以為空 *)用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常借助（B）來實現(xiàn)算法。A．棧 B.隊列 C.樹 D．圖廣搜都是隊列

鄰接表是鏈表*)在下列存儲形式中，（D）不是樹的存儲形式？A．雙親表示法 B．孩子鏈表表示法C．孩子兄弟表示法 D．順序存儲表示法*)二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)11二叉樹有如下性質(zhì)

N0=N2+1，葉子節(jié)點個數(shù)等于度為2的節(jié)點個數(shù)+1

*)深度為h的滿m叉樹的第k層有（B）個結(jié)點。(1=<k=<h)mk-1 B．mk-1 C．mh-1 D．mh-1*)n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，以下關(guān)于該樹的敘述中，錯誤的是（A）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點C．樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D．樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值*）拓撲排序算法能判斷有向圖中存在環(huán)*)一棵完全二叉樹上有1001個結(jié)點，則該二叉樹中度為1的結(jié)點個數(shù)是1，葉子結(jié)點的個數(shù)是500，二叉樹的高度是10。答：該樹有：2^9+489=1001同所以該樹高度為10其中10層的489個節(jié)點度為0同時這489個節(jié)點使得第9層有244度為21個度為1第9層共有2^（9-1）個節(jié)點256個節(jié)點所以第9層度為葉子節(jié)點有11個加上第10層的489個一共有500個葉子節(jié)點*)某二叉樹結(jié)點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為4個提示：根據(jù)中序后序畫出二叉樹*)設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（100）個葉子結(jié)點提示：在哈夫曼樹中，葉子節(jié)點總比內(nèi)節(jié)點多一個，沒有度為1的節(jié)點所以設(shè)度為0的為a度為2的為ba=b+1n=a+b所以n=2*a-1b=100*)在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（2）倍*)具有n個頂點的有向圖最多有（n(n-1)）條邊。完全有向圖*)若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（連通圖）圖*)已知圖的鄰接表如右圖所示，則從頂點v0出發(fā)的按照深度優(yōu)先遍歷的結(jié)果是（）*）Kruskal算法適合構(gòu)造一個稀疏圖G的最小生成樹，Prim算法適合構(gòu)造一個稠密圖G的最小生成樹*)有很少條邊或弧的圖稱為稀疏圖,反之稱為稠密圖對*)p1882（1）鄰接矩陣和鄰接表*)簡述迪杰斯特拉算法思想。*)簡述圖的廣度優(yōu)先搜索算法思想。廣度優(yōu)先搜索是一種圖的搜索算法。在搜索開始，會確定一個搜索的起點，然后選擇一個與其相鄰的且在值上與節(jié)點最接近的點，然后迭代進行，如果在最后發(fā)現(xiàn)所有鄰居都已經(jīng)被訪問過，則開始回溯*)簡述克魯斯卡爾算法思想。答：考慮問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。

具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。*)度為2的有序樹是二叉樹錯*)存在這樣的二叉樹，其任何次序的遍歷結(jié)果都相同對*)圖的廣度優(yōu)先搜索樹是惟一的。錯*)圖的深度優(yōu)先遍歷類似于二叉樹的__前序遍歷_______*)G是一個非連通無向圖，共有28條邊，則該圖至少有（9）個頂點注：將28條邊全部連接起來的最小頂點數(shù)為8，因為非連通，再加一個頂點得答案9*)存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 錯*)完全二叉樹某結(jié)點有右子樹，則必然有左子樹。 對 *)圖的深度優(yōu)先序列和廣度優(yōu)先序列不是惟一的。 對 *)鄰接表只能用于存儲有向圖。 錯 *)從源點到終點的最短路徑是唯一的。對 *)強連通圖的各頂點間均可達。對*)完全二叉樹某結(jié)點有右子樹，則必然有左子樹。 對 *)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。 對 *)圖的廣度優(yōu)先搜索樹是惟一的。錯 *)圖的生成樹是惟一的。 錯 *)無向圖的連通分量是其極小連通子圖。 錯*)二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。 錯 *)具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。 對 *)哈夫曼樹中沒有度數(shù)為1的結(jié)點。 對 *)中序遍歷一棵二叉排序樹可以得到一個有序的序列。 對*)二叉樹的先序、中序、后序遍歷*)在用二叉鏈表存儲一棵二叉樹時，n個結(jié)點的二叉樹共有___2n_____個指針域，其中有____n-1____個指針域是存放了地址，有_____n+1__個指針是空指針。*)圖有鄰接矩陣、鄰接表等存儲結(jié)構(gòu)，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。*)在無向圖G的鄰接矩陣A中，A[i][j]=1，則A[j][i]=1*)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為8，葉子結(jié)點的個數(shù)為___64_____。*)一棵完全二叉樹上有500個結(jié)點，則該二叉樹中度為1的結(jié)點個數(shù)是1，葉子結(jié)點的個數(shù)是250，二叉樹的高度是9。*)遍歷圖的基本方法有廣度優(yōu)先遍歷和深度優(yōu)先遍歷兩種，其中可以借助棧實現(xiàn)的是深度優(yōu)先遍歷，可以借助隊列實現(xiàn)的是廣度優(yōu)先遍歷。*)具有10個頂點的無向圖，邊的總數(shù)最多為____45____。注：n(n-1)/2*)二叉樹的后序遍歷是CBEDA，中序序列是BCADE，則該二叉樹的樹根是A，根結(jié)點的左孩子是B，右孩子是D，二叉樹的先序序列為ABCDE。*)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的先序遍歷序列為__ABDECF_________，中序遍歷序列為__DBEAFC________，后序遍歷序列為___DEBFCA________。*)樹結(jié)構(gòu)中根節(jié)點___沒有_____雙親結(jié)點，其余每個結(jié)點都有1個雙親結(jié)點；葉子結(jié)點沒有孩子結(jié)點，其余每個結(jié)點都有至少1個孩子結(jié)點。*)在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的__2____倍。*)度為2的樹與二叉樹有何區(qū)別？答：度為2的樹是不區(qū)分左右子樹的，而二叉樹左子樹與右子樹是不一樣的度為2的樹是不包含空樹，而二叉樹是可以有空樹的總結(jié)：二叉樹定義要比度為2的樹嚴格*)簡述連通圖的生成樹的定義答：連通圖G(V,E),當從圖的任意一頂點出發(fā)，將邊集E(G)分成T（G）和B（G），其中T（G）是遍歷圖時所經(jīng)歷過的邊的集合，B（G）是遍歷圖未經(jīng)過邊的集合，即，G1（V,T）就是G的極小聯(lián)通子圖，所以G1就是連通圖G的生成樹。*)一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為6，5，9，13，30，1，畫出對應(yīng)的哈夫曼樹（要求每個結(jié)點左孩子的頻率不高于右孩子的頻率）；計算其帶權(quán)路徑長度WPL解：WPL=1*5+5*5+6*4+9*3+13*2+30*1=137*)已知如圖所示的無向網(wǎng)，請畫出它的最小生成樹(兩個算法都要掌握)。答：普里姆算法克魯斯卡爾算法*)假設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC，畫出這棵二叉樹，求這棵二叉樹的后序序列。答：后序遍歷為：FDBGHECA*)已知如圖所示的有向圖，請給出：每個頂點的入度和出度、鄰接矩陣和鄰接表。ID：入度OD：出度ID(1)=3OD（1）=0（1）ID(2)=2OD（2）=1（1）ID(3)=1OD（3）=2（1）ID(4)=1OD（4）=3（1）ID(5)=2OD（5）=1ID(6)=2OD（6）=3*)P17(1)(2),(3)(4)(5)(6)*)邏輯結(jié)構(gòu)的四種基本關(guān)系。*)數(shù)據(jù)結(jié)構(gòu)主要包括哪三方面內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算.*)邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系。邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，而存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示，它包括數(shù)據(jù)元素的表示及其關(guān)系的表示。一種邏輯結(jié)構(gòu)可以采用一種或幾種存儲方式來表達數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的存儲結(jié)構(gòu)稱為給定邏輯結(jié)構(gòu)的存儲實現(xiàn)或存儲映像。*)線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。線性結(jié)構(gòu)是最簡單最常用的一種數(shù)據(jù)結(jié)構(gòu),線性結(jié)構(gòu)的特點是結(jié)構(gòu)中的元素之間滿足線性關(guān)系,按這個關(guān)系可以把所有元素排成一個線性序列.線性表,串,棧和隊列都屬于線性結(jié)構(gòu).

而非線性結(jié)構(gòu)是指在該類結(jié)構(gòu)中至少存在一個數(shù)據(jù)元素,它具有兩個或者兩個以上的前驅(qū)或后繼.如樹和二叉樹等.*)評估算法的優(yōu)劣，通常從時間復雜度和空間復雜度兩個方面考察。*)數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：邏輯結(jié)構(gòu)和__儲存____結(jié)構(gòu)，數(shù)據(jù)的存儲方法主要有兩種：順序存儲方法和鏈式存儲方法。*)程序段“i=1;while(i<=n)i=i*3;”的時間復雜度為。解析：假設(shè)循環(huán)次數(shù)是x。

i=1,3,9,27,i=3^x

條件是i<=n

3^x<=n

所以x<=log3n一共執(zhí)行循環(huán)體log3n次，所以時間復雜度是O(log3n)*)線性結(jié)構(gòu)中元素之間是一對一關(guān)系，樹結(jié)構(gòu)中元素之間是一對多關(guān)系，圖結(jié)構(gòu)中元素之間是多對多關(guān)系。*)線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，其元素的個數(shù)稱為線性表的長度。*)p51(1)(2)(3)(5)(6)(7)(9)(11)(13)*)存儲密度*)非空的循環(huán)單鏈表head的尾結(jié)點p滿足（A）。A．p->next==head B.p->next==NULL C.p==NULL D.p==headP83(1)(2)(3)(10)(12)(14)(15)P108(1)(5)(6)(7)(8)(11)(12)(14)(15)判斷題：*)數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。錯*)順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯*)單鏈表不是一種隨機存儲結(jié)構(gòu)對*)循環(huán)鏈表不是線性表。錯*)數(shù)組元素的下標值越大，存取時間越長。 錯 *)線性表中的所有元素都有一個前驅(qū)元素和后繼元素。錯*)一個遞歸算法必須包括終止條件和迭代部分。 錯是遞歸部分 *)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。 對*)空串就是空格串。 錯 空串是"";空白串是null

*)廣義表的元素可以是單原子也可以是子表。對*)棧和隊列都是受限的線性結(jié)構(gòu)。 對 *)以鏈表作為棧的存儲結(jié)構(gòu)，出棧必須判別?？盏那闆r。對*）循環(huán)鏈表不是線性表。錯1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容。2.在具有n個元素的循環(huán)隊列中，隊滿時具有n-1個元素。3.在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)當有多個函數(shù)構(gòu)成嵌套調(diào)用時，按照____后調(diào)用先返回________的原則，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過_____棧_____來實現(xiàn)。4.廣義表(a，(b)，((c，(d))))的長度是2，深度是3，表頭是a，表尾是(b)，((c，(d)))。5.設(shè)二維數(shù)組A的內(nèi)存首地址為M，其行下標i=0,1,…,8,列下標j=1,2,…,10。若A按行先存儲，則元素A[8,5]的地址為M+84；當A按列先存儲時，該地址存放的的元素是A[8][5]。設(shè)每個字符占一個字節(jié)。若其首地址是S，每個元素占k個字節(jié)，則數(shù)組元素A[i][j]的地址P是p=S+(i*n+j)*kP=M+(8*10+4)*11.評估算法的優(yōu)劣，通常從時間復雜度和空間復雜度兩個方面考察。2.數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：___線性__結(jié)構(gòu)和_非線性_結(jié)構(gòu)，數(shù)據(jù)的存儲方法主要有兩種：順序存儲方法和鏈式存儲方法。3.用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列時，如果當前front和rear的值分別為3和0，則從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為4和2。解析：當出隊列中刪除一個元素，也就是出隊，即front+1:=4再插入兩個元素，即rear+2=22.線性結(jié)構(gòu)中元素之間是一對一關(guān)系，樹結(jié)構(gòu)中元素之間是一對多關(guān)系，圖結(jié)構(gòu)中元素之間是多對多關(guān)系。3.具有n個元素的循環(huán)隊列中，隊滿時有n-1個元素。4.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結(jié)點數(shù)為__9_____個，樹的深度為3，樹的度為___8____。1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容。2.線性結(jié)構(gòu)中元素之間是一對一關(guān)系，樹結(jié)構(gòu)中元素之間是一對多關(guān)系，圖結(jié)構(gòu)中元素之間是多對多關(guān)系。3.用容量為6的數(shù)組來實現(xiàn)循環(huán)隊列時，如果當前front和rear的值分別為4和1，則從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為和5,6。*)在具有n個元素的循環(huán)隊列中，隊滿時具有n-1個元素。*)在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)已知循環(huán)隊列的存儲空間大小為20，且當前隊列的頭指針和尾指針的值分別為8和3，則該隊列的當前的長度為__15_____；插入2個元素又刪除5個元素后頭指針變?yōu)?0，尾指針變?yōu)?，隊列長度變?yōu)?8。長度計算：（20-8）+（3-0）=15*)簡述隊列和棧的相同點和不同點。棧和隊列都是線性表，都是限制了插入刪除點的線性表（或者說是控制了訪問點的線性表）共同點：都是只能在線性表的端點插入和刪除 不同點棧的插入和刪除都在線性表的同一個端點，該點通稱棧頂，相應(yīng)地，不能插入刪除的另一個端點通稱棧底，其特性是后進先出隊列在線性表的表頭插入，表尾刪除，表頭一般稱隊頭，表尾一般稱隊尾，其特性是先進先出

相同之處：n個（同類）數(shù)據(jù)元素的有限序列稱為線性表。線性表的特點是數(shù)據(jù)元素之間存在“一對一”的關(guān)系，棧和隊列都是操作受限制的線性表，他們和線性表一樣，數(shù)據(jù)元素之間都存在“一對一”的關(guān)系不同之處：棧只允許在一段進行插入或刪除操作的線性表，其最大的特點是“后進后出”；對列是只允許在一端進行插入，另一端進行刪除操作的線性表，其最大的特點是“先進后出”。*)簡述數(shù)據(jù)結(jié)構(gòu)主要研究的對象和研究的問題數(shù)據(jù)的邏輯結(jié)構(gòu)，即數(shù)據(jù)關(guān)系之間的邏輯關(guān)系；數(shù)據(jù)的存儲結(jié)構(gòu)，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示；操作算法，即插入、刪除、修改、查詢、排序等。*)假定有三個元素A、B、C、D依次進棧，進棧過程中允許出棧，試寫出所有元素C先出棧的出棧序列。ABDC，BADC*)簡述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點。頭結(jié)點：是為了方便操作鏈表而附設(shè)的,頭結(jié)點數(shù)據(jù)域通常用來保存跟鏈表有關(guān)的信息,比如鏈表的長度；

首元結(jié)點：就是鏈表里“正式”的第一個結(jié)點,即鏈表的開始結(jié)點。

頭指針：頭指針是指向鏈表的基地址。如果鏈表存在頭結(jié)點則頭指針就是指向頭結(jié)點的地址,反之指向首元結(jié)點的地址。*)順序表與鏈表各自的優(yōu)缺點是什么？順序表存儲：

優(yōu)點：（1）空間利用率高。（局部性原理，連續(xù)存放，命中率高）

（2）存取速度高效，通過下標來直接存儲。缺點：（1）插入和刪除比較慢，比如：插入或者刪除一個元素時，整個表需要遍歷移動元素來重新排一次順序。

（2）不可以增長長度，有空間限制,當需要存取的元素個數(shù)可能多于順序表的元素個數(shù)時,會出現(xiàn)"溢出"問題.當元素個數(shù)遠少于預先分配的空間時,空間浪費巨大。鏈表存儲：優(yōu)點：（1）存取某個元素速度慢。

（2）插入和刪除速度快，保留原有的物理順序，比如：插入或者刪除一個元素時，只需要改變指針指向即可。

（3）沒有空間限制,存儲元素的個數(shù)無上限,基本只與內(nèi)存空間大小有關(guān).

缺點：（1）占用額外的空間以存儲指針(浪費空間，不連續(xù)存放，malloc開辟，空間碎片多)

（2）查找速度慢，因為查找時，需要循環(huán)鏈表訪問，需要從開始節(jié)點一個一個節(jié)點去查找元素訪問。

*)棧、隊列和線性表的區(qū)別是什么？棧和隊列都是線性表，并且都是特殊的線性表：特殊在于限制了插入和刪除點棧是在線性表的某固定一端插入和刪除，因此特性為后進先出隊列是在線性表的一端插入，另外一端刪除，因此特性為先進先出*)請將banana用工具H()—Head()，T()—Tail()從L中取出。其中，L=(apple,(orange,(strawberry,(banana)),peach),pear)。H（H（T（H（T（H（T（L）））））））根據(jù)廣義表的定義來取值程序設(shè)計題主要考鏈表，包括鏈表的查詢，插入，刪除，循環(huán)鏈表的合并#include"stdafx.h"#include<stdio.h>#include<iostream.h>typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;//鏈表的初始化intInitList(LinkList&L){L=newLNode;L->next=NULL;return1;}//創(chuàng)建一個單鏈表voidCreateList_H(LinkList&L,intn){ inti; LinkListp;L=newLNode; L->next=NULL; for(i=0;i<n;i++){ p=newLNode;// scanf("%d",&p->data); cin>>p->data; p->next=L->next; L->next=p; }}//根據(jù)下標查找數(shù)據(jù)intGetElem(LinkList&L,inti,ElemType&e){LinkListp;p=L->next;intj=1;while(p&&j<i){p=p->next;