0.本篇問題：?
- 數據、數據元素、數據對象、數據項之間的基本關系？
- ADT是什么？
- 數據結構的三要素？
- 數據的邏輯結構有哪些？
- 數據的存儲結構有哪些？
- 算法的五個特征？
- O(1)? O(logn) ?O(n^n)? O(n) ?O(n^2)? ? O(n^3) ?O(2^n) ?O(n!) ?O(nlogn) 大小關系？
★ 錯題&典型題
1. 可以用（ ）定義一個完整的數據結構
A.數據元素????????B.數據對象????????C.數據關系????????D.抽象數據類型
2.以下屬于邏輯結構的是（ ）
A.順序表????????B.哈希表????????C.有序表????????D.單鏈表
3.以下關于數據結構的說法中，正確的是（ ）
A.數據結構的邏輯結構獨立于其存儲結構
B.數據結構的存儲結構獨立于其邏輯結構
C.數據的邏輯結構唯一決定其存儲結構
D.數據結構僅由其邏輯結構和存儲結構決定
4.一個算法應該是（ ）
A.程序????????B.問題求解步驟的描述????????C.要滿足五個基本特性????????D. A和C
5.某算法的時間復雜度為O(n^2),則表示該算法的（ ）
A.問題規模是n^2?????????????????? B.執行時間等于n^2????????
C.執行時間與n^2成正比????????D.問題規模與n^2成正比
6.【2017】?求下面程序時間復雜度
int func(int n) {int i = 0, sum = 0;while (sum < n) sum += ++i;return i; }
7.【2019】求下面程序時間復雜度?
x = 0; while (n >= (x + 1) * (x + 1))x = x + 1;
8.【2022】求下面程序時間復雜度
int sum = 0; for (int i = 1; i < n; i *= 2)for (int j = 0; j < i; j++)sum++;
一、數據、數據元素、數據對象、數據項、數據結構、數據類型
1.1 概念（P1）
- 數據結構是相互之間存在一種或多種特定關系的數據元素的集合；它包括三方面的內容：邏輯結構，存儲結構，數據的運算。
- 數據對象是具有相同性質的數據元素的集合，是數據的一個子集；
- 數據是信息的載體，是描述客觀事物屬性的數、字符及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合；
- 數據元素是數據的基本單位，通常作為一個整體進行考慮和處理；
- 一個數據元素有若干數據項組成，數據項是構成數據元素的不可分割的最小單位。
- 數據類型：原子類型、結構類型、抽象數據類型（ADT）：描述了數據的邏輯結構和抽象運算，通常用（數據對象，數據關系，基本操作）這樣的三元組來表示，eg.棧、隊列，樹...（ADT和數據密切相關，但不完全相同）
1.2? 我的理解
- 數據項是最小的，數據是最大的；
- 數據項構成數據元素；
- 數據元素構成數據對象；
- 所有數據對象的總和是數據。
-
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。(數據元素+關系) - 數據對象是具有相同性質的數據元素的集合，是數據的一個子集。(數據元素)
- 世界上所有的信息、符號的總和是數據。
- 這些數據有所有大學學生數據（數據對象），所有餐廳顧客數據（數據對象），XX大學學生數據（數據對象），所有動物的XX數據（數據對象）...
- XX大學同學ABCD...數據（數據元素），...
- 班級學生有自己的學號（數據項），姓名（數據項），年齡（數據項）...
- 數據結構是帶存儲關系的同學ABCD...的數據（通過它你不僅知道這些數據，還知道它們之間的關系是怎樣的，如何存儲的）
- 數據對象，數據元素，數據項根據研究內容的不同都是相對的，這項研究中的數據元素可能是下一項研究中的數據對象。
二、數據結構的三要素
2.1 數據結構三要素
邏輯結構，存儲結構，運算????????知存儲就知邏輯，知邏輯不一定知存儲！
????????2.2.1 邏輯結構
? ? ? ? ? ? ? ? 四類基本結構：線性結構、集合(同屬一個集合無其他關系)、樹形、圖狀結構(網狀結構)。
????????2.2.2 存儲結構
? ? ? ? ? ? ? ? ①順序存儲
? ? ? ? ? ? ? ? ②鏈式存儲
? ? ? ? ? ? ? ? ③索引存儲（索引表中每項是索引項（關鍵字，地址）） 優點：檢索快，缺點：索引表額外占據存儲空間；增刪要修改索引表，時間花費多。
? ? ? ? ? ? ? ? ④散列存儲（哈希存儲）
? ? ? ? 2.2.3 運算
? ? ? ? ? ? ? ? 施加在數據上的運算，包括運算的定義和實現。運算的定義是針對邏輯結構的，指出運算的功能；運算的實現是針對存儲結構的，指出運算的具體操作步驟。
三、算法?
3.1 算法的概念和特征
????????算法是對特定問題求解步驟的一種描述，他是指令的有限數列，其中的每條指令表示一個或多個操作。
? ? ? ? 特征：①有窮性 ②確定性 ③可行性 ④輸入>=0 ⑤輸出>=1
3.2 時間復雜度&空間復雜度?
? ? ? ? 是問題規模n的函數。
Q:算法問題規模永遠是A:不是。在算法中，問題規模不一定是n。
n通常用來表示輸入規模，比如在一個排序算法中，n可能代表要排序的元素個數。但問題規模也可以用其他方式來衡量。?
例如，在圖算法中，除了用頂點數量n來表示問題規模，還可能會涉及邊的數量m。對于一些復雜的算法，如計算兩個圖的同構問題，問題規模可能是由多個因素共同決定的，包括頂點數、邊數、頂點和邊的屬性等復雜因素。
在矩陣運算相關的算法中，矩陣的行數和列數都可能影響問題規模，而不是簡單地用一個n來表示。
? ? ? ? 常見的漸進時間復雜度比較：
? ? ? ? O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
答案：1.D????????2.C????????3.A? ? ? ? 4.B? ? ? ? 5.C? ? ? ? 6.O(n^(1/2))????????7.O(n^(1/2))????????8.O(n)
-THE END-
