1. 數據結構是一門研究非數值計算程序設計中的操作對象 以及這些對象之間的關系和操作的學科

2. 研究包括邏輯結構和存儲結構

? ?1) 邏輯結構（從具體問題抽象出來的數學模型）分為

? ? ? ? ?集合結構 線性結構 樹結構 圖結構（分類依據是元素之間的關系不同）

? ?2)存儲結構（也稱物理結構 邏輯結構在計算機的存儲表示）分為

? ? ? ? ?順序存儲結構 鏈式存儲結構

3. 抽象數據類型是由用戶定義 表示應用問題的數學模型 以及定義在這個模型一組操作的總稱 包括數據對象 數據對象上關系的集合 數據對象基本操作的集合

4. 算法（為了解決某類問題而規定的一組有限長的操作序列）

? ? ?算法的五個特性：有窮性 確定性 可行性 輸入和輸出

? ? ?算法優劣的評價：正確性 可讀性 健壯性（魯棒性） 高效性

5. 算法分析的兩個主要方面

? ? ?頻度：一條語句重復執行次數；

? ? ?規模：算法求解問題的輸入量；

　　算法時間復雜度（即算法的運算時間 表示方法T(n)=O(f(n))）

? ? ? ? ? 常見的時間復雜度排列順序　　

　　　 ?常數階 對數階 線性階 線性對數階 平方階 立方階 k次方階

　　算法空間復雜度（表示方法S（n）=O（f（n）））

6.一些術語

數據：用客觀事物的符號表示 是所能輸入到計算機中并被計算機程序處理的符號的總稱

數據元素：是數據的基本單位在計算機中通常作為一個整體處理和考慮

數據項：是組成數據的 有獨立含義的 不可分割的最小單位

數據對象：是性質相同的數據元素的集合，是數據的子集

數據結構：是相互之間存在一種或多種特定關系的數據關系的集合

數據類型：一個值的集合和定義在這個值集上的一組操作的總稱

附幾道教科書上的習題：

1.與數據元素本身的形式、內容、相對位置、個數無關的是數據的（?? ）。

A．存儲結構?????????????? B．存儲實現

C．邏輯結構?? ????????????D．運算實現

?

?

2.以下說法正確的是（?? ）。解釋：數據元素是數據的基本單位，數據項是數據的最小單位，數據結構是帶有結構的各數據元素的集合

A．數據元素是數據的最小單位

B．數據項是數據的基本單位

C．數據結構是帶有結構的各數據項的集合

D．一些表面上很不相同的數據可以有相同的邏輯結構

?

3.（1）x=90; y=100;?

while(y>0)

if(x>100)

?{x=x-10;y--;}

else x++;

答案：O(1)

解釋：程序的執行次數為常數階。

?

（2）for (i=0; i<n; i++)

for (j=0; j<m; j++)

a[i][j]=0;

答案：O(m*n)

解釋：語句a[i][j]=0;的執行次數為m*n。

?

（3）s=0;

?? ??for i=0; i<n; i++)

for(j=0; j<n; j++)

? ???????s+=B[i][j];

sum=s;

答案：O(n²)

解釋：語句s+=B[i][j];的執行次數為n²。

?

（4）i=1;

? ???while(i<=n)

??????? i=i*3;

答案：O(log₃n)

解釋：語句i=i*3;的執行次數為 log₃n。

?

（5）x=0;

for(i=1; i<n; i++)

?? for (j=1; j<=n-i; j++)

x++;

答案：O(n²)

解釋：語句x++;的執行次數為n-1+n-2+……＋1= n(n-1)/2。

?

（6）x=n; //n>1

y=0;

while(x≥(y+1)* (y+1))

????y++;

答案：O（x^(1/2)）

解釋：語句y++;的執行次數為 x^(1/2)。

?

轉載于:https://www.cnblogs.com/lnzhangsong/p/5088937.html

總結

以上是生活随笔為你收集整理的有关数据结构基础知识(数据结构 严蔚敏版)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。