1、數(shù)據(jù)（Data）

---- 是對信息的一種符號表示。在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。

2、數(shù)據(jù)元素（Data Element）

---- 是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。

? ? ? 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。

3、數(shù)據(jù)對象（Data Object）

---- 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

4、數(shù)據(jù)結(jié)構(gòu)（Data Structure）

---- 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

? ? ? 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：

-- 1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合（一種類型）外，別無其它關(guān)系。各個數(shù)據(jù)元素是“平等”的。

-- 2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。

-- 3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。

-- 4）圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。（數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的存儲映像稱為數(shù)據(jù)的存儲結(jié)構(gòu)。）

數(shù)據(jù)元素的存儲結(jié)構(gòu)形式有四種：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)。

順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。

鏈?zhǔn)酱鎯Y(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。

5、算法：是對特定問題求解步驟的一種描述。

---- 算法是指令的有限序列，其中每一條指令表示一個或多個操作。

算法具有以下五個特性：

-- 1）有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。

-- 2）確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。

-- 3）可行性：一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

-- 4）輸入：一個算法有0個或多個輸入，這些輸入取自于某個特定的對象集合。

-- 5）輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

---- 算法設(shè)計的要求：評價一個好的算法有以下幾個標(biāo)準(zhǔn)：

-- 1）正確性（Correctness）算法應(yīng)滿足具體問題的需求。

-- 2）可讀性（Readability）算法應(yīng)該好讀，以有利于閱讀者對程序的理解。

-- 3）健壯性（Robustness）算法應(yīng)具有容錯處理功能。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。

-- 4）時間效率高和存儲量低。時間效率指的是算法的執(zhí)行時間，執(zhí)行時間長的效率低。

存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間，主要指算法運行程序時所占用的內(nèi)存或外部硬盤存儲空間。

---- 算法效率的度量方法：事后統(tǒng)計方法和事前分析估算方法

-- 事后統(tǒng)計方法：這種方法主要是通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機(jī)計時器對不同算法編制的程序的運行時間進(jìn)行比較，從而

確定算法效率的高低。（依賴計算機(jī)硬件和軟件等環(huán)境因素）

-- 事前分析估算方法：在計算機(jī)程序編制前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算。

---- 函數(shù)的漸近增長：給定兩個函數(shù)f(n)和g(n)，如果存在一個整數(shù)N，使得對于所有的n>N,f(n)總是比g(n)大，那么，我們說f(n)的增長

漸近快于g(n)。

---- 算法時間復(fù)雜度：在進(jìn)行算法分析時，語句總的執(zhí)行次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T（n）隨n的變化情況并確定T(n)

的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間量度，記作：T（n）= O（f（n））。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長

率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。

用大寫O()來體現(xiàn)算法時間復(fù)雜度的記法，稱之為大O記法。一般情況下，隨著n的增大，T(n)增長最慢的算法為最優(yōu)算法。

---- 推導(dǎo)大O階方法：

-- 1）用常數(shù)1取代運行時間中的所有加法常數(shù)。

-- 2）在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

-- 3）如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。得到的結(jié)果就是大O階。

---- 常用的時間復(fù)雜度所耗費的時間從小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

O(1): 常數(shù)階，O(logn): 對數(shù)階，O(n): 線性階，O(n^2): 平方階等。

6、描述頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）的區(qū)別？

答：頭指針是指向鏈表中第一個結(jié)點的指針。

首元結(jié)點是指鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點。頭結(jié)點是在首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點不存儲數(shù)據(jù)元素，其指針域指向首元

結(jié)點，其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及首元結(jié)點的操作進(jìn)行統(tǒng)一處理。