高中 CSP初試精講精練 第二節(jié) 數(shù)據(jù)結構（基礎）

CSP-J/S初賽知識點精講精練第二講

數(shù)據(jù)結構基礎04九月2024線性表線性結構在數(shù)據(jù)元素存在非空有限集中：存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素。存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素。除了第一個外，集合中每個數(shù)據(jù)元素都只有一個前趨元素。除了最后一個外，集合中每個數(shù)據(jù)元素都只有一個后繼元素。線性表線性表有n個數(shù)據(jù)元素的有限序列，同一個線性表中的元素必定有相同特性，元素之間存在序偶關系。線性表中的元素個數(shù)n(n>=0)定義為該表的長度，當n==0時稱為空表，非空表中每個數(shù)據(jù)元素都有一個確定的位置。線性表是一個相當靈活的數(shù)據(jù)結構，它的長度可以根據(jù)需要增長或縮短。線性表線性表(List)有n個數(shù)據(jù)元素的有限序列，同一個線性表中的元素必定有相同特性，元素之間存在序偶關系。線性表中的元素個數(shù)n(n>=0)定義為該表的長度，當n==0時稱為空表，非空表中每個數(shù)據(jù)元素都有一個確定的位置。線性表是一個相當靈活的數(shù)據(jù)結構，它的長度可以根據(jù)需要增長或縮短。依據(jù)存儲結構不同的分類順序存儲結構的順序表鏈式存儲結構的鏈表（單鏈表、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表）線性表線性表的特點：1.數(shù)據(jù)元素的個數(shù)n定義為表的長度。2.n=0時為空表。3.將非空的線性表(n>0)記作：(a1,a2,…an)4.數(shù)據(jù)元素ai(1<=i<=n)只是一個抽象的符號，其具體含義在不同情況下不同。5.同一線性表中的元素必定具有相同特性，數(shù)據(jù)元素間的關系是線性關系。線性表是典型的線性結構。順序表概念：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，這種存儲結構的線性表稱為順序表。特點：邏輯上相鄰的數(shù)據(jù)元素，物理次序也是相鄰的。只要確定好了存儲線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機存取，所以線性表的順序存儲結構是一種隨機存取的儲存結構，因為高級語言中的數(shù)組類型也是有隨機存取的特性，所以通常我們都使用數(shù)組來描述數(shù)據(jù)結構中的順序儲存結構，用動態(tài)分配的一維數(shù)組表示線性表。順序表的優(yōu)缺點優(yōu)點：無須為表中元素之間的邏輯關系而增加額外的存儲空間；可以快速存取表中任一位置元素。缺點：插入和刪除操作需要移動大量元素；當線性表長度較大時，難以確定存儲空間的容量；造成存儲空間的“碎片”。鏈表在鏈式結構中，除了要存儲數(shù)據(jù)元素的信息外，還要存儲它的后繼元素的存儲地址。因此，為了表示每個數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關系，對數(shù)據(jù)ai來說，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像，稱為結點（Node）。例題一鏈表不具有的特點是（

）A.插入刪除不需要移動元素B.不必事先估計存儲空間C.所需空間與線性表長度成正比D.可隨機訪問任一元素D棧與隊列棧（Stack）支持push與pop兩種操作的數(shù)據(jù)結構。從頂端放入，從頂端取出。最后入棧的數(shù)據(jù)最先被取出，被稱為LastInFirstOut，簡稱LIFO表。棧頂：棧最頂端的元素。棧底：棧最底端的元素。棧與隊列棧（Stack）<stack>頭文件stack<int>a聲明int型棧aa.push(x)往棧頂前添加一個元素x。a.pop(

)從棧頂彈出（刪除）一個元素。a.top(

)返回棧頂?shù)闹怠.empty(

)返回是否為空。（1為空，0為非空）a.size(

)返回棧里的元素個數(shù)。例題二某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進，出，進，進，進，出，出，進，進，進，出，出”。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（

）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2C棧與隊列隊列（Queue）支持push與pop兩種操作的數(shù)據(jù)結構。從隊尾放入，從隊首取出。最初放入的數(shù)據(jù)最先被取出，被稱為FirstInFirstOut，簡稱FIFO表。隊首/隊頭：隊列的第一項。隊尾：隊列的最后一項。棧與隊列隊列（Queue）<queue>頭文件queue<int>a聲明int型隊列aa.push(x)往隊尾后添加一個元素x。a.pop()從隊首彈出（刪除）一個元素。a.front()返回隊首的值。a.back()返回隊尾的值。a.empty()返回是否為空。（1為空，0為非空）a.size()返回隊列里的元素個數(shù)。樹樹是n（n>=0）個結點的有限集。當n=0時，稱為空樹。在任意一棵非空樹中應滿足：有且僅有一個特定的稱為根的結點。當n>1時，其余節(jié)點可分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。樹父親（parentnode）：對于除根以外的每個結點，定義為從該結點到根路徑上的第二個結點。根結點沒有父結點。祖先（ancestor）：一個結點到根結點的路徑上，除了它本身外的結點。根結點的祖先集合為空。子結點（childnode）：如果u是v的父親，那么v是u的子結點。子結點的順序一般不加以區(qū)分，二叉樹是一個例外。在分支結點中,每個結點的分支數(shù)就是該結點的度。度為0(沒有子女結點)的結點稱為葉子結點(又稱終端結點)。結點的深度（depth）：到根結點的路徑上的邊數(shù)。樹的高度（height）：所有結點的深度的最大值。兄弟（sibling）：同一個父親的多個子結點互為兄弟。后代（descendant）：子結點和子結點的后代。子樹（subtree）：刪掉與父親相連的邊后，該結點所在的子圖。二叉樹二叉樹：所有結點的子節(jié)點個數(shù)都不超過二的樹。常常對兩個子結點的順序加以區(qū)分，分別稱之為左子結點和右子結點。完整二叉樹（full/properbinarytree）：每個結點的子結點數(shù)量均為0或者2的二叉樹。換言之，每個結點或者是樹葉，或者左右子樹均非空。完全二叉樹（completebinarytree）：只有最下面兩層結點的度數(shù)可以小于2，且最下面一層的結點都集中在該層最左邊的連續(xù)位置上。完美二叉樹（perfectbinarytree）：所有葉結點的深度均相同，且所有非葉節(jié)點的子節(jié)點數(shù)量均為2的二叉樹稱為完美二叉樹。例題三一棵二叉樹如圖所示，若采用順序存儲結構，即用一維數(shù)組元素存儲該二叉樹中的結點（根結點的下標為1,若某結點的下標為i,則其左孩子位于下標2i處、右孩子位于下標2i+1處），則該數(shù)組的最大下標至少為（

）。A.6B.10C.15D.12CDFS深度優(yōu)先搜索深度優(yōu)先搜索算法（DepthFirstSearch，簡稱DFS）：一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當節(jié)點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。整個進程反復進行直到所有節(jié)點都被訪問為止。屬于盲目搜索,最糟糕的情況算法時間復雜度為O(!n)。二叉樹的DFS包括：先序遍歷、中序遍歷、后序遍歷DFS深度優(yōu)先搜索DFS：先序遍歷按照根，左，右的順序遍歷二叉樹。DFS深度優(yōu)先搜索DFS：中序遍歷按照左，根，右的順序遍歷二叉樹。DFS深度優(yōu)先搜索DFS：后序遍歷按照左，右，根的順序遍歷二叉樹。例題四DFS反推根據(jù)先序遍歷，寫出其余兩種遍歷。先序遍歷：ABDEHCFGI

例題四DFS反推根據(jù)先序遍歷，寫出其余兩種遍歷。BFS廣度優(yōu)先從樹根開始，嚴格按照層次來訪問節(jié)點。BFS過程中也可以順便求出各個節(jié)點的深度和父親節(jié)點。樹的層序遍歷樹層序遍歷是指按照從根節(jié)點到葉子節(jié)點的層次關系，一層一層的橫向遍歷各個節(jié)點。根據(jù)BFS的定義可以知道，BFS所得到的遍歷順序就是一種層序遍歷。但層序遍歷要求將不同的層次區(qū)分開來，所以其結果通常以二維數(shù)組的形式表示。下圖的樹的層序遍歷的結果是[[1],[2,3,4],[5,6]]（每一層從左向右）圖圖(graph)是一個二元組G=(V(G),E(G))。其中V(G)是非空集，稱為點集(vertexset)，對于V中的每個元素，我們稱其為頂點(vertex)或節(jié)點(node)，簡稱點；E(G)為V(G)各結點之間邊的集合，稱為邊集(edgeset)，對于E中的每個元素，我們稱其為邊(Edge)。常用G=(V,E)表示圖。圖完全圖：任意兩點都有邊相連，一個n個節(jié)點完全圖的邊數(shù)為Cn2簡單路徑：兩點之間通過不重復的邊相連。連通圖：任意兩點都