《数据结构》说课稿（最终五篇）

《数据结构》说课稿（最终五篇）第一篇：《数据结构》说课稿《数据结构》“最短路径”问题说课稿一、教材分析1、特点与地位：重点中的重点。本课是教材《数据结构》第六章第五节的内容。图是一种典型的非线性数据结构，应用十分广泛。求两结点之间的最短路径问题是图最常见的应用的之一，在交通运输、通讯网络等方面具有一定的实用意义。2、重点与难点：根据高职数据结构教育要求，理论“必需，够用”，侧重于某项技术的理论依据，重点放在技能培养上。结合学生现有抽象思维能力水平，已掌握基本概念等学情，以及求解最短路径问题的自身特点，确立本课的重点和难点如下：（1）重点：如何将现实问题抽象成求解最短路径问题，以及该问题的解决方案。（2）难点：求解最短路径算法的程序实现。3、教学安排：最短路径问题包含两种情况：一种是求从某个源点到其他各结点的最短路径，另一种是求每一对结点之间的最短路径。根据教学大纲安排，重点讲解第一种情况问题的解决。安排一个课时讲授。教材直接分析算法，考虑实际应用需要，补充旅游景点线路选择的实例，实例中问题解决与算法分析相结合，逐步推动教学过程。二、教学目标分析1、知识目标：掌握最短路径概念、能够求解最短路径。2、能力目标：（1）通过将旅游景点线路选择问题抽象成求最短路径问题，培养学生的数据抽象能力。（2）通过旅游景点线路选择问题的解决，培养学生的独立思考、分析问题、解决问题的能力。（3）通过算法的程序实现，提高学生的编程能力。3、素质目标：培养学生讲究工作方法、与他人合作，提高工作效率的职业素质。三、教法分析课前充分准备，研读教材，查阅相关资料，制作多媒体课件。教学过程中除了使用传统的“讲授法”以外，主要采用“案例教学法”，同时辅以多媒体课件，以启发的方式展开教学。由于本节课的内容属于图这一章的难点，考虑学生的接受能力，注意与学生沟通，根据学生的反应控制好教学进度是本节课成功的关键。四、学法指导1、课前上次课结课时给学生布置任务，使其有针对性的预习。2、课中指导学生讨论任务解决方法，引导学生分析本节课知识点。3、课后给学生布置同类型任务，加强练习。五、教学过程分析（一）课前复习（3~5分钟）回顾“路径”的概念，为引出“最短路径”做铺垫。教学方法及注意事项：（1）采用提问方式，注意及时小结，提问的目的是帮助学生回忆概念。（2）提示学生“温故而知新”，养成良好的学习习惯。（二）导入新课（3~5分钟）以城市公路网为例，基于求两个点间最短距离的实际需要，引出本课教学内容“求最短路径问题”。教学方法及注意事项：（1）先讲实例，再指出概念，既可以吸引学生注意力，激发学习兴趣，又可以实现教学内容的自然过渡。（2）此处使用案例教学法，不在于问题的求解过程，只是为了说明问题的存在，所以这里的例子只需要概述，能够说明问题即可。（三）讲授新课（25~30分钟）1、求某一结点到其他各结点的最短路径（重点）主要采用案例教学法，提出旅游景点选择的例子，解决如何选择代价小、景点多的路线。（1）将实际问题抽象成图中求任一结点到其他结点最短路径问题。（3~5分钟）教学方法及注意事项：①主要采用讲授法，将实际问题用图形表示出来。语言描述转换的方法（用圆圈加标号表示某一景点，用箭头表示从某景点到其他景点是否存在旅游线路，并且将旅途费用写在箭头的旁边。）一边用语言描述，一边在黑板上画图。②注意示范画图只进行一部分，让学生独立思考、自主完成余下部分的转化。③及时总结，原型抽象（景点作为图的结点，景点间的线路作为图的边，旅途费用作为边的权值），将案例求解问题抽象成求图中某一结点到其他各结点的最短路径问题。④利用多媒体课件，向学生展示一张带权有向图，并略作解释，为后续教学做准备。（2）迪杰斯特拉算法（难点）（17~20分钟）先讲算法思想，主要采用多媒体教学。教学方法及注意事项：①充分利用课件。将教材中的算法思想细化，分步解释给学生。用投影仪演示给学生看，在有限的时间内，学生一边看投影仪上的文字，一边听教师的分析，提高教学效率。注意讲解后给学生留出适当的思考时间。②利用FLASH动画，结合第一步案例中抽象出的有向带权图、算法思想，求解答案。帮助学生进一步理解算法思想。再讲算法实现，主要采用启发式教学。教学方法及注意事项：①启发式教学，如何在计算机中实现上述算法呢？如何实现按路径长度递增产生最短路径？如何记录求解过程中每一步当前的V0到Vi的最短路径呢？引入dist[]数组。②结合案例分析求解最短路径过程中dist[]数组的变化过程。（重点）注意此处最好借助黑板，按照算法思想的步骤，逐步修改dist[]数组。同样，也是只示范一部分，余下部分由学生独立思考完成。③程序代码的讲解，注重思路，淡化语言。本课程不是语言课，对于实现语言不做要求，鼓励学生自己动手将教材提供程序做适当修改，用C++实现，培养他们的编程能力。2、求每一对结点之间的最短路径（5~6分钟）两种思路：一种重复执行n次Dijkstra算法，另一种弗洛伊德（Floyed）算法。教学方法及注意事项：此处只介绍算法思想，算法实现给学生作为拓展内容，自由把握。（四）课堂小结（3~5分钟）1、明确本节课重点Dijkstra算法，及算法实现的辅助数组dist[]的变化过程。2、提示学生，在案例中数据抽象时，用结点表示活动，用有向边便是活动之间的优先关系，这种方式形成的图又可以解决哪类实际问题呢？引导学生预习，为下次课的学习埋下伏笔。（五）布置作业（1~2分钟）1、书面作业：P1746.72、复习本次课内容，预习下次课内容。至此，整个教学过程结束，注意留出1~3分钟机动时间，准备一道备用习题，灵活把握时间安排。六、教学特色以旅游路线选择为主线，灵活采用案例教学、示范教学、多媒体课件等多种手段辅助教学，使枯燥的理论讲解生动起来。在顺利开展教学的同时，体现所讲内容的实用性，提高学生的学习兴趣。第二篇：数据结构实验：线性表的基本操作【实验目的】学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。【实验内容】1.顺序表的实践1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。2)在sqlist[]={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。3)在sqlist[]={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。2)将该单链表的所有元素显示出来。3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。【实验步骤】1.打开VC++。2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。4．写好代码5．编译－＞链接－＞调试【实验心得】线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。实验二：栈的表示与实现及栈的应用【实验目的】（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。n,n0,1Fib(n)Fib(n1)Fib(n2),n14.编写程序，实现Hanoi塔问题。【实验步骤】1.打开VC++。2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。4．写好代码5．编译－＞链接－＞调试【实验心得】通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（LastInFirstOut）的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。实验三：二叉树的建立及遍历【实验目的】（1）掌握利用先序序列建立二叉树的二叉链表的过程。（2）掌握二叉树的先序、中序和后序遍历算法。【实验内容】1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda【实验步骤】1.打开VC++。2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。4．写好代码5．编译－＞链接－＞调试【实验心得】这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。实验四：查找与排序【实验目的】（1）掌握折半查找算法的实现。（2）掌握冒泡排序算法的实现。【实验内容】1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，922.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49【实验步骤】1.打开VC++。2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。4．写好代码5．编译－＞链接－＞调试（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(“输入元素个数和各元素的值:”);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}实验结果如下所示：（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(“输入元素个数和各元素的值:”);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);}实验结果如下所示：【实验心得】通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.第三篇：数据结构参考材料数据结构参考题目一、选择1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A.栈B.队列C.树D.图2.下面程序段的时间复杂度为（）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.串的长度相等且对应的字符相同5．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0B.1C.48D.497.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（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]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字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．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A线性结构B.树形结构C.线性结构和树型结构D.线性结构和图状结构12．栈的插入和删除操作在()进行。A．栈顶B.栈底C.任意位置D指定位置13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24B.71C.48D.5314．一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是()A.231B.321C.312D.12315．关于栈和队列的说法中正确的是（）A．栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构16．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）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．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1B.2C.3D.419．执行下面程序段时，S语句被执行的次数为：（）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所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A.a，b，c，dB.a，b，d，cC.d，c，b，aD.c，d，a，b22．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A．front==rearB.(front+1)%m==rearC.rear+1==frontD.(rear+1)%m==front24．设有二维数组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的完全二叉树中，结点数最多为（）hA．2h-1B.2h+1C.2-1D.2h26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A.mnB.mn-1C.n(m-1)D.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A.nB.n-1C.n+1D.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）A.矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1B.2C.3D.430．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）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.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）11.数据的存储结构是数据的逻辑结构的存储映象（）。12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。30.将插入和删除限定在表的同一端进行的线性表是队列（）。三、画图题1.请根据下列二元组画出相应的数据结构K={15,11,20,8,14,13}R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>}2.请根据下列二元组画出相应的数据结构K={A,B,C,D,E,F,G,H,I,J}R={,,,,,,,,}3．请根据下列二元组画出相应的数据结构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.请根据下列二元组画出相应的数据结构K={1,2,3,4,5}R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>}5．请根据下列二元组画出相应的数据结构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．请根据下列二元组画出相应的数据结构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），设散列表为HT[0..12]，散列函数为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出发）______，____，______，______，______，______，______。4.写出下图所示的二叉树的前中后序遍历结果：前序：中序：后序：5.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。五、编程题1.请编写一个算法，实现十进制整数与二进制数的转换。Voidshi_to_er(unsignedx){2.写出二分法查找的算法：Intsearch_bin(Keytypek,sstablest){3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。LINKLIST*INVERTLINK(LINKLIST*H){第四篇：数据结构数据结构】二叉排序树的建立，查找，插入和删除实践题/*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请输入要查找的数据：”);scanf(“n%d”,&Key);SearchBST(T,Key);printf(“查找操作完毕。n”);break;case'3':printf(“n请输入要插入的数据：”);scanf(“n%d”,&Key);InsertBST(&T,Key);printf(“插入操作完毕。n”);break;case'4':printf(“n请输入要删除的数据：”);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(“请输入一个关键字(输入0时结束输入)：n”);scanf(“%d”,&Key);while(Key){InsertBST(&T,Key);printf(“请输入下一个关键字(输入0时结束输入)：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(“没有找到要删除的结点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);}}第五篇：数据结构教学大纲《数据结构与算法》教学大纲课程编号：030816适用专业：教育技术学总学时数：64学分：4编制单位：茂名学院理学院教育与信息技术系编制时间：2008年6月20日一、课程地位、性质和任务《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课程。通过本课程的教学，使学生知道求解非数值类问题的基本模型（表、树、图），模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。本课程以提高学生的计算机应用能力和综合素质为目标，通过课程教学，为学生构建数据结构与算法方面的知识体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计能力，另一方面，在工程应用中，具有甄别好算法的能力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计能力。二、与其他课程的关系先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础三、教学内容、课时安排和基本要求（一）教学部分第1章绪论（2学时）1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析（算法及其设计的要求，算法效率的度量，算法的存储空间需求）1.5问题求解基本要求：了解：抽象数据类型，算法设计方法与算法分析。掌握：数据与数据结构、算法的基本概念；问题求解的方法与步骤重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤难点：评价算法的标准和评价方法，最坏情况和平均情况的区分。第2章线性表（8学时）2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现（线性链表，循环链表，双向链表）2.4一元多项式的表示及相加基本要求：了解：两种存储结构（顺序存储结构和链式存储结构）及一元多项式的表示及相加。掌握：要求熟练掌握处理线性表的各种算法。为后继章节的学习打基础。重点：各种算法。难点：链表的理解。第3章栈与队列（4学时）3.1栈（定义，栈的表示和实现）3.2栈的应用举例（数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值）3.3栈与递归的实现3.4队列及其实现（定义，链队列，循环队列）3.5*离散事件模拟教学要求：熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要的数据结构，是数据结构课程的基础。基本要求：了解：栈和队列的定义及其实现。掌握：熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。重点：栈和队列的算法实现。难点：栈和队列的算法实现。第4章串（2学时）4.1串类型的定义4.2串的表示和实现（定长顺序存储，堆分配存储，串的块链存储）4.3串的模式匹配算法（求子串位置的定位函数，模式匹配的一种改进算法）4.4串操作应用举例（文本编辑，建立词索引表）基本要求：了解：串的基本概念及主要操作和运算。掌握：掌握串的基本概念和运算。重点：主要操作和运算。难点：模式匹配及串的应用。第5章数组（2学时）5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储（特殊矩阵，稀疏矩阵）5.4广义表的定义5.5广义表的存储结构5.6m元多项式的表示5.7广义