2023計(jì)算機(jī)考研初試在即，在最后階段建議各位同學(xué)將知識(shí)點(diǎn)再系統(tǒng)復(fù)習(xí)一遍，以免有所遺漏！2022計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)第一單元知識(shí)點(diǎn)包含數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)抽象和抽象數(shù)據(jù)類型、算法分析的基本方法。高頓考研為大家整理了2022計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)第一單元知識(shí)點(diǎn)的詳細(xì)內(nèi)容，供大家參考復(fù)習(xí)！
數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)：計(jì)算機(jī)加工處理的對(duì)象，分為數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)
數(shù)據(jù)元素(結(jié)點(diǎn)、頂點(diǎn))：組成數(shù)據(jù)的基本單位
數(shù)據(jù)項(xiàng)(字段、域)：組成數(shù)據(jù)的最小單位
數(shù)據(jù)結(jié)構(gòu)的概念：
(1)邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯關(guān)系
(a)集合結(jié)構(gòu)
(b)線性結(jié)構(gòu)
(c)樹形結(jié)構(gòu)
(d)圖狀結(jié)構(gòu)
3類基本的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖狀結(jié)構(gòu)
2類基本的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)，非線性結(jié)構(gòu)
(2)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的表示形式
(a)順序存儲(chǔ)結(jié)構(gòu)
(b)鏈接存儲(chǔ)結(jié)構(gòu)
(c)索引存儲(chǔ)結(jié)構(gòu)
(d)散列存儲(chǔ)結(jié)構(gòu)
(3)運(yùn)算：在數(shù)據(jù)上執(zhí)行的操作
創(chuàng)建、清除、插入、刪除等
·數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算定義組成了數(shù)據(jù)結(jié)構(gòu)的規(guī)范。
·數(shù)據(jù)的存儲(chǔ)表示和運(yùn)算算法的描述構(gòu)成數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。
數(shù)據(jù)結(jié)構(gòu)的分類：
(1)靜態(tài)數(shù)據(jù)結(jié)構(gòu)：一旦創(chuàng)建，其結(jié)構(gòu)不再改變的數(shù)據(jù)結(jié)構(gòu)。
(2)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)：允許進(jìn)行插入刪除等操作，其結(jié)構(gòu)是動(dòng)態(tài)變化的數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)抽象和抽象數(shù)據(jù)類型
(1)抽象(降低了問題求解的難度)
數(shù)據(jù)抽象：只關(guān)注數(shù)據(jù)元素間的邏輯關(guān)系，忽略數(shù)據(jù)在計(jì)算機(jī)中的具體表示。
過程抽象：只關(guān)注數(shù)據(jù)運(yùn)算的定義，忽略運(yùn)算的具體實(shí)現(xiàn)方法。
(2)封裝與信息隱蔽
(錯(cuò)誤局部化，降低問題求解的復(fù)雜性，提高程序的可靠性)
封裝:是指把數(shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算組合在一起的機(jī)制。使用者只能通過一組允許的運(yùn)算訪問其中的數(shù)據(jù)。
信息隱蔽：對(duì)使用者隱藏了數(shù)據(jù)結(jié)構(gòu)或程序的實(shí)現(xiàn)細(xì)節(jié)。
(3)數(shù)據(jù)類型和抽象數(shù)據(jù)類型
數(shù)據(jù)類型：它是數(shù)據(jù)抽象的一種方式。一個(gè)數(shù)據(jù)類型定義了一個(gè)值的集合以及作用于該值集的運(yùn)算集合。
抽象數(shù)據(jù)類型(ADT)：該類型的對(duì)象及其運(yùn)算的規(guī)范,與該類型對(duì)象的表示和運(yùn)算的實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽，即所謂使用和實(shí)現(xiàn)分離，數(shù)據(jù)結(jié)構(gòu)是一種抽象數(shù)據(jù)類型。
算法分析的基本方法
計(jì)算機(jī)算法：一個(gè)有窮的指令序列，它規(guī)定了解決某一特定問題的一系列運(yùn)算。
計(jì)算機(jī)算法的特征：輸入、輸出、確定性、能行性、有窮性
“好算法”的特征：正確、簡(jiǎn)明、健壯、效率
(1)時(shí)間復(fù)雜度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
考點(diǎn)：最好、最壞和平均時(shí)間復(fù)雜度
(2)空間復(fù)雜度
算法執(zhí)行過程中對(duì)存儲(chǔ)空間的需求量。
通常是分析最壞的情況。