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