一、什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(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ù)類型再沒有其他的關(guān)系。

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

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

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

物理結(jié)構(gòu)包括順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。

二、解釋一下順序存儲與鏈式存儲

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

三、頭指針和頭結(jié)點的區(qū)別？

頭指針：是指向第一個節(jié)點存儲位置的指針，具有標識作用，頭指針是鏈表的必要元素，無論鏈表是否為空，頭指針都存在。

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

四、線性結(jié)構(gòu)的特點

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

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

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

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

五、數(shù)組和鏈表的區(qū)別？

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

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

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

六、單鏈表結(jié)構(gòu)和順序存儲結(jié)構(gòu)的區(qū)別？

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

七、棧和隊列的區(qū)別

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

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