1.什么是數(shù)據(jù)結(jié)構(gòu)?

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)包括4種

(1)集合：數(shù)據(jù)元素之間除了有相同的數(shù)據(jù)類型再?zèng)]有其他的關(guān)系

(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)一的關(guān)系 ——線性表、棧、隊(duì)列

(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)多的關(guān)系

(4)圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。

物理結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

2.解釋一下順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)

順序存儲(chǔ)結(jié)構(gòu)是用一段連續(xù)的存儲(chǔ)空間來存儲(chǔ)數(shù)據(jù)元素，可以進(jìn)行隨機(jī)訪問，訪問效率較高。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用任意的存儲(chǔ)空間來存儲(chǔ)數(shù)據(jù)元素，不可以進(jìn)行隨機(jī)訪問，訪問效率較低。

3.頭指針和頭結(jié)點(diǎn)的區(qū)別?

頭指針：是指向第一個(gè)節(jié)點(diǎn)存儲(chǔ)位置的指針，具有標(biāo)識(shí)作用，頭指針是鏈表的必要元素，無論鏈表是否為空，頭指針都存在。

頭結(jié)點(diǎn)：是放在第一個(gè)元素節(jié)點(diǎn)之前，便于在第一個(gè)元素節(jié)點(diǎn)之前進(jìn)行插入和刪除的操作，頭結(jié)點(diǎn)不是鏈表的必須元素，可有可無，頭結(jié)點(diǎn)的數(shù)據(jù)域也可以不存儲(chǔ)任何信息。

4.線性結(jié)構(gòu)的特點(diǎn)

(1)集合中必存在唯一的一個(gè)"第一個(gè)元素";

(2)集合中必存在唯一的一個(gè)"最后的元素";

(3)除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼";

(4)除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。

5.數(shù)組和鏈表的區(qū)別?

從邏輯結(jié)構(gòu)來看：數(shù)組的存儲(chǔ)長度是固定的，它不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況。鏈表能夠動(dòng)態(tài)分配存儲(chǔ)空間以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況，并且易于進(jìn)行插入和刪除操作。

從訪問方式來看：數(shù)組在內(nèi)存中是一片連續(xù)的存儲(chǔ)空間，可以通過數(shù)組下標(biāo)對(duì)數(shù)組進(jìn)行隨機(jī)訪問，訪問效率較高。鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)空間不是必須連續(xù)的，可以是任意的，訪問必須從前往后依次進(jìn)行，訪問效率較數(shù)組來說比較低。

如果從第i個(gè)位置插入多個(gè)元素，對(duì)于數(shù)組來說每一次插入都需要往后移動(dòng)元素，每一次的時(shí)間復(fù)雜度都是O(n)，而單鏈表來說只需要在第一次尋找i的位置時(shí)時(shí)間復(fù)雜度為O(n)，其余的插入和刪除操作時(shí)間復(fù)雜度均為O(1)，提高了插入和刪除的效率。

6.單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)的區(qū)別?

當(dāng)進(jìn)行插入和刪除操作時(shí)，順序存儲(chǔ)結(jié)構(gòu)每次都需要移動(dòng)元素，總的時(shí)間復(fù)雜度為O(n^2)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)確定i位置的指針后，其時(shí)間復(fù)雜度僅為O(1)。由于順序存儲(chǔ)結(jié)構(gòu)需要進(jìn)行預(yù)分配存儲(chǔ)空間，所以容易造成空間浪費(fèi)或者溢出。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不需要預(yù)分配存儲(chǔ)空間，元素個(gè)數(shù)不受限制。

7.棧和隊(duì)列的區(qū)別

隊(duì)列是允許在一段進(jìn)行插入另一端進(jìn)行刪除的線性表，對(duì)于進(jìn)入隊(duì)列的元素按“先進(jìn)先出”的規(guī)則處理，在表頭進(jìn)行刪除在表尾進(jìn)行插入。

棧是只能在表尾進(jìn)行插入和刪除操作的線性表。對(duì)于插入到棧的元素按“后進(jìn)先出”的規(guī)則處理，插入和刪除操作都在棧頂進(jìn)行。由于進(jìn)棧和出棧都是在棧頂進(jìn)行，所以要有一個(gè)size變量來記錄當(dāng)前棧的大小，當(dāng)進(jìn)棧時(shí)size不能超過數(shù)組長度，size+1，出棧時(shí)棧不為空，size-1。

8.各種查找方法(各方法是如何實(shí)現(xiàn)的要會(huì)用語言描述)

查找分為靜態(tài)查找表和動(dòng)態(tài)查找表;靜態(tài)查找表包括：順序查找、折半查找、分塊查找;動(dòng)態(tài)查找包括：二叉排序樹和平衡二叉樹。

(1)順序查找：把待查關(guān)鍵字key放入哨兵位置(i=0)，再從后往前依次把表中元素和key比較，如果返回值為0則查找失敗，表中沒有這個(gè)key值，如果返回值為元素的位置i(i!=0)則查找成功，設(shè)置哨兵的位置是為了加快執(zhí)行速度，時(shí)間復(fù)雜度為O(n)，其特點(diǎn)是：結(jié)構(gòu)簡單，對(duì)順序結(jié)構(gòu)和鏈?zhǔn)绞浇Y(jié)構(gòu)都適用，但查找效率太低。

(2)折半查找：要求查找表為順序存儲(chǔ)結(jié)構(gòu)并且有序，若關(guān)鍵字在表中則返回關(guān)鍵字的位置，若關(guān)鍵字不在表中時(shí)停止查找的典型標(biāo)志是：查找范圍的上界<=查找范圍的下界。

(3)分塊查找：先把查找表分為若干子表，要求每個(gè)子表的元素都要比后面的子表的元素小，也就是保證塊間是有序的(但是子表內(nèi)不一定有序)，把各子表中的最大關(guān)鍵字構(gòu)成一張索引表，表中還包含各子表的起始地址。特點(diǎn)是：塊間有序，塊內(nèi)無序，查找時(shí)塊間進(jìn)行索引查找，塊內(nèi)進(jìn)行順序查找。

(4)二叉排序樹：二叉排序樹的定義為：一棵空樹，或者是一棵具有如下特點(diǎn)的樹：如果該樹有左子樹，則其左子樹的所有節(jié)點(diǎn)值小于根的值;若該樹有右子樹，則其右子樹的所有節(jié)點(diǎn)值均大于根的值;其左右子樹也分別為二叉排序樹

(5)平衡二叉樹：平衡二叉樹又稱為AVL樹，它或者是一棵空樹或者具有如下特點(diǎn)：他的左子樹和右子樹的高度差的絕對(duì)值不能大于1，且他的左右子樹也都是平衡二叉樹。

如果再一個(gè)平衡二叉樹中插入一個(gè)節(jié)點(diǎn)可能造成失衡，這時(shí)就要進(jìn)行樹結(jié)構(gòu)的調(diào)整，即平衡旋轉(zhuǎn)。包括4中情況：在左子樹的左子樹上插入節(jié)點(diǎn)時(shí)向右進(jìn)行單向旋轉(zhuǎn);在右子樹的右子樹上插入節(jié)點(diǎn)時(shí)向左進(jìn)行單向旋轉(zhuǎn);在左子樹的右子樹插入節(jié)點(diǎn)時(shí)先向左旋轉(zhuǎn)再向右旋轉(zhuǎn);在右子樹的左子樹插入節(jié)點(diǎn)時(shí)先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)。

9.哈希表的概念、構(gòu)造方法、沖突的解決辦法?

哈希表又稱為散列表，是根據(jù)關(guān)鍵字碼的值直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，即它通過把關(guān)鍵碼的值映射到表中的一個(gè)位置以加快查找速度，其中映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

哈希函數(shù)的構(gòu)造方法包括：直接定址法，除留余數(shù)法，數(shù)字分析法，平方取中法，折疊法，隨機(jī)數(shù)法

(1)直接定址法：取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址，H(key)=a*key+b。

(2)除留余數(shù)法：取關(guān)鍵字對(duì)p取余的值作為散列地址，其中p

(3)數(shù)字分析法：當(dāng)關(guān)鍵字的位數(shù)大于地址的位數(shù)，對(duì)關(guān)鍵字的各位分布進(jìn)行分析，選出分布均勻的任意幾位作為散列的地址，適用于所有關(guān)鍵字都已知的情況。

(4)平方取中法：對(duì)關(guān)鍵字求平方，再取結(jié)果中的中間幾位作為散列地址。

(5)折疊法：將關(guān)鍵字分為位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址。適用于關(guān)鍵字位數(shù)較多，且關(guān)鍵字中每一位上數(shù)字分布大致均勻。

(6)隨機(jī)數(shù)法：選擇一個(gè)隨機(jī)函數(shù)，把關(guān)鍵字的隨機(jī)函數(shù)值作為散列地址。適合于關(guān)鍵字的長度不相同時(shí)。

哈希沖突的解決方法包括：開放定址法和拉鏈法，當(dāng)沖突發(fā)生時(shí)，使用某種探測技術(shù)形成一個(gè)探測序列，然后沿此序列逐個(gè)單單元查找，直到找到該關(guān)鍵字或者碰到一個(gè)開放的地址為止，探測到開放的地址表明該表中沒有此關(guān)鍵字，若要插入，則探測到開放地址時(shí)可將新節(jié)點(diǎn)插入該地址單元。其中開放定址法包括：線性探查法，二次探查法，雙重散列法

(1)線性探查法：基本思想，探查時(shí)從地址d開始，首先探查T[d],在探查T[d+1]…直到查到T[m-1]，此后循環(huán)到T[0],T[1]…直到探測到T[d-1]為止。

(2)二次探查法：基本思想，探查時(shí)從地址d開始，首先探查T[d],再探查T[d+12],T[d+22]…等，直到探查到有空余地址或者探查到T[d-1]為止，缺點(diǎn)是無法探查到整個(gè)散列空間。

(3)雙重散列法：基本思想，使用兩個(gè)散列函數(shù)來確定地址，探查時(shí)從地址d開始，首先探查T[d],再探查T[d+h1(d)],T[d+2*h1(d)]…

鏈接法：將所有關(guān)鍵字為同義詞的節(jié)點(diǎn)鏈接在同一個(gè)單鏈表中，若選定的散列表長度為m，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組，凡是散列地址為i的節(jié)點(diǎn)均插入到頭指針為i的單鏈表中。

10.各種排序算法(各方法如何實(shí)現(xiàn)要會(huì)用語言描述)

內(nèi)部排序包括：插入排序、選擇排序、交換排序、歸并排序、基數(shù)排序。其中插入排序包括：直接插入排序、折半插入排序、希爾排序;選擇排序包括：簡單選擇排序，堆排序;交換排序包括：冒泡排序、快速排序。

(1)直接插入排序(穩(wěn)定)：基本思想為：將序列分為有序部分和無序部分，從無序部分依次選擇元素與有序部分比較找到合適的位置，將原來的元素往后移，將元素插入到相應(yīng)位置上。時(shí)間復(fù)雜度為：O(n^2),空間復(fù)雜度為O(1)

(2)折半插入排序(穩(wěn)定)：基本思想為：設(shè)置三個(gè)變量low high mid，令mid=(low+high)/2,若a[mid]>key,則令high=mid-1,否則令low=mid+1,直到low>high時(shí)停止循環(huán)，對(duì)序列中的每個(gè)元素做以上處理，找到合適位置將其他元素后移進(jìn)行插入。比較次數(shù)為O(nlog2n),但是因?yàn)橐笠疲虼藭r(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)。 優(yōu)點(diǎn)是：比較次數(shù)大大減少。

(3)希爾排序(不穩(wěn)定)：基本思想為：先將序列分為若干個(gè)子序列，對(duì)各子序列進(jìn)行直接插入排序，等到序列基本有序時(shí)再對(duì)整個(gè)序列進(jìn)行一次直接插入排序。優(yōu)點(diǎn)是：讓關(guān)鍵字值小的元素能夠很快移動(dòng)到前面，且序列基本有序時(shí)進(jìn)行直接插入排序時(shí)間效率會(huì)提升很多，空間復(fù)雜度為O(1)。

(4)簡單選擇排序(不穩(wěn)定)：基本思想為：將序列分為2部分，每經(jīng)過一趟就在無序部分找到一個(gè)最小值然后與無序部分的第一個(gè)元素交換位置。優(yōu)點(diǎn)是：實(shí)現(xiàn)簡單，缺點(diǎn)是：每一趟只能確定一個(gè)元素的位置，時(shí)間效率低。時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(1)。

(5)堆排序(不穩(wěn)定)：設(shè)有一個(gè)任意序列，k1,k2,…,kn，當(dāng)滿足下面特點(diǎn)時(shí)稱之為堆：讓此序列排列成完全二叉樹，該樹具有以下特點(diǎn)，該樹中任意節(jié)點(diǎn)均大于或小于其左右孩子，此樹的根節(jié)點(diǎn)為最大值或者最小值。優(yōu)點(diǎn)是：對(duì)大文件效率明顯提高，但對(duì)小文件效率不明顯。時(shí)間復(fù)雜度為O(nlog2n),空間復(fù)雜度為O(1)。

(6)冒泡排序(穩(wěn)定)：基本思路為：每一趟都將元素進(jìn)行兩兩比較，并且按照“前小后大”的規(guī)則進(jìn)行交換。優(yōu)點(diǎn)是：每一趟不僅能找到一個(gè)最大的元素放到序列后面，而且還把其他元素理順，如果下一趟排序沒有發(fā)生交換則可以提前結(jié)束排序。時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)。

(7)快速排序(不穩(wěn)定)：基本思路為：在序列中任意選擇一個(gè)元素作為中心，比它大的元素一律向后移動(dòng)，比它小的元素一律向前移動(dòng)，形成左右兩個(gè)子序列，再把子序列按上述操作進(jìn)行調(diào)整，直到所有的子序列中都只有一個(gè)元素時(shí)序列即為有序。優(yōu)點(diǎn)是：每一趟不僅能確定一個(gè)元素，時(shí)間效率較高。時(shí)間復(fù)雜度為O(nlog2n),空間復(fù)雜度為O(log2n).

(8)歸并排序(穩(wěn)定)：基本思想為：把兩個(gè)或者兩個(gè)以上的有序表合并成一個(gè)新的有序表。時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度和待排序的元素個(gè)數(shù)相同。

(9)基數(shù)排序：時(shí)間復(fù)雜度為：對(duì)于n個(gè)記錄進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+rd)),其中每一趟分配的時(shí)間復(fù)雜度為O(n),回收的時(shí)間復(fù)雜度為O(rd)。

“前小后大”的規(guī)則進(jìn)行交換。優(yōu)點(diǎn)是：每一趟不僅能找到一個(gè)最大的元素放到序列后面，而且還把其他元素理順，如果下一趟排序沒有發(fā)生交換則可以提前結(jié)束排序。時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)。

(7)快速排序(不穩(wěn)定)：基本思路為：在序列中任意選擇一個(gè)元素作為中心，比它大的元素一律向后移動(dòng)，比它小的元素一律向前移動(dòng)，形成左右兩個(gè)子序列，再把子序列按上述操作進(jìn)行調(diào)整，直到所有的子序列中都只有一個(gè)元素時(shí)序列即為有序。優(yōu)點(diǎn)是：每一趟不僅能確定一個(gè)元素，時(shí)間效率較高。時(shí)間復(fù)雜度為O(nlog2n),空間復(fù)雜度為O(log2n).

(8)歸并排序(穩(wěn)定)：基本思想為：把兩個(gè)或者兩個(gè)以上的有序表合并成一個(gè)新的有序表。時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度和待排序的元素個(gè)數(shù)相同。

(9)基數(shù)排序：時(shí)間復(fù)雜度為：對(duì)于n個(gè)記錄進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+rd)),其中每一趟分配的時(shí)間復(fù)雜度為O(n),回收的時(shí)間復(fù)雜度為O(rd)。