1.什麽是數據結構？
數據結構是計算機存儲和組織數據的方式。數據結構是指相互之間具有壹種或多種特定關系的數據元素的集合。結構包括邏輯結構和物理結構。
數據的邏輯結構包括四種類型。
(1)集合:數據元素之間除了數據類型相同之外，沒有其他關系。
(2)線性結構:數據元素——線性表、棧、隊列之間是壹壹對應的關系。
(3)樹形結構:數據元素之間是壹對多的關系。
(4)圖形結構:數據元素之間是多對多的關系。
物理結構包括順序存儲結構和鏈式存儲結構。
第二，解釋順序存儲和鏈式存儲。
順序存儲結構使用連續的存儲空間來存儲數據元素，可以隨機存取，存取效率高。鏈式存儲結構使用任意存儲空間存儲數據元素，不允許隨機訪問，因此訪問效率較低。
三、頭指針和頭節點的區別？
頭指針:指向第壹個節點的存儲位置的指針，具有標識的作用。頭指針是鏈表的必要元素，無論鏈表是否為空，它都存在。
頭節點:放在第壹個元素節點之前，方便在第壹個元素節點之前插入和刪除。頭節點不是鏈表的必要元素，是可選的。頭節點的數據字段可能不存儲任何信息。
第四，線性結構的特點
(1)集合中必須有唯壹的“首元素”；
(2)集合中必須只有壹個“最後元素”；
(3)除了最後壹個元素，其他所有數據元素都有唯壹的“繼承者”；
(4)除了第壹個元素，其他所有數據元素都有唯壹的“前驅”。
5.數組和鏈表有什麽區別？
從邏輯結構上看，數組的存儲長度是固定的，所以不能適應數據的動態增減。鏈表可以動態分配存儲空間以適應數據的動態增減，插入和刪除都很容易。
從訪問方式上看，數組在內存中是壹個連續的存儲空間，可以通過數組下標隨機訪問數組，訪問效率高。鏈表是壹種鏈式存儲結構，存儲空間不壹定是連續的，可以是任意的。存取必須從前到後進行，存取效率低於數組。
如果從第I個位置插入多個元素，對於數組來說，每次插入都需要將元素後移，每次插入的時間復雜度為O(n)，而對於單鏈表來說，只有第壹次找到I的位置時時間復雜度為O(n)，其他插入和刪除操作的時間復雜度為O(1)，提高了插入和刪除的效率。
6.單鏈表結構和順序存儲結構有什麽區別？
在插入和刪除時，順序存儲結構每次都需要移動元素，總時間復雜度為O (n 2)，而鏈式存儲結構在確定I位置的指針後只需要O(1)。因為順序存儲結構需要預先分配存儲空間，容易造成空間浪費或溢出。鏈式存儲結構不需要預先分配存儲空間，元素數量不受限制。
七、堆棧和隊列的區別
Queue是壹個線性表，可以在壹段插入，在另壹端刪除。進入隊列的元素根據“先進先出”規則處理，在頭部刪除，在尾部插入。
Stack是壹個線性表，只能在頁腳插入和刪除。附加到廣播到堆棧的元素數據，“LIFO”規則處理、插入和刪除操作都在堆棧頂部執行。
第壹，因為棧入口和棧出口都是在棧頂進行的，所以應該有壹個大小變量。
記錄當前堆棧的大小。進入堆棧時，大小不能超過數組的長度。
Size+1，彈出時堆棧不為空，size-1。
八、介紹字符串匹配算法:
樸素匹配算法和KMP算法
1.BF算法(BruteForce)
目標字符串T(要匹配的字符串)
模式字符串p(短字符串)
①比較T的第壹個字符和s的第壹個字符，如果相等，繼續t-2VSp-2，如果相等，繼續t-3VSp？
②不等式為t-1VSp-2，t-2VSp-3。
2.KMP算法:從主串中快速找到子串。
①上下子串的前綴匹配
②找到* * *(取最長且小於比較的上下串長度)前的後綴。
(3)將後面的P子串前綴移到後綴位置。
蠻力算法在模式串中有很多字符，在主串中有幾個連續的字符，但是當最後壹個字符不相等時，主串的比較位置需要回退。KMP算法在上述情況下，主字符串位置不需要被返回，這樣可以大大提高效率。
9.深度優先搜索和廣度優先搜索是如何實現的？
深度優先搜索:(1)訪問起點v0。
(2)如果v0的第壹個鄰點沒有被訪問過，則深度遍歷鄰點；
(3)如果已經訪問了v0的第壹個相鄰點，則訪問它的第二個相鄰點進行深度遍歷；重復上述步驟，直到訪問完所有節點。
廣度優先搜索:(1)訪問起點v0。
(2)依次遍歷v0的所有未訪問過的相鄰點。
(3)依次訪問下壹層未訪問過的相鄰點；重復以上步驟，直到所有頂點都被訪問過。
X.如何構造霍夫曼樹？
求w的最小和，再求w的最小和；左小右大；施工結束後，左0右1
XI。最小生成樹
最小生成樹是尋找能連接所有節點的最小邊，最短路徑是
需要從壹個節點到其余節點的最短路徑。
最小鹽樹:
在給定的無向圖G=(V，e)，(U，V)表示連接頂點U和頂點V(即)的邊，w(u，V)表示這條邊的權重。如果有壹個子集(即非循環圖)其中T是e，所以w(T)是最小值，那麽這個T是g的最小生成樹。
w(t)=w(u，u)
最小生成樹實際上是最小(u，u)et。
prim (PRIM)算法的基本思想是:將頂點設置到其他點權重最小的邊上，添加壹個新的頂點集，然後尋找邊…直到遍歷所有點。
從連通網絡N={V，E}中的壹個頂點u0開始，選擇與之關聯的權重最小的邊，將其頂點添加到頂點集合S中，然後，從所有頂點中選擇權重最小的邊，其中壹個頂點在S集合中，另壹個頂點不在S集合中，將對應的頂點添加到S集合中，直到所有頂點都添加到S集合中。
kruskal算法的基本思想是:依次選擇最小的邊，這樣就不存在循環，所有點的遍歷結束。
假設有壹個有N個頂點的連通網絡，N={V，E]。在初始測試中，建立了只有n個頂點且沒有邊的不連通圖T。T中的每個頂點被視為壹個連通分支。如果從邊集合E中選擇具有最小權重的邊，並且該邊的兩個端點不在連通分支中，則將該邊添加到T中，否則，將選擇具有最小權重的新邊，直到所有頂點都在該邊中。
十二、最短路徑算法
Dijkstra算法的時間復雜度為O(n~2)
Fly od時間復雜度為O(n ^ 3)，空間復雜度為O(n ^ 2)；
最短路徑:用於計算從壹個節點到所有其他節點的最短路徑。主要特征是從起點向外擴展，直到終點。
Dij astra算法
經典的單源最短路徑算法主要基於其動態規劃思想。
弗洛伊德算法
尋找任意頂點間最短路徑的經典方法是貪心法。
十三、介紹拓撲排序以及如何實現？
拓撲排序的步驟:
(1)在有向圖中任意選擇壹個沒有前任的節點輸出。
(2)從圖中刪除節點和與之相連的邊。
(3)重復上述步驟，直到輸出所有頂點或者當前圖中不存在沒有前任的頂點，這意味著該圖是循環圖，因此可以通過拓撲排序來判斷壹個圖是否有循環。
十四。簡述各種搜索方法。
搜索分為靜態查找表和動態查找表。
靜態查找表包括:順序查找、對折查找和塊查找；
動態搜索包括二叉排序樹和平衡二叉樹。
(1)順序查找:將待查找的鑰匙放入崗哨位置(i=0)，然後將表格中的元素從後向前依次與鑰匙進行比較。如果返回值為0，則搜索失敗，並且表中沒有這樣的鍵值。如果返回值是元素的位置i(il=0)，則搜索成功。設置崗哨位置是為了加快執行速度，其時間復雜度為O(n)。
(2)對折查找:要求查找表為順序存儲結構，有序。如果關鍵字在表中，則返回關鍵字的位置。如果關鍵字不在表中，停止搜索的典型標誌是:搜索範圍的上限
(3)分塊搜索:首先將查找表分成若幹個子表，要求每個子表的元素小於下面子表的元素，即保證塊是有序的(但不壹定在子表中)，每個子表中最大的關鍵字組成壹個索引表，其中也包含每個子表的起始地址。特點是:塊間有序，塊內無序，塊間索引搜索，塊內順序搜索。
(4)二叉排序樹:二叉排序樹定義為空樹或具有以下特征的樹:如果樹有左子樹，則其左子樹的所有節點值都小於根值；如果樹有右子樹，右子樹的所有節點值都大於根值；它的左右子樹也是二進制排序樹。
(5)平衡二叉樹:平衡二叉樹又稱AVL樹，要麽是空樹，要麽具有以下特征:他的左子樹和右子樹的高度差的絕對值不能大於1，他的左右子樹也是平衡二叉樹。
如果在另壹棵平衡二叉樹中插入壹個節點可能會造成不平衡，那麽就要調整樹的結構，也就是平衡旋轉。包括4中情況:在左子樹的左子樹中插入節點時向右單向旋轉；將節點插入右子樹的右子樹時，向壹個方向向左旋轉；左子樹的右子樹插入壹個節點時，先向左旋轉，再向右旋轉；將節點插入到右子樹的左子樹時，先向右旋轉，再向左旋轉。
十五、各種排序算法簡介(1)
內部排序包括:插入排序、選擇排序、交換排序、歸並排序和基數排序。
其中，插入排序包括:直接插入排序、半插入排序和hill排序；
選擇排序包括:簡單選擇排序和堆排序；交換排序包括冒泡排序和快速排序。
(1)直接插入排序(穩定):基本思想是:將序列分為有序部分和無序部分，依次從無序部分中選取元素並與有序部分進行比較，找到合適的位置，將原來的元素後移，將元素插入相應的位置。時間復雜度為O(n~2)，空間復雜度為O(1)。
(2)半插入排序(穩定):基本思想是:設置三個變量，低高mid，和make
Mid=(低+高)/2，如果a[mid]>；鍵，則讓高=mid-1，否則讓低=mid+1直到低>；高時停止循環，對序列中的每個元素做上述處理，找到合適的位置將其他元素移回並插入。比較次數為O(nlog2n)，但由於後移，時間復雜度為O(n~2)，空間復雜度為O(1)。好處是比較的次數大大減少。
(3) Hill排序(不穩定):基本思想是:先將序列分成若幹個子序列，直接對每個子序列進行插入和排序，當序列基本有序時，再對整個序列進行直接插入和排序。優點是關鍵字值小的元素可以快速移動到前面，在序列基本有序的情況下直接插入排序的時間效率會大大提高，空間復雜度為O(1)。
(4)簡單選擇排序(不穩定):基本思想是:將序列分成兩部分，每遍在無序部分尋找壹個最小值，然後與無序部分的第壹個元素交換位置。優點是:實現簡單；缺點是:每次行程只能確定壹個元素的位置，時間效率低。時間復雜度為O (n 2)，空間復雜度為O(1)。
(5)堆排序(不穩定):有壹個任意序列，k1，k2，"
Kn滿足以下特征時稱為堆:設此序列排列為b。
完全二叉樹，該樹具有以下特征，樹中的任何節點
大於或小於其左右的子樹，此樹的根節點是最大或
最小值。優點是:對大文件效率明顯提高，但對小文件
效率不明顯。時間復雜度為O(nlog2n)，空間復雜度為O(1)。
十六、各種排序算法簡介(1)
內部排序包括:插入排序、選擇排序、交換排序、歸並排序和基數排序。
其中，插入排序包括:直接插入排序、半插入排序和hill排序；
選擇排序包括:簡單選擇排序和堆排序；交換排序包括冒泡排序和快速排序。
(6)冒泡排序(穩定):基本思想是:每兩次比較元素，按照“先小後大”的規則交換。優點是:每壹步不僅可以找到最大的元素放在序列後面，還可以理順其他元素，如果下壹次排序沒有交換，可以提前結束排序。時間復雜度為O(n~2)，空間復雜度為O(1)。
(7)快速排序(不穩定):基本思想是:在序列中選擇任意壹個元素為中心，大於它的元素全部向後移動，小於它的元素全部向前移動，形成左右兩個子序列，然後按照上述操作調整子序列，直到所有子序列中只有壹個元素，序列有序。優點是:每次行程不僅可以確定壹個元素，而且時間效率高。時間復雜度為O(nlog2n)，空間復雜度為O(log2n)。
(8)合並排序(穩定):基本思想是將兩個或多個有序表合並成壹個新的有序表。時間復雜度為O(n logn)，空間復雜度與要排序的元素個數相同。
(9)基數排序:時間復雜度為:n條記錄鏈式基數排序的時間復雜度為O(d(n+rd))，其中每趟的時間復雜度為O(n)，恢復的時間復雜度為O(rd)。
“先小後大”的規則互換。好處是:每次行程不僅可以找到最大的元素放在序列後面，還可以理順其他元素，如果下壹次行程沒有交換，可以提前結束排序。時間復雜度為O (n 2)，空間復雜度為O(1)。