2024年數(shù)據(jù)結構考研真題與典型題詳解

第1章緒論1.1知識要點總結一、數(shù)據(jù)結構的基本概念1．基礎概念和術語（1）數(shù)據(jù)（Data）：數(shù)據(jù)是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。（2）數(shù)據(jù)元素（DataElement）：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。（3）數(shù)據(jù)項（DataItem）：數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位，數(shù)據(jù)項是對客觀事物的某一方面的數(shù)據(jù)描述。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（DataItem）組成。（4）數(shù)據(jù)對象（DataObject）：數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C={‘A’,’B’,’C’,…}（5）數(shù)據(jù)結構（DataStructure）：數(shù)據(jù)結構是指相互之間存在一定聯(lián)系（關系）的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系（關系）稱為邏輯結構。2．數(shù)據(jù)結構的形式定義數(shù)據(jù)結構的形式定義是一個二元組：DataStructure=（D,S）其中D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。數(shù)據(jù)元素之間的關系可以是元素之間本身代表的某種自然關系，也可以是為了處理問題方便而人為定義的關系，這種自然或人為定義的關系稱為數(shù)據(jù)元素之間的邏輯關系，相應的結構稱為邏輯結構。3．數(shù)據(jù)結構的組成數(shù)據(jù)結構的三個組成部分：（1）邏輯結構數(shù)據(jù)元素之間的邏輯關系的描述。數(shù)據(jù)元素之間的邏輯結構有四種基本類型：①集合：結構中的數(shù)據(jù)除了“同屬于一個集合”外，沒有其它關系。②線性結構：結構中的數(shù)據(jù)元素之間存在一對一的關系。③樹形結構：結構中的數(shù)據(jù)元素之間存在一對多的關系。④圖形結構或網狀結構：結構中的數(shù)據(jù)元素之間存在多對多的關系。（2）存儲結構數(shù)據(jù)結構在計算機中的實際表達方式，它包括對數(shù)據(jù)元素的表示和對關系的表示。存儲結構主要有：順序存儲、鏈式存儲、索引存儲和散列存儲。①順序存儲結構：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結構。數(shù)據(jù)元素存放的地址是連續(xù)的。其優(yōu)點是可以實現(xiàn)隨機存取，存儲空間??；缺點是只能使用相鄰的一整塊存儲單元，容易產生碎片。②鏈式存儲結構：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針，用該指針來表示數(shù)據(jù)元素之間的邏輯結構。對數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。其優(yōu)點是能充分利用所有存儲單元；缺點是每個結點都需要額外的存儲空間，且只能實現(xiàn)順序存取。③索引存儲結構：在存儲元素信息的同時．還建立附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式是：（關鍵字．地址），關鍵字唯一標識一個元素，地址作為指向元素的指針。其優(yōu)點是檢索速度快；缺點是需要額外的存儲空間來存放索引表。④散列（或哈希）存儲結構：根據(jù)元素的關鍵字通過哈希函數(shù)直接計算出該元素的存儲地址。其優(yōu)點是檢索速度快，缺點是可能存在沖突，而解決沖突會增加時空開銷。（3）數(shù)據(jù)操作對數(shù)據(jù)要進行的運算。【例】下列有關數(shù)據(jù)存儲結構的敘述中，正確的是（ ）。A．順序存儲方式只能用于存儲線性結構B．順序存儲方式的優(yōu)點是占用存儲空問小，插入、刪除等操作效率高C．鏈表的每個結點中都恰好含有一個指針D．Hash存儲的基本思想是由關鍵詞的值決定數(shù)據(jù)的存儲地址【答案】D查看答案【解析】順序存儲方式除了用于存儲線性結構外，還能存儲數(shù)組或完全二叉樹等非線性結構，但在插入、刪除操作時，由于要移動大量的數(shù)據(jù)，執(zhí)行效率低。鏈表的形式有單鏈表、雙鏈表和多重鏈表，除了單鏈表外，其他鏈表中的結點需要兩個以上的指針。二、抽象數(shù)據(jù)類型1．數(shù)據(jù)類型數(shù)據(jù)類型（DataType）：數(shù)據(jù)類型是一個值的集合和定義在該集合上的一組操作的總稱。2．抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）：是指一個數(shù)學模型以及定義在該數(shù)據(jù)模型上的一組操作。ADT的定義僅是一組邏輯特性的描述，與其在計算機內的表示和實現(xiàn)無關。因此，不論ADT內部結構如何變化，只要其數(shù)學特性不變，都不影響其外部使用。ADT的形式化定義是三元組：ADT={D,S,P}。其中：D是數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。三、算法分析1．算法（1）概念算法（Algorithm）：算法是對特定問題求解方法（步驟）的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。（2）特性算法由五個特性：①有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。②確定性：算法中每一條指令必須有確切的含義，不存在二義性，且算法只有一個入口和出口。③可行性：算法描述的操作都可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。④輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。⑤輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關系的量。（3）評價標準評價一個好的算法有以下幾個標準：①正確性：算法應滿足具體問題的需求。②可讀性：算法應容易供人閱讀和交流?？勺x性好的算法有助于對算法的理解和修改。③健壯性：算法應具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法能適當?shù)刈龀龇磻蜻M行處理。④通用性：算法應具有一般性，處理結果對于一般數(shù)據(jù)集合都成立。⑤效率和存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指的是執(zhí)行過程中所需要的最大存儲空間。2．效率的度量（1）時間復雜度算法中的基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間度量記做T（n）=O（f（n））（其中“O”是指T（n）的數(shù)量級），稱作算法的漸進時間復雜度，簡稱時間復雜度。算法的時間復雜度一般用最深層循環(huán)內的語句中的原操作的執(zhí)行頻度（重復執(zhí)行的次數(shù)）來表示。常用的時間復雜度的關系：O（1）<O（log2n）<O（n）<O（nlog2n）<O（n2）<O（n3）指數(shù)時間復雜度關系為：O（2n）<O（n!）<O（nn）有的情況下，算法中基本操作重復執(zhí)行的次數(shù)會隨問題的輸入數(shù)據(jù)集的不同而不同（2）空間復雜度空間復雜度指的是算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。記做：S（n）=O（f（n）），其中n為問題的規(guī)模。空間復雜度一般包括三個方面：①指令常數(shù)變量所占用的存儲空間。②輸入數(shù)據(jù)所占用的存儲空間。③輔助存儲空間。【例】有以下算法，其時間復雜度為（）。A．O（1）B．O（log2n）C．O（n）D．（