數(shù)據(jù)結(jié)構(gòu)簡答題打印版

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu)簡答題1.1 簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對客觀事物的符號表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。 數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型

2、的擴(kuò)展。1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。1.7 在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：(1) 通過scanf和printf語

3、句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對其進(jìn)行格式控制，較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會引起整個(gè)系統(tǒng)的崩潰。 (2)通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。 (3)通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護(hù)較為困難。2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在

4、首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。2.2 填空題。解：(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。2.3 在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)

5、元素在物理位置上是連續(xù)存儲的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。3.2 簡述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3.11 簡述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。隊(duì)列也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。4.1 解：空格串是指一個(gè)或多個(gè)空格字符(ASCII碼為20H)組成的串，而空串中沒有任何字符。4.2 解：串賦值(StrAssign)、串比較(StrCompare)、求串長(

6、StrLength)、串連接(Concat)、求子串(SubString)這五種基本操作構(gòu)成串類型的最小操作子集。6.2 一棵度為2的樹與一棵二叉樹有何區(qū)別？解：二叉樹是顆有序樹，但度為2的樹則未必有序。三、簡答題 1. 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。1頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？2線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線

7、性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作較簡單。3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個(gè)線性表同時(shí)并存，而且在處理過程中各表的長度會動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？3應(yīng)選用鏈接存儲結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動(dòng)

8、元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。4應(yīng)選用順序存儲結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈

9、表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next 和 rear, 查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6. 假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。6共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7. 什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之

10、。7在隊(duì)列的順序存儲結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費(fèi)存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)

11、新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。 第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無頭結(jié)點(diǎn)的單鏈表LinkList *q,*p;if(L&&L->next) q=L; L=L->next; p=L;while (p->next) p

12、=p->next; p->next=q; q->next=NULL;return (L);8該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。四、應(yīng)用題1. 已知一棵樹邊的集合為<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>，請畫出這棵樹，并回答

13、下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹深度是多少？1. 解答：abcdegfhimnjki圖5-15根據(jù)給定的邊確定的樹如圖5-15所示。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號分別是2和5；樹

14、的深度為5。2. 一棵度為2的樹與一棵二叉樹有何區(qū)別。2. 解答：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹不能交換。3. 試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和二叉樹的所有不同形態(tài)？3. 解答：略4. 已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。4. 解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始

15、對全部結(jié)點(diǎn)編號，回答下列問題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號是多少？（3）編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號是多少？（4）編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號是多少？5. 解答：（1）第i層上的結(jié)點(diǎn)數(shù)目是mi-1。（2）編號為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號是(n-2)/m)+1。（3）編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號是(n-1)*m+i+1。（4）編號為n的結(jié)點(diǎn)有右兄弟的條件是(n-1)%m0。其右兄弟的編號是n+1。6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們在

16、后序遍歷和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時(shí)，得到的遍歷序列相同；6. 解答：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。7. 假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。7. 解答：后序序列：ACDBGJKIHFE8. 假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二

17、叉樹的后序遍歷序列。8. 解答：先序序列：ABCDGEIHFJK9. 給出如圖5-14所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對應(yīng)的二叉樹。9. 解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹如圖5-16所示。10給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)相應(yīng)的哈夫曼樹。10. 解答：構(gòu)造而成的哈夫曼樹如圖5-17所示。ABDEFCGHJIKNOML圖5-14【例6-5】 一個(gè)帶權(quán)無向圖的最小生成樹是否一定唯一？在什么情況下構(gòu)造出的最小生成樹可能不唯一？解：一個(gè)帶權(quán)無向圖的最小生成樹不一定是唯一的。從Kruskal算法構(gòu)

18、造最小生成樹的過程可以看出，當(dāng)從圖中選擇當(dāng)前權(quán)值最小的邊時(shí)，如果存在多條這樣的邊，并且這些邊與已經(jīng)選取的邊構(gòu)成回路，此時(shí)這些邊就不可能同時(shí)出現(xiàn)在一棵最小生成樹中，對這些邊的不同選擇結(jié)果可能會產(chǎn)生不同的最小生成樹。三、應(yīng)用題 1. 已知一個(gè)順序存儲的有序表為(15,26,34,39,45,56,58,63,74,76)，試畫出對應(yīng)的折半查找判定樹，求出其平均查找長度。 1. 折半查找判定樹如圖7-3所示，平均查找長度等于29/10。圖7-3中的結(jié)點(diǎn)與有序表中元素的對應(yīng)關(guān)系如下表所示。圖7-31094567812312345678910152634394556586374762. 假定一個(gè)線性表為

19、(38,52,25,74,68,16,30,54,90,72)，畫出按線性表中元素的次序生成的一棵二叉排序樹，求出其平均查找長度。圖7-4385225167430689054722. 二叉排序樹如圖7-4所示，平均查找長度等于32/10。 3. 假定一個(gè)待哈希存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，哈希地址空間為HT13，若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測法處理沖突，試求出每一元素在哈希表中的初始哈希地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最終哈希地址

20、 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 3. H(K)=K % 13平均查找長度為14/10，其余解答如下。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最終哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 254. 假定一個(gè)待哈希存儲的線性表為(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空間為HT12，若采用除留余數(shù)法構(gòu)

21、造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長度。4. H(K)=K % 11，哈希表如圖7-5所示，平均查找長度17/12。圖7-50 三、簡答題2.【嚴(yán)題集1.2】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。3. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的。四、簡答題1. 【嚴(yán)題集2.3】試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：

22、順序存儲時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（1？），存儲空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲密度?。?lt;1），存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2 .【嚴(yán)題集2.1】描述以下

23、三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進(jìn)行操作時(shí)，可以對空表、非空表的情況以及對首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭

24、結(jié)點(diǎn)headàdatalink 頭指針 首元結(jié)點(diǎn)簡而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。┦自亟Y(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。四、簡答題（每小題4分，共20分）1. 【嚴(yán)題集3.2和3.11】說明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在

25、一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。4. 【統(tǒng)考書P60 4-13】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長度）。我們常采用法，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是： f=rear 隊(duì)滿標(biāo)志是：f=(r+1)%N2.【全國專升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最