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

CSP-J/S初賽知識(shí)點(diǎn)精講精練第二講

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

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

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

)返回棧頂?shù)闹?。a.empty(

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

)返回棧里的元素個(gè)數(shù)。例題二某個(gè)車(chē)站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車(chē)，并且只有一個(gè)出入口。已知某時(shí)刻該車(chē)站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”。假設(shè)車(chē)輛入站的順序?yàn)?，2，3，……，則車(chē)輛出站的順序?yàn)椋?/p>

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

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

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