第一章 概 論
一. 基本要求重點、難點
對本章的學習，主要是要熟悉各名詞和術語的含義；掌握各種基本概念，特別是數據結構的邏輯結構、存儲結構、數據運算3方面的內容及這3方面的相互關系；熟悉C語言的書寫規范，理解算法的5個要素的確切含義，即有窮性、確定性、可行性及有輸入、有輸出，從而掌握計算語句頻度和估計算法時間復雜度的方法等，為學習數據結構打下基礎。
二. 考核目標和考核要求
要求達到識記層次的有：數據、數據元素、數據項、數據結構等的基本概念；數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系；數據結構的兩大邏輯結構和四種常用的存儲表示方法；數據結構在各種軟件系統中所起的作用；選擇合適的數據結構是解決應用問題的關鍵步驟。
要求達到理解層次有：算法、算法的時間復雜度和空間復雜度、最壞情況下的時間復雜度和平均時間復雜度等概念；算法的時間復雜度不僅僅依賴於問題的規模，也取決於輸入實例的初始狀態；算法描述和算法分析的方法，對於一般算法能力分析出時間復雜度。
要求達到簡單應用的有：時間復雜度的算法
三. 練習題
1. 單項選擇題
1.1在數據結構中，從邏輯上可以把數據結構分為（ B ）
A） 緊湊結構和非緊湊結構
B） 線性結構和非線性結構
C） 內部結構和外部結構
D） 動態結構和靜態結構
數據結構中從邏輯上可以把數據結構分為線性結構和非線性結構
1.2線性表的順序存儲結構是一種（ C ）的存儲結構
A） 順序存取
B） 索引存取
C） 隨機存取
D） 散列存取
線性表的順序存儲結構是一種隨機存取的存儲結構，線性表的鏈式存儲結構是一種順序存取的存儲結構。
1.3邏輯關系是指數據元素的（ A ）
A） 關聯
B） 存儲方式
C） 結構
D） 數據項
1.4下列時間復雜度中最壞的是（ D ）
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.5下列時間復雜度最好的是（ A ）
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.6下列算法是時間復雜度是（ D ）
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=i+j;
A） O（1）
B） O（n）
C） O（log2n）
D） O（n2）
1.7算法分析的兩個主要方面是（ D ）
A） 正確性和簡明性
B） 數據復雜性和程序復雜性
C） 可讀性和可維護性
D） 時間復雜性和空間復雜性
1.8線性表若采用鏈式存儲結構存儲時，要求內存中可用存儲單元地址（ A ）
A） 不一定連續的
B） 部分地址必須是連續的
C） 必須是連續的
D） 一定是不連續的
1.9算法指的是（ D ）
A） 計算機程序
B） 解決問題的計算方法
C） 排序算法
D） 解決問題的有限運算序列
1.10數據的基本單位是（ B ）
A） 文件
B） 數據元素
C） 符號
D） 關鍵字
2. 填空題
2.1數據結構一般包括[邏輯結構]、存儲結構和數據運算三個方面的內容。
2.2從數據結構S中找出滿足條件的結點在S中的位置的運算是[查找]
2.3從數據結構S中讀出結構中指定位置上的內容的運算是[讀取]
2.4從數據結構S中的某指定位置上增加一個結點的運算是[插入]
2.5從數據結構S中撤消結構中指定位置上結點的運算是[刪除]
2.6從數據結構S中修改結構中某指定結點內容的運算是[更新]
2.7數據的存儲結構（物理結構）可以用順序存儲、鏈式存儲、[索引存儲]及散列存儲等四種存儲方法表示。
2.8選用算法除了首先考慮“正確性”外，主要考慮[執行算法所需要的時間]、執行算法所需要的存儲空間、算法易於理解，易於編程，易於調試
2.9數據結構是研究數據的物理結構和[邏輯運算]以及它們之間的相互關系，並對這種結構定義相應的運算
2.10數據的邏輯結構是從邏輯關系上描述數據，它與數據的[存儲結構]無關，是獨立於計算機的。
3. 簡答題
3.1簡述數據與數據元素的關系與區別
答：凡是能被計算機存儲、加工的對象統稱為數據，數據是一個集合。數據元素是數據的基本單位，是數據的一個元素。數據元素與數據之間的關系是元素與集合之間的關系。
3.2簡述數據、數據元素、數據類型、數據結構、存儲結構、線性結構、非線性結構的概念
答：數據：數據是信息的載體，它能夠被計算機識別、存儲和加工處理
數據元素：是數據的基本單位。有時一個數據元素包含幾個數據項
數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱
數據結構：指的是數據之間的邏輯關系也稱數據的邏輯結構。它包括線性結構和非線性結構兩大類。
存儲結構：數據元素及其關系在計算機存儲器內的表示，稱為數據的存儲結構。
線性結構：如果結構非空，則有且僅有一個開始結點和一個終端結點，並且所有的結點都最多只有一個直接前驅和一個直接後繼
非線性結構：該結構的邏輯特征是一個結點可能有多個直接前驅和直接後繼
3.3簡述順序存儲結構與鏈式存儲結構在表示數據元素之間關系上的主要區別
答：順序存儲結構是將各數據元素的存儲位置按其之間的邏輯關系存放在一塊連續的存儲空間內，由數據元素的存儲位置體現數據元素之間的邏輯關系。鏈式存儲結構各數據元素不一定是存儲在連續的一塊存儲空間內，數據元素之間的邏輯關系與存儲位置沒有一一對應的關系，數據元素之間的邏輯關系，是依靠附加在存儲數據元素的結點中的指針表示。
3.4通常從哪幾個方面評價算法的質量
答：
a.算法必須是正確的
b.執行算法所耗費的時間
c.執行算法所耗費的空間，其中主要考慮輔助存儲空間
d.算法應易於理解、易於編碼、易於調試等
4. 應用題
4.1求下述算法的時間復雜度
for(i=1;i<=n;i++)
{
y=y+1;
for(j=1;j<=2*n;j++)
x=x+1;
}
答：其中語句y=y+1的頻度是n-1，語句x=x+1的頻度是（n-1）（2n+1）。所以該程序的算法時間復雜度是：T（n）=O（（n-1）（2n+1））=O（n2）
4.2求下述算法的時間復雜度
x=1;
sum=0;
for(i=1;i<=n;i++)
{
x=x*i;
sum=sum+x;
}
答：由於嵌套最深的語句的頻度為n，所以其算法的時間復雜度為O（n）。
