計算機演算法數據結構

『壹』 什麼是演算法與數據結構

演算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決一類問題。
一個演算法應該具有以下五個重要的特徵：
1、有窮性： 一個演算法必須保證執行有限步之後結束；
2、確切性： 演算法的每一步驟必須有確切的定義；
3、輸入：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定除了初始條件；
4、輸出：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；
5、可行性： 演算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。
計算機科學家尼克勞斯-沃思曾著過一本著名的書《數據結構十演算法= 程序》，可見演算法在計算機科學界與計算機應用界的地位。

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關。
一般認為，一個數據結構是由數據元素依據某種邏輯聯系組織起來的。對數據元素間邏輯關系的描述稱為數據的邏輯結構；數據必須在計算機內存儲，數據的存儲結構是數據結構的實現形式，是其在計算機內的表示；此外討論一個數據結構必須同時討論在該類數據上執行的運算才有意義。
在許多類型的程序的設計中，數據結構的選擇是一個基本的設計考慮因素。許多大型系統的構造經驗表明，系統實現的困難程度和系統構造的質量都嚴重的依賴於是否選擇了最優的數據結構。許多時候，確定了數據結構後，演算法就容易得到了。有些時候事情也會反過來，我們根據特定演算法來選擇數據結構與之適應。不論哪種情況，選擇合適的數據結構都是非常重要的。
選擇了數據結構，演算法也隨之確定，是數據而不是演算法是系統構造的關鍵因素。這種洞見導致了許多種軟體設計方法和程序設計語言的出現，面向對象的程序設計語言就是其中之一。
在計算機科學中，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象（數據元素）以及它們之間的關系和運算等的學科，而且確保經過這些運算後所得到的新結構仍然是原來的結構類型。
「數據結構」作為一門獨立的課程在國外是從1968年才開始設立的。 1968年美國唐·歐·克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本演算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。「數據結構」在計算機科學中是一門綜合性的專業基礎課。數據結構是介於數學、計算機硬體和計算機軟體三者之間的一門核心課程。數據結構這一門課的內容不僅是一般程序設計（特別是非數值性程序設計）的基礎，而且是設計和實現編譯程序、操作系統、資料庫系統及其他系統程序的重要基礎。
計算機是一門研究用計算機進行信息表示和處理的科學。這裡面涉及到兩個問題：
信息的表示
信息的處理
而信息的表示和組又直接關繫到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統程序和應用程序的規模很大，結構又相當復雜。因此，為了編寫出一個「好」的程序，必須分析待處理的對象的特徵及各對象之間存在的關系，這就是數據結構這門課所要研究的問題。眾所周知，計算機的程序是對信息進行加工處理。在大多數情況下，這些信息並不是沒有組織，信息（數據）之間往往具有重要的結構關系，這就是數據結構的內容。數據的結構，直接影響演算法的選擇和效率。
計算機解決一個具體問題時，大致需要經過下列幾個步驟：首先要從具體問題中抽象出一個適當的數學模型，然後設計一個解此數學模型的演算法（Algorithm），最後編出程序、進行測試、調整直至得到最終解答。尋求數學模型的實質是分析問題，從中提取操作的對象，並找出這些操作對象之間含有的關系，然後用數學的語言加以描述。計算機演算法與數據的結構密切相關，演算法無不依附於具體的數據結構，數據結構直接關繫到演算法的選擇和效率。運算是由計算機來完成，這就要設計相應的插入、刪除和修改的演算法 。也就是說，數據結構還需要給出每種結構類型所定義的各種運算的演算法。
數據是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並由計算機程序處理的符號的總稱。
數據元素是數據的基本單位，在計算機程序中通常作為一個整體考慮。一個數據元素由若干個數據項組成。數據項是數據的不可分割的最小單位。有兩類數據元素：一類是不可分割的原子型數據元素，如：整數"5"，字元 "N" 等；另一類是由多個款項構成的數據元素，其中每個款項被稱為一個數據項。例如描述一個學生的信息的數據元素可由下列6個數據項組成。其中的出身日期又可以由三個數據項："年"、"月"和"日"組成，則稱"出身日期"為組合項，而其它不可分割的數據項為原子項。
關鍵字指的是能識別一個或多個數據元素的數據項。若能起唯一識別作用，則稱之為 "主" 關鍵字，否則稱之為 "次" 關鍵字。
數據對象是性質相同的數據元素的集合，是數據的一個子集。數據對象可以是有限的，也可以是無限的。
數據處理是指對數據進行查找、插入、刪除、合並、排序、統計以及簡單計算等的操作過程。在早期，計算機主要用於科學和工程計算，進入八十年代以後，計算機主要用於數據處理。據有關統計資料表明，現在計算機用於數據處理的時間比例達到80%以上，隨著時間的推移和計算機應用的進一步普及，計算機用於數據處理的時間比例必將進一步增大。
數據結構是指同一數據元素類中各數據元素之間存在的關系。數據結構分別為邏輯結構、存儲結構（物理結構）和數據的運算。數據的邏輯結構是對數據之間關系的描述，有時就把邏輯結構簡稱為數據結構。邏輯結構形式地定義為（K，R）（或（D，S）），其中，K是數據元素的有限集，R是K上的關系的有限集。
數據元素相互之間的關系稱為結構。有四類基本結構：集合、線性結構、樹形結構、圖狀結構（網狀結構）。樹形結構和圖形結構全稱為非線性結構。集合結構中的數據元素除了同屬於一種類型外，別無其它關系。線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。在圖形結構中每個結點的前驅結點數和後續結點數可以任意多個。
數據結構在計算機中的表示（映像）稱為數據的物理（存儲）結構。它包括數據元素的表示和關系的表示。數據元素之間的關系有兩種不同的表示方法：順序映象和非順序映象，並由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常藉助於程序設計語言中的數組來實現。鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常藉助於程序設計語言中的指針類型來實現。索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。
數據結構中，邏輯上（邏輯結構：數據元素之間的邏輯關系）可以把數據結構分成線性結構和非線性結構。線性結構的順序存儲結構是一種隨機存取的存儲結構，線性表的鏈式存儲結構是一種順序存取的存儲結構。線性表若採用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連續。邏輯結構與數據元素本身的形式、內容、相對位置、所含結點個數都無關。
演算法的設計取決於數據（邏輯）結構，而演算法的實現依賴於採用的存儲結構。數據的運算是在數據的邏輯結構上定義的操作演算法，如檢索、插入、刪除、更新的排序等。

『貳』 什麼是數據結構和演算法

數據結構，Data_Structure，其中D是數據元素的集合，R是該集合中所有元素之間的關系的有限集合。數據結構則是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關。

數據結構是計算機專業學生在大學期間都會學習的一門課程，但是由於課程偏理論，缺乏實際操作的學習體驗，而讓大家產生了一種「數據結構不重要，我只要學習了Java/C語言/Python同樣能敲代碼」的錯覺，但其實它是一門集技術性、理論性和實踐性於一體的課程。

演算法是某一系列運算步驟，它表達解決某一類計算問題的一般方法，對這類方法的任何一個輸入，它可以按步驟一步一步計算，最終產生一個輸出。

小碼哥的李明傑也說過所有的計算問題，都離不開要計算的對象或者要處理的信息，如何高效的把它們組織起來，就是數據結構關心的問題，所以演算法是離不開數據結構的，這就是數據與演算法。

『叄』 計算機二級選擇題干貨（五）——數據結構和演算法

1、線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱後進先出表（Last In First Out）；隊列可看作是插入在一端進行，刪除在另一端進行的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。在隊列中，只能刪除隊頭元素，隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表（First In First Out）。

2、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

3、棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又稱先進後出表（FILO-First In Last Out）。線性表可以順序存儲，也可以鏈式存儲，而棧是一種線性表，也可以採用鏈式存儲結構。

4、棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區別是：棧只允許在表的一端進行插入或刪除操作，是一種"後進先出"的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種"先進先出"的線性表。

5、在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態變化

top=0表示棧空，top=50表示棧滿。入棧操作首先將top加1，然後將新元素插入到top指針指向的位置；退棧操作首先將top指針指向的元素賦給一個指定的變數，然後將top減1。棧頂指針top動態反映了棧中元素的變化情況。

6、棧是一種先進後出的線性表，棧實際上也是線性表，只不過是一種特殊的線性表。隊列是指允許在一端進行插入、而在另一端進行刪除的線性表，隊列是一種"先進先出"或"後進後出"的線性表

隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。它又稱為"先進先出"或"後進後出"的線性表，體現了"先來先服務"的原則。

7、帶鏈的隊列也是線性鏈表，在線性鏈表中指向線性表中的第一個結點的指針稱為頭指針，頭指針為NULL或0時稱為空表，指向隊尾元素的指針稱為尾指針。隊列在隊尾插入元素，稱為入隊運算；在隊頭刪除元素，稱為退隊運算。帶鏈隊列在開辟存儲空間時，可以按照存儲空間地址增大的方向開辟，也可以按照存儲空間地址減少的方向開辟。

8、所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第1個位置，形成邏輯上的環狀空間，供隊列循環使用。所以循環隊列還是屬於線性結構。循環隊列的頭指針front指向隊列的第一個元素的前一位置，隊尾指針rear指向隊列的最後一個元素，循環隊列的動態變化需要頭尾指針共同反映循環隊列的長度是：(sq.rear-sq.front+maxsize)%maxsize，所以循環隊列的長度是由隊頭和隊尾指針共同決定的

 在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。

 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就進一。每進行一次退隊運算，排頭指針就進一。當rear或front的值等於隊列的長度+1時，就將rear或front的值置為1。一般情況下，rear大於front，因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限之後又從數組的低端開始，此時，rear是小於front的。

循環隊列就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在實際應用中，隊列的順序存儲結構一般採用循環隊列的形式。因此，循環隊列不是隊列的一種鏈式存儲結構。循環隊列是一種存儲結構，因此循環隊列是一種物理結構，而不是邏輯結構。循環隊列是隊列的順序存儲結構，因此循環隊列是線性結構。

9、循環隊列不同於循環鏈表，循環隊列是順序存儲結構，循環鏈表是鏈式存儲結構。雙向鏈表是鏈式存儲結構，其中每個結點都有左指針和右指針，不同於二叉樹結點的左子樹指針和右子樹指針。非線性結構和線性結構是數據的邏輯結構，順序和鏈式是數據的存儲結構，例如二叉樹是非線性結構，也可以按照層序進行順序存儲。

10、非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後驅。常見的非線性結構有：樹（二叉樹等），圖（網等）。

11、由於二叉樹的存儲結構中每一個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表，二叉鏈表屬於非線性結構。

12、遍歷是指不重復的訪問所有結點。線性單鏈表每個結點只有一個指針域，由這個指針只能找到後件結點，但不能找到前件結點。雙向鏈表中的每個結點設置兩個指針，左指針指向其前件結點，右指針指向其後件結點。循環鏈表中增加了一個表頭結點，循環鏈表中的所有結點的指針構成了一個環狀鏈。二叉鏈表即二叉樹的鏈式存儲結構，每個存儲結點有兩個指針域，左指針域指向該結點的左子結點的存儲地址，右指針域指向該結點的右子結點的存儲地址。

13、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的;（2）線性表中各元素在存儲空間中是按邏輯順序依次存放的。

14、循環鏈表具有以下兩個特點：(1)在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。(2)循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

15、在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點。

16、根據二叉樹的性質：二叉樹第i（i≥1）層上至多有2i-1個結點。

17、所謂滿二叉樹是指這樣的一種二叉樹：除最後一層外，每層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m個結點。

18、在任意一顆樹中，結點總數=總分支數目+1

19、二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。本題中度為2的結點數為n，故葉子結點數為n+1個。

二叉樹的性質：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。

20、在用完全二叉樹表示堆，樹中所有非葉子結點值均不小於其左右子樹的根結點值，因此，堆頂元素必為序列的n個元素中的最大項。

21、作為一個演算法，一般應具有以下幾個基本特徵。

 可行性

 確定性

 有窮性

擁有足夠的情報

22、計算機演算法是指解題方案的准確而完整的描述

演算法的有窮性，是指演算法必須在有限的時間內做完，即演算法必須能在執行有限個步驟之後終止。

23、希爾排序法的基本思想是：將整個無序序列分割成若干小的子序列分別進行插入排序。所以希爾排序法屬於插入類排序，但它對簡單插入排序做了很大的改進。

24、快速排序的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄繼續進行排序，以達到整個序列有序；插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中，從而得到一個新的序列；選擇排序的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置），然後對剩下的子表採用同樣的方法，直到表空為止；歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表。

25、在單鏈表中，增加頭結點的目的是______。

頭結點不僅標識了表中首結點的位置，而且根據單鏈表（包含頭結點）的結構，只要掌握了表頭，就能夠訪問整個鏈表，因此增加頭結點目的是為了便於運算的實現。

26、演算法分析是指對一個演算法的運行時間和佔用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示。分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度，提高演算法的執行效率。

27、演算法是指解題方案的准確而完整的描述。但演算法不等於程序，也不等於計算方法。當然，程序也可以作為演算法的一種描述，但程序通常還需要考慮很多與方法和分析無關的細節問題，這是因為在編寫程序時要受到計算機系統運行環境的限制。通常，程序的編制不可能優於演算法的設計。作為一個演算法，一般應具有可行性、確定性、有窮性、擁有足夠情報四個基本特徵。因此設計演算法時不僅僅要考慮結果的可靠性，即不僅考慮演算法結果的可行性，還要考慮步驟的確定性，時間和步驟的有窮性等。因此，演算法是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。

28、一個演算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是演算法的控制結構。因此設計演算法時不僅需要考慮數據結構的設計，還要考慮數據的操作和運算及各操作之間的執行順序。

29、在有向圖中，若任意兩個頂點都連通，則稱該圖是強連通圖，這樣的有向圖的形狀是環狀，因而至少應有n條邊。

30、當數據表A中每個元素距其最終位置不遠，說明數據表A按關鍵字值基本有序，在待排序序列基本有序的情況下，採用插入排序所用時間最少。

31、數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。

32、假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後掃描和n/2遍的從後往前掃描，需要比較次數為n(n-1)/2。快速排序法的最壞情況比較次數也是n(n-1)/2

（1）冒泡排序法：是一種最簡單的交換類排序法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要比較的次數為n(n-1)/2次。

 （2）簡單插入排序法：在簡單插入排序法中，每一次比較後最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。

 （3）簡單選擇排序法：對於長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然後將該最小的元素與子表中的第一個元素進行交換。簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。

 （4）堆排序法：堆排序的方法為：①首先將一個無序序列建成堆。②然後將堆頂元素（序列中的最大項）與堆中最後一個元素交換（最大項應該在序列的最後）。在最壞情況下，堆排序需要比較的次數為。

 假設線性表的長度為16，那麼冒泡排序、直接插入排序、簡單選擇排序都需要比較120次，而堆排序需要比較64次。

33、對於長度為n的線性表，在最壞的情況下，快速排序所需要的比較次數為n(n-1)/2；冒泡排序所需要的比較次數為n(n-1)/2；直接插入排序所需要的比較次數為n(n-1)/2；堆排序所需要的比較次數為。

34、在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次。

35、二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

二分法檢索要求線性表結點按關鍵值排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功；否則根據比較結果確定下一步在表的前半部分或後半部分繼續進行。二分法檢索的效率比較高，設線性表有n個元素，則最多的檢索次數為大於log2n(2為底數)的最小整數，最少的檢索次數為1。

36、一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。

37、順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素，鏈式存儲結構中各數據結點的存儲序號是不連續的，並且各結點在存儲空間中的位置關系與邏輯關系也不一致。兩者都可以存儲線性的、有序的邏輯結構，順序結構使用的是連續物理空間，鏈式結構可以使用零散的物理空間存儲，鏈式結構更靈活，不存在誰節約空間的說法

38、順序存儲結構中，數據元素存放在一組地址連續的存儲單元中，每個數據元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到，從而實現了隨機存取。對於鏈式存儲結構，要對某結點進行存取，都得從鏈的頭指針指向的結點開始，這是一種順序存取的存儲結構。

39、鏈式存儲結構克服了順序存儲結構的缺點：它的結點空間可以動態申請和釋放；它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。故鏈式存儲結構下的線性表便於插入和刪除操作。

40、線性表的順序存儲結構的存儲空間只用於存放結點數據，而鏈式存儲結構的存儲空間不僅要存放結點數據，還要存放數據的指針，所以線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構

41、在進行順序查找過程中，如果線性表中的第1個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查找的元素是線性表中的最後一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次

42、對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較 次，而順序查找需要比較n次。二分法查找只適用於順序存儲的有序表，如果採用鏈式存儲結構，也只能用順序查找,所以，對長度為n的有序鏈表進行查找，最壞情況下需要的比較次數為n

43、根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。

44、如果一個非空的數據結構滿足下列兩個條件：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個後件。則稱該數據結構為線性結構，又稱線性表。

45、有一個以上根結點的數據結構肯定是非線性結構，循環鏈表、雙向鏈表是線性結構；線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。

46、在鏈表中，如果有兩個結點的同一個指針域的值相等，則該鏈表一定是非線性結構

47、線性表的鏈式存儲結構稱為線性鏈表，為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干位元組，通常稱這些小塊為存儲結點。每一個存儲結點分為兩部分：一部分用於存儲數據元素的值，稱為數據域；另一部分用於存放下一個數據元素的存儲序號，即指向後件的結點，稱為指針域。在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，以便用於存儲該元素的值，然後將存放新元素值的結點鏈接到線性表中指定的位置。在線性鏈表的插入過程中不發生數據無素移動的現象，只需改變有關結點的指針即可，從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結點，首先要在線性鏈表中找到這個結點，然後將要刪除結點放回到可利用棧。在線性鏈表中刪除一個元素後，不需要移動表的數據元素，只需改變被刪元素所在結點的前一個結點的指針域即可。因此，進行插入與刪除時，不需要移動表中的元素。

48、在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷和後序遍歷。

前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

二叉樹的中序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。

49、鏈表有線性鏈表，也有非線性鏈表。線性鏈表和二叉樹鏈表的結點都有兩個指針域，前者是線性結構，後者是非線性結構。線性單鏈表中的結點只有一個指針，葉子結點一般是對樹結構而言，樹結構是非線性結構，不是線性表。

50、演算法的復雜度主要包括時間復雜度和空間復雜度：演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度；演算法的時間復雜度是指執行演算法所需要的計算工作量，即演算法執行過程中所需要的基本運算次數，為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。二者沒有直接關系。

51、一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間。一個演算法所佔用的存儲空間包括程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間相對於問題規模來說是常數，則稱該演算法是原地(in place)工作的。

52、我們通常用時間復雜度和空間復雜度來衡量演算法效率，演算法的時間復雜度是指執行演算法所需要的計算工作量；演算法所執行的基本運算次數與問題的規模有關，而一個演算法的空間復雜度，一般是指執行這個演算法所需要的內存空間；一般來說，一種數據的邏輯結構根據需要可以表示成多種存儲結構。

所謂演算法的時間復雜度，是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率，在度量一個演算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與演算法實現過程中的許多細節無關。為此，可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。

53、子程序調用是一種層次關系，子程序調用功能模塊，調用功能模塊的個數也不確定，可以是一個，也可以是多個。二叉樹是一種很有用的非線性結構，二叉樹不同於樹形結構。二叉樹具有以下兩個特點：①非空二叉樹只有一個根結點；②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。選項D規定每個結點只能有兩個後件。在子程序調用中，調用的功能模塊可以是多個，可以調用超過兩個功能模塊。

54、結構圖的深度表示控制的層數結構圖的深度表示控制的層數

55、數據結構是指反映數據元素之間關系的數據元素集合的表示。更通俗地說，數據結構是指帶有結構的數據元素的集合。所謂結構實際上就是指數據元素之間的前後件關系。線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，還要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。

『肆』 網路與編程中常用的演算法與數據結構有哪些

演算法就是計算機處理解決問題的計算機能理解的方法。
比如算一個階乘 , 計算機的演算法就是寫一個循環,從高到底, 一直乘下去,直到 1 為止。
復雜的演算法比如一個強連通帶權網路,求兩點間的最短路徑,這個很有用啊....比如採用廣度優先演算法,或深度優先演算法
數據結構指數據在計算機中存儲存在的方式。
比如文件在硬碟中,有二進制,文本等形式存放, 程序中的一組數字可能放在數組裡面,也可能在棧裡面,也肯能在鏈表裡面