數(shù)據(jù)結(jié)構(gòu)面試常見問題

時間：2024-09-01 08:45:32 面試筆試我要投稿

相關(guān)推薦

　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。下面就是小編整理的數(shù)據(jù)結(jié)構(gòu)面試常見問題，一起來看一下吧。

數(shù)據(jù)結(jié)構(gòu)面試常見問題

　　數(shù)據(jù)結(jié)構(gòu)面試常見問題篇1

　　數(shù)據(jù)結(jié)構(gòu)與算法，這個部分的內(nèi)容其實(shí)是十分的龐大，要想都覆蓋到不太容易。在校學(xué)習(xí)階段我們可能需要對每種結(jié)構(gòu)，每種算法都學(xué)習(xí)，但是找工作筆試或者面試的時候，要在很短的時間內(nèi)考察一個人這方面的能力，把每種結(jié)構(gòu)和算法都問一遍不太現(xiàn)實(shí)。所以，實(shí)際的情況是，企業(yè)一般考察一些看起來很基本的概念和算法，或者是一些變形，然后讓你去實(shí)現(xiàn)。也許看起來簡單，但是如果真讓你在紙上或者是計(jì)算機(jī)上快速地完成一個算法，并且設(shè)計(jì)測試案例，最后跑起來，你就會發(fā)現(xiàn)會很難了。這就要求我們要熟悉，并牢固掌握常用的算法，特別是那些看起來貌似簡單的算法，正是這些用起來很普遍的算法，才要求我們能很扎實(shí)的掌握，在實(shí)際工作中提高工作效率。遇到復(fù)雜的算法，通過分析和扎實(shí)的基本功，應(yīng)該可以很快地進(jìn)行開發(fā)。

　　閑話少說，下面進(jìn)入正題。

　　一.數(shù)據(jù)結(jié)構(gòu)部分

　　1.數(shù)組和鏈表的區(qū)別。（很簡單，但是很�？迹浀靡卮鹑妫�

　　C++語言中可以用數(shù)組處理一組數(shù)據(jù)類型相同的數(shù)據(jù)，但不允許動態(tài)定義數(shù)組的大小，即在使用數(shù)組之前必須確定數(shù)組的大小。而在實(shí)際應(yīng)用中，用戶使用數(shù)組之前有時無法準(zhǔn)確確定數(shù)組的大小，只能將數(shù)組定義成足夠大小，這樣數(shù)組中有些空間可能不被使用，從而造成內(nèi)存空間的浪費(fèi)。鏈表是一種常見的數(shù)據(jù)組織形式，它采用動態(tài)分配內(nèi)存的形式實(shí)現(xiàn)。需要時可以用new分配內(nèi)存空間，不需要時用將已分配的空間釋放，不會造成內(nèi)存空間的浪費(fèi)。

　　從邏輯結(jié)構(gòu)來看：數(shù)組必須事先定義固定的長度（元素個數(shù)），不能適應(yīng)數(shù)據(jù)動態(tài)地增減的情況，即數(shù)組的`大小一旦定義就不能改變。當(dāng)數(shù)據(jù)增加時，可能超出原先定義的元素個數(shù)；當(dāng)數(shù)據(jù)減少時，造成內(nèi)存浪費(fèi)；鏈表動態(tài)地進(jìn)行存儲分配，可以適應(yīng)數(shù)據(jù)動態(tài)地增減的情況，且可以方便地插入、刪除數(shù)據(jù)項(xiàng)。（數(shù)組中插入、刪除數(shù)據(jù)項(xiàng)時，需要移動其它數(shù)據(jù)項(xiàng)）。

　　從內(nèi)存存儲來看：（靜態(tài))數(shù)組從棧中分配空間（用NEW創(chuàng)建的在堆中）, 對于程序員方便快速,但是自由度��；鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩.

　　1.從訪問方式來看：數(shù)組在內(nèi)存中是連續(xù)存儲的，因此，可以利用下標(biāo)索引進(jìn)行隨機(jī)訪問；鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)，在訪問元素的時候只能通過線性的方式由前到后順序訪問，所以訪問效率比數(shù)組要低。

　　2.鏈表的一些操作，如鏈表的反轉(zhuǎn)，鏈表存在環(huán)路的判斷（快慢指針），雙向鏈表，循環(huán)鏈表相關(guān)操作。

　　3.隊(duì)列（特殊的如優(yōu)先級隊(duì)列），棧的應(yīng)用。（比如隊(duì)列用在消息隊(duì)列，棧用在遞歸調(diào)用中）

　　4.二叉樹的基本操作

　　二叉樹的三種遍歷方式（前序，中序，后序）及其遞歸和非遞歸實(shí)現(xiàn)，三種遍歷方式的主要應(yīng)用（如后綴表達(dá)式等）。相關(guān)操作的時間復(fù)雜度。

　　5.字符串相關(guān)

　　整數(shù)，浮點(diǎn)數(shù)和字符串之間的轉(zhuǎn)換（atoi,atof,itoa）

　　字符串拷貝注意異常檢查，比如空指針，字符串重疊，自賦值，字符串結(jié)束符'/0'等。

　　二.算法部分

　　1.排序算法：

　　排序可以算是最基本的，最常用的算法，也是筆試面試中最常被考察到的算法。最基本的冒泡排序，選擇排序，插入排序要可以很快的用代碼實(shí)現(xiàn)，這些主要考察你的實(shí)際編碼能力。堆排序，歸并排序，快排序，這些算法需要熟悉主要的思想，和需要注意的細(xì)節(jié)地方。需要熟悉常用排序算法的時間和空間復(fù)雜度。

　　各種排序算法的使用范圍總結(jié)：

　�。�1）當(dāng)數(shù)據(jù)規(guī)模較小的時候，可以用簡單的排序算法如直接插入排序或直接選擇排序。

　　（2）當(dāng)文件的初態(tài)已經(jīng)基本有序時，可以用直接插入排序或冒泡排序。

　�。�3）當(dāng)數(shù)據(jù)規(guī)模比較大時，應(yīng)用速度快的排序算法�？梢钥紤]用快速排序。當(dāng)記錄隨機(jī)分布的時候，快排的平均時間最短，但可能出現(xiàn)最壞的情況，這時候的時間復(fù)雜度是O(n^2)，且遞歸深度為n,所需的�？臻g問O(n)。

　�。�4）堆排序不會出現(xiàn)快排那樣的最壞情況，且堆排序所需的輔助空間比快排要少。但這兩種算法都不是穩(wěn)定的，若要求排序時穩(wěn)定的，可以考慮用歸并排序。

　　（5）歸并排序可以用于內(nèi)排序，也可以用于外排序。在外排序時，通常采用多路歸并，并且通過解決長順串的合并，產(chǎn)生長的初始串，提高主機(jī)與外設(shè)并行能力等措施，以減少訪問外存額次數(shù)，提高外排序的效率。

　　2,查找算法

　　能夠熟練寫出或者是上機(jī)編碼出二分查找的程序。

　　3.hash算法

　　4.一些算法設(shè)計(jì)思想。

　　貪心算法，分治算法，動態(tài)規(guī)劃算法，隨機(jī)化算法，回溯算法等。這些可以根據(jù)具體的例子程序來復(fù)習(xí)。

　　5.STL

　　STL(Standard Template Library)是一個C++領(lǐng)域中，用模版技術(shù)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法庫，已經(jīng)包含在了C++標(biāo)準(zhǔn)庫中。其中的vecor,list,stack,queue等結(jié)構(gòu)不僅擁有更強(qiáng)大的功能，還有了更高的安全性。除了數(shù)據(jù)結(jié)構(gòu)外，STL還包含泛化了的迭代器，和運(yùn)行在迭代器上的各種實(shí)用算法。這些對于對性能要求不是太高，但又不希望自己從底層實(shí)現(xiàn)算法的應(yīng)用還是很具有誘惑力的。

　　數(shù)據(jù)結(jié)構(gòu)面試常見問題篇2

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

　　數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)組織（存儲）和操作進(jìn)行檢索和訪問的方式。它還定義了不同數(shù)據(jù)集相互關(guān)聯(lián)、建立關(guān)系和形成算法的方式。

　　2. 描述數(shù)據(jù)結(jié)構(gòu)的類型？

　　列表：鏈接到先前或/和后續(xù)數(shù)據(jù)項(xiàng)的相關(guān)事物的集合。

　　數(shù)組：所有相同的值的集合。

　　Records：字段的集合，每個字段都包含來自單一數(shù)據(jù)類型的數(shù)據(jù)。

　　樹：在分層框架中組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。這種形式的數(shù)據(jù)結(jié)構(gòu)遵循數(shù)據(jù)項(xiàng)插入、刪除和修改的順序。

　　表格：數(shù)據(jù)以行和列的形式保存。這些與記錄相當(dāng)，因?yàn)閿?shù)據(jù)的結(jié)果或更改反映在整個表中。

　　3. 什么是線性數(shù)據(jù)結(jié)構(gòu)？請舉例

　　如果數(shù)據(jù)結(jié)構(gòu)的所有元素或數(shù)據(jù)項(xiàng)都按順序或線性順序排列，則數(shù)據(jù)結(jié)構(gòu)是線性的。元素以非分層方式存儲，因此除了列表中的第一個和最后一個元素外，每個項(xiàng)目都有后繼者和前驅(qū)者。數(shù)組、堆棧、字符串、隊(duì)列和鏈表，都屬于線性數(shù)據(jù)結(jié)構(gòu)。

　　4. 數(shù)據(jù)結(jié)構(gòu)有哪些應(yīng)用？

　　數(shù)值分析、操作系統(tǒng)、人工智能、編譯器設(shè)計(jì)、數(shù)據(jù)庫管理、圖形、統(tǒng)計(jì)分析和仿真。

　　5、文件結(jié)構(gòu)和存儲結(jié)構(gòu)有什么區(qū)別？

　　區(qū)別在于訪問的內(nèi)存區(qū)域。存儲結(jié)構(gòu)是指計(jì)算機(jī)系統(tǒng)內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，而文件結(jié)構(gòu)是指輔助存儲器中的存儲結(jié)構(gòu)。

　　6、什么是多維數(shù)組？

　　多維數(shù)組的意思是指三維或者三維以上的數(shù)組。三維數(shù)組具有高、寬、深的概念,或者說行、列、層的概念,即數(shù)組嵌套數(shù)組達(dá)到三維及其以上。是最常見的多維數(shù)組,由于其可以用來描述三維空間中的位置或狀態(tài)而被廣泛使用。

　　7. 什么是鏈表數(shù)據(jù)結(jié)構(gòu)？

　　這是最常見的數(shù)據(jù)結(jié)構(gòu)面試問題之一，面試官希望你能給出全面的答案。嘗試盡可能多地解釋，而不是用一句話來完成你的答案！

　　它是一個線性數(shù)據(jù)結(jié)構(gòu)或一系列數(shù)據(jù)對象，其中元素不存儲在相鄰的內(nèi)存位置。元素使用指針鏈接以形成鏈。每個元素都是一個單獨(dú)的對象，稱為節(jié)點(diǎn)。每個節(jié)點(diǎn)有兩項(xiàng)：數(shù)據(jù)字段和對下一個節(jié)點(diǎn)的引用。鏈表中的入口點(diǎn)稱為頭。如果列表為空，則頭部為空引用，最后一個節(jié)點(diǎn)具有對空的引用。

　　一個鏈表是一個動態(tài)的.數(shù)據(jù)結(jié)構(gòu)，其中節(jié)點(diǎn)的數(shù)量是不固定的，這樣的例子有擴(kuò)大和縮小需求的能力。

　　它適用于以下情況：

　　我們處理未知數(shù)量的對象或不知道列表中有多少項(xiàng)目；

　　我們需要從列表中進(jìn)行恒定時間的插入/刪除，就像在時間可預(yù)測性至關(guān)重要的實(shí)時計(jì)算中一樣；

　　不需要隨機(jī)訪問任何元素；

　　該算法需要一個數(shù)據(jù)結(jié)構(gòu)，無論對象在內(nèi)存中的物理地址如何，都需要在其中存儲對象；

　　我們需要在列表中間插入項(xiàng)目，就像在優(yōu)先隊(duì)列中一樣；

　　一些實(shí)現(xiàn)是堆棧和隊(duì)列、圖形、名稱目錄、動態(tài)內(nèi)存分配以及對長整數(shù)執(zhí)行算術(shù)運(yùn)算

　　8.什么是雙向鏈表？請舉例

　　它是鏈表的一種復(fù)雜類型（雙端 LL），其中一個節(jié)點(diǎn)有兩個鏈接，一個連接到序列中的下一個節(jié)點(diǎn)，另一個連接到前一個節(jié)點(diǎn)。這允許在兩個方向上遍歷數(shù)據(jù)元素。

　　舉例：

　　帶有下一個和上一個導(dǎo)航按鈕的音樂播放列表