0907《數(shù)據(jù)結(jié)構(gòu)》2023年6月期末考試指導(dǎo)

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

一、考試說明

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

二、復(fù)習(xí)重點(diǎn)內(nèi)容

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

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

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

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

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。4、數(shù)據(jù)結(jié)構(gòu)的二元組表示

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

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

算法具有以下五個(gè)特性：

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

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

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

1、線性鏈表基本概念

結(jié)點(diǎn)：數(shù)據(jù)元素及直接后繼的存儲(chǔ)位置（地址）組成一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，稱為一個(gè)結(jié)點(diǎn)；

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

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

頭指針：用于存放線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。假設(shè)L為鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)，若L為“空〞（L=NULL），則所表示的線性鏈表為“空〞表，其長(zhǎng)度n為“零〞。

1

頭結(jié)點(diǎn)：線性鏈表的第一元素結(jié)點(diǎn)前面的一個(gè)附加結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。2、線性表的順序存儲(chǔ)結(jié)構(gòu)

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

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

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

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

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

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

1、棧的定義及基本運(yùn)算

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

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

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

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

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

2

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

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

⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維的m*n數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：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)先順序存儲(chǔ)的。

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

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)先順序存儲(chǔ)的。2、對(duì)稱矩陣

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

對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能儉約近一半的存儲(chǔ)空間。

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

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

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

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

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

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