2021年《數(shù)據(jù)結(jié)構(gòu)》考研真題與考研復(fù)習(xí)

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

P=pFJ?A.O(1)B.O(log2n)C.O(n)D