第一章資料結構與演算法
1.1 演算法
：是指解題方****而完整的描述。演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。
演算法的特徵包括：
（1）可行性；
（2）確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性。
（3）有窮性，演算法必須能在有限的時間內做完，包括合理的執行時間的含義；
（4）擁有足夠的情報。
演算法的基本要素：一是對資料物件的運算和操作；二是演算法的控制結構。
指令系統：乙個計算機系統能執行的所有指令的集合。
基本運算包括：算術運算、邏輯運算、關係運算、資料傳輸。
演算法的控制結構：。
演算法基本設計方法：列舉法、歸納法、遞推、遞迴、減鬥遞推技術、回溯法。
演算法複雜度：和。 兩個之間沒有聯絡的。
是指執行演算法所需要的計算工作量。即演算法執行過程中所需要的基本運算次數。通常，乙個演算法所用的時間包括編譯時間和執行時間
是指執行這個演算法所需要的記憶體空間。包括演算法程式所佔的空間，輸入的初始資料所佔的空間，演算法執行過程中所需的額外空間。
例題：演算法的時間複雜度取決於（ ）
a)問題的規模 b）待處理的資料的初態 c）問題的難度 d）a和b
答案：d
解析：演算法的時間複雜度不僅與問題的規模有關，而且與輸入資料有關，即輸入資料所有的可能取值範圍及輸入各種資料或資料集的概率有關。所以正確答案選d。
1.2 資料結構的基本概念
資料結構研究的三個方面：
（1）資料集合中各資料元素之間所固有的邏輯關係，即；
（2）在對資料進行處理時，各資料元素在計算機中的儲存關係，即；
（3）對各種資料結構進行的運算。
資料結構是指相互有關聯的資料元素的集合。
資料的邏輯結構應包含：
（1）表示資料元素的資訊；
（2）表示各資料元素之間的前後件關係(指邏輯關係，與儲存位置無關)。
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構,也稱資料物理結構。
資料的儲存結構有順序、鏈結、索引等。
線性結構條件：
（1）有且只有乙個根結點；
（2）每乙個結點最多有乙個前件，也最多有乙個後件。
非線性結構：不滿足線性結構條件的資料結構。
例題：1、資料的儲存結構是指（ ）
a）儲存在外存中的資料 b）資料所佔的儲存空間量
c）資料在計算機中的儲存順序方式 d）資料的邏輯結構在計算機中的表示
答案：d
解析：資料的儲存結構是指資料的邏輯結構在計算機儲存空間中的存放形式。
2、在資料結構中，與所使用的計算機無關的資料結構是（ ）
a）邏輯 b）儲存 c）邏輯與儲存 d）物理
答案：a
解析：資料的邏輯結構，是從實際出發，為實現特定的功能所建立的資料結構，用來描述資料元素之間的邏輯關係，它是面向問題的。
1．3 線性表及其順序儲存結構
是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為，
而由多個記錄構成的線性表又稱為。
非空線性表的結構特徵：
（1）且只有乙個根結點a1，它無前件；
（2）有且只有乙個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有乙個前件，也有且只有乙個後件。
結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序儲存結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的儲存空間是連續的；
（2）線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素ai的儲存位址為：adr(ai)=adr(a1)+(i-
adr(a1)為第乙個元素的位址，k代表每個元素佔的位元組數。
順序表的運算：查詢、插入、刪除。
1．4 棧和佇列
是限定在一端進行插入與刪除的線性表。
1、先進後出 filo;
1、支援子程式呼叫;
2、具有記憶功能；
3、可以不用順序存放資料；
4、只能夠在top首部進行操作，bottom是絕對不動的；
5、棧的存放資料的個數為 num = （bottom – top）+1；
其允許插入與刪除的一端稱為棧頂，用指標top表示棧頂位置。
不允許插入與刪除的另一端稱為棧底，用指標bottom表示棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織資料，棧具有記憶作用。
棧的儲存方式有順序儲存和鏈式儲存。
棧的基本運算：(1) 入棧運算，在棧頂位置插入元素；
(2) 退棧運算，刪除元素(取出棧頂元素並賦給乙個指定的變數)；
(3) 讀棧頂元素，將棧頂元素賦給乙個指定的變數，此時指標無變化。
是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。
1、rear指標指向隊尾，front指標指向隊頭。
3、先進先出fifo,或者是後進後出lilo
2、迴圈佇列裡面的個數計算方法：
a、rear > front 的時候， num = rear – front；
b、rear < front 的時候， num = rear + n – front；
用rear指標指向隊尾，用front指標指向隊頭元素的前乙個位置。
佇列是「先進先出」（fifo）或「後進後出」（lilo）的線性表。
佇列運算包括：(1) 入隊運算：從隊尾插入乙個元素； (2) 退隊運算：從隊頭刪除乙個元素。
佇列的順序儲存結構一般採用佇列迴圈的形式。
迴圈佇列s=0表示佇列空；s=1且front=rear表示佇列滿。
計算迴圈佇列的元素個數：「尾指標減頭指標」，若為負數，再加其容量即可。
1．5 線性鍊錶
資料結構中的每乙個結點對應於乙個儲存單元，這種儲存單元稱為儲存結點，簡稱。
結點由兩部分組成：（1）用於儲存資料元素值，稱為；（2）用於存放指標，稱為用於指向前乙個或後乙個結點。
在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
鏈式儲存方式即可用於表示線性結構，也可用於表示非線性結構。
線性單鏈表中，head稱為頭指標，head=null（或0）稱為空表。
如果是雙項鍊表的兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點
線性鍊錶的基本運算：查詢、插入、刪除。
例題：鍊錶不具備的特點是（ ）
a）可隨機訪問任意乙個節點 b）插入和刪除不需要移動任何元素
c）不必事先估計儲存空間 d）所需空間與其長度成正比
答案：a
解析：鍊錶的優點是在進行插入和刪除運算時，只需要改變指標即可，不需要移動元素，當儲存空間不足時，可以動態為其分配記憶體空間，所以不必估計儲存空間的大小。順序表可以隨機訪問任意乙個結點，而鍊錶必須從第乙個資料結點出發，逐一查詢每個結點。
所以正確答案為a。
1．6 樹與二叉樹
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，沒有前件的結點只有乙個，稱為樹的根結點，簡稱樹的根。
每乙個結點可以有多個後件，稱為該結點的子結點。
沒有後件的結點稱為葉子結點。
在樹結構中，乙個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
的特點：（1）非空二叉樹只有乙個根結點；（2）每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：必考的題目
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多乙個；
例題：一棵二叉樹中共有70個葉子結點與80個度為1的結點，則該二叉樹中的總結點數為（ ）
a）219 b）221 c)229 d）231
答案為a，根據性質3，度為0的結點（即葉子結點）總是必度為2的結點多乙個，故度為2的結點數為69個，所以共有結點69+80+70=219個，故選a
（4）二叉樹中 n = n0 +n1 +n2
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分
(5) 具有n個結點的完全二叉樹的深度為[log2n]+1；
(6) 設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1,2,…n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則k結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
補充：增加度為1的結點不會影響二叉樹的葉子結點數，每增加乙個度為2的結點便會增加
乙個葉子結點，沒有度為2的結點時葉子結點數為1。
已知完全二叉樹有x個結點，求其葉子結點數：
①確定層數為k； ②第k層的結點數y=x-(2 k-1-1)；
③第k-1層的葉子結點數n=2 (k-1)-1-y/2《若y/2有餘，則要加1>； ④最後y+n。
是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹儲存結構採用，對於滿二叉樹與完全二叉樹可以按層序進行順序儲存。
二叉樹的遍歷：（一般畫個圖要你把順序寫出來）
（1）（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；（樹根在第一，下走不跳結點）
（2）（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；（有左先左，再尋根，後找右。最左邊的結點最先遍歷，最右邊的結點最後遍歷）
（3）（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。（有左先左，再找右，後尋根，到最右一路上行，樹根在最後）
小結：邏輯結構可分為線性表和非線性表。
線性表包括棧、佇列，其儲存方式為順序儲存、鏈式儲存均可。鏈式型有：線性鍊錶，帶鏈的棧，帶鏈的佇列，迴圈鍊錶等。
公共基礎知識考點彙總
1 公文寫作的語言運用 公文語言的特點 莊重 準確 樸實 精練 嚴謹 規範。公文中需用歷史年號時，要先標出公曆年份，再注歷史年號並加圓括號，如1912年 元年 數量表示時，表示增加時用倍數或分數，表示減少時只能用分數。2 各種文種的撰寫 1 規範性公文。規範性公文一般包括檔案標題 發布或通過或批准的...
2019公共基礎知識全面彙總
2011公共基礎知識教材考點總結 第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依...
公共基礎知識
第一章資料結構與演算法 考點1 演算法的基本概念 演算法 是指一組有窮的指令集，是解題方 而完整的描述。演算法不等於程式，也不等於計算方法。演算法的基本特徵 確定性，演算法中每一步驟都必須有明確定義，不允許有多義性 有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止 可行性，演算法原...