1、精選優質文檔-傾情為你奉上試比較順序存儲結構和鏈式存儲結構的優缺點。在什么情況下用順序表比鏈表好？ 答： 順序存儲時，相鄰數據元素的存放地址也相鄰（邏輯與物理統一）；要求內存中可用存儲單元的地址必須是連續的。 優點：存儲密度大（1），存儲空間利用率高。缺點：插入或刪除元素時不方便。 鏈式存儲時，相鄰數據元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 優點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小（<1），存儲空間利用率低。 順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪

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

3、科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數據元素是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數據對象是性質相同的數據元素的集合，是數據的一個子集。數據結構是相互之間存在一種或多種特定關系的數據元素的集合。存儲結構是數據結構在計算機中的表示。數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。是對一般數據類型的擴展。試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。解：抽象數據類型包含一般數據類型的概念，但含義比一般數據類型更廣、更抽象。一般數據類型由具體語言系統內部定義

4、，直接提供給編程者定義用戶數據，因此稱它們為預定義數據類型。抽象數據類型通常由編程者定義，包括定義它所使用的數據和在這些數據上所進行的操作。在定義抽象數據類型中的數據部分和操作部分時，要求只定義到數據的邏輯結構和操作說明，不考慮數據的存儲結構和操作的具體實現，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。描述以下三個概念的區別：頭指針，頭結點，首元結點（第一個元素結點）。頭指針是指向鏈表中第一個結點的指針。首元結點是指鏈表中存儲第一個數據元素的結點。頭結點是在首元結點之前附設的一個結點，該結點不存儲數據元素，其指針域指向首元結點，其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及

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

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

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

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

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

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

11、的時間又涉及以下三點：（1）程序運行時所需輸入的數據總量。（2）計算機執行每條指令所需的時間。（3）程序中指令重復執行的次數簡述邏輯結構與存儲結構的關系答：數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關聯方式或“鄰接關系”），數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。數據運算是數據結構的一個重要方面,試舉例說明兩個數據結構的邏輯結構和存儲方式完全相同,只是對于運算的定義不同,因而兩個結構具有顯著不同的特性,則這兩個數據結構是不同的.答：棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數據結構。線性

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

13、便靈活，效率高，但插入、刪除操作時將引起元素移動，因而降低效率；鏈接存儲內存采用動態分配，利用率高，但需增設指示結點之間有序關系的指針域，存取數據元素不如順序存儲方便，但結點的插入、刪除操作十分簡單。      (2)應選用鏈接表存儲結構。其理由是，鏈式存儲結構用一組任意的存儲單元依次存儲線性表里各元素，這里存儲單元可以是連續的，也可以是不連續的。這種存儲結構，在對元素作插入或刪除運算時，不需要移動元素，僅修改指針即可。所以很容易實現表的容量擴充。      (3)應選用順序

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

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