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

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ù)是對客觀事物的符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(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ù)學模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴展。1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)

2、據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A定義數(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)輸出和輸入：(1)通過scanf和printf語句；(2)通過函數(shù)的參數(shù)顯式傳遞；(3)

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

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

5、 其特點是可以進行隨機存取。3.2 簡述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。棧是限定僅在表尾進行插入或刪除操作的線性表。3.11 簡述隊列和堆棧這兩種數(shù)據(jù)類型的相同點和差異處。解：棧是一種運算受限的線性表，其限制是僅允許在表的一端進行插入和刪除運算。隊列也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。4.1 解：空格串是指一個或多個空格字符(ascii碼為20h)組成的串，而空串中沒有任何字符。4.2 解：串賦值(strassign)、串比較(strcompare)、求串長(strlength)、串連接(concat)、 求子

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

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

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

9、使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear-next-next和rear,查找時間都是 0(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為0(n)。10 假定有四個元素 a, b, c, d依次進棧，進棧過程中允許出棧， 試寫出所有可能的出棧 序列。11 共有14種可能的出棧序列，即為：abcd, abdc , acbd, acdb , bacd , adcb , badc , bcad, bcda , bdca,cbad, cbda , cdba, dcba12 什么是隊列的上溢現(xiàn)象？ 一般有幾種解決

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

11、移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向 隊頭移動一個位置，假定空余空間足夠。第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。 將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用 循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。8.下述算法的功能是什么 ？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;

12、p-next=q; q-next=null;return (l);8.該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來 的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、應(yīng)用題1.已知一棵樹邊的集合為, , , , , , , , , , , , ,請畫出這棵樹，并回答下列問題:(1)哪個是根結(jié)點？(2)哪些是葉子結(jié)點?(3)哪個是結(jié)點g的雙親?(4)哪些是結(jié)點g的祖先?(5)哪些是結(jié)點g的孩子?(6)哪些是結(jié)點哪些是結(jié)點e的孩子？e的兄弟？哪些是結(jié)點f的兄弟?(8)結(jié)點b和n的層次號分別是什么?(9)樹的深度是多少？(10)以結(jié)點c為根的子樹深度是多少?1 .解答

13、：圖 5-15根據(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 . 一棵度為2的樹與一棵二叉樹有何區(qū)別。3 .解答：度為2的樹有兩個分支，但分支沒有左右之分； 一棵二叉樹也有兩個分支，但有左右之分，左右子樹不能交換。4 .試分別畫出具有3個結(jié)點的樹和二叉樹的所有不同形態(tài)？5 .解答： 略6 .已知用一維數(shù)組存放的一棵完全二叉樹：abcdefghijkl ,寫出該二叉樹的先序、

14、中序和后序遍歷序列。7 .解答：先序序列:abdhiejkcflg中序序列：hdibjekalfcg后序序列：hidjkeblfgca8 . 一棵深度為h的滿k叉樹有如下性質(zhì)：第 h層上的結(jié)點都是葉子結(jié)點，其余各層上 每個結(jié)點都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結(jié)點編號, 回答下列問題：(1)各層的結(jié)點數(shù)目是多少？(2)編號為n的結(jié)點的父結(jié)點如果存在，編號是多少？(3)編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是多少？(4)編號為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？5.解答：(1)第i層上的結(jié)點數(shù)目是 mi-1。(2)編號為n的結(jié)點的父結(jié)點如果存在

15、，編號是 (n-2)/m)+1 。(3)編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是 (n-1)*m+i+1。(4)編號為n的結(jié)點有右兄弟的條件是 (n-1)%m w0。其右兄弟的編號是 n+1。6.找出所有滿足下列條件的二叉樹：(1)它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；(2)它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；(3)它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；6 .解答：(1)先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點均無左孩子的非空二叉(2)中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點均無右孩子的非空二叉(3)先序序列和后序序列相同的二叉樹為：空

16、樹或僅有一個結(jié)點的二叉樹。7 .假設(shè)一棵二叉樹白先序序列為ebadcfhgikj ,中序序列為 abcdefghijk ,請寫出該二叉樹的后序遍歷序列。8 .解答：后序序列： acdbgjkihfe9 .假設(shè)一棵二叉樹白后序序列為dcegbfhkjia ,中序序列為 dcbgeahfijk ,請寫出該二叉樹的后序遍歷序列。10 解答：先序序列： abcdgeihfjk11 給出如圖5-14所示的森林的先根、后根遍歷結(jié)點序列，然后畫出該森林對應(yīng)的二叉12 解答：先根遍歷:abcdefghijklmno后根遍歷：bdefcahjigknoml森林轉(zhuǎn)換成二叉樹如圖 5-16所示。13 .給定一組權(quán)值

17、(5, 9, 11, 2, 7, 16),試設(shè)計相應(yīng)的哈夫曼樹。14 .解答：構(gòu)造而成的哈夫曼樹如圖5-17所示?！纠?-5】一個帶權(quán)無向圖的最小生成樹是否一定唯一？在什么情況下構(gòu)造出的最小 生成樹可能不唯一？解：一個帶權(quán)無向圖的最小生成樹不一定是唯一的。從 kruskal算法構(gòu)造最小生成樹的 過程可以看出，當從圖中選擇當前權(quán)值最小的邊時，如果存在多條這樣的邊，并且這些邊與已經(jīng)選取的邊構(gòu)成回路，此時這些邊就不可能同時出現(xiàn)在一棵最小生成樹中，對這些邊的不同選擇結(jié)果可能會產(chǎn)生不同的最小生成樹。三、應(yīng)用題1.已知一個順序存儲的有序表為(15,26,34,39,45,56,58,63,74,76),試

18、畫出對應(yīng)的折半查找判定樹，求出其平均查找長度。1.折半查找判定樹如圖 7-3所示，平均查找長度等于29/10。圖7-3中的結(jié)點與有序表中元素的對應(yīng)關(guān)系如下表所示。123456789012334556756495683462.假定一個線性表為(38,52,25,74,68,16,30,54,90,72),畫出按線性表中元素的次序生成 的一棵二叉排序樹，求出其平均查找長度。2.二叉排序樹如圖3.假定一個待哈希存儲的線性表為(32,75,29,63,48,94,25,46,18,70),哈希地址空間12為ht13,若采用除留余數(shù)法構(gòu)造哈希函數(shù)和線性探測法處理沖突，試求出每一元素在哈 希表中的初始哈希

19、地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。32752963489425 ,4618兀索 初始哈希地址 最終哈希地址0123456789 10 11j表3 . h(k)=k % 13平均查找長度為14/10,其余解答如下。兒系32752963489425461870初始哈希地劃6103119312755最終哈希地劃6103119412758012345678910 11 12音表2994183246704875634.假定一個待哈希存儲的線性表為（32,75,29,63,48,94,25,36,18,70,49,80）,哈希地址空間為ht12,若采用除留余數(shù)法構(gòu)造哈希函數(shù)和拉鏈

20、法處理沖突，試畫出最后得到的哈希表， 并求出平均查找長度。4 . h（k）=k % 11 ,哈希表如圖7-5所示，平均查找長度17/12。0三、簡答題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ù)元素，而且還在其上定義了一組操作。6 .簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。四、簡答題1 .【嚴題集2.3試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順 序表比鏈表好？答：順序存儲時，相鄰數(shù)據(jù)元

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

22、結(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é)點headdatal

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

24、后進先出表 lifo ;隊列是只允許在一端進行插入、另一端進行刪除運算，因而 是先進先出表fifo。用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其 他運算等等。4.【統(tǒng)考書p60 4-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）%n2 .【全國專升本資格考試】遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么？答：不一定。時間復雜度與樣本個數(shù) n有關(guān)，是指最深層的執(zhí)行語句耗費時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、簡答題（每小題 4分，共20分）【