【正文】 第一章 緒論 ? 考綱要求 考綱中沒有這一章 ? 考綱分析 建議考生復(fù)習(xí)時復(fù)習(xí)這一章，因為把握這一章有助于對整個課程知識的理解。本章主要掌握 DS和算法的基本概念，其出題形式主要為選擇題。關(guān)于 DS的深刻理解有可能出小分值的綜合應(yīng)用題。由于分值有限，算法時間復(fù)雜度的分析一般不會以綜合應(yīng)用題的形式單獨(dú)出題，通常會結(jié)合算法設(shè)計題來分析，由于 DS課程要求掌握初步的算法分析技術(shù)，因此，算法分析題不會太難。 ? 基本知識點： 數(shù)據(jù)結(jié)構(gòu)和算法的概念 ? 重點： 數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運(yùn)算三方面的概念及相互關(guān)系 ? 難點： 分析算法的時間復(fù)雜度 第一章 緒論 DS的基本概念 ? 考核知識點 1. 數(shù)據(jù)：是信息的載體。 2. 數(shù)據(jù)元素（也稱為結(jié)點）：是表示數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。 3. 數(shù)據(jù)項：是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。 4. 數(shù)據(jù)對象：是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。（在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對象簡稱為數(shù)據(jù)）。 5. 數(shù)據(jù)結(jié)構(gòu) (★★★ )DataStructure=(D,R)，其中 D是數(shù)據(jù)元素的集合， R是 D上關(guān)系的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)（物理結(jié)構(gòu)）。 DS的基本概念 ? 考核知識點 6. 數(shù)據(jù)的邏輯結(jié)構(gòu) (★★★★ ) 是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同， 數(shù)據(jù)結(jié)構(gòu)分為四類： 1) 集合：數(shù)據(jù)元素之間就是 “ 屬于同一個集合 ” ，除此之外，無任何關(guān)系； 2) 線性結(jié)構(gòu)：一對一； 3) 樹結(jié)構(gòu)：一對多的層次關(guān)系； 4) 圖結(jié)構(gòu)：多對多的任意關(guān)系。 樹和圖結(jié)構(gòu)也稱為非線性結(jié)構(gòu)。 DS的基本概念 ? 考核知識點 7. 數(shù)據(jù)的存儲結(jié)構(gòu) (★★★★ ) 又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機(jī)中的表示。通常有 兩種 存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)和 鏈接存儲結(jié)構(gòu) 。 順序存儲結(jié)構(gòu)的基本思想是：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示； 鏈接存儲結(jié)構(gòu)的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。 存儲結(jié)構(gòu)除了存儲數(shù)據(jù)元素之外，還必須存儲數(shù)據(jù)元素之間的邏輯關(guān)系。 DS的基本概念 ? 考核知識點 8. 抽象數(shù)據(jù)類型 ADT(★★ ) 抽象數(shù)據(jù)類型是一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。它提供了使用和實現(xiàn)兩個不同的視圖，實現(xiàn)了封裝和信息隱藏。 典型題解析 ? 1. 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承（如圖），則表示該遺產(chǎn)繼承關(guān)系的最合適的 DS應(yīng)該是（ ）。 A. 樹 B. 圖 C. 線性表 D. 集合 解答： B 丈夫 妻子 子女 1 子女 n 。 典型題解析 ? 2. 計算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（ ）。 A. 數(shù)據(jù)和數(shù)據(jù)之間存在某種聯(lián)系 B. 元素和元素之間存在某種聯(lián)系 C. 元素內(nèi)部具有某種結(jié)構(gòu) D. 數(shù)據(jù)項和數(shù)據(jù)項之間存在某種聯(lián)系 解答： B 分析： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元 素的集合，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位，元素內(nèi)部各數(shù)據(jù)項一般不予考慮。 典型題解析 ? 3. 在鏈接存儲結(jié)構(gòu)中，要求（ ）。 A. 每個結(jié)點占用一片連續(xù)的存儲區(qū)域 B. 所有結(jié)點占用一片連續(xù)的存儲區(qū)域 C. 結(jié)點的最后一個域是指針類型 D. 每個結(jié)點有多少個后繼就設(shè)有多少個指針 解答： A 分析： 結(jié)點作為存取操作的獨(dú)立單位，需要占用連續(xù)的存儲區(qū)域，但不要求結(jié)點中各組成部分（域）的順序。 典型題解析 ? 4. 下列說法中不正確的是（ ）。 A. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 B. 數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小單位 C. 數(shù)據(jù)可由若干個數(shù)據(jù)項構(gòu)成 D. 數(shù)據(jù)元素可由若干個數(shù)據(jù)項構(gòu)成 解答： C 分析： 數(shù)據(jù)是由若干個數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素是由若干個數(shù)據(jù)項構(gòu)成。 典型題解析 ? 5. 可以用（ ）、數(shù)據(jù)關(guān)系和基本操作定義一個完整的抽象數(shù)據(jù)類型。 A. 數(shù)據(jù)元素 B. 數(shù)據(jù)對象 C. 原子類型 D. 存儲結(jié)構(gòu) 解答： B 分析： ADT的三要素為：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作。 典型題解析（應(yīng)用題） ? 1. 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。 解答： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，抽象數(shù)據(jù)類型是指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一個操作，程序設(shè)計語言中的數(shù)據(jù)類型是一個值的集合和定義在這個值集上一組操作的總稱。 抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一種抽象。在高級程序設(shè)計語言中，基本數(shù)據(jù)類型隱含著數(shù)據(jù)結(jié)構(gòu)和定義在該結(jié)構(gòu)上的操作的統(tǒng)一。例如 C++中的整型就是整數(shù)的數(shù)學(xué)含義與算術(shù)運(yùn)算的統(tǒng)一體，只是由于這些基本數(shù)據(jù)類型中的數(shù)據(jù)結(jié)構(gòu)的具體表示、基本操作和具體實現(xiàn)都很規(guī)范，可以通過系統(tǒng)內(nèi)置而隱藏起來。 典型題解析（應(yīng)用題） ? 2. 說明數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。 解答： 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密切相關(guān)的兩個方面。數(shù)據(jù)的邏輯結(jié)構(gòu) 屬于用戶視圖，是面向問題的 ，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式。數(shù)據(jù)的存儲結(jié)構(gòu)屬于 具體實現(xiàn)的視圖，是面向計算機(jī)的， 其基本目標(biāo)是將數(shù)據(jù)及其邏輯關(guān)系存儲到計算機(jī)的內(nèi)存中。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲，而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。 典型題解析（應(yīng)用題） ? 3. 抽象數(shù)據(jù)類型的主要特點是什么？數(shù)據(jù)類型和抽象數(shù)據(jù)類型的關(guān)系