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

1、試比較順序存儲(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í)不方便。 鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?lt;1），存儲(chǔ)空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。

2、0;若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。 一棵度為2的有序樹與一棵二叉樹有何區(qū)別?答：一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結(jié)點(diǎn)次序是相對(duì)于另一結(jié)點(diǎn)而言的，如果有序樹中的子樹只有一個(gè)孩子時(shí)，這個(gè)孩子結(jié)點(diǎn)就無(wú)須區(qū)分其左右次序.而二叉樹無(wú)論其孩子數(shù)是否為2，均需確定其左右次序，也就是說(shuō)二叉樹的結(jié)點(diǎn)次序不是相對(duì)于另一結(jié)點(diǎn)而言而是確定的。簡(jiǎn)述下列術(shù)語(yǔ)：數(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ì)算

3、機(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ò)展。試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語(yǔ)言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶

4、數(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)和操作說(shuō)明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。描述以下三個(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)一處理

5、。線性表的兩種存儲(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í)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(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ǔ)

6、單元可以是連續(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)？試說(shuō)明理由。應(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è)置頭指針好嗎？為什么?

7、設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(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)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫出所有可能的出棧序列。共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DC

8、BA什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(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)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下

9、方法解決：第一種：采用移動(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)先出”的原則。如何知道循環(huán)隊(duì)列是空還是滿?第一，采用計(jì)數(shù)器來(lái)判斷，空時(shí)，計(jì)數(shù)器為0，滿時(shí)，計(jì)數(shù)器為maxsize；第二，另設(shè)一個(gè)布爾變量以匹別隊(duì)列的空和滿；第三，少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則

10、認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空）；說(shuō)明線性表,棧,隊(duì)列的異同點(diǎn)相同點(diǎn):都是線性結(jié)構(gòu),都是邏輯結(jié)構(gòu)的概念,都可以用順序存儲(chǔ)或者鏈表存儲(chǔ). 棧和隊(duì)列兩種特殊的線性表,即受限的線性表,只是對(duì)插入, 刪除運(yùn)算加以限制.不同點(diǎn):1 運(yùn)算規(guī)則不同: 線性表為隨機(jī)存取. 棧只允許在一端進(jìn)行插入.刪除運(yùn)算. 列隊(duì)只允許在一端進(jìn)行插入,另一端進(jìn)行刪除運(yùn)算.2 用途不同,堆棧用于子程序調(diào)用和保護(hù)現(xiàn)場(chǎng),隊(duì)列用于多道作業(yè)處理,指令存儲(chǔ)及其他運(yùn)算等等.當(dāng)你為解決某一問(wèn)題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí),應(yīng)從哪些方面考慮?通常從兩方面考慮：第一是算法所需的存儲(chǔ)空間量；第二是算法所需的時(shí)間。對(duì)算法所需的時(shí)間又涉及以下三點(diǎn)：（1

11、）程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量。（2）計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間。（3）程序中指令重復(fù)執(zhí)行的次數(shù)簡(jiǎn)述邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系答：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面,試舉例說(shuō)明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式完全相同,只是對(duì)于運(yùn)算的定義不同,因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性,則這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是不同的.答：棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲(chǔ)表示也可相同（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)），但由于其運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序

12、表，二是鏈表。試問(wèn)：      (1)兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?    (2)如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)?為什么?     (3)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么? 解答：(1)順序存儲(chǔ)是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪

13、除操作時(shí)將引起元素移動(dòng)，因而降低效率；鏈接存儲(chǔ)內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作十分簡(jiǎn)單。      (2)應(yīng)選用鏈接表存儲(chǔ)結(jié)構(gòu)。其理由是，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表里各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲(chǔ)結(jié)構(gòu)，在對(duì)元素作插入或刪除運(yùn)算時(shí)，不需要移動(dòng)元素，僅修改指針即可。所以很容易實(shí)現(xiàn)表的容量擴(kuò)充。      (3)應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。其理由是，每個(gè)數(shù)

14、據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。 2、用線性表的順序結(jié)構(gòu)來(lái)描述一個(gè)城市的設(shè)計(jì)和規(guī)劃合適嗎?為什么? 不合適。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及非常多的項(xiàng)目，很復(fù)雜，經(jīng)常需要修改、 擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應(yīng)其需要，故是不合適的。 3、在單鏈表和雙向表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任一結(jié)點(diǎn)? 在單鏈表中只能由當(dāng)前結(jié)

15、點(diǎn)訪問(wèn)其后的任一結(jié)點(diǎn)，因?yàn)闆](méi)有指向其前驅(qū)結(jié)點(diǎn)的指針。而在雙向鏈表中，既有指向后繼結(jié)點(diǎn)的指針又有指向前驅(qū)結(jié)點(diǎn)的指針，故可由當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)鏈表中任一結(jié)點(diǎn)。對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么?(至少說(shuō)出兩條好處) (1) 對(duì)帶頭結(jié)點(diǎn)的鏈表，在表的任何結(jié)點(diǎn)之前插入結(jié)點(diǎn)或刪除表中任何結(jié)點(diǎn)，所要做的都是修改前一結(jié)點(diǎn)的指針域，因?yàn)槿魏卧亟Y(jié)點(diǎn)都有前驅(qū)結(jié)點(diǎn)。若鏈表沒(méi)有頭結(jié)點(diǎn)，則首元素結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，在其前插入結(jié)點(diǎn)或刪除該結(jié)點(diǎn)時(shí)操作會(huì)復(fù)雜些。  (2) 對(duì)帶頭結(jié)點(diǎn)的鏈表，表頭指針是指向頭結(jié)點(diǎn)的非空指針，因此空表與非空表的處理是一樣的。 在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少？ 1. 單鏈表。當(dāng)我們知道指針p指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到