《數(shù)據(jù)結(jié)構(gòu)》說課稿（最終五篇）

《數(shù)據(jù)結(jié)構(gòu)》說課稿（最終五篇）第一篇：《數(shù)據(jù)結(jié)構(gòu)》說課稿《數(shù)據(jù)結(jié)構(gòu)》“最短路徑”問題說課稿一、教材分析1、特點與地位：重點中的重點。本課是教材《數(shù)據(jù)結(jié)構(gòu)》第六章第五節(jié)的內(nèi)容。圖是一種典型的非線性數(shù)據(jù)結(jié)構(gòu)，應(yīng)用十分廣泛。求兩結(jié)點之間的最短路徑問題是圖最常見的應(yīng)用的之一，在交通運輸、通訊網(wǎng)絡(luò)等方面具有一定的實用意義。2、重點與難點：根據(jù)高職數(shù)據(jù)結(jié)構(gòu)教育要求，理論“必需，夠用”，側(cè)重于某項技術(shù)的理論依據(jù)，重點放在技能培養(yǎng)上。結(jié)合學(xué)生現(xiàn)有抽象思維能力水平，已掌握基本概念等學(xué)情，以及求解最短路徑問題的自身特點，確立本課的重點和難點如下：（1）重點：如何將現(xiàn)實問題抽象成求解最短路徑問題，以及該問題的解決方案。（2）難點：求解最短路徑算法的程序?qū)崿F(xiàn)。3、教學(xué)安排：最短路徑問題包含兩種情況：一種是求從某個源點到其他各結(jié)點的最短路徑，另一種是求每一對結(jié)點之間的最短路徑。根據(jù)教學(xué)大綱安排，重點講解第一種情況問題的解決。安排一個課時講授。教材直接分析算法，考慮實際應(yīng)用需要，補充旅游景點線路選擇的實例，實例中問題解決與算法分析相結(jié)合，逐步推動教學(xué)過程。二、教學(xué)目標(biāo)分析1、知識目標(biāo)：掌握最短路徑概念、能夠求解最短路徑。2、能力目標(biāo)：（1）通過將旅游景點線路選擇問題抽象成求最短路徑問題，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。（2）通過旅游景點線路選擇問題的解決，培養(yǎng)學(xué)生的獨立思考、分析問題、解決問題的能力。（3）通過算法的程序?qū)崿F(xiàn)，提高學(xué)生的編程能力。3、素質(zhì)目標(biāo)：培養(yǎng)學(xué)生講究工作方法、與他人合作，提高工作效率的職業(yè)素質(zhì)。三、教法分析課前充分準(zhǔn)備，研讀教材，查閱相關(guān)資料，制作多媒體課件。教學(xué)過程中除了使用傳統(tǒng)的“講授法”以外，主要采用“案例教學(xué)法”，同時輔以多媒體課件，以啟發(fā)的方式展開教學(xué)。由于本節(jié)課的內(nèi)容屬于圖這一章的難點，考慮學(xué)生的接受能力，注意與學(xué)生溝通，根據(jù)學(xué)生的反應(yīng)控制好教學(xué)進度是本節(jié)課成功的關(guān)鍵。四、學(xué)法指導(dǎo)1、課前上次課結(jié)課時給學(xué)生布置任務(wù)，使其有針對性的預(yù)習(xí)。2、課中指導(dǎo)學(xué)生討論任務(wù)解決方法，引導(dǎo)學(xué)生分析本節(jié)課知識點。3、課后給學(xué)生布置同類型任務(wù)，加強練習(xí)。五、教學(xué)過程分析（一）課前復(fù)習(xí)（3~5分鐘）回顧“路徑”的概念，為引出“最短路徑”做鋪墊。教學(xué)方法及注意事項：（1）采用提問方式，注意及時小結(jié)，提問的目的是幫助學(xué)生回憶概念。（2）提示學(xué)生“溫故而知新”，養(yǎng)成良好的學(xué)習(xí)習(xí)慣。（二）導(dǎo)入新課（3~5分鐘）以城市公路網(wǎng)為例，基于求兩個點間最短距離的實際需要，引出本課教學(xué)內(nèi)容“求最短路徑問題”。教學(xué)方法及注意事項：（1）先講實例，再指出概念，既可以吸引學(xué)生注意力，激發(fā)學(xué)習(xí)興趣，又可以實現(xiàn)教學(xué)內(nèi)容的自然過渡。（2）此處使用案例教學(xué)法，不在于問題的求解過程，只是為了說明問題的存在，所以這里的例子只需要概述，能夠說明問題即可。（三）講授新課（25~30分鐘）1、求某一結(jié)點到其他各結(jié)點的最短路徑（重點）主要采用案例教學(xué)法，提出旅游景點選擇的例子，解決如何選擇代價小、景點多的路線。（1）將實際問題抽象成圖中求任一結(jié)點到其他結(jié)點最短路徑問題。（3~5分鐘）教學(xué)方法及注意事項：①主要采用講授法，將實際問題用圖形表示出來。語言描述轉(zhuǎn)換的方法（用圓圈加標(biāo)號表示某一景點，用箭頭表示從某景點到其他景點是否存在旅游線路，并且將旅途費用寫在箭頭的旁邊。）一邊用語言描述，一邊在黑板上畫圖。②注意示范畫圖只進行一部分，讓學(xué)生獨立思考、自主完成余下部分的轉(zhuǎn)化。③及時總結(jié)，原型抽象（景點作為圖的結(jié)點，景點間的線路作為圖的邊，旅途費用作為邊的權(quán)值），將案例求解問題抽象成求圖中某一結(jié)點到其他各結(jié)點的最短路徑問題。④利用多媒體課件，向?qū)W生展示一張帶權(quán)有向圖，并略作解釋，為后續(xù)教學(xué)做準(zhǔn)備。（2）迪杰斯特拉算法（難點）（17~20分鐘）先講算法思想，主要采用多媒體教學(xué)。教學(xué)方法及注意事項：①充分利用課件。將教材中的算法思想細(xì)化，分步解釋給學(xué)生。用投影儀演示給學(xué)生看，在有限的時間內(nèi)，學(xué)生一邊看投影儀上的文字，一邊聽教師的分析，提高教學(xué)效率。注意講解后給學(xué)生留出適當(dāng)?shù)乃伎紩r間。②利用FLASH動畫，結(jié)合第一步案例中抽象出的有向帶權(quán)圖、算法思想，求解答案。幫助學(xué)生進一步理解算法思想。再講算法實現(xiàn)，主要采用啟發(fā)式教學(xué)。教學(xué)方法及注意事項：①啟發(fā)式教學(xué)，如何在計算機中實現(xiàn)上述算法呢？如何實現(xiàn)按路徑長度遞增產(chǎn)生最短路徑？如何記錄求解過程中每一步當(dāng)前的V0到Vi的最短路徑呢？引入dist[]數(shù)組。②結(jié)合案例分析求解最短路徑過程中dist[]數(shù)組的變化過程。（重點）注意此處最好借助黑板，按照算法思想的步驟，逐步修改dist[]數(shù)組。同樣，也是只示范一部分，余下部分由學(xué)生獨立思考完成。③程序代碼的講解，注重思路，淡化語言。本課程不是語言課，對于實現(xiàn)語言不做要求，鼓勵學(xué)生自己動手將教材提供程序做適當(dāng)修改，用C++實現(xiàn)，培養(yǎng)他們的編程能力。2、求每一對結(jié)點之間的最短路徑（5~6分鐘）兩種思路：一種重復(fù)執(zhí)行n次Dijkstra算法，另一種弗洛伊德（Floyed）算法。教學(xué)方法及注意事項：此處只介紹算法思想，算法實現(xiàn)給學(xué)生作為拓展內(nèi)容，自由把握。（四）課堂小結(jié)（3~5分鐘）1、明確本節(jié)課重點Dijkstra算法，及算法實現(xiàn)的輔助數(shù)組dist[]的變化過程。2、提示學(xué)生，在案例中數(shù)據(jù)抽象時，用結(jié)點表示活動，用有向邊便是活動之間的優(yōu)先關(guān)系，這種方式形成的圖又可以解決哪類實際問題呢？引導(dǎo)學(xué)生預(yù)習(xí)，為下次課的學(xué)習(xí)埋下伏筆。（五）布置作業(yè)（1~2分鐘）1、書面作業(yè)：P1746.72、復(fù)習(xí)本次課內(nèi)容，預(yù)習(xí)下次課內(nèi)容。至此，整個教學(xué)過程結(jié)束，注意留出1~3分鐘機動時間，準(zhǔn)備一道備用習(xí)題，靈活把握時間安排。六、教學(xué)特色以旅游路線選擇為主線，靈活采用案例教學(xué)、示范教學(xué)、多媒體課件等多種手段輔助教學(xué)，使枯燥的理論講解生動起來。在順利開展教學(xué)的同時，體現(xiàn)所講內(nèi)容的實用性，提高學(xué)生的學(xué)習(xí)興趣。第二篇：數(shù)據(jù)結(jié)構(gòu)實驗：線性表的基本操作【實驗?zāi)康摹繉W(xué)習(xí)掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的設(shè)計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法?！緦嶒瀮?nèi)容】1.順序表的實踐1)建立4個元素的順序表s=sqlist[]={1，2，3，4，5}，實現(xiàn)順序表建立的基本操作。2)在sqlist[]={1，2，3，4，5}的元素4和5之間插入一個元素9，實現(xiàn)順序表插入的基本操作。3)在sqlist[]={1，2，3，4，9，5}中刪除指定位置（i=5）上的元素9，實現(xiàn)順序表的刪除的基本操作。2.單鏈表的實踐3.1)建立一個包括頭結(jié)點和4個結(jié)點的（5，4，2，1）的單鏈表，實現(xiàn)單鏈表建立的基本操作。2)將該單鏈表的所有元素顯示出來。3)在已建好的單鏈表中的指定位置（i=3）插入一個結(jié)點3，實現(xiàn)單鏈表插入的基本操作。4)在一個包括頭結(jié)點和5個結(jié)點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結(jié)點，實現(xiàn)單鏈表刪除的基本操作。5)實現(xiàn)單鏈表的求表長操作?！緦嶒灢襟E】1.打開VC++。2.建立工程：點File->New，選Project標(biāo)簽，在列表中選Win32ConsoleApplication，再在右邊的框里為工程起好名字，選好路徑，點OK->finish。至此工程建立完畢。3.創(chuàng)建源文件或頭文件：點File->New，選File標(biāo)簽，在列表里選C++SourceFile。給文件起好名字，選好路徑，點OK。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。4．寫好代碼5．編譯－＞鏈接－＞調(diào)試【實驗心得】線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中，碰到的第一個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。通過學(xué)習(xí)我知道了對線性表進行建立、插入、刪除，同時單鏈表也是進行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復(fù)雜度均為0（n）.通過這次的學(xué)習(xí)，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念?？傊@次實驗我找到了自己的不足之處，以后會努力的。實驗二：棧的表示與實現(xiàn)及棧的應(yīng)用【實驗?zāi)康摹浚?）掌握棧的順序存儲結(jié)構(gòu)及其基本操作的實現(xiàn)。（2）掌握棧后進先出的特點，并利用其特性在解決實際問題中的應(yīng)用。（3）掌握用遞歸算法來解決一些問題。【實驗內(nèi)容】1.編寫程序，對于輸入的任意一個非負(fù)十進制整數(shù)，輸出與其等值的八進制數(shù)。2.編寫遞歸程序，實現(xiàn)N！的求解。3.編寫遞歸程序，實現(xiàn)以下函數(shù)的求解。n,n0,1Fib(n)Fib(n1)Fib(n2),n14.編寫程序，實現(xiàn)Hanoi塔問題?！緦嶒灢襟E】1.打開VC++。2.建立工程：點File->New，選Project標(biāo)簽，在列表中選Win32ConsoleApplication，再在右邊的框里為工程起好名字，選好路徑，點OK->finish。至此工程建立完畢。3.創(chuàng)建源文件或頭文件：點File->New，選File標(biāo)簽，在列表里選C++SourceFile。給文件起好名字，選好路徑，點OK。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。4．寫好代碼5．編譯－＞鏈接－＞調(diào)試【實驗心得】通過這次的學(xué)習(xí)我掌握了棧這種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應(yīng)地，表頭端稱為棧底（botton）；棧又稱為后進先出（LastInFirstOut）的線性表,簡稱LIFO結(jié)構(gòu)，因為它的修改是按后進先出的原則進行的。加上這個實驗，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學(xué)習(xí)有很大的作用，可以說這是學(xué)習(xí)以后知識的總要基礎(chǔ)。實驗三：二叉樹的建立及遍歷【實驗?zāi)康摹浚?）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法?！緦嶒瀮?nèi)容】1.編寫程序，實現(xiàn)二叉樹的建立，并實現(xiàn)先序、中序和后序遍歷。如：輸入先序序列abc###de###，則建立如下圖所示的二叉樹。并顯示其先序序列為：abcde中序序列為：cbaed后序序列為：cbeda【實驗步驟】1.打開VC++。2.建立工程：點File->New，選Project標(biāo)簽，在列表中選Win32ConsoleApplication，再在右邊的框里為工程起好名字，選好路徑，點OK->finish。至此工程建立完畢。3.創(chuàng)建源文件或頭文件：點File->New，選File標(biāo)簽，在列表里選C++SourceFile。給文件起好名字，選好路徑，點OK。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。4．寫好代碼5．編譯－＞鏈接－＞調(diào)試【實驗心得】這次試驗是關(guān)于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實驗中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數(shù)的計算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗不太好做，期間出現(xiàn)了很多邏輯錯誤，變量初始化的問題等，不過經(jīng)過仔細(xì)排查最后都一一解決了。實驗四：查找與排序【實驗?zāi)康摹浚?）掌握折半查找算法的實現(xiàn)。（2）掌握冒泡排序算法的實現(xiàn)?！緦嶒瀮?nèi)容】1.編寫折半查找程序，對以下數(shù)據(jù)查找37所在的位置。5，13，19，21，37，56，64，75，80，88，922.編寫冒泡排序程序，對以下數(shù)據(jù)進行排序。49，38，65，97，76，13，27，49【實驗步驟】1.打開VC++。2.建立工程：點File->New，選Project標(biāo)簽，在列表中選Win32ConsoleApplication，再在右邊的框里為工程起好名字，選好路徑，點OK->finish。至此工程建立完畢。3.創(chuàng)建源文件或頭文件：點File->New，選File標(biāo)簽，在列表里選C++SourceFile。給文件起好名字，選好路徑，點OK。至此一個源文件就被添加到了你剛創(chuàng)建的工程之中。4．寫好代碼5．編譯－＞鏈接－＞調(diào)試（1）查找算法的代碼如下所示：#include“stdio.h”#include“malloc.h”#defineOVERFLOW-1#defineOK1#defineMAXNUM100#defineN10typedefintElemtype;typedefintStatus;typedefstruct{Elemtype*elem;intlength;}SSTable;StatusInitList(SSTable&ST){inti,n;ST.elem=(Elemtype*)malloc(Elemtype));if(!ST.elem)return(OVERFLOW);printf(“輸入元素個數(shù)和各元素的值:”);scanf(“%dn”,&n);for(i=1;i<=n;i++){(MAXNUM*sizeofscanf(“%d”,&ST.elem[i]);}ST.length=n;returnOK;}intSeq_Search(SSTableST,Elemtypekey){inti;ST.elem[0]=key;for(i=ST.length;ST.elem[i]!=key;--i);returni;}intBinarySearch(SSTableST,Elemtypekey){intmid,low,high,i=1;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid]==key)returnmid;elseif(keyhigh=mid-1;else}return0;}voidmain(){SSTableST;InitList(ST);Elemtypekey;intn;printf(“key=”);scanf(“%d”,&key);printf(“nn”);/*printf(“AfterSeqSearch::”);n=Seq_Search(ST,key);printf(“positionisin%dnn”,n);*/printf(“AfterBinarySearch::”);n=BinarySearch(ST,key);low=mid+1;if(n)printf(“positionisin%dnn”,n);else}實驗結(jié)果如下所示：（2）排序算法的代碼如下所示：#include“stdio.h”#include“malloc.h”#defineOVERFLOW-1#defineOK1#defineMAXNUM100#defineN10typedefintElemtype;typedefintStatus;typedefstruct{Elemtype*elem;intlength;}SSTable;StatusInitList(SSTable&ST)printf(“notinnn”);{inti,n;ST.elem(Elemtype));if(!ST.elem)return(OVERFLOW);printf(“輸入元素個數(shù)和各元素的值:”);scanf(“%dn”,&n);for(i=1;i<=n;i++){scanf(“%d”,&ST.elem[i]);}ST.length=n;returnOK;}voidSort(SSTableST){inti,j,t;for(i=1;ifor(j=i+1;j<=ST.length;j++)if(ST.elem[i]>ST.elem[j]){t=ST.elem[i];=(Elemtype*)malloc(MAXNUM*sizeof}}ST.elem[i]=ST.elem[j];ST.elem[j]=t;voiddisplay(SSTableST){inti;for(i=1;i<=ST.length;i++){printf(“%d”,ST.elem[i]);}}voidmain(){SSTableST;InitList(ST);intn;printf(“beforesort::n”);display(ST);Sort(ST);printf(“naftersort::n”);display(ST);}實驗結(jié)果如下所示：【實驗心得】通過這次實驗,我明白了程序里的折半查找和冒泡查找.其實排序可以有很多種，但是其目的應(yīng)該都是為了能夠在海量的數(shù)據(jù)里迅速查找到你要的數(shù)據(jù)信息，折半查找是種比較快的方式，但前提是要是有序的排序才可以。對于有序表，查找時先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進行比較，若相等，則查找成功；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進行折半查找；否則在前半部分進行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實際上死先確定待查找元素所在的區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。算法中需要用到三個變量，low表示區(qū)域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.第三篇：數(shù)據(jù)結(jié)構(gòu)參考材料數(shù)據(jù)結(jié)構(gòu)參考題目一、選擇1.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是（）A.棧B.隊列C.樹D.圖2.下面程序段的時間復(fù)雜度為（）for(i=0;inext=HL;B.P->next=HL;HL=p;C.P->next=HL;p=HL;D.P->next=HL->next;HL->next=p;4.兩個字符串相等的條件是（）A.串的長度相等B.含有相同的字符集C.都是非空串D.串的長度相等且對應(yīng)的字符相同5．若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M行的棧操作系列是（）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX6.已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為（）A.0B.1C.48D.497.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結(jié)果為（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）A.插入排序B.冒泡排序C.快速排序D.歸并排序8.已知散列表的存儲空間為T[0..16]，散列函數(shù)H（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關(guān)鍵字：T[5]=39，T[6]=57和T[7]=7，則下一個關(guān)鍵字23插入的位置是（）A.T[2]B.T[4]C.T[8]D.T[10]9.如果將矩陣An×n的每一列看成一個子表，整個矩陣看成是一個廣義表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為Dout，則所有頂點的入度之和為（）A.DoutB.Dout-1C.Dout+1D.n11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（）A線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.線性結(jié)構(gòu)和樹型結(jié)構(gòu)D.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)12．棧的插入和刪除操作在()進行。A．棧頂B.棧底C.任意位置D指定位置13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A.24B.71C.48D.5314．一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()A.231B.321C.312D.12315．關(guān)于棧和隊列的說法中正確的是（）A．棧和隊列都是線性結(jié)構(gòu)B.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)C.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)D.棧和隊列都不是線性結(jié)構(gòu)16．關(guān)于存儲相同數(shù)據(jù)元素的說法中正確的是（）A．順序存儲比鏈?zhǔn)酱鎯ι僬伎臻gB.順序存儲比鏈?zhǔn)酱鎯Χ嗾伎臻gC.順序存儲和鏈?zhǔn)酱鎯Χ家笳加谜麎K存儲空間D.鏈?zhǔn)酱鎯Ρ软樞虼鎯﹄y于擴充空間17．已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（）A.q→next=s；p→next=s；B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→next=q；18．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）A.1B.2C.3D.419．執(zhí)行下面程序段時，S語句被執(zhí)行的次數(shù)為：（）for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A.n*nB.n*n/2C.n(n+1)D.n(n+1)/220．在長度為n的線性表中刪除一個指針p所指結(jié)點的時間復(fù)雜度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）A.a，b，c，dB.a，b，d，cC.d，c，b，aD.c，d，a，b22．關(guān)于串的敘述中，正確的是（）A．空串是只含有零個字符的串B.空串是只含有空格字符的串C.空串是含有零個字符或含有空格字符的串D.串是含有一個或多個字符的有窮序列23．在具有m個單元的循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）A．front==rearB.(front+1)%m==rearC.rear+1==frontD.(rear+1)%m==front24．設(shè)有二維數(shù)組1A［n］［n］表示如下：23456，則A［i］［i］（0≤i≤n-1）的D.i2/2值為（）A．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/225．高度為h的完全二叉樹中，結(jié)點數(shù)最多為（）hA．2h-1B.2h+1C.2-1D.2h26．由m棵結(jié)點數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點的右子樹上具有的結(jié)點個數(shù)是（）A.mnB.mn-1C.n(m-1)D.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）A.nB.n-1C.n+1D.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）A.矩陣中非全零元素的行數(shù)等于圖中的頂點數(shù)B.第i行上與第i列上非零元素總和等于頂點Vi的度數(shù)C.矩陣中的非零元素個數(shù)等于圖的邊數(shù)D.第i行上非零元素個數(shù)和第i列上非零元素個數(shù)一定相等29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=keymod13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（）A.1B.2C.3D.430．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）A.36，44，49，55，81，88B.44，36，49，55，81，88C.44，36，49，81，55，88D.44，36，49，55，88，81二、填空題1.數(shù)據(jù)是計算機加工處理的對象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面()。3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進先出的線性表（）。5.從循環(huán)鏈表的某一結(jié)點出發(fā)，只能找到它的后繼結(jié)點，不能找到它的前驅(qū)結(jié)點（）。6.單鏈表設(shè)置頭結(jié)點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）。9.從非循環(huán)鏈表的某一結(jié)點出發(fā)，既能找到它的后繼結(jié)點，又能找到它的前驅(qū)結(jié)點（）。10.單鏈表結(jié)點的指針域是用來存放其直接后繼結(jié)點的首地址的（）11.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象（）。12.用順序表來存儲線性表時，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。13.在非線性結(jié)構(gòu)中，至少存在一個元素不止一個直接前驅(qū)或不止一個直接后驅(qū)（）。14.樹的最大特點是一對多的層次結(jié)構(gòu)（）。15.隊列的特點是先進先出（）。16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲結(jié)構(gòu)獨立于計算機（）。18.線性表簡稱為”順序表”。（）19.對數(shù)據(jù)的任何運算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點出發(fā)，可以找到表中的所有結(jié)點（）。21.棧是一種先進先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型（）。28.線性表的順序存儲方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進后出的線性表（）。30.將插入和刪除限定在表的同一端進行的線性表是隊列（）。三、畫圖題1.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={15,11,20,8,14,13}R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>}2.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={A,B,C,D,E,F,G,H,I,J}R={,,,,,,,,}3．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={1,2,3,4,5,6,7}R={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>}4.請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={1,2,3,4,5}R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>}5．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={0,1,2,3,4,5,6,7}R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)}6．請根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)K={1,2,3,4,5,6,7}R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}四、運算題1．已知一個圖的頂點集V和邊集H分別為：V＝{0，1，2，3，4，5，6，7}E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。2.一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。平均查找長度：（寫出計算過程）3．已知一個圖的頂點集V和邊集H分別為：V＝{0，1，2，3，4，5，6，7}E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發(fā)）______，____，______，______，______，______，______。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：前序：中序：后序：5.設(shè)有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。五、編程題1.請編寫一個算法，實現(xiàn)十進制整數(shù)與二進制數(shù)的轉(zhuǎn)換。Voidshi_to_er(unsignedx){2.寫出二分法查找的算法：Intsearch_bin(Keytypek,sstablest){3.請編寫一個算法，實現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點）。LINKLIST*INVERTLINK(LINKLIST*H){第四篇：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)】二叉排序樹的建立，查找，插入和刪除實踐題/*sy53.c*/#include#includetypedefintKeyType;typedefstructnode{KeyTypekey;structnode*lchild,*rchild;}BSTNode;typedefBSTNode*BSTree;BSTreeCreateBST(void);voidSearchBST(BSTreeT,KeyTypeKey);voidInsertBST(BSTree*Tptr,KeyTypeKey);voidDelBSTNode(BSTree*Tptr,KeyTypeKey);voidInorderBST(BSTreeT);main(){BSTreeT;charch1,ch2;KeyTypeKey;printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);T=CreateBST();ch1='y';while(ch1=='y'||ch1=='Y'){printf(“請選擇下列操作：n”);printf(“1------------------更新二叉排序樹存儲n”);printf(“2------------------二叉排序樹上的查找n”);printf(“3------------------二叉排序樹上的插入n”);printf(“4------------------二叉排序樹上的刪除n”);printf(“5------------------二叉排序樹中序輸出n”);printf(“6------------------退出n”);scanf(“n%c”,&ch2);switch(ch2){case'1':T=CreateBST();break;case'2':printf(“n請輸入要查找的數(shù)據(jù)：”);scanf(“n%d”,&Key);SearchBST(T,Key);printf(“查找操作完畢。n”);break;case'3':printf(“n請輸入要插入的數(shù)據(jù)：”);scanf(“n%d”,&Key);InsertBST(&T,Key);printf(“插入操作完畢。n”);break;case'4':printf(“n請輸入要刪除的數(shù)據(jù)：”);scanf(“n%d”,&Key);DelBSTNode(&T,Key);printf(“刪除操作完畢。n”);break;case'5':InorderBST(T);printf(“n二叉排序樹輸出完畢。n”);break;case'6':ch1='n';break;default:ch1='n';}}}BSTreeCreateBST(void){BSTreeT;KeyTypeKey;T=NULL;printf(“請輸入一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“%d”,&Key);while(Key){InsertBST(&T,Key);printf(“請輸入下一個關(guān)鍵字(輸入0時結(jié)束輸入)：n”);scanf(“n%d”,&Key);}returnT;}voidSearchBST(BSTreeT,KeyTypeKey){BSTNode*p=T;while(p){if(p->key==Key){printf(“已找到n”);return;}p=(Keykey)?p->lchild:p->rchild;}printf(“沒有找到n”);}voidInsertBST(BSTree*T,KeyTypeKey){BSTNode*f,*p;p=(*T);while(p){if(p->key==Key){printf(“樹中已有Key不需插入n”);return;}f=p;p=(Keykey)?p->lchild:p->rchild;}p=(BSTNode*)malloc(sizeof(BSTNode));p->key=Key;p->lchild=p->rchild=NULL;if((*T)==NULL)(*T)=p;elseif(Keykey)f->lchild=p;elsef->rchild=p;}/*InsertBST*/voidDelBSTNode(BSTree*T,KeyTypeKey){BSTNode*parent=NULL,*p,*q,*child;p=*T;while(p){if(p->key==Key)break;parent=p;p=(Keykey)?p->lchild:p->rchild;}if(!p){printf(“沒有找到要刪除的結(jié)點n”);return;}q=p;if(q->lchild&&q->rchild)for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;if(!parent)*T=child;else{if(p==parent->lchild)parent->lchild=child;elseparent->rchild=child;if(p!=q)q->key=p->key;}free(p);}voidInorderBST(BSTreeT){if(T!=NULL){InorderBST(T->lchild);printf(“%5d”,T->key);InorderBST(T->rchild);}}第五篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱課程編號：030816適用專業(yè)：教育技術(shù)學(xué)總學(xué)時數(shù)：64學(xué)分：4編制單位：茂名學(xué)院理學(xué)院教育與信息技術(shù)系編制時間：2008年6月20日一、課程地位、性質(zhì)和任務(wù)《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計算機相關(guān)學(xué)科專業(yè)的基礎(chǔ)課程中的一門重要的核心課程。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據(jù)問題設(shè)計和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計應(yīng)用程序打下基礎(chǔ)。本課程以提高學(xué)生的計算機應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計高效的算法，提高程序設(shè)計能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學(xué)生的程序設(shè)計能力。二、與其他課程的關(guān)系先修課：程序設(shè)計基礎(chǔ)、離散數(shù)學(xué)、計算機組成原理、計算機文化基礎(chǔ)三、教學(xué)內(nèi)容、課時安排和基本要求（一）教學(xué)部分第1章緒論（2學(xué)時）1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4算法和算法分析（算法及其設(shè)計的要求，算法效率的度量，算法的存儲空間需求）1.5問題求解基本要求：了解：抽象數(shù)據(jù)類型，算法設(shè)計方法與算法分析。掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、算法的基本概念；問題求解的方法與步驟重點：數(shù)據(jù)結(jié)構(gòu)和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟難點：評價算法的標(biāo)準(zhǔn)和評價方法，最壞情況和平均情況的區(qū)分。第2章線性表（8學(xué)時）2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表）2.4一元多項式的表示及相加基本要求：了解：兩種存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)）及一元多項式的表示及相加。掌握：要求熟練掌握處理線性表的各種算法。為后繼章節(jié)的學(xué)習(xí)打基礎(chǔ)。重點：各種算法。難點：鏈表的理解。第3章棧與隊列（4學(xué)時）3.1棧（定義，棧的表示和實現(xiàn)）3.2棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號匹配的檢驗，行編輯程序，迷宮求解，表達(dá)式求值）3.3棧與遞歸的實現(xiàn)3.4隊列及其實現(xiàn)（定義，鏈隊列，循環(huán)隊列）3.5*離散事件模擬教學(xué)要求：熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。棧和隊列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)?；疽螅毫私猓簵：完犃械亩x及其實現(xiàn)。掌握：熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。重點：棧和隊列的算法實現(xiàn)。難點：棧和隊列的算法實現(xiàn)。第4章串（2學(xué)時）4.1串類型的定義4.2串的表示和實現(xiàn)（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進算法）4.4串操作應(yīng)用舉例（文本編輯，建立詞索引表）基本要求：了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應(yīng)用。第5章數(shù)組（2學(xué)時）5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4廣義表的定義5.5廣義表的存儲結(jié)構(gòu)5.6m元多項式的表示5.7廣義