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

2、性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。作拘絨性嶷的兩種基本的存儲結構；順序裘和錯表。它們在存龍和提作上各賞優缺順序表鏈表1,方法簡單，各種高級直亶中咅E有數組，容易實現V2不用為衰喬結點用的邏輯關系,而噌加額外的存儲開銷，萍儲密度 大了3具有按元素序號陋機誼間的 持點， 査找連彥快.1插入、刪除時，貝裝找 到對應前驅結點修改指 針麗可，無需移2釆用珂態存儲分配，不 會適成內存浪費和淙出缺點.h插入刪除撓作眄需碧移動元翥平 垛移動大釣袁中一半的兀 靶 對兀 薰較多的順序表散率低.Z米用靜態空1可分配，需要預先分 配足夠大的存儲空麻 含造成內 存 胡浪費和隘出.1.在有些唐

3、言中，不支 持指計，不容易實2、需要用額外空閭存 儲建注恚的關系，存儲 密度小沃不能腿機訪 問、查扶時要從頭培針 遍歷.一棵度為 2 2 的有序樹與一棵二叉樹有何區別？答：一棵度為二的有序樹與一棵二叉樹的區別在于：有序樹的結點次序是相對于另一結點而言的，如果有序樹中的子樹只有一個孩子時，這個孩子結點就無須區分其左右次序？而二叉樹無論其孩子數是否為 2 2，均需確定其左右次序，也就是說二叉樹的結點次序不是相對于另一結點而言而是確定的。三. . 算法的度僅與訶題的規模梱關吟？不，事實上，算肚的時間復雜度不僅與問題的熾模相關，還 與輸入丈例中的兀素取值等相關， 但在最 壞的情況匸其時何復雜度就是只與

4、求解問題的規模相關的?況們在討論時間良朵度時，一股就是以 最壞情況下的時何疑雜度為 準的。四、常用的存儲裘爪方袪有唧兒種？常舟的存儲表亦方法有四種：順序存儲方注：它是把遐輯I相嘟的結電存儲在物理位置 相如的存儲單兀里?皓方風的邏再關. .系由存簡甲兀的鄰按天薈來休規口由此得到的存備義不稱為順 房存豬結構?讎接存儲方法它不耍求暹輯上相觀的結點在物理位置上亦相鄭 結辦創的還輯關系懸 由附加的折計宇段表亦的. . 由此得到的存碎表示稱為叢式存蒔結構n累引存箭方也土除鋰丈存曾結點 忙息外. .還建立帽加的當廟表來標識結點加地址?做列存磚方注：就是很據結臨的關鍵字 直接汁第出 該結點的存儲地址 為什么在

5、取循環鏈表屮設置尾指件比設置化摘廿更好？ 答主甩指計是指向経端第點的指針. . 用它廉春審單? ?餚環進表可以便得査找謎表的開怕結慮利塔瑞結點 都很方Wb設一帯頭結貞的單 貓壞鏈表. .具尾猜廿為皿雷. .則卄始第點科纜瑞 結點的位置分別vrear-八ncxfcxi和盹嗽査找時閭都是0（1）.若用頭折針來表莎該謎表，則査找終端結點的時間為0（心?何時選用嗽序表、何時選用能表作為能性表的存福第構為宜答：在丈際戰用中，血很據冥體阿題的要 * *和性JE來選樣顧序我或僅覆作対線性競的存儲垢構，通 常有以卞幾方而的考慮 】基哩間的考慮L出耍求存槪的線性表畏度亜化不大，易F事先確 定其大小時. .為A1

6、存需空聞，立采用 順序義反乙十線性表長度變化大 莽以估計英存踴現模時. . 來用動盡惟表作為存皤結構為好. .2? ?基于時間的考慮? ?若線性表的操杵主婆是進行在找， 很少做捕入利制除操作時，采用咂序 表歎存篠第構為宜；反之，科需耍對紙性蕓竝柑嗾繁地播入咸珮 除等的操作時，宜采用鏈 表做存需箱陶“并且，若漣表的插入利韻除主要 發上在表前首尾兩端，則采 川凰指併表耶的單循外詵表為宜口簡述下列術語：數據，數據元素、數據對象、數據結構、存儲結構、數據類型和抽象數據類型。數據是對客觀事物的符號表示。 在計算機科學中是指所有能輸入到計算機中并被計算機程序 處理的符 號的總稱。數據元素是數據的基本單位，

7、 在計算機程序中通常作為一個整體進行考慮和處理。數據對象是性質相同的數據元素的集合，是數據的一個子集。數據結構是相互之間存在一種或多種特定關系的數據元素的集合。存儲結構是數據結構在計算機中的表示。數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。 抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。是對一般數據類型的擴展。試描述數據結構和抽象數據類型的概念與程序設計語言中數據類型概念的區別。 解：抽象數據類型包含一般數據類型的概念， 但含義比一般數據類型更廣、 更抽象。一般數 據類型 由具體語言系統內部定義， 直接提供給編程者定義用戶數據， 因此稱它們為預定義數 據類型。抽象數據

8、類型通常由編程者定義，包括定義它所使用的數據和在這些數據上所進行的操作。在定義抽象數據類型中的數據部分和操作部分時，要求只定義到數據的邏輯結構和操作說明，不考慮數據的存儲結構和操作的具體實現，這樣抽象層次更高， 更能為其他用戶提供良好的使用接口。描述以下三個概念的區別：頭指針，頭結點，首元結點（第一個元素結點）。頭指針是指向鏈表中第一個結點的指針。首元結點是指鏈表中存儲第一個數據元素的結點頭結點是在首元結點之前附設的一個結點， 其作用主要是為了方便對鏈表的操作。 處理。線性表的兩種存儲結構各有哪些優缺點？ 線性表具有兩種存儲結構即順序存儲結構和鏈接存儲結構。 線性表的順序存儲結構可以直接 存取

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

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

11、可以使得查 找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rearrear，則開始結點和終端結點的位置分別是rear-rear-next-next-nextnext 和 rear,rear,查找時間都是 0 0 (1 1)。若用頭指針來表示該鏈表，則查找終端結點的時間為0 0( n n)。假定有四個元素 A,A, B,B, C,C, D D 依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。共有 1414 種可能的出棧序列，即為：ABCD,ABCD, ABDCABDC ACBD,ACBD, ACDBACDB BACD,BACD, ADCB,ADCB, BADC,

12、BADC, BCAD,BCAD, BCDABCDA BDCA,CBAD,BDCA,CBAD, CBDACDBA,CBDACDBA, DCBADCBA 什么是隊列的上溢現象？ 一般有幾種解決方法，試簡述之。在隊列的順序存儲結構中，設隊頭指針為frontfront，隊尾指針為 rearrear，隊列的容量(即存儲的空間大小)為 maxmax numnum 。當有元素要加入隊列(即入隊)時，若rear=maxrear=max numnum ，則會發生隊 列的上溢現象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結構或操作

13、方式的選擇不當所致，可以用循環隊列解決。該結點不存儲數據元素，其指針域指向首元結點，它可以對空表、非空表以及首元結點的操作進行統一一般地，要解決隊列的上溢現象可有以下幾種方法：(1 1 ) 可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。( 2 2 ) 要避免出現“假溢出”現象可用以下方法解決：第一種：采用移動元素的方法。每當有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當刪去一個隊頭元素，則可依次移動隊列中的元素總是使frontfront 指針指向隊列中的第一個位置。第三種：采用循環隊列方式。將隊頭、隊尾看作是一個首

14、尾相接的循環隊列，即用循環數組實現，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進先出”的原則。如何知道循環隊列是空還是滿？第一，采用計數器來判斷，空時，計數器為0,0,滿時，計數器為 maxsize;maxsize;第二，另設一個布爾變量以匹別隊列的空和滿；第三，少用一個元素的空間，約定入隊前，測試尾指針在循環意義下加 1 1 后是否等于頭指針，若相等則認為隊滿（注意：rearrear 所指的單元始終為空）；1. 數據結構和數搖類空胸個概倉之何有區別嗎？苓：簡單地說，敬據結構定義了一組按某些關系結含在一起的數組元索.數裾類型不僅苣茨了一組帶皓構的數據元素，而且還在算上定義了一組操虹2.

15、 簡述線性給構與非戲性結構的不同點 . .答：線性結構反映結點間的邏輯關系是一對一的，非線性結構反映結點間的邏輯關系是多對多的.說明線性表，棧，隊列的異同點相同點：都是線性結構，都是邏輯結構的概念，都可以用順序存儲或者鏈表存儲？棧和隊列兩種 特殊的線性表，即受限的線性表，只是對插入，刪除運算加以限制. .不同點：1 1 運算規則不同：線性表為隨機存取？棧只允許在一端進行插入？刪除運算？列隊只 允許在一端進行插入，另一端進行刪除運算？當你為解決某一問題而選擇數據結構時，應從哪些方面考慮？通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的 時間又涉及以下三點： （1

16、1）程序運行時所需輸入的數據總量。 （2 2）計算機執行每條指令所需 的時間。（3 3）程序中指令重復執行的次數 簡述邏輯結構與存儲結構的關系答：數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關聯方式或“鄰接關系”），數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。2 2 用途不同，堆棧用于子程序調用和保護現場，隊列用于多道作業處理，指令存儲及其他運算數據運算是數據結構的一個重要方面，試舉例說明兩個數據結構的邏輯結構和存儲方式完全相同，只是對于運算的定義不同，因而兩個結構具有顯著不同的特性，則這兩個數據結構是不同的？答：棧和隊列的邏輯結構相同，其存儲表示

17、也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數據結構。線性表有兩種存儲結構：一是順序表，二是鏈表。試問：（1 1）兩種存儲表示各有哪些主要優缺點？（2 2） 如果有 n n 個 線性表同時并存， 并且在處理過程中各表的長度會動態發生變化， 線性表的 總數也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？（ 3 3） 若線性表的總數基本穩定，且很少進行插入和刪除，但要求以最快的速度存取線性表 中的元素，那么，應采用哪種存儲結構？為什么？解答：（1 1）順序存儲是按索引（隱含的）直接存取數據元素，方便靈活，效率高，但插入、 刪除操作時將引起元素移動，因而降低效率； 鏈接存

18、儲內存采用動態分配，利用率高，但需 增設指示結點之間有序關系的指針域， 存取數據元素不如順序存儲方便， 但結點的插入、刪 除操作 十分簡單。（2 2） 應選用鏈接表存儲結構。其理由是，鏈式存儲結構用一組任意的存儲單元依次存儲線性表里各元素， 這里存儲單元可以是連續的， 也可以是不連續的。 這種存 儲結構，在對元素作插入或刪除運算時， 不需要移動元素，僅修改指針即可。所以很容易實 現表的容量擴充。（ 3 3）應選用順序存儲結構。其理由是，每個數據元素的存儲位置和線性表的起始位置相差 一個和數據元素在線性表中的序號成正比的常數。 由此，只要確定了起始位置，線性表中任 一數據元素都可隨機存取， 所以線性表的順序存儲結構是一種隨機存取的存儲結構。 而鏈表 則是一種順序存取的存儲結構。 2 2、用線性表的順序結構來描述一個城市的設計和規劃合適嗎 ? ?為什么？不合適。因為一個城市的設計和規劃涉及非常多的項目，很復雜，經常需要修改、 擴充和 刪除各種信息，才能適應不斷發展的需要。有鑒于此，順序線性表不能很好適應其需要，故 是不合適的。 3 3、在單鏈表和雙向表中，能否從當前結點出發訪問到任一結點？在單鏈表中只能由當前結點訪問其后