數據結構面試常見(jiàn)問(wèn)題

　　數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關(guān)系的數據元素的集合。下面就是小編整理的數據結構面試常見(jiàn)問(wèn)題，一起來(lái)看一下吧。

　　數據結構面試常見(jiàn)問(wèn)題 篇1

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

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

　　一.數據結構部分

　　1.數組和鏈表的區別。（很簡(jiǎn)單，但是很�？�，記得要回答全面）

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

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

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

　　1.從訪(fǎng)問(wèn)方式來(lái)看：數組在內存中是連續存儲的，因此，可以利用下標索引進(jìn)行隨機訪(fǎng)問(wèn)；鏈表是鏈式存儲結構，在訪(fǎng)問(wèn)元素的時(shí)候只能通過(guò)線(xiàn)性的方式由前到后順序訪(fǎng)問(wèn)，所以訪(fǎng)問(wèn)效率比數組要低。

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

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

　　4.二叉樹(shù)的基本操作

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

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

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

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

　　二.算法部分

　　1.排序算法：

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

　　各種排序算法的使用范圍總結：

　�。�1）當數據規模較小的時(shí)候，可以用簡(jiǎn)單的排序算法如直接插入排序或直接選擇排序。

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

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

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

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

　　2,查找算法

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

　　3.hash算法

　　4.一些算法設計思想。

　　貪心算法，分治算法，動(dòng)態(tài)規劃算法，隨機化算法，回溯算法等。這些可以根據具體的例子程序來(lái)復習。

　　5.STL

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

　　數據結構面試常見(jiàn)問(wèn)題 篇2

　　1. 什么是數據結構？

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

　　2. 描述數據結構的類(lèi)型？

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

　　數組：所有相同的值的集合。

　　Records：字段的集合，每個(gè)字段都包含來(lái)自單一數據類(lèi)型的數據。

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

　　表格：數據以行和列的形式保存。這些與記錄相當，因為數據的結果或更改反映在整個(gè)表中。

　　3. 什么是線(xiàn)性數據結構？請舉例

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

　　4. 數據結構有哪些應用？

　　數值分析、操作系統、人工智能、編譯器設計、數據庫管理、圖形、統計分析和仿真。

　　5、文件結構和存儲結構有什么區別？

　　區別在于訪(fǎng)問(wèn)的內存區域。存儲結構是指計算機系統內存中的數據結構，而文件結構是指輔助存儲器中的存儲結構。

　　6、什么是多維數組？

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

　　7. 什么是鏈表數據結構？

　　這是最常見(jiàn)的數據結構面試問(wèn)題之一，面試官希望你能給出全面的答案。嘗試盡可能多地解釋?zhuān)�而不是用一句�?huà)來(lái)完成你的答案！

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

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

　　它適用于以下情況：

　　我們處理未知數量的對象或不知道列表中有多少項目；

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

　　不需要隨機訪(fǎng)問(wèn)任何元素；

　　該算法需要一個(gè)數據結構，無(wú)論對象在內存中的物理地址如何，都需要在其中存儲對象；

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

　　一些實(shí)現是堆棧和隊列、圖形、名稱(chēng)目錄、動(dòng)態(tài)內存分配以及對長(cháng)整數執行算術(shù)運算

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

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

　　舉例：

　　帶有下一個(gè)和上一個(gè)導航按鈕的音樂(lè )播放列表

　　具有 BACK-FORWARD 訪(fǎng)問(wèn)頁(yè)面的瀏覽器緩存

　　瀏覽器上的撤消功能

　　9. 為什么要做算法分析？

　　一個(gè)問(wèn)題可以使用多種解決算法以多種方式解決。算法分析提供對算法所需資源的估計，以解決特定的計算問(wèn)題。還確定了執行所需的時(shí)間和空間資源量。

　　算法的時(shí)間復雜度量化了算法運行所花費的時(shí)間，作為輸入長(cháng)度的函數�？臻g復雜度量化了算法占用的空間或內存量，以作為輸入長(cháng)度的函數運行。

【數據結構面試常見(jiàn)問(wèn)題】相關(guān)文章：

應聘面試的常見(jiàn)問(wèn)題11-21

主管面試常見(jiàn)問(wèn)題11-27

外企面試的常見(jiàn)問(wèn)題11-27

壓力面試常見(jiàn)問(wèn)題12-12

醫學(xué)面試的常見(jiàn)問(wèn)題03-26

兒科面試常見(jiàn)問(wèn)題04-08

游戲面試常見(jiàn)問(wèn)題07-06

最新面試常見(jiàn)問(wèn)題12-30

護理面試的常見(jiàn)問(wèn)題06-24

cra面試常見(jiàn)問(wèn)題08-13