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

試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答：順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大（1），存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。╪ext-next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front，隊尾指針為rear，隊列的容量（即存儲的空間大?。閙axnum。當有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當所致，可以用循環(huán)隊列解決。一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。如何知道循環(huán)隊列是空還是滿?第一，采用計數(shù)器來判斷，空時，計數(shù)器為0，滿時，計數(shù)器為maxsize；第二，另設(shè)一個布爾變量以匹別隊列的空和滿；第三，少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空）；說明線性表,棧,隊列的異同點相同點:都是線性結(jié)構(gòu),都是邏輯結(jié)構(gòu)的概念,都可以用順序存儲或者鏈表存儲. 棧和隊列兩種特殊的線性表,即受限的線性表,只是對插入, 刪除運算加以限制.不同點:1 運算規(guī)則不同: 線性表為隨機存取. 棧只允許在一端進行插入.刪除運算. 列隊只允許在一端進行插入,另一端進行刪除運算.2 用途不同,堆棧用于子程序調(diào)用和保護現(xiàn)場,隊列用于多道作業(yè)處理,指令存儲及其他運算等等.當你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時,應從哪些方面考慮?通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的時間又涉及以下三點：（1）程序運行時所需輸入的數(shù)據(jù)總量。（2）計算機執(zhí)行每條指令所需的時間。（3）程序中指令重復執(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)在計算機中的表示，包括數(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)相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：(1)兩種存儲表示各有哪些主要優(yōu)缺點?(2)如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結(jié)構(gòu)?為什么?(3)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應采用哪種存儲結(jié)構(gòu)?為什么?解答：(1)順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起元素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作十分簡單。(2)應選用鏈接表存儲結(jié)構(gòu)。其理由是，鏈式存儲結(jié)構(gòu)用一組任意的存儲單元依次存儲線性表里各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結(jié)構(gòu)，在對元素作插入或刪除運算時，不需要移動元素，僅修改指針即可。所以很容易實現(xiàn)表的容量擴充。(3)應選用順序存儲結(jié)構(gòu)。其理由是，每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機存取，所以線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。而鏈表則是一種順序存取的存儲結(jié)構(gòu)。2、用線性表的順序結(jié)構(gòu)來描述一個城市的設(shè)計和規(guī)劃合適嗎?為什么?不合適。因為一個城市的設(shè)計和規(guī)劃涉及非常多的項目，很復雜，經(jīng)常需要修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應其需要，故是不合適的。3、在單鏈表和雙向表中，能否從當前結(jié)點出發(fā)訪問到任一結(jié)點?在單鏈表中只能由當前結(jié)點訪問其后的任一結(jié)點，因為沒有指向其前驅(qū)結(jié)點的指針。而在雙向鏈表中，既有指向后繼結(jié)點的指針又有指向前驅(qū)結(jié)點的指針，故可由當前結(jié)點出發(fā)訪問鏈表中任一結(jié)點。對鏈表設(shè)置頭結(jié)點的作用是什么?(至少說出兩條好處)(1)對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一結(jié)點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點。若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點或刪除該結(jié)點時操作會復雜些。(2)對帶頭結(jié)點的鏈表，表頭指針是指向頭結(jié)點的非空指針，因此空表與非空表的處理是一樣的。在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應的鏈表中刪去？若可以，其時間復雜度各為多少？1.單鏈表。當我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。2.雙鏈表。由于這樣的鏈表提供雙向鏈接，