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

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

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

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

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

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

7、性表的順序存儲結構可以直接存取數據元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結構中內存采用動態分配，利用率高，但需增設指示結點之間關系的指針域，存取數據元素不如順序存儲方便，但結點的插入、刪除操作較簡單。3. 對于線性表的兩種存儲結構，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態發生變化，線性表的總數也會自動改變，在此情況下，應選用哪一種存儲結構？為什么？3應選用鏈接存儲結構，因為鏈式存儲結構是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續的，也可以是不連續的：這種存儲結構對于元素的刪除或插入運算是不需要移動

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

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

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

11、新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。 第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。 第三種：采用循環隊列方式。將隊頭、隊尾看作是一個首尾相接的循環隊列，即用循環數組實現，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無頭結點的單鏈表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該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。四、應用題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）哪個是根結點？（2）哪些是葉子結點？（3）哪個是結點g的雙親？（4）哪些是結點g的祖先？（5）哪些是結點g的孩子？（6）哪些是結點e的孩子？（7）哪些是結點e的兄弟？哪些是結點f的兄弟？（8）結點b和n的層次號分別是什么？（9）樹的深度是多少？（10）以結點c為根的子樹深度是多少？1. 解答：abcdegfhimnjki圖5-15根據給定的邊確定的樹如圖5-15所示。其中根結點為a；葉子結點有：d、m、n、j、k、f、l；c是結點g的雙親；a、c是結點g的祖先；j、k是結點g的孩子；m、n是結點e的子孫；e是結點d的兄弟；g、h是結點f的兄弟；結點b和n的層次號分別是2和5；樹

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

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

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

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

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

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

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

22、順序存儲時，相鄰數據元素的存放地址也相鄰（邏輯與物理統一）；要求內存中可用存儲單元的地址必須是連續的。優點：存儲密度大（1？），存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小（<1），存儲空間利用率低。順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪除這樣的動態操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2 .【嚴題集2.1】描述以下

23、三個概念的區別：頭指針、頭結點、首元結點（第一個元素結點）。在單鏈表中設置頭結點的作用是什么？答：首元結點是指鏈表中存儲線性表中第一個數據元素a1的結點。為了操作方便，通常在鏈表的首元結點之前附設一個結點，稱為頭結點，該結點的數據域中不存儲線性表的數據元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統一處理。頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。若鏈表中附設頭結點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環鏈表均適用。是否設置頭結點，是不同的存儲結構表示同一邏輯結構的問題。 頭

24、結點headàdatalink 頭指針 首元結點簡而言之，頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針；頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息（內放頭指針？那還得另配一個頭指針！）首元素結點是指鏈表中存儲線性表中第一個數據元素a1的結點。四、簡答題（每小題4分，共20分）1. 【嚴題集3.2和3.11】說明線性表、棧與隊的異同點。劉答：相同點：都是線性結構，都是邏輯結構的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：運算規則不同，線性表為隨機存取，而棧是只允許在

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