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

數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)答題1.1簡(jiǎn)述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對(duì)客觀事物的符號(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)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(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ù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。1.7在程序設(shè)計(jì)中，可采用下列三種方法實(shí)現(xiàn)輸出和輸入：通過scanf和printf語句；通過函數(shù)的參數(shù)顯式傳遞；通過全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式控制，較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護(hù)較為困難。2.1描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。2.2填空題。解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。2.3在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。3.2簡(jiǎn)述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3.11簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。隊(duì)列也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。精品word完整版-彳丁業(yè)資料分享4.1解：空格串是指一個(gè)或多個(gè)空格字符(ASCII碼為20H)組成的串，而空串中沒有任何字符。解：串賦值(StrAssign)、串比較(StrCompare)、求串長(StrLength)、串連接(Concat)、求子串(SubString)這五種基本操作構(gòu)成串類型的最小操作子集。一棵度為2的樹與一棵二叉樹有何區(qū)別？解：二叉樹是顆有序樹，但度為2的樹則未必有序。三、簡(jiǎn)答題描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(即表頭結(jié)點(diǎn))的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線性表同時(shí)并存，而且在處理過程中各表的長度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說明理由。應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么？設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(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)。假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。共有14種可能的出棧序列，即為：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量(即存儲(chǔ)的空間大小)為maxnum。當(dāng)有元素要加入隊(duì)列(即入隊(duì))時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。

精品word完整版-彳丁業(yè)資料分享要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(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)先出”的原則。下述算法的功能是什么？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=p-＞next;p-＞next=q;q-＞next=NULL;}return(L);}該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。四、應(yīng)用題＜c，g＞，＜c，(1)(2)(3)(4)(5)(6)(7)(8)(9)1.已知一棵樹邊的集合為{＜1m＞，＜i，n＞，＜e，i＞，＜b，＜c，g＞，＜c，(1)(2)(3)(4)(5)(6)(7)(8)(9)哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪個(gè)是結(jié)點(diǎn)g的雙親？哪些是結(jié)點(diǎn)g的祖先？哪些是結(jié)點(diǎn)g的孩子？哪些是結(jié)點(diǎn)e的孩子？哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？結(jié)點(diǎn)b和n的層次號(hào)分別是什么？樹的深度是多少？以結(jié)點(diǎn)c為根的子樹深度是多少?解答：根據(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的層次號(hào)分別是2和5；樹的深度為5。一棵度為2的樹與一棵二叉樹有何區(qū)別。解答：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹不能交換。試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和二叉樹的所有不同形態(tài)？解答：略已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，回答下列問題：各層的結(jié)點(diǎn)數(shù)目是多少？編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是多少？編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是多少？編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？解答：第i層上的結(jié)點(diǎn)數(shù)目是mi-1。編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是((n-2)/m)+1。編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是(n-1)*m+i+1。編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是(n-1)%mN0。其右兄弟的編號(hào)是n+1。找出所有滿足下列條件的二叉樹：它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；解答：先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。解答：后序序列：ACDBGJKIHFE假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。解答：先序序列：ABCDGEIHFJK給出如圖5-14所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對(duì)應(yīng)的二叉樹。

解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹如圖5-16所示。給定一組權(quán)值(5,9,11,2,7,16),試設(shè)計(jì)相應(yīng)的哈夫曼樹。10.解答：構(gòu)造而成的哈夫曼樹如圖5-17所示。圖5-14圖5-14【例6-5】一個(gè)帶權(quán)無向圖的最小生成樹是否一定唯一？在什么情況下構(gòu)造出的最小生成樹可能不唯一？解:一個(gè)帶權(quán)無向圖的最小生成樹不一定是唯一的。從Kruskal算法構(gòu)造最小生成樹的過程可以看出，當(dāng)從圖中選擇當(dāng)前權(quán)值最小的邊時(shí)，如果存在多條這樣的邊，并且這些邊與已經(jīng)選取的邊構(gòu)成回路，此時(shí)這些邊就不可能同時(shí)出現(xiàn)在一棵最小生成樹中，對(duì)這些邊的不同選擇結(jié)果可能會(huì)產(chǎn)生不同的最小生成樹。三、應(yīng)用題1.已知一個(gè)順序存儲(chǔ)的有序表為(15,26,34,39,45,56,58,63,74,76),試畫出對(duì)應(yīng)的折半查找判定樹，求出其平均查找長度。折半查找判定樹如圖7-3所示，平均查找長度等于29/10。圖7-3中的結(jié)點(diǎn)與有序表中元素的對(duì)應(yīng)關(guān)系如下表所示。12312345678901233455675649568346圖7-32,假定一個(gè)線性表為2,假定一個(gè)線性表為(38,52,25,74,68,16,30,54,90,72),畫出按線性表中元素的次序生成的一棵二叉排序樹，求出其平均查找長度。2.二叉排序樹如圖7-4所示，平均查找長度等于32/10。圖7-4圖7-43.假定一個(gè)待哈希存儲(chǔ)的線性表為(32,75,29,63,48,94,25,46,18,70),哈希地址空間為HT[13],若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測(cè)法處理沖突，試求出每一元素在哈希表中的初始哈希地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。主元素32752963489425461870初始哈希地址最終哈希地址0123456789101112哈希表3.H(K)=K%13平均查找長度為14/10，其余解答如下。主元素32752963489425461870初始哈希地址6103119312755最終哈希地址61031194127580123456789101112哈希表299418324670487563254,假定一個(gè)待哈希存儲(chǔ)的線性表為(32,75,29,63,48,94,25,36,18,70,49,80),哈希地址空間為HT[12],若采用除留余數(shù)法構(gòu)造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長度。4.H(K)=K%11，哈希表如圖7-5所示，平均查找長度17/12。0 12 3 < 6 7S9 10 11圖7-5三、簡(jiǎn)答題【嚴(yán)題集1.2②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。四、簡(jiǎn)答題【嚴(yán)題集2.3②】試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：①順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大(=1?)，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。精品word完整版-彳丁業(yè)資料分享②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小（＜1），存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2.【嚴(yán)題集2.1①】描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素al的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(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è)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。頭結(jié)點(diǎn)headdatalink頭指針 首元結(jié)點(diǎn)簡(jiǎ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)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素al的結(jié)點(diǎn)。四、簡(jiǎn)答題（每小題4分，共20分）【嚴(yán)題集3.2①和3.11①】說明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。【統(tǒng)考書P604-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）%N【全國專升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、簡(jiǎn)答題（每小題4分，共20分）【嚴(yán)題集6.2