數(shù)據(jù)結(jié)構(gòu)知識點歸納

1、一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點構(gòu)成一、數(shù)據(jù)結(jié)構(gòu)的章節(jié)結(jié)構(gòu)及重點構(gòu)成數(shù)據(jù)結(jié)構(gòu)學科的章節(jié)劃分基本上為:概論，線性表，棧和隊列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動態(tài)存儲分配。對于絕大多數(shù)的學校而言，“外排，文件，動態(tài)存儲分配”三章基本上是不考的，在大多數(shù)高校的計算機本科教學過程中，這三章也是基本上不作講授的。數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：1.概論:概念，時間復雜度。2.線性表線性表:基礎章節(jié)，必考內(nèi)容之一。概念，算法設

2、計題?；A章節(jié)，必考內(nèi)容之一。概念，算法設計題。3.棧和隊列:基本概念。4.串:基本概念。5.多維數(shù)組及廣義表:基本概念。6.樹和二叉樹樹和二叉樹:重點難點章節(jié)，各校必考章節(jié)。概念，問答，算法設計題。重點難點章節(jié)，各校必考章節(jié)。概念，問答，算法設計題。7.圖:重點難點章節(jié)，各校必考章節(jié)。概念，問答，算法設計題。重點難點章節(jié)，各校必考章節(jié)。概念，問答，算法設計題。8.查找查找:重點難點章節(jié)，概念，問答。重點難點章節(jié)，概念，問答。9.排序排

3、序:重點難點章節(jié)，問答各種排序算法的排序過程重點難點章節(jié)，問答各種排序算法的排序過程二、各章節(jié)的主要內(nèi)容：第一章概述主要內(nèi)容：主要內(nèi)容：本章主要起到總領作用，為讀者進行數(shù)據(jù)結(jié)構(gòu)的學習進行了一些先期鋪墊。大家主要注意以下幾點:（1）數(shù)據(jù)結(jié)構(gòu)的基本概念。（數(shù)據(jù)；數(shù)據(jù)元素；數(shù)據(jù)項；數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)的邏輯結(jié)構(gòu)：線性和非線性，數(shù)據(jù)的邏輯結(jié)構(gòu)：線性和非線性，具體分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)：順序存儲和鏈式存儲；

4、順序存儲和鏈式存儲；運算）（2）算法的度量：時間效率和空間效率，分別用時間復雜度和空間復雜度度量，掌握時間復雜度的度量掌握時間復雜度的度量方法量方法。方法量方法。（大（大O表示法）表示法）參考題目：參考題目：填空題：1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（）和（）。2、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（）和（）3.數(shù)據(jù)的物理結(jié)構(gòu)主要包括（）和（）兩種情況。4線性

5、表，棧，隊列和二叉樹四種數(shù)據(jù)結(jié)構(gòu)中（）是非線性結(jié)構(gòu)，（）是線性結(jié)構(gòu)。5、線性結(jié)構(gòu)中元素之間存在（）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（）關(guān)系。6、程序段的時間復雜度是_______。f(i=1inext=PnextPnext=SBPnext=SnextSnext=P；CPnext=PPnext=S；DPnext=SSnext=P；6、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點，其算法所需的時間復雜度為（）A

6、Ｏ（1）BＯ（log2n）CO（n）DO（n2）7、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前趨，若在p，q之間插入s結(jié)點，則執(zhí)行的操作是（）。Asnext=pnextpnext=sBqnext=ssnext=pCpnext=snextsnext=pDpnext=ssnext=q8、設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中（）個數(shù)據(jù)元素，刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數(shù)是（）

7、。在順序表中插入一個元素，需要平均移動（）元素，刪除一個元素，需要平均移動（）元素，具體移動的元素個數(shù)與（）有關(guān)，插入刪除操作的時間復雜度均為()。9、設單鏈表的結(jié)點結(jié)構(gòu)為(datanext)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句:（）。10設指針變量p指向單鏈表中結(jié)點A的前驅(qū)結(jié)點，若刪除單鏈表中結(jié)點A，則執(zhí)行操作（）三、算法設計：1.

8、設計算法，計算順序表中數(shù)據(jù)元素為x的元素個數(shù)。順序表結(jié)構(gòu)如下：typedefstructintdata[100]intlengthsqlist函數(shù)首部為：intcount(sqlistLintx)2設計算法，在順序線性表中，刪除順序表中第i個元素，順序表結(jié)構(gòu)同上題。函數(shù)首部為：intdel(sqlistLinti)3設計算法，在順序線性表中，刪除值為x的元素。函數(shù)首部為：voiddelx(sqlistLintx)4.對給定的單鏈表L(元