0907《數(shù)據(jù)結構》2023年6月期末考試指導

本文格式為Word版，下載可任意編輯——0907《數(shù)據(jù)結構》2023年6月期末考試指導0907《數(shù)據(jù)結構》2023年6月期末考試指導

一、考試說明

本課程為閉卷考試，總分值100分，考試時間90分鐘。考試題型如下：1、選擇題（每題4分，共10題）2、填空題（每題4分，共5題）3、主觀題（40分）

二、復習重點內容

第一章緒論1、數(shù)據(jù)

數(shù)據(jù)是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2、數(shù)據(jù)元素和數(shù)據(jù)對象

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中尋常作為一個整體進行考慮和處理。數(shù)據(jù)對象是性質一致的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。3、數(shù)據(jù)的規(guī)律結構和存儲結構

數(shù)據(jù)之間的相互關系稱為規(guī)律結構。尋常分為集合、線性結構、樹型結構、圖狀結構或網(wǎng)狀結構四類基本結構

數(shù)據(jù)結構在計算機中的表示稱為數(shù)據(jù)的物理結構，又稱為存儲結構。4、數(shù)據(jù)結構的二元組表示

數(shù)據(jù)結構的形式定義為，數(shù)據(jù)結構是一個二元組：Data-Structure=(D，S)

其中：D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。5、算法的特性

算法具有以下五個特性：

（1）有窮性：一個算法必需總是在執(zhí)行有窮步之后終止，且每一步都在有窮時間內完成。（2）確定性：算法中每一條指令必需有確鑿的含義。不存在二義性。且算法只有一個入口和一個出口。

（3）可行性：一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

（4）輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。（5）輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。其次章線性表

1、線性鏈表基本概念

結點：數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結構，稱為一個結點；

結點的數(shù)據(jù)域：結點中用于保存數(shù)據(jù)元素的部分；

結點的指針域：結點中用于保存數(shù)據(jù)元素直接后繼存儲地址的部分；空指針：不指向任何結點，線性鏈表最終一個結點的指針尋常是指針。

頭指針：用于存放線性鏈表中第一個結點的存儲地址。假設L為鏈表的頭指針，它指向表中第一個結點，若L為“空〞（L=NULL），則所表示的線性鏈表為“空〞表，其長度n為“零〞。

1

頭結點：線性鏈表的第一元素結點前面的一個附加結點，稱為頭結點。2、線性表的順序存儲結構

把線性表的結點按規(guī)律順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。

假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第I+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(aI)之間滿足以下關系：LOC(ai+1)=LOC(ai)+l

線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(ai)=LOC(a1)+(I-1)*l

由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。3、線性鏈表

鏈表是指用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內存中的任意位置上的。因此，鏈表中結點的規(guī)律次序和物理次序不一定一致。為了能正確表示結點間的規(guī)律關系，在存儲每個結點值的同時，還必需存儲指示其后繼結點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結點結構：（data,next）

其中：data域是數(shù)據(jù)域，用來存放結點的值。next是指針域（亦稱鏈域），用來存放結點的直接后繼的地址（或位置）。鏈表正是通過每個結點的鏈域將線性表的n個結點按其規(guī)律次序鏈接在一起的。由于上述鏈表的每一個結只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。第三章棧和隊列

1、棧的定義及基本運算

棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，尋常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當表中沒有元素時稱為空棧。

假設棧S=(a1，a2，a3，?an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，?an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的，只能在棧頂插入和刪除元素。因此，棧稱為后進先出表（LIFO）。2、隊列的定義及基本運算

隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。

先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(FirstInFirstOut)的線性表，簡稱FIFO表。當隊列中沒有元素時稱為空隊列。在空隊列中依次參與元素a1,a2,?an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,?an，也就是說隊列的修改是依先進先出的原則進行的。第四章串1、串定義

串(String)是零個或多個字符組成的有限序列。一般記作S=“a1a2a3?an〞，其中S是串名，雙引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符。尋常將僅由一個或多個空格組成的串稱為空白串(BlankString)。要注意空串和空白串的不同，例如“〞和“〞分別表示長度為1的空白串和長度為0的空串。第五章數(shù)組和廣義表

2

1、數(shù)組的順序存儲方式

數(shù)組尋常有兩種順序存儲方式：

⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維的m*n數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a(0,0),a(0,1),…,a(0,n-1),a(1,0),a(1,1),…a(1,n-1),……,a(m-1,0),a(m-1,1),…,a(m-1,n-1)在PASCAL、C語言中，數(shù)組就是按行優(yōu)先順序存儲的。

⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列優(yōu)先順序存儲的線性序列為：

a(0,0),a(1,0),?,a(m-1,0),a(0,1),a(1,1),?a(m-1,1),??,a(0,n-1),a(1,n-1),?,a(m-1,n-1)在FORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。2、對稱矩陣

在一個n階方陣A中，若元素滿足下述性質：aij=aji0≦i,j≦n-1則稱A為對稱矩陣。

對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能儉約近一半的存儲空間。

(1).若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+?+i=i(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai2,?,aij-1），因此有：

k=i*(i+1)/2+j0≦k=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。

這也是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二查樹不是樹的特別狀況，它們是兩個概念。2、樹的存儲結構(1).雙親表示法

在樹中，除根結點沒有雙親外，其他每個結點的雙親是唯一確定的。(2).孩子表示法

采用孩子表示法表示一棵樹時，樹中每個結點除了存儲其自身的值之外，還必需指出其所有子女的位置。(3).孩子兄弟表示法

所謂孩子兄弟表示法，即在存儲樹中每個結點時，除了包含該結點值域外，還設置兩個指針域firstchild和rightsibling，分別指向該結點的第一個子女和其右兄弟，即以二叉鏈表方式加以存儲，因此該方法也常被稱為二叉