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

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

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

3、序:重點(diǎn)難點(diǎn)章節(jié)，問答各種排序算法的排序過程重點(diǎn)難點(diǎn)章節(jié)，問答各種排序算法的排序過程二、各章節(jié)的主要內(nèi)容：第一章概述主要內(nèi)容：主要內(nèi)容：本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。大家主要注意以下幾點(diǎn):（1）數(shù)據(jù)結(jié)構(gòu)的基本概念。（數(shù)據(jù)；數(shù)據(jù)元素；數(shù)據(jù)項(xiàng)；數(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ù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)；

4、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)；運(yùn)算）（2）算法的度量：時(shí)間效率和空間效率，分別用時(shí)間復(fù)雜度和空間復(fù)雜度度量，掌握時(shí)間復(fù)雜度的度量掌握時(shí)間復(fù)雜度的度量方法量方法。方法量方法。（大（大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、表，棧，隊(duì)列和二叉樹四種數(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、程序段的時(shí)間復(fù)雜度是_______。f(i=1inext=PnextPnext=SBPnext=SnextSnext=P；CPnext=PPnext=S；DPnext=SSnext=P；6、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為（）A

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

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

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