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

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

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

2. 大O表示法

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

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

3. 順序表和鏈表

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

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

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

4. 鏈表反轉(zhuǎn)

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

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

5. 鏈表升序合并

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

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

6. 棧和隊(duì)列

隊(duì)列是一端進(jìn)行插入另一端進(jìn)行刪除的線性表

棧是表尾進(jìn)行插入和刪除的線性表

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

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

前綴表達(dá)式和后綴表達(dá)式

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

方法一：入隊(duì)tag=1，出隊(duì)tag=0

方法二：記錄元素?cái)?shù)量num

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

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

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

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

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

10. 重建二叉樹

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

至于為什么不能不能根據(jù)前，后序列構(gòu)造出二叉樹，是因?yàn)椋覀冎恢雷铋_始頭節(jié)點(diǎn)的位置，其余元素不清楚是劃分到左子樹還是右子樹

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