數(shù)據(jù)結(jié)構(gòu)簡答題_第1頁
數(shù)據(jù)結(jié)構(gòu)簡答題_第2頁
數(shù)據(jù)結(jié)構(gòu)簡答題_第3頁
數(shù)據(jù)結(jié)構(gòu)簡答題_第4頁
數(shù)據(jù)結(jié)構(gòu)簡答題_第5頁
已閱讀5頁,還剩1頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、精選優(yōu)質(zhì)文檔-傾情為你奉上試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好? 答: 順序存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一);要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。 優(yōu)點:存儲密度大(1),存儲空間利用率高。缺點:插入或刪除元素時不方便。 鏈?zhǔn)酱鎯r,相鄰數(shù)據(jù)元素可隨意存放,但所占存儲空間分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針 優(yōu)點:插入或刪除元素時很方便,使用靈活。缺點:存儲密度?。?lt;1),存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作;鏈表宜于做插入、刪

2、除這樣的動態(tài)操作。 若線性表的長度變化不大,且其主要操作是查找,則采用順序表; 若線性表的長度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。 一棵度為2的有序樹與一棵二叉樹有何區(qū)別?答:一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結(jié)點次序是相對于另一結(jié)點而言的,如果有序樹中的子樹只有一個孩子時,這個孩子結(jié)點就無須區(qū)分其左右次序.而二叉樹無論其孩子數(shù)是否為2,均需確定其左右次序,也就是說二叉樹的結(jié)點次序不是相對于另一結(jié)點而言而是確定的。簡述下列術(shù)語:數(shù)據(jù),數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。數(shù)據(jù)是對客觀事物的符號表示。在計算機(jī)

3、科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位,在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示。數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴(kuò)展。試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。解:抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念,但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(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ù)據(jù)的邏輯結(jié)構(gòu)和操作說明,不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實現(xiàn),這樣抽象層次更高,更能為其他用戶提供良好的使用接口。描述以下三個概念的區(qū)別:頭指針,頭結(jié)點,首元結(jié)點(第一個元素結(jié)點)。頭指針是指向鏈表中第一個結(jié)點的指針。首元結(jié)點是指鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點。頭結(jié)點是在首元結(jié)點之前附設(shè)的一個結(jié)點,該結(jié)點不存儲數(shù)據(jù)元素,其指針域指向首元結(jié)點,其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及

5、首元結(jié)點的操作進(jìn)行統(tǒng)一處理。線性表的兩種存儲結(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),因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲

6、線性表中的各元素,這里存儲單元可以是連續(xù)的,也可以是不連續(xù)的:這種存儲結(jié)構(gòu)對于元素的刪除或插入運算是不需要移動元素的,只需修改指針即可,所以很容易實現(xiàn)表的容量的擴(kuò)充。對于線性表的兩種存儲結(jié)構(gòu),若線性表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除操作,但要求以最快的速度存取線性表中的元素,應(yīng)選用何種存儲結(jié)構(gòu)?試說明理由。應(yīng)選用順序存儲結(jié)構(gòu),因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此,只要確定了其起始位置,線性表中的任一個數(shù)據(jù)元素都可隨機(jī)存取,因此,線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu),而鏈表則是一種順序存取的存儲結(jié)構(gòu)。在單循環(huán)鏈表中設(shè)置尾指針

7、比設(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依次進(jìn)棧,進(jìn)棧過程中允許出棧,試寫出所有可能的出棧序列。共有14種可能的出棧序列,即為:ABCD, ABDC,ACBD, ACDB,BACD,ADCB,BADC,BCAD, BCDA,BDCA,CBAD,

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

9、出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決:第一種:采用移動元素的方法。每當(dāng)有一個新元素入隊,就將隊列中已有的元素向隊頭移動一個位置,假定空余空間足夠。第二種:每當(dāng)刪去一個隊頭元素,則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種:采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列,即用循環(huán)數(shù)組實現(xiàn),此時隊首仍在隊尾之前,作插入和刪除運算時仍遵循“先進(jìn)先出”的原則。如何知道循環(huán)隊列是空還是滿?第一,采用計數(shù)器來判斷,空時,計數(shù)器為0,滿時,計數(shù)器為maxsize;第二,另設(shè)一個布爾變量以匹別隊列的空和滿;第三,少用一個元素的空間,約定入隊前,測試尾指針在循環(huán)意義下加1

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論