數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)資料

1、izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！計算機(jī)科學(xué)與技術(shù)專升本數(shù)據(jù)結(jié)構(gòu)期htkvvivCMtnrmHEvmhwerihamvBszuA數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料iz

2、TTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！考試時間：12月27日周一下午14:00-15:30考試地點：創(chuàng)新樓110復(fù)習(xí)范圍：算法與數(shù)據(jù)結(jié)構(gòu)第一至第八章考試題型：選擇題

3、（每小題分，共分）判斷題（每小題分，共分）填空題（每空2分，共20分）應(yīng)用題（每小題，分，共20分）設(shè)計題（每小題，分，共10分）知識概要：第1章算法與程序1概念和術(shù)語數(shù)據(jù)：是能輸入到計算機(jī)中并能被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，它在計算機(jī)處理和程序設(shè)計中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。數(shù)據(jù)對象：是具有相同特征的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)：是數(shù)據(jù)元素的組織形式，或數(shù)據(jù)元素相互之間存在一種或多種特定關(guān)系的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)：是指數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)：是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)內(nèi)存中的存儲方式，又稱

4、物理結(jié)構(gòu)。數(shù)據(jù)類型：是一組具有相同性質(zhì)的操作對象以及該組操作對象上的運算方法的集合。抽象數(shù)據(jù)類型：是指一個數(shù)學(xué)模型以及在該模型上定義的一套運算規(guī)則的集合。算法：建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的，為解決問題而采取的步驟和方法。2邏輯結(jié)構(gòu)的四種基本形態(tài)根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列四類基本結(jié)構(gòu)：（1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素間除了“同屬于一個集合”的關(guān)系外，別無其它關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的關(guān)系。（3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系。（4）圖型結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個對多個的關(guān)系。3數(shù)據(jù)存儲結(jié)構(gòu)的基本組織方式數(shù)據(jù)存儲結(jié)構(gòu)有順序

5、和鏈?zhǔn)絻煞N方式。（1）順序存儲結(jié)構(gòu)的特點：要借助數(shù)據(jù)元素在存儲器中的相應(yīng)位置來體現(xiàn)數(shù)據(jù)元素相互間的邏輯關(guān)系，常用高級編程語言中的“一維數(shù)組”來描述或?qū)崿F(xiàn)。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點：通過表示數(shù)據(jù)元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常用鏈表來實現(xiàn)。在順序存儲結(jié)構(gòu)的基礎(chǔ)上，又可延伸變化出另外兩種存儲結(jié)構(gòu)，即索引存儲和散列存儲。（1）索引存儲就是在數(shù)據(jù)文件的基礎(chǔ)上增加了一個索引表文件。通過索引表建立索引，可以把一個順序表分成幾個順序子表，其目的是在查詢時提高查找效率，避免盲目查找。（2）散列存儲就是通過數(shù)據(jù)元素與存儲地址之間建立起某種映射關(guān)系，使每個數(shù)據(jù)元素與每一個存儲地址之間盡量達(dá)到一

6、一對應(yīng)的目的。這樣，查找時同樣可大大提高效率。4數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的核心研究內(nèi)容包括三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及相應(yīng)的基本操作運算的定義和實現(xiàn)。5算法的五個重要特征（1）有窮性：一個算法必須保證在執(zhí)行有限步驟之后結(jié)束，而不是無限的。（2）確定性：算法中每一條指令必須有明確的含義，而不能是模棱兩可的。（3）可行性：每一個操作步驟都必須在有限的時間內(nèi)完成。（4）輸入：一個算法可以有一個或多個輸入，也可以沒有輸入。（5）輸出：一個算法可以有一個或多個輸出。沒有輸出的算法是沒有實際意義的。6算法的評價標(biāo)準(zhǔn)（1）正確性。（2）易讀性。（3）高效性。（4）可維護(hù)性。7算法分析的目的算法分

7、析主要是指分析算法的效率。算法效率的度量主要從兩個方面：算法的運行時間和算法所需的存儲空間。分析的目的是通過考察算法的時間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。一般情況下，鑒于運算空間（內(nèi)存）較為充足，所以把算法的時間復(fù)雜度分析作為重點。8算法的時間復(fù)雜度分析（1）算法運算時間的度量的兩種方法：事后統(tǒng)計的方法和事前分析估算的方法。（2）算法運行時間的分析規(guī)則通常把一個程序的運行時間定義為一個（），其中是該程序輸入數(shù)據(jù)的規(guī)模，而不是某一個具體的輸入。的單位是不確定的，一般把它看成在一個特定計算機(jī)上執(zhí)行的指令條數(shù)。通常記作：，其中表示數(shù)據(jù)輸入規(guī)模。常見的算法時間復(fù)雜度的形式按性能降序的排

8、列如下：9算法空間復(fù)雜度的含義空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。算法在計算機(jī)存儲器內(nèi)占用的存儲空間主要分為三部分：算法源代碼本身占用的存儲空間；算法輸入輸出數(shù)據(jù)所占用的存儲空間；算法運行過程中臨時占用的存儲空間。考慮一個算法的空間復(fù)雜度時，要綜合分析這三個方面的因素。通常記作,其中為問題的規(guī)模（或大?。５?、3章線性表、棧、隊列1線性表的定義線性表是個數(shù)據(jù)元素的有限序列，其中（）為線性表的長度。izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自

9、己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！線性表中各個元素的類型相同。對于線性表（，,，）而言，數(shù)據(jù)元素沒有直接前趨,沒有直接后繼，表中的其它元素（順序表沒有直接后繼，表中的其它元素（順序表）有且僅一個直接前趨和直接后繼izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesi

10、ha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！順序表是指線性表的順序存儲結(jié)構(gòu)，即用一組連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素。在語言中可用一維數(shù)組來表示。在順序表中，以數(shù)據(jù)元素在計算機(jī)內(nèi)“物理位置相鄰”來表示表中數(shù)據(jù)元素間的邏輯關(guān)系。順序表是一種隨機(jī)存儲結(jié)構(gòu)，只要確定了存儲順序表的起

11、始位置，則表中任一元素都可以隨機(jī)存取。所以在順序表中可以方便的進(jìn)行數(shù)據(jù)元素的查找及存取。但是在進(jìn)行插入和刪除操作時，將會引起元素的大量移動，因而效率比較低，并且易產(chǎn)生空間浪費或“上溢”現(xiàn)象。順序表的操作還應(yīng)注意元素的存儲位置，即數(shù)組下標(biāo)（語言中下標(biāo)從開始）。3鏈表鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈表是用一組任意的存儲單元（可以是連續(xù)的，也可以是不連續(xù)的）存放線性表的數(shù)據(jù)元素。在鏈表中，通過指針來表示元素之間的邏輯關(guān)系的，不再有邏輯順序與物理存儲順序一致的特點，是非順序存儲結(jié)構(gòu)。在單鏈表中，每個結(jié)點由數(shù)據(jù)域和指針域組成。數(shù)據(jù)域保存數(shù)據(jù)元素的信息，指針域存放其直接后繼的存儲位置。其類型可描述為：單鏈表

12、由頭指針唯一確定。為了便于操作，可在鏈表的第一個結(jié)點之前添加一個表頭結(jié)點。在鏈表中進(jìn)行插入和刪除操作只需要修改有關(guān)的指針內(nèi)容，不需要移動元素。因此，鏈表較順序表的插入和刪除操作更加方便、高效。為了便于實現(xiàn)各種運算，若無特殊說明，均采用帶頭結(jié)點的鏈表。4棧棧（）是限定僅在表的一端進(jìn)行插入或刪除操作的線性表。通常把允許插入和刪除操作的一端稱為棧頂（），而另一端稱為棧底（t表為空時稱為空棧。在棧上的主要運算是入棧和出棧。棧中元素如果按，的順序進(jìn)棧，則出棧順序為，。因此，棧又稱為“后進(jìn)先出”（）的線性表，簡稱表。同線性表相似，棧也有順序棧和鏈棧兩種存儲結(jié)構(gòu)。順序棧易產(chǎn)生“上溢”現(xiàn)象，而鏈棧不容易產(chǎn)生。

13、另外，注意對棧的操作只能在棧頂進(jìn)行。5隊列隊列（）是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。通常把允許插入的一端稱為隊尾（），允許刪除的一端稱為隊頭（）。隊列中元素如果按，的順序進(jìn)隊，則出隊的順序仍為，。因此，隊列又稱為“先進(jìn)先出”（）的線性表，簡稱表。隊列也有順序隊列和鏈隊列兩種存儲結(jié)構(gòu)。在順序隊列中，為避免“假滿”現(xiàn)象，一般采用循環(huán)隊列（即首尾相接）。鏈隊列會因為隊滿而產(chǎn)生“上溢”現(xiàn)象。由第4章串祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出

14、自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwoizTTTfvwvewcnrintfEvwolohesiha祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！計算機(jī)科學(xué)與技術(shù)（專升本1計算機(jī)科學(xué)與技術(shù)（專升本1概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)期串（）（或字符串）：是由零個或多個字符組成的有限序列。一般記為其中，是串的名，用雙引號括起來的字符序列是串的值。串的長度：串中字符的個數(shù)n。子串和主串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串空串：不包含任何字符的串，表示為“”?？崭翊河梢粋€

15、或多個空格字符組成的串。例如：“”。2串的基本操作（）用串變量賦值和用串常量賦值（2）判等函數(shù)equat）l（s,（3）求長函數(shù)length（s）（4）連接函數(shù)concat（s,t）（5）求子串函數(shù)substproi,snlge（ns）,（6）定位函數(shù)index（s,t）（7）置換函數(shù)replace（s,t,v）（8）插入子串insert（s,pos,t）（9）刪除子串delete（s,pos,k）（10）串的復(fù)制copy（s,t）3串的順序存儲結(jié)構(gòu)（順序串）串的順序存儲方式類似于線性表的順序存儲方式，其存儲結(jié)構(gòu)用語言描述為：定義順序串類型第5章數(shù)組和廣義表1多維數(shù)組的順序存儲結(jié)構(gòu)對于多維數(shù)組

16、，有兩種存儲方式：一是以行為主序（或先行后列）的順序存放，如、等程序設(shè)計語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，如語言中，用的是以列為主序的分配順序，即一列一列地分配。以行為主序的分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第二個下標(biāo)再變，從右向左，最后是左下標(biāo)。以列為主序分配的規(guī)律是：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個下標(biāo)再變，從左向右，最后是右下標(biāo)。不論按何種方式存儲，只要確定了數(shù)組的首地址以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的計算機(jī)科學(xué)與技術(shù)(專升本)數(shù)據(jù)結(jié)構(gòu)期

17、末考試復(fù)習(xí)資料古月編輯整理存儲地址表示為其下標(biāo)的線性函數(shù)。設(shè)有二維數(shù)組，以“以行為主序”的分配為例，按照元素的下標(biāo)確定其地址的計算方法如下。設(shè)數(shù)組的基址為(a,每個數(shù)組元素占據(jù)個地址單元，計算a的物理地址的函數(shù)為：(aO(a,)-同理，對于三維數(shù)組，即數(shù)組，對于數(shù)組元素a其物理地址為：(a)(a)()注意：在語言中，數(shù)組中每一維的下界定義為，貝y：(aO(a()2特殊矩陣壓縮存儲的意義在很多科學(xué)計算與工程應(yīng)用中，經(jīng)常要使用矩陣的概念。矩陣具有與數(shù)組相似的性質(zhì)，如元素數(shù)目固定、元素按下標(biāo)關(guān)系有序地排列，所以在編程時可以利用二維數(shù)組來存儲矩陣，也可以利用程序設(shè)計語言中的各種矩陣運算。在某些情況下，

18、特別是在數(shù)值分析中，經(jīng)常會出現(xiàn)一些階數(shù)很高的矩陣，其中含有許多值相同的元素或零元素，如三角矩陣、對稱矩陣、稀疏矩陣等，從節(jié)約存儲空間的角度考慮，此時若用二維數(shù)組存儲會造成空間的極大浪費。為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。即為對多個相同值的元素只分配一個存儲空間，而對零元素可以不分配空間。3對稱矩陣壓縮存儲的方法對稱矩陣的特點是：在一個階方陣中，有a,其中WW，對稱矩陣關(guān)于主對角線對稱，因此只需存儲上三角或下三角部分即可。TOC o 1-5 h z對于對稱矩陣中的任意元素a,若令a,(),則將上面兩個式子綜合起來得到：(。)給出對稱矩陣中任意元素a,依據(jù)它的下標(biāo)和就可由上述對應(yīng)關(guān)系式

19、確定其在數(shù)組中的位置，因此a的地址可由下式計算。(a)()()()()其中：為每個數(shù)據(jù)元素所占的存儲單元長度。a()。()(+)4三角矩陣壓縮存儲的方法形如圖的矩陣稱為三角矩陣，其中為某個常數(shù)。其中下面圖(a為下三角矩陣：主對角線以上均為同一個常數(shù)；(b)為上三角矩陣，主對角線以下均為同一個常數(shù)；下面討論它們的壓縮存儲方法。(a)下三角矩陣(b)上三角矩陣圖三角矩陣計算機(jī)科學(xué)與技術(shù)專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理三角矩陣中的重復(fù)元素可以共享一個存儲空間，其余的元素有個，因此可壓縮存儲到向量中，存放在向量的最后一個分量中，排列時以行序為主。和的對應(yīng)關(guān)系是：下三角矩陣：上三角矩陣:5稀疏

20、矩陣及其壓縮存儲的特點設(shè)矩陣中有個非零元素且，這樣的矩陣稱為稀疏矩陣。稀疏矩陣的壓縮存儲采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個三元組（），然后再按某種規(guī)律存儲這些三元組，這種方法可以節(jié)約存儲空間。6稀疏矩陣壓縮存儲的順序存儲方式以順序方式組織存儲時常用的方法是三元組順序表，方法是：將三元組按行優(yōu)先的順序，同一行中列號從小到大的規(guī)律排列成一個線性表，采用順序存儲方法存儲該表。7稀疏矩陣壓縮存儲的鏈?zhǔn)酱鎯Ψ绞较∈杈仃噳嚎s存儲的鏈?zhǔn)酱鎯Ψ绞剑词宙湵?。?dāng)矩陣中非零元素的個數(shù)和位置在使用中經(jīng)常發(fā)生變化時，不宜采用順序存儲結(jié)構(gòu)，可采用十字鏈表進(jìn)行存儲。其結(jié)點結(jié)構(gòu)如圖所示。8廣義表（列表

21、）的定義、術(shù)語及它與線性表的關(guān)系廣義表（當(dāng)是（2）個數(shù)據(jù)元素的有序序列，一般記作：=（IO圖十字鏈表的結(jié)點結(jié)構(gòu)其中：是廣義表的名稱，是它的長度，每個（ww）是的成員，它可以是單個元素，也可以是一個廣義表，分別稱為廣義表的單元素和子表。當(dāng)廣義表非空時，稱第一個元素為的表頭（），稱其余元素組成的表（，）為的表尾（）。表的深度：表中元素的最深嵌套層數(shù)。廣義表與線性表的關(guān)系：當(dāng)廣義表中的元素全部是原子時，廣義表即為線性表。因此，可認(rèn)為線性表是廣義表的特例，廣義表是線性表的推廣。9廣義表的三個重要性質(zhì)C）廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，。C

22、）廣義表可以是遞歸的表。廣義表的定義并沒有限制元素的遞歸，即廣義表也可以是其自身的子表。例如表就是一個遞歸的表。C）廣義表可以為其他表所共享。例如，表、表、表是表的共享子表。在中可以不必列出子表的值，而用子表的名稱來引用。O廣義表的存儲結(jié)構(gòu)祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本

23、數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！按結(jié)點形式的不同，廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可分為兩種不同的存儲方式。一種稱為頭尾表示法，另一種稱為孩子兄弟表示法。11廣義表的基本運算廣義表有兩個重要的基本操作，即取頭操作（）和取尾操作（）i此外，在廣義表上可以定義與線性表類似的一些操作，如建立、插入、刪除、拆開、連接、復(fù)制、遍歷等。第6章樹從對線性結(jié)構(gòu)的研究過渡到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變。1理解樹的遞歸定義樹（）是零個或多個結(jié)點的有限集合。結(jié)點數(shù)為的樹稱為空樹，結(jié)點數(shù)大于的樹稱為非空樹。在一棵非空樹中：（）

24、有且僅有一個特定的稱為根（）的結(jié)點；（）當(dāng)結(jié)點數(shù)大于時，除根結(jié)點外，其它結(jié)點被分成（）個互不相交的子集：，其中每個子集本身又是一棵樹（稱之為子樹），每一棵子樹的根（WW）都是根結(jié)點的后繼，樹1，稱為根的子樹。，掌握樹的基本概念結(jié)點的度（）:是指結(jié)點擁有的子樹的數(shù)目。葉子或終端結(jié)點：是指度為0的結(jié)點。非終端結(jié)點或分支結(jié)點：是指度不為0的結(jié)點。樹的度：是指樹內(nèi)各結(jié)點的度的最大值。孩子（）和雙親（）：某個結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)的，該結(jié)點稱為其孩子的雙親。兄弟：同一個雙親的孩子結(jié)點互為兄弟。結(jié)點的層次：規(guī)定根所在的層次為第1層，根的孩子在第二層，依次類推。樹的深度或高度：樹中結(jié)點最大的層

25、數(shù)。有序樹：是指樹中結(jié)點的各子樹從左至右是有次序的，否則稱為無序樹。森林：是指（三）棵互不相交的樹的集合。3理解二叉樹的遞歸定義及其與樹的區(qū)別二叉樹（）是結(jié)點的有限集合，這個集合或者為空，或者是由一個根結(jié)點和兩棵互不相交的分別稱為左子樹和右子樹的二叉樹組成。二叉樹中的每個結(jié)點至多有兩棵子樹，且子樹有左右之分，次序不能顛倒。二叉樹是一種重要的樹型結(jié)構(gòu)，但二叉樹不是樹的特例。二叉樹的5種形態(tài)分別為：空二叉樹，只有根結(jié)點的二叉樹，根結(jié)點和左子樹，根結(jié)點和右子樹，根結(jié)點和左右子樹。二叉樹與樹的區(qū)別：二叉樹中每個結(jié)點的孩子至多不超過兩個，而樹對結(jié)點的孩子數(shù)無限制；另外，二叉樹中結(jié)點的子樹有左右之分，而樹

26、的子樹沒有次序。4掌握滿二叉樹和完全二叉樹的概念滿二叉樹（）和完全二叉樹（），是兩種特殊形態(tài)的二叉樹。計算機(jī)科學(xué)與技術(shù)專升本數(shù)據(jù)結(jié)構(gòu)期htkvvivCMtnrmHE計算機(jī)科學(xué)與技術(shù)專升本數(shù)據(jù)結(jié)構(gòu)期htkvvivCMtnrmHEvmhwerihamvBszuA一棵深度為且有個結(jié)點的二叉樹稱為滿二叉樹。深度為，有個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為的滿二叉樹中編號從至的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。完全二叉樹的特點是：1）只允許最后一層有空缺結(jié)點且空缺在右邊，即葉子結(jié)點只能在層次最大的兩層上出現(xiàn)；（）對任一結(jié)點，如果其右子樹的深度為，則其左子樹的深度必為或理解二叉樹的性質(zhì)已知二叉樹的

27、深度可求出該二叉樹擁有的最多結(jié)點數(shù)，已知結(jié)點數(shù)可求出對應(yīng)樹或二叉樹的最大和最小高度。性質(zhì)在二叉樹的第層上最多有個結(jié)點（三）。性質(zhì)深度為的二叉樹最多有個結(jié)點（三）。性質(zhì)對任何一棵二叉樹，如果其終端結(jié)點數(shù)為，度為的結(jié)點數(shù)為，則2性質(zhì)性質(zhì)在二叉樹的第層上最多有個結(jié)點（三）。性質(zhì)深度為的二叉樹最多有個結(jié)點（三）。性質(zhì)對任何一棵二叉樹，如果其終端結(jié)點數(shù)為，度為的結(jié)點數(shù)為，則2性質(zhì)具有個結(jié)點的完全二叉樹的深度為性質(zhì)如果對一棵有個結(jié)點的完全二叉樹（其深度為1，其中，為不大于的最大整數(shù)）祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出

28、自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnri

29、ntfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！的結(jié)點按層序編號（編號方法為從第層到最后一層，每一層從左到右），則對任一結(jié)點（1）如果，則結(jié)點是二叉樹的根，無雙親；如果則其雙親是第個結(jié)點。2）如果1）如果，則結(jié)點是二叉樹的根，無雙親；如果則其雙親是第個結(jié)點。2）如果，則結(jié)點無左孩子（即結(jié)點為葉子結(jié)點）;否則其左孩子是第個結(jié)點。3）如果，則結(jié)點無右孩子；否則其右孩子是第+個1結(jié)點。二叉樹中結(jié)點的編號規(guī)則和對應(yīng)的順序

30、存儲結(jié)構(gòu)順序存儲二叉樹的具體方法是：在一棵具有個結(jié)點的完全二叉樹中，從根結(jié)點開始編號為，自上到下，二叉樹中結(jié)點的編號規(guī)則和對應(yīng)的順序存儲結(jié)構(gòu)順序存儲二叉樹的具體方法是：在一棵具有個結(jié)點的完全二叉樹中，從根結(jié)點開始編號為，自上到下，每層自左至右地給所有結(jié)點編號，這樣可以得到一個反映整個二叉樹結(jié)構(gòu)的線性序列；然后將完全二叉樹上編號為的結(jié)點依次存儲在一維數(shù)組中下標(biāo)為的元素中。上編號為的結(jié)點依次存儲在一維數(shù)組中下標(biāo)為的元素中。祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出

31、自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewc

32、nrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！二叉樹的鏈接存儲結(jié)構(gòu)及存儲結(jié)點的類型定義鏈?zhǔn)酱鎯κ鞘褂面湵韥泶鎯Χ鏄渲械臄?shù)據(jù)元素，鏈表中的一個結(jié)點相應(yīng)地存儲二叉樹中的一個結(jié)點。常見的二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有兩種：二叉鏈表和三叉鏈表。二叉鏈表是指鏈表中的每個結(jié)點包含兩個指針域和一個數(shù)據(jù)域，分別用來存儲指向二叉樹中結(jié)點的左右孩子的指針及結(jié)點信息。三叉鏈表是指鏈表中的每個結(jié)點包含三個指針域和一個數(shù)據(jù)域，相比二叉鏈表多出的一個指針域則用來指向該結(jié)點的雙親結(jié)點。不論哪種鏈表，

33、頭指針都指向二叉樹的根結(jié)點。），在含有個結(jié)點的二叉鏈表中，共有個指針域，但實際有效的指針數(shù)等于二叉樹中的分支數(shù)（即），所以共存在個空的指針域。掌握二叉樹的先序、中序、后序遍歷的遞歸算法和非遞歸算法。能夠根據(jù)先序+中序、后序+中序的遍歷序列確定一棵二叉樹，并理解為什么先序+后序不能唯一確定一棵二叉樹。o掌握線索二叉樹的定義及存儲結(jié)構(gòu)，會畫出先序、中序和后序線索二叉樹或相應(yīng)的線索鏈表。2掌握遍歷中序線索二叉樹的規(guī)則及算法。計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整

34、理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！3掌握樹的三種存儲結(jié)構(gòu)：雙親表示法、孩子表示法、孩子兄弟表示

35、法，掌握這三種存儲方法的特點，并且能夠畫出指定樹的存儲結(jié)構(gòu)圖。4理解二叉樹與樹或森林轉(zhuǎn)換的目的，掌握樹和二叉樹之間的相互轉(zhuǎn)換，掌握森林和二叉樹之間的相互轉(zhuǎn)換。5掌握樹的先根、后根和按層遍歷的過程。6掌握森林的先根、后根遍歷。7掌握路徑、路徑長度、結(jié)點的權(quán)、結(jié)點的帶權(quán)路徑長度、樹的帶權(quán)路徑長度的概念。路徑：若在樹中存在著一個結(jié)點序列，使得是的雙親（WW）,則此結(jié)點序列稱為從到的路徑。路徑長度：從到所經(jīng)過的分支數(shù)稱為這兩點之間的路徑長度，它等于路徑上的結(jié)點數(shù)減1結(jié)點的權(quán)：在許多應(yīng)用中，常常將樹中的某個結(jié)點賦上一個具有某種意義的數(shù)值，這個和某個結(jié)點相關(guān)的數(shù)值稱為該結(jié)點的權(quán)或權(quán)值。結(jié)點的帶權(quán)路徑長度：

36、是指從樹根到該結(jié)點之間的路徑長度與結(jié)點的權(quán)值的乘積。樹的帶權(quán)路徑長度：是指樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為。其中表示葉子結(jié)點的個數(shù)，表示葉子結(jié)點的權(quán)值，表示根結(jié)點到的路徑長度。8掌握哈夫曼樹的概念。哈夫曼樹（）又稱為最優(yōu)二叉樹，它是個帶權(quán)的葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度最小的二叉樹。9掌握哈夫曼樹的構(gòu)造方法，即根據(jù)一組給定的權(quán)值構(gòu)造相應(yīng)的哈夫曼樹。O理解哈夫曼編碼的含義，能夠根據(jù)實際問題構(gòu)造哈夫曼編碼。第章圖，基本概念及術(shù)語圖：由兩個集合和所組成，記作=V，其中是圖中頂點的非空有限集合，是圖中邊的有限集合。有向圖：如果圖中每條邊都是有向的即每條邊在圖示時都用箭頭表示方向，則

37、稱此圖為有向圖。有向圖的邊也稱為弧，如圖中是有向圖，它由和組成。，E圖圖示例無向圖：如果圖中每條邊都是頂點無序?qū)Γ瑒t稱為無向圖。無向邊用圓括號括起的兩個相關(guān)頂點來表示。在無向圖中，和是表示同一條邊。如圖所示，和都是無向圖。其中，無向完全圖和有向完全圖：若一個無向圖有個頂點，而每一個頂點與其他個頂點之間都有邊，這樣的圖稱之為無向完全圖。即共有一/條邊。類似地，在有個頂點的有向圖中，若有一條弧，即任意兩頂點之間都有雙向相反的兩條弧連接，則稱此圖為有向完全圖。子圖：設(shè)有兩個圖和且滿足條件：WV且B則稱是的子圖。路徑：在圖G中，從頂點V到V的一條路徑是頂點序列且是中的邊，路徑上邊的數(shù)目稱之為該路徑長度

38、。對于有向圖，其路徑也是有向的，路徑由弧組成。簡單路徑：如果一條路徑上所有頂點除其起始點和終止點外彼此都是不同的，則稱該路徑是簡單路徑?；芈泛秃唵位芈罚涸谝粭l路徑中，如果其起始點和終止點是同一頂點，則稱其為回路。簡單路徑相應(yīng)的回路稱為簡單回路。連通圖和強(qiáng)連通圖：在無向圖中，若從到有路徑，則稱和是連通的。若中任意兩頂點都是連通的，則稱是連通圖。對于有向圖而言，若中每一對不同頂點和之間都有到和到的路徑，則稱為強(qiáng)連通圖。度、入度和出度：若是中的一條邊，則稱頂點和是鄰接的.并稱邊依附于頂點和。所謂頂點的度，就是依附于該頂點的邊數(shù)。在有向圖中，以某頂點為頭，即終止于該頂點的弧的數(shù)目稱為該頂點的入度；以某

39、頂點為尾，即起始于該頂點的弧的數(shù)目稱為該頂點的出度。該頂點的入度和出度之和稱為該頂點的度。若圖中每一條邊都有一個對應(yīng)的數(shù)，則稱為網(wǎng)。這些邊上的數(shù)字稱為權(quán)，它可以表示兩頂點之間的距離或所花費的代價。類似地，邊上帶權(quán)的有向圖稱為有向網(wǎng)。如在圖中是一個網(wǎng)，而圖則是一個有向網(wǎng)。個有向網(wǎng)。計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的

40、成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升

41、本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！2圖的存儲結(jié)構(gòu)常用的存儲結(jié)構(gòu)有鄰接矩陣和鄰接表。C）鄰接矩陣表示法的鄰接矩陣是按如下

42、定義的階方陣:）W的鄰接矩陣是按如下定義的階方陣:）W或V丘時轉(zhuǎn)。選取和關(guān)鍵字較小的存入輔助數(shù)組。和組成,兩個子表長度分別為如果y轉(zhuǎn)。否則如果y轉(zhuǎn)。否則,將尚未處理完的子表中兀素存入。如果,存,入+;轉(zhuǎn)。如果，將存入izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfv

43、wvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資

44、料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！合并結(jié)束。（2）兩路歸并的迭代算法一個元素的表總是有序的。所以對個元素的待排序列，每個元素可看成一個有序子表。對子表兩兩合并一個元素的表總是有序的。所以對生成個子表，所得子表除最后一個子表長度可能為1外，其余子表長度均為2，再進(jìn)行兩兩合并，直到生成，個元素按關(guān)鍵字有序的表。（3）算法分析歸并排序是穩(wěn)定排序，若用單鏈表作

45、為存儲結(jié)構(gòu)，可以實現(xiàn)就地排序。這種排序方法可用于內(nèi)部排序，也可用于外部排序中。時間復(fù)雜度為。需進(jìn)行趟歸并，每一趟歸并中，比較次數(shù)最多為次,移動次數(shù)等為次?？臻g復(fù)雜度為。6基數(shù)排序基數(shù)排序是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法。計算機(jī)科學(xué)與技術(shù)（專升本（1）計算機(jī)科學(xué)與技術(shù)（專升本（1）多關(guān)鍵字排序數(shù)據(jù)結(jié)構(gòu)期uimvivtiHCmriHFwoloheeihamvBsziiA料古月編輯整理多關(guān)鍵字排序按照從最主位關(guān)鍵字到最次位關(guān)鍵字或從最次位關(guān)鍵字到最主位關(guān)鍵字的順序逐次排序，分兩種方法：最咼位優(yōu)先法（簡稱法）最低位優(yōu)先法（簡稱法）（2）鏈?zhǔn)交鶖?shù)排序算法思想基數(shù)排序：從最低位關(guān)鍵

46、字起，按關(guān)鍵字的不同值將序列中的記錄“分配”到個隊列中，然后再“收集”之。如此重復(fù)次即可。鏈?zhǔn)交鶖?shù)排序是用個鏈隊列作為分配隊列，關(guān)鍵字相同的記錄存入同一個鏈隊列中，收集則是將各鏈隊列按關(guān)鍵字大小順序連接起來。算法分析基數(shù)排序是穩(wěn)定排序，如果記錄序列初始不是順序存儲，而是單鏈表形式，那么各輔助鏈隊列無須分配結(jié)點空間，利用原鏈表的結(jié)點空間即可，而且分配和收集時都不必移動記錄，只要修改指針，這樣可以節(jié)省一定的時間和空間。7各種內(nèi)部排序方法的比較與討論（1）內(nèi)部排序方法的共同點基本操作相同大多數(shù)排序算法都有兩個基本的操作：（i）比較兩個關(guān)鍵字的大小。（）改變指向記錄的指針或移動記錄本身，這種基本操作的

47、實現(xiàn)依賴于待排序記錄的存儲方式。待排文件的常用存儲方式相同盡管排序可以采用不同方法，但所有待排序文件的存儲方式都可以采用以下形式：（）順序表（或直接用向量）作為存儲結(jié)構(gòu)（）以鏈表作為存儲結(jié)構(gòu)。（）用順序的方式存儲待排序的記錄，但同時建立一個輔助表。（2）內(nèi)部排序方法的不同點排序方法平均時間復(fù)雜度最壞時間復(fù)雜度輔助存儲空間穩(wěn)定性插入排序穩(wěn)定希爾排序不確定不確定不穩(wěn)定冒泡排序穩(wěn)定簡單選擇排序穩(wěn)定基數(shù)排序穩(wěn)定快速排序不穩(wěn)定堆排序不穩(wěn)定歸并排序穩(wěn)定（3）排序方法的選擇若較?。ㄈ鏦0可采用直接插入或簡單選擇排序。若文件初始狀態(tài)基本有序（指正序），則應(yīng)選用直接插入、冒泡或隨機(jī)的快速排序為宜。若較大，則應(yīng)采

48、用時間復(fù)雜度為（）的排序方法：快速排序、堆排序或歸并排序?？焖倥判蚴悄壳盎诒容^的內(nèi)部排序中最好的方法，當(dāng)待排序的關(guān)鍵字隨機(jī)分布時，快速排序的平均時間最短。堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。模擬試卷：數(shù)據(jù)結(jié)構(gòu)模擬試卷、選擇題（每小題1.分5，共30分）、有一個含頭結(jié)點的單鏈表，頭指針為則判斷其是否為空的條件為（）。、非空的循環(huán)單鏈表的尾指針滿足（）。3鏈表不具有的特點是（）?？呻S機(jī)訪問任一個元素插入刪除不需要移動元素不必事先估計存儲空間所需空間與線性表的長度成正比4、若某鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后

49、一個結(jié)點，則采用（C）存儲方式最節(jié)省運算時間。A單鏈表B雙鏈表C單循環(huán)鏈表D帶頭結(jié)點的雙循環(huán)鏈表5若線性表最常用的操作是存取第個元素及其前驅(qū)的值，則采用（）存儲方式節(jié)省時間。A單鏈表B雙鏈表C單循環(huán)鏈表D順序表、設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是，其頭尾指針分別為，若隊列中元素個數(shù)為（）。、設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是，其頭尾指針分別為，若隊列中元素個數(shù)為（）。6設(shè)一個棧的輸入序列為，則借助一個棧所得到的輸出序列不可能的是（）。AA，B，C，DBD，C，B，A7、一個隊列的入隊序列是1，2，3，CA，C，D，BDD，A，B，C4，則隊列的輸出序列是（B）。Ar-fBr-f+C1（r-f）+m1odn

50、D（r-f）+mnodn9串是（）。A不少于一個字母的序列B任意個字母的序列C不少于一個字符的序列D有限個字符的序列、數(shù)組的每個元素占個單元，將其按行優(yōu)先次序存儲在起始地址為的連續(xù)內(nèi)存單元中,則的地址是（）。1、1將一棵有1、個、結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為（A）。izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrin

51、tfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！2對二叉樹從開始編號，要求每個結(jié)點的編號大于其左右孩子的編號

52、，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用()實現(xiàn)編號。先序遍歷中序遍歷后序遍歷從根開始進(jìn)行層次遍歷3、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()的二叉樹?？栈蛑挥幸粋€結(jié)點高度等于其結(jié)點數(shù)任一結(jié)點無左孩子任一結(jié)點無右孩子4在有個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為()。不確定5一個有個頂點的無向圖最多有()邊。(-(-16、任何一個無向連通圖的最小生成樹(B)。只有一棵有一棵或多棵一定有多棵可能不存在17、一組記錄的關(guān)鍵字為(46，79，56，38，40，84)，利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。8已知數(shù)據(jù)表中每個元素距其最

53、終位置不遠(yuǎn)，則采用()排序算法最節(jié)省時間。堆排序插入排序快速排序直接選擇排序19、下列排序算法中，()算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費時間反而最多。堆排序冒泡排序快速排序排序20、對于鍵值序列(12，13，1，118，60，15，7，18，25，10)0，用篩選法建堆，必須從鍵值為(B)的結(jié)點開始。二、判斷題(每小題分，共分。正確的在括號內(nèi)打V”錯誤的打X)1、在單鏈表中，頭結(jié)點是必不可少的。()2、如果一個二叉樹中沒有度為1的結(jié)點，則必為滿二叉樹。()3、循環(huán)鏈表的結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是結(jié)點間的連接方式不同。()4、順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)

54、只能用來存放非線性結(jié)構(gòu)。()5、在一個大根堆中，最小元素不一定在最后。()6、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。()7、在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰。()8、內(nèi)部排序是指排序過程在內(nèi)存中進(jìn)行的排序。()9、拓?fù)渑判蚴侵附Y(jié)點的值是有序排列。()10、線性表采用鏈?zhǔn)酱鎯Γ炔捎庙樞虼鎯Ψ绞?，使得插入、刪除、查找等運算的時間性能都更好。()三、填空題(每個填空2分，共20分)1、在順序表(即順序存儲結(jié)構(gòu)的線性表)中插入一個元素，需要平均移動個_元_素_。_2、快速排序的最壞情況，其待排序的初始排列是。izTTTfvwvewcnrintfEvwol

55、ohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)(專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計

56、算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！編輯整理、單循環(huán)鏈表中指針?biāo)附Y(jié)點為尾結(jié)點的條件是、一個棧的輸入序列為12，3寫出不可能是棧的輸出序列個結(jié)點的二叉樹，采用二叉鏈表存放，空鏈域的個數(shù)為、隊列的特性是、在求最小生成樹的兩種算法中，_算法_適_編輯整理、單循環(huán)鏈表中指針?biāo)附Y(jié)點為尾結(jié)點的條件是、一個棧的輸入序列為12，3寫出不可能是棧的輸出序列個結(jié)點的二叉樹，采用二叉鏈表存放，空鏈域的個數(shù)為、隊列的特性是、在求最小生成樹的兩種算法中，_算法_適_合_于_稀疏圖。、已知一棵二叉樹的前序序列為，中

57、序序列為，后序序列為、對二叉排序樹進(jìn)行遍_歷_，_可得到結(jié)點的有序排列。0設(shè)一哈希表表長為，用除留余數(shù)法構(gòu)造哈希函數(shù)，即（）為使函數(shù)具有較好性能，應(yīng)選四、應(yīng)用題（每小題5分，共20分）、已知關(guān)鍵字序列為：（7）哈希表長為10，哈希函數(shù)為：，解決沖突用線性探測再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查找長度。、給定葉結(jié)點權(quán)值：（1，3，5，6，7，8），構(gòu)造哈夫曼樹，并計算其帶權(quán)路徑長度。、從空樹開始，逐個讀入并插入下列關(guān)鍵字，構(gòu)造一棵二叉排序樹24，88，42，97，22，15，7，13）。祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參

58、考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！izTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！計算機(jī)科學(xué)與技術(shù)（專升本）計算機(jī)科學(xué)與技術(shù)（專升本）4、已知無向圖如圖1所示給出圖的鄰接表。從開始，給出一棵廣度優(yōu)先生成樹。五、設(shè)計題（每小題5分，共10分）1有一個帶頭結(jié)點的單鏈表，已知指向頭結(jié)點的指針，試寫出在元素值

59、為的結(jié)點（假設(shè)該結(jié)點存在）之后插入元素值為的結(jié)點（該結(jié)點未建立）的算法過程。、以二叉鏈表為存儲結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點數(shù)的算法的遞歸函數(shù)。計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)資料古月編輯整理祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！i

60、zTTTfvwvewcnrintfEvwolohesihaizTTTfvwvewcnrintfEvwolohesiha計算機(jī)科學(xué)與技術(shù)（專升本數(shù)據(jù)結(jié)構(gòu)期祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！祝愿大家考試考出自己理想的成績，本資料僅供參考，謝謝！tfrwmvtiHCmriHEwdtoHEeiHAmvssziiA一、選擇題（每小題，.分5，共30分）、若線性表最常用的操作是存取第個元素及其前驅(qū)元素的值，則采用（）存儲方式最節(jié)省時間。單鏈表雙向鏈表單循環(huán)鏈表順序表、串的長度是（D）。串中不同字母的個數(shù)串中不同字符的個數(shù)串中所含字符的個數(shù)，且大于串中所含字符的個數(shù)、數(shù)組，的每個元素占個