1、數(shù)據(jù)結(jié)構(gòu)=邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+操作?
2、數(shù)據(jù)的基本單位：數(shù)據(jù)元素
3、數(shù)據(jù)元素的最小單位：數(shù)據(jù)項(xiàng)
4、在數(shù)據(jù)庫中：數(shù)據(jù)元素為行，數(shù)據(jù)項(xiàng)為列（簡稱行為元素，列為項(xiàng)）
5、數(shù)據(jù)元素的集合稱為：數(shù)據(jù)對象
6、數(shù)據(jù)類型是 （3種）：原子類型、結(jié)構(gòu)類型、抽象數(shù)據(jù)類型
7、抽象數(shù)據(jù)類型包含：數(shù)據(jù)對象、數(shù)據(jù)對象上的關(guān)系集合、以及數(shù)據(jù)對象的基本操作
抽象數(shù)據(jù)類型與已有的數(shù)據(jù)類型（如float、int）有什么區(qū)別？ ?? 二者無區(qū)別，只是float、int是已實(shí)現(xiàn)的類型
定義格式：ADT抽象數(shù)據(jù)類型名{
數(shù)據(jù)對象的定義：
數(shù)據(jù)關(guān)系的定義：
基本操作的定義：}
8、邏輯結(jié)構(gòu)是（4種2大類）
? ?? 2大類：線性和非線性結(jié)構(gòu)
? ?? 分為4種：線性結(jié)構(gòu)、集合、樹、圖
9、存儲結(jié)構(gòu)是（4種）優(yōu)缺點(diǎn)有哪些：順序存儲、鏈?zhǔn)酱鎯?、索引存儲、散列存?/p>
10、如何解決一個問題：先畫關(guān)系而后選存儲方式
11、棧是限制了插入刪除點(diǎn)的線性表，只是邏輯結(jié)構(gòu)，與存儲結(jié)構(gòu)無關(guān)
12、舉例說明，相同的邏輯結(jié)構(gòu)，不同的存儲方式在相同的操作下，其運(yùn)算效率不同
線性表的順序存儲和鏈?zhǔn)酱鎯Γ翰迦耄瑒h除操作
13、如何定義一個結(jié)構(gòu)是邏輯結(jié)構(gòu)還是物理結(jié)構(gòu)
當(dāng)一個結(jié)構(gòu)，如數(shù)組、鏈表、樹、圖，在邏輯結(jié)構(gòu)中只有一種定義，而在物理結(jié)構(gòu)中卻有兩種選擇，那么這個結(jié)構(gòu)就屬于邏輯結(jié)構(gòu)；
相反，當(dāng)此結(jié)構(gòu)在原有基礎(chǔ)上加上了某種限定，使得其在物理結(jié)構(gòu)中只有一種定義，那么這個結(jié)構(gòu)就屬于物理（存儲）結(jié)構(gòu)；
14、如何判斷數(shù)據(jù)結(jié)構(gòu)不同：
看如何定義，如果是名字不同：比如棧和隊(duì)列，邏輯結(jié)構(gòu)都是線性表，存儲結(jié)構(gòu)都可以是順序或者鏈表
如果是分類不同：比如線性表和二叉樹，邏輯結(jié)構(gòu)不同，但是都可以順序或者鏈?zhǔn)酱鎯?/p>
15、數(shù)據(jù)結(jié)構(gòu)的操作：
（1）建立數(shù)據(jù)結(jié)構(gòu)；（2）清除數(shù)據(jù)結(jié)構(gòu)；（3）插入數(shù)據(jù)元素；（4）刪除數(shù)據(jù)元素；（5）更新數(shù)據(jù)元素；
（6）查找數(shù)據(jù)元素；（7）按序重新排列；（8）判定某個數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達(dá)到最大允許的容量；
（9）統(tǒng)計(jì)數(shù)據(jù)元素的個數(shù)。
16、算法的基本概念（4個）：有窮性、確定性、可行性、輸入/輸出
17、算法的設(shè)計(jì)要求（4個）：正確性、可讀性、健壯性、效率與低存儲量需求
18、算法的度量：時間復(fù)雜度和空間復(fù)雜度
19、時間復(fù)雜度的分析方法：大O法和語句頻度法
20、語句的頻度：一個語句在該算法中被重復(fù)執(zhí)行的次數(shù)
21、大O法：它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和基本運(yùn)算的頻度f(n)的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度
22、語句頻度法：計(jì)算該語句重復(fù)執(zhí)行的次數(shù)
23、時間復(fù)雜度的定義：(不僅依賴于問題規(guī)模，還依賴于待輸入的數(shù)據(jù)性質(zhì))
24、分析程序的時間復(fù)雜性是有兩條原則：
加法規(guī)則：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法規(guī)則：T(n)=T1(n)+T2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))
25、常見的漸近時間復(fù)雜度：對數(shù)函數(shù)<冪函數(shù)<指數(shù)函數(shù)
O(1)<O()<O(
)<O(
)<O(
)<O(
)<O(
)<O(
)<O(
)
26、空間復(fù)雜度：即3個組成部分（P<personal>+I/O+add）
存放本身所用的指令和常數(shù)、輸入輸出占用的空間、信息的輔助空間
27、算法原地工作：是指算法所需輔助空間為常量，記作O(1)
28、時間復(fù)雜度計(jì)算方法：
1、循環(huán)主體中的變量參與循環(huán)條件的判斷
找出主體語句中與T(n)成正比的循環(huán)變量，將其帶入條件中進(jìn)行計(jì)算
2、循環(huán)主體中的變量與循環(huán)條件無關(guān)
遞歸程序：使用公式進(jìn)行遞推（數(shù)學(xué)歸納法或直接累計(jì)循環(huán)次數(shù)）
非遞歸程序：直接累計(jì)次數(shù)
遞歸：是直接或者間接調(diào)用自身的函數(shù)，當(dāng)操作有某種重復(fù)模式的數(shù)據(jù)結(jié)構(gòu)和問題時十分有效。
29、遞歸的例子
1、 1到n求和： s（n） = n + s（n-1）
2、 n的階乘： f（n） = n * f（n-1）
3、 快速排序： quicksort（a，low，high） => ?quicksort（a，low，pivot-1） ⊙ quicksort（a，pivot+1， high）
4、 樹的前序、中序、后續(xù)遍歷： preorder（T） = > ?read（T->data） preorder（T->leftChild） preorder（T->rightChild）
參考來自：遞歸程序的含義、實(shí)現(xiàn)機(jī)制以及復(fù)雜度計(jì)算 - 蒼穹逸影 - 博客園
30、王道拓展題：斐波那契數(shù)列算法的時間復(fù)雜度
斐波那契數(shù)列的定義：F(n+1)=F(n)+F(n-1)
遞歸：O()
非遞歸：O(n)
參考來自：斐波那契數(shù)列兩種算法的時間復(fù)雜度 - 在下雨的Tokyo - 梳理：博客園
全文知識點(diǎn)梳理參考：王道考研數(shù)據(jù)結(jié)構(gòu)參考書、趙海英數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)視頻
