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

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

精品word完整版-彳丁業(yè)資料分享要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。下述算法的功能是什么？LinkList*Demo(LinkList*L){//L是無頭結(jié)點的單鏈表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é)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、應(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)哪個是根結(jié)點？哪些是葉子結(jié)點？哪個是結(jié)點g的雙親？哪些是結(jié)點g的祖先？哪些是結(jié)點g的孩子？哪些是結(jié)點e的孩子？哪些是結(jié)點e的兄弟？哪些是結(jié)點f的兄弟？結(jié)點b和n的層次號分別是什么？樹的深度是多少？以結(jié)點c為根的子樹深度是多少?解答：根據(jù)給定的邊確定的樹如圖5-15所示。其中根結(jié)點為a；葉子結(jié)點有：d、m、n、j、k、f、l；c是結(jié)點g的雙親；a、c是結(jié)點g的祖先；j、k是結(jié)點g的孩子；m、 n是結(jié)點e的子孫；e是結(jié)點d的兄弟；g、h是結(jié)點f的兄弟；結(jié)點b和n的層次號分別是2和5；樹的深度為5。一棵度為2的樹與一棵二叉樹有何區(qū)別。解答：度為2的樹有兩個分支，但分支沒有左右之分；一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。試分別畫出具有3個結(jié)點的樹和二叉樹的所有不同形態(tài)？解答：略已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結(jié)點編號，回答下列問題：各層的結(jié)點數(shù)目是多少？編號為n的結(jié)點的父結(jié)點如果存在，編號是多少？編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是多少？編號為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？解答：第i層上的結(jié)點數(shù)目是mi-1。編號為n的結(jié)點的父結(jié)點如果存在，編號是((n-2)/m)+1。編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是(n-1)*m+i+1。編號為n的結(jié)點有右兄弟的條件是(n-1)%mN0。其右兄弟的編號是n+1。找出所有滿足下列條件的二叉樹：它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；解答：先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉樹；中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉樹；先序序列和后序序列相同的二叉樹為：空樹或僅有一個結(jié)點的二叉樹。假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。解答：后序序列：ACDBGJKIHFE假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請寫出該二叉樹的后序遍歷序列。解答：先序序列：ABCDGEIHFJK給出如圖5-14所示的森林的先根、后根遍歷結(jié)點序列，然后畫出該森林對應(yīng)的二叉樹。

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