本章考試大綱：（1）資料結構與演算法（基礎，識記）；（2）程式設計基礎（基礎，理解）；（3）軟體工程基礎（基礎，理解）；（4）資料庫基礎（基礎，了解）。
1、資料結構與演算法
1.1演算法（基礎，識記）
（1）演算法的基本概念
計算機演算法為計算機解題的過程實際上是在實施某種演算法。所謂演算法是對解題方案準確而完善的描述。
演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
基本運算和操作包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的三種基本控制結構：順序結構、選擇結構、迴圈結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減半遞推技術、回溯法。
列舉法：根據提出的問題，列舉所有可能的情況，並用問題中給定的條件檢驗哪些是需要的，哪些是不需要的；
歸納法：通過列舉少量特殊情況，經過分析，最後找出一般的關係；
遞推：指從已知的初始條件出發，逐次推出所要求的各中間結果和最後結果；
遞迴：解決一些複雜問題時，為了降低問題的複雜程度等，一般總是將問題逐層分解，最後歸結為一些簡單的問題，再沿著原來分解的逆過程逐步進行綜合。遞迴分為直接遞迴和間接遞迴兩種；
減半遞推技術：「減半」是指將問題的規模減半，而問題的性質不變。所謂「遞推」是指重複「減半」過程；
回溯法：通過對問題的分析，找出乙個解決問題的線索，然後沿著這個線索逐步試探，對於每一步的試探，若試探成功，就得到問題的解；若試探失敗，就逐步回退，回到別的線路再進行試探。
（2）演算法複雜度
演算法複雜度包括時間複雜度和空間複雜度。如表1-1所示。
表1-1 演算法複雜度
1.2資料結構的基本概念（基礎，識記）
（1）資料結構研究的3個方面
資料集合中各資料元素之間所固有的邏輯關係，即資料的邏輯結構。
在對資料進行處理時，各資料元素在計算機中的儲存關係，即資料的儲存結構。
對各種資料結構進行的運算。
（2）資料結構
資料結構是指相互有關聯的資料元素的集合。
邏輯結構：
資料的邏輯結構是對資料元素之間的邏輯關係的描述，它可以用乙個資料元素的集合和定義在此集合中的若干關係來表示。資料的邏輯結構有兩個要素：一是資料元素的集合，通常記為d；二是d上的關係，它反映了資料元素之間的前後件關係，通常記為r。
乙個資料結構可以表示成：b=（d,r）
其中，b表示資料結構。為了反映d中各資料元素之間的前後件關係，一般用二元組來表示。
儲存結構：
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構（也稱資料的物理結構）。
由於資料元素在計算機儲存空間中的位置關係可能與邏輯關係不同，因此，為了表示存放在計算機儲存空間中的各資料元素之間的邏輯關係（即前後件關係），在資料的儲存結構中，不僅要存放各資料元素的資訊，還需要存放各資料元素之間的前後件關係的資訊。
一種資料的邏輯結構根據需要可以表示成多種儲存結構，常用的有順序、鏈式等儲存結構。
順序儲存方式主要用於線性的資料結構，它把邏輯上相鄰的資料元素儲存在物理上相鄰的儲存單元中，結點之間的關係由儲存單元的鄰接關係來體現。
鏈式儲存結構就是在每個結點中至少包含乙個指標域，用指標來體現資料元素之間邏輯上的聯絡。
（3）線性結構和非線性結構
根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分成兩大型別：線性結構與非線性結構。
如果乙個非空的資料結構滿足下列兩個條件：
有且只有乙個根結點；
每乙個結點最多有乙個前件，也最多有乙個後件。
則稱該資料結構為線性結構。線性結構又稱線性表。在乙個線性結構中插入或刪除任何乙個結點後還應是線性結構。棧、佇列、串等都是線性結構。
如果乙個資料結構不是線性結構，則稱之為非線性結構。陣列、廣義表、樹和圖等資料結構都是非線性結構。
1.3線性表（基礎，識記）
（1）線性表的基本概念
線性表是由n（n>=0）個資料元素a1，a2，…，an組成的乙個有限序列，表中的每乙個資料元素，除了第乙個外，有且只有乙個前件，除了最後乙個外，有且只有乙個後件。
（2）線性表的順序儲存結構的基本特點
線性表中所有元素所佔的儲存空間是連續的。
線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素ai的儲存位址為：adr(ai)=adr(a1)+(i-1)k,adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
（3）線性表的運算
線性表的運算有查詢、插入、刪除3種。
線性表的插入：
插入的實現方法：要在第i（1<=i<=n）個元素之前插入乙個新元素時，首先要從最後乙個元素開始，直到第i個元素之間的n-i+1個元素依次向後移動乙個位置，移動結束後，第i個元素位置被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加1。
線性表插入操作演算法的複雜度分析：由線性表插入過程可知，如果插入位置在第i（1<=i<=n）個元素之前，則原來第i個元素之後的所有元素都必須向後移動。在平均情況下，要**性表中插入乙個新元素，需要移動表中一半的元素，最壞情況下要移動表中的所有元素。
線性表的刪除：
刪除的實現方法：要刪除第i（1<=i<=n）個元素時，首先要從第i+1個元素開始，直到最後乙個元素之間的n-i個元素依次向前移動乙個位置。刪除結束後，線性表的長度就減少1。
線性表刪除操作演算法的複雜度分析：如果刪除的是第i（1<=i<=n）個元素，則原來第i個元素之後的所有元素都必須向前移動乙個位置。在平均情況下，要**性表中刪除乙個已有的元素，需要移動表中一半的元素，最壞情況下要移動表中的所有元素。
（4）線性表順序儲存結構的適用場合
線性表的順序儲存結構對於小線性表或其中元素不常變動的線性表來說是合適的，因為順序儲存的結構比較簡單。但是這種順序儲存結構對於元素需要變動的大線性表就不合適了，因為插入和刪除的效率比較低。
1.4棧（基礎，識記）
（1）棧的基本概念
棧（stack）是一種特殊的線性表，是限定只在一端進行插入與刪除的線性表。
在棧中，一端是封閉的，既不允許進行插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。
棧頂元素總是最後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才被刪除的元素。
棧是按照「先進後出」或「後進先出」的原則組織資料的。例如，槍械的子彈匣就可以用來形象地表示棧結構。子彈匣的一端是完全封閉的，最後被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最後被彈出。
（2）棧的順序儲存及其運算
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
入棧運算。在棧頂位置插入乙個新元素。首先將棧頂指標加1，然後將新元素插入到棧頂指標指向的位置。
退棧運算。取出棧頂元素並賦給乙個指定變數。首先將棧頂元素賦給乙個指定的變數，然後將棧頂指標減1.當棧頂指標為0時，說明棧空，不可能進行退棧操作。此時，發生棧「下溢」錯誤。
讀棧頂元素。將棧頂元素賦給乙個指定的變數，棧指標不變。當棧頂指標為0時，讀棧頂元素操作失敗。
1.5佇列（基礎，識記）
（1）佇列的基本概念
佇列是只允許在一端進行刪除，在另一端進行插入的順序表，通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。當表中沒有元素時稱為空佇列。
佇列的修改是依照先進先出的原則進行的，因此佇列也稱為先進先出的線性表，或者後進後出的線性表。若有佇列：q=（q1，q2，…，qn）
那麼，q1為隊頭元素（排頭元素），qn為隊尾元素。佇列中的元素是按照q1，q2，…，qn的順序進入的，退出佇列也只能按照這個次序依次退出，即只有在q1，q2，…，qn-1都退隊之後，qn才能退出佇列。因最先進入佇列的元素將最先出隊，所以佇列具有先進先出特性，體現「先來先服務」的原則。
隊頭元素q1是最先被插入的元素，也是最先被刪除的元素。隊尾元素qn是最後被插入的元素，也是最後被刪除的元素。因此，與棧相反，佇列又稱為「先進先出」（first in first out，fifo）或「後進後出」（last in last out，lilo）的線性表。
（2）佇列運算
入隊運算是往佇列隊尾插入乙個資料元素。首先將隊尾指標加1（rear=rear+1），並當rear=m+1（m表示佇列的長度）時置rear=1；然後將新元素插入到指標指向的位置。
退隊運算是從佇列隊頭刪除乙個資料元素。首先將排頭指標加1（front=front+1），並當front=m+1（m表示佇列的長度）時置front=1；然後將排頭指標指向的元素賦給指定變數。
（3）迴圈佇列
在實際應用中，佇列的順序儲存結構一般採用佇列的形式。所謂迴圈佇列，就是將佇列儲存空間的最後乙個位置繞到第乙個位置，形成邏輯上的環狀空間。迴圈佇列s=0表示佇列空；s=1且front=rear表示佇列滿。
計算迴圈佇列的元素個數：「尾指標減頭指標」，若為負數，再加其容量即可。
1.6鍊錶（基礎，識記）
在鏈式儲存方式中，要求每個結點由兩個部分組成：一部分用於儲存資料元素值，稱為資料域；另一部分用於存放指標，稱為指標域。其中指標用於指向該結點的前乙個或後乙個結點（即前件或後件）。
（1）線性鍊錶
線性表的鏈式儲存結構稱為線性鍊錶。
**性煉表中，各資料元素結點的儲存空間可以是不連續的，且各資料元素的儲存順序與邏輯順序可以不一致。**性煉表中進行插入與刪除，不需要移動鍊錶中的元素。
在某些應用中，對線性鍊錶中的每個結點設定兩個指標，乙個稱為左指標，用以指向其前件結點；另乙個稱為右指標，用以指向其後件結點。這樣的表稱為雙向鍊錶。
線性單鏈表中，head稱為頭指標，head=null（或0）稱為空表。如果是雙向鍊錶的兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
公共基礎知識重點
第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依據。第二方面，是物質和意識是否具有同...
公共基礎知識
第一章資料結構與演算法 考點1 演算法的基本概念 演算法 是指一組有窮的指令集，是解題方 而完整的描述。演算法不等於程式，也不等於計算方法。演算法的基本特徵 確定性，演算法中每一步驟都必須有明確定義，不允許有多義性 有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止 可行性，演算法原...
公共基礎知識
公共基礎知識.txt花前月下，不如花錢 日 下。葉子的離開，是因為風的追求還是樹的不挽留？乾掉熊貓，我就是國寶！別和我談理想，戒了！1 制度化教育階段開始於 近代。2 各國的學校教育系統基本形成於 19世紀末。3 現在世界上大多數國家的義務教育年限在 9年或9年以上。4 不憤不啟，不悱不發 啟發教學...