回覆列表
  • 1 # 西安北大青鳥華美教育

    資料結構與演算法,這個部分的內容其實是十分的龐大,要想都覆蓋到不太容易。在校學習階段我們可能需要對每種結構,每種演算法都學習,但是找工作筆試或者面試的時候,要在很短的時間內考察一個人這方面的能力,把每種結構和演算法都問一遍不太現實。所以,實際的情況是,企業一般考察一些看起來很基本的概念和演算法,或者是一些變形,然後讓你去實現。也許看起來簡單,但是如果真讓你在紙上或者是計算機上快速地完成一個演算法,並且設計測試案例,最後跑起來,你就會發現會很難了。這就要求我們要熟悉,並牢固掌握常用的演算法,特別是那些看起來貌似簡單的演算法,正是這些用起來很普遍的演算法,才要求我們能很紮實的掌握,在實際工作中提高工作效率。遇到複雜的演算法,透過分析和紮實的基本功,應該可以很快地進行開發。

    閒話少說,下面進入正題。

    一.資料結構部分

    1.陣列和連結串列的區別。(很簡單,但是很常考,記得要回答全面)

    C++語言中可以用陣列處理一組資料型別相同的資料,但不允許動態定義陣列的大小,即在使用陣列之前必須確定陣列的大小。而在實際應用中,使用者使用陣列之前有時無法準確確定陣列的大小,只能將陣列定義成足夠大小,這樣陣列中有些空間可能不被使用,從而造成記憶體空間的浪費。連結串列是一種常見的資料組織形式,它採用動態分配記憶體的形式實現。需要時可以用new分配記憶體空間,不需要時用delete將已分配的空間釋放,不會造成記憶體空間的浪費。  從邏輯結構來看:陣列必須事先定義固定的長度(元素個數),不能適應資料動態地增減的情況,即陣列的大小一旦定義就不能改變。當資料增加時,可能超出原先定義的元素個數;當資料減少時,造成記憶體浪費;連結串列動態地進行儲存分配,可以適應資料動態地增減的情況,且可以方便地插入、刪除資料項。(陣列中插入、刪除資料項時,需要移動其它資料項)。    從記憶體儲存來看:(靜態)陣列從棧中分配空間(用NEW建立的在堆中), 對於程式設計師方便快速,但是自由度小;連結串列從堆中分配空間, 自由度大但是申請管理比較麻煩.

    從訪問方式來看:陣列在記憶體中是連續儲存的,因此,可以利用下標索引進行隨機訪問;連結串列是鏈式儲存結構,在訪問元素的時候只能透過線性的方式由前到後順序訪問,所以訪問效率比陣列要低。

    2.連結串列的一些操作,如連結串列的反轉,連結串列存在環路的判斷(快慢指標),雙向連結串列,迴圈連結串列相關操作。

    3.佇列(特殊的如優先順序佇列),棧的應用。(比如佇列用在訊息佇列,棧用在遞迴呼叫中)

    4.二叉樹的基本操作

    二叉樹的三種遍歷方式(前序,中序,後序)及其遞迴和非遞迴實現,三種遍歷方式的主要應用(如字尾表示式等)。相關操作的時間複雜度。

    5.字串相關

    整數,浮點數和字串之間的轉換(atoi,atof,itoa)

    字串複製注意異常檢查,比如空指標,字串重疊,自賦值,字串結束符"/0"等。

    二.演算法部分

    1.排序演算法:

    排序可以算是最基本的,最常用的演算法,也是筆試面試中最常被考察到的演算法。最基本的氣泡排序,選擇排序,插入排序要可以很快的用程式碼實現,這些主要考察你的實際編碼能力。堆排序,歸併排序,快排序,這些演算法需要熟悉主要的思想,和需要注意的細節地方。需要熟悉常用排序演算法的時間和空間複雜度。

    各種排序演算法的使用範圍總結:(1)當資料規模較小的時候,可以用簡單的排序演算法如直接插入排序或直接選擇排序。(2)當檔案的初態已經基本有序時,可以用直接插入排序或氣泡排序。(3)當資料規模比較大時,應用速度快的排序演算法。可以考慮用快速排序。當記錄隨機分佈的時候,快排的平均時間最短,但可能出現最壞的情況,這時候的時間複雜度是O(n^2),且遞迴深度為n,所需的棧空間問O(n)。(4)堆排序不會出現快排那樣的最壞情況,且堆排序所需的輔助空間比快排要少。但這兩種演算法都不是穩定的,若要求排序時穩定的,可以考慮用歸併排序。(5)歸併排序可以用於內排序,也可以用於外排序。在外排序時,通常採用多路歸併,並且透過解決長順串的合併,產生長的初始串,提高主機與外設並行能力等措施,以減少訪問外存額次數,提高外排序的效率。

    2,查詢演算法

    能夠熟練寫出或者是上機編碼出二分查詢的程式。

    3.hash演算法

    4.一些演算法設計思想。

    貪心演算法,分治演算法,動態規劃演算法,隨機化演算法,回溯演算法等。這些可以根據具體的例子程式來複習。

    5.STL

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

  • 2 # X工程師

    作為優秀的程式設計師,基礎演算法,如演算法導論裡面常見的演算法要知其原理,學習演算法思維思想。

    在業務層面,也有一些和你工資內容相關的應用級演算法,也需要了解學習。

    最根本的是,學習演算法思想,怎麼去追求極致的演算法效能和方法

  • 中秋節和大豐收的關聯?
  • 那些讀自考的人最後怎麼樣了?