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

數(shù)據(jù)是描述客觀事物的符號，能夠被計算機識別，并且給計算機處理的符號集合

數(shù)據(jù)結(jié)構(gòu)是計算機內(nèi)部組織數(shù)據(jù)的方式

2. 大O表示法

大O符號，又稱為漸進符號，是用于描述函數(shù)漸近行為的數(shù)學符號。更確切地說，它是用另一個通常更簡單的函數(shù)來描述一個函數(shù)數(shù)量級的漸近上界。

時間復(fù)雜度，是一個用于度量一個算法的運算時間的一個描述，本質(zhì)是一個函數(shù)，它描述的只是代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢

3. 順序表和鏈表

邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，邏輯上都是相鄰的元素，但是物理上，順序表是相鄰的，鏈表一般都是不相鄰的

訪問元素的時候，對于按值查找，都是O(n)，有序的話是O(log2n)

空間分配的情況，若順序表是靜態(tài)分配，空間固定，過多元素會溢出，若是動態(tài)分配，擴容存在時間消耗;鏈表的話則自由靈活

4. 鏈表反轉(zhuǎn)

方式一：使用棧結(jié)構(gòu)來反轉(zhuǎn)，時間和空間開銷不立理想

方式二：使用三指針來反轉(zhuǎn)，效率高

5. 鏈表升序合并

方法一：遞歸，時間空間復(fù)雜度為O(n+m)

方法二：迭代，時間復(fù)雜度為O(n+m)，空間復(fù)雜度為O(1)

6. 棧和隊列

隊列是一端進行插入另一端進行刪除的線性表

棧是表尾進行插入和刪除的線性表

它們都可以用數(shù)組和鏈表來實現(xiàn)

7. 棧和隊列的應(yīng)用

前綴表達式和后綴表達式

8. 判斷循環(huán)隊列是否為空?

方法一：入隊tag=1，出隊tag=0

方法二：記錄元素數(shù)量num

方法三：少用一個空間，(rear+1%maxsize=front

9. 各種二叉樹的區(qū)別

完全二叉樹和滿二叉樹：除了最后一層外，其他任何一層的節(jié)點數(shù)均達到最大值，且最后一層也只是在最右側(cè)缺少節(jié)點

二叉排序樹和二叉搜索樹：都是一樣的，節(jié)點值大于左子節(jié)點的數(shù)值，小于右邊子節(jié)點的數(shù)值

平衡二叉樹(AVL)：任意結(jié)點的左、右子樹高度差的絕對值不超過1

10. 重建二叉樹

根據(jù)前，中遍歷次序構(gòu)造二叉樹和根據(jù)中，后序列構(gòu)造二叉樹，只需要找到頭節(jié)點，然后遞歸找到左右子樹就行了

至于為什么不能不能根據(jù)前，后序列構(gòu)造出二叉樹，是因為，我們只知道最開始頭節(jié)點的位置，其余元素不清楚是劃分到左子樹還是右子樹

以上就是“2023新年真題，數(shù)據(jù)結(jié)構(gòu)與算法面試題”，你能回答上來嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動力節(jié)點Java官網(wǎng)。