数据结构教案.docx

《数据结构教案.docx》由会员分享，可在线阅读，更多相关《数据结构教案.docx（31页珍藏版）》请在三一办公上搜索。

1、数据结构教案安做财经大学信息工程学院二OO共年九月凄做射保大琴教案专用页内容（标题）第1章绪论课时3课时教学目的及要求教学目的：介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。基本概念和术语；学习数据结构的意义；算法的描述和分析。教学要求：了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。重点难点及其处理重点：/据结构的基本概念和术语，（2）了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。难点：算法复杂度的分析方法。算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。算法的时间复杂

2、度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。处理：通过对一些已学习过的数据类型进行分析，由此引申出数据结构的概念。通过一些算法举例，来说明具体的算法如何分析时间复杂度。教学方法课堂讲授与课下作业相结合。参献考文1 .朱若愚.数据结构（第二版）.北京：电子工业出版社，20012 .张绍民.数据结构教程（C语言版）.北京：中国电力出版社，2002课外作业及要求估算冒泡排序法的时间复杂度后记凄做射保大琴教案专用页内容（标题）第2章线性表2.1线性表的逻辑结构2.2线性表的顺序存储结构课时3课时教学目的及要求教学目的：介绍线性表的逻辑结构和顺序存储表示方法，以及定义在逻辑结构上的各种基本运算

3、及其在顺序存储结构上如何实现这些基本运算。教学要求：在熟悉顺序存储结构的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。重点难点及其处理重点：（1）线性表的逻辑结构。（2）线性表的逻辑结构特征。线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。顺序表上的插入、删除操作及其平均时间性能分析。点：顺序表上实现的各种基本算法及相关的时间性能分析利用顺序表设计算法解决简单的应用问题。处理：通过和C程序设计课程中学过的数组相比较，来引入线性表。使用本章所学到的基本知识设

4、计有效算法解决与线性表相关的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .朱若愚.数据结构（第二版）.北京：电子工业出版社，20012 .张绍民.数据结构教程（C语言版）.北京：中国电力出版社，20023 .胡学钢.数据结构算法设计指导.北京：清华大学出版社，2001课外作业及要求后记廛做财钻大至教案专用页内容(标题)第2章线隹表2.3 线性表的链式存储结构2.4 顺序表和链表的比较课时3课时教学目的及要求教学目的：介绍线性表的链式存储表示方法，以及定义在链式结构上的各种基本运算及其在各种链表上如何实现这些基本运算。教学要求：在熟悉这些内容的基础上，能够针对具

5、体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。重占八、难点及其处理重点：(1)链表如何表示线性表中元素之间的逻辑关系。(2)单链表、双链表、循环链表链接方式上的区别。(3)单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。(4)双链表的定义及其相关的算法(5)顺序表和链表的比较熟练掌握单链表上实现的各种基本算法及相关的时间性能分析，难点：(I).链表中头指针和头结点的使用。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。(3)针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构

6、才能取得较优的时空性能。处理：能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。利用链表设计算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .朱若愚.数据结构(第二版).北京：电子工业出版社，20012 .张绍民.数据结构教程(C语言版).北京：中国电力出版社，20023 .胡学钢.数据结构算法设计指导.北京：清华大学出版社，2001课外作业及要求1 .试写出一个计算链表中数据元素结点个数的算法，其中指针P指向读链表的第一个结点.2 .试设计实现在单链表中删去值相同的多余结点的算法.3 .有一个线性表(al,a2,，an),它存储在

7、有附加表头结点的单链表中，写一个算法，求出该线性表中值为X的元素的序号.如果X不存在，则输出序号为0.4 .写一个算法将一单链表逆置.要求操作在原链表上进行.5 .在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法.后记建做财或大专教案专用页内容（标题）第3章栈和队列3.1栈的逻辑结构、存储结构及其相关算法课时3课时教学目的及要求教学目的：介绍栈的逻辑结构定义及在两种存储结构上如柯实现栈的基本运算。教学要求：要求在掌握栈的特点的基础上，懂得在什么样的情况下能够使用栈。重点难占八、及其处理重点：栈的逻辑结构特点，栈与线性表的异同。顺序栈上实

8、现的进栈、退栈等基本算法。栈的“上溢”和“下溢”的概念及其判别条件。（4）掌握栈和队列在两种存储结构上实现的基本运算。难点：是栈中对边界条件的处理。利用栈设计算法解决简单的应用问题。处理：加过现实生活中的例子来理解栈的特点，通过对栈的逻辑结构、存储结构的深入分析来理解栈的相关算法。通过栈的应用来掌握栈的特点，什么样的情况下能够使用栈。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1 .赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大

9、学出版社，1999课 外 作 业 及 要 后记1 .假定有编号为A、B、C、D的4辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序（注：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退）。写出每一种可能的序列.2 .已知堆栈采用链式存储结构，初始时为空，试画出a,b、c、d4个元素依次进栈以后堆栈的状态，然后再画出此时的栈顶元素出栈后的状态.3 .写出链栈的取栈顶元素和置栈空的算法.4 .写出多个链表栈中取第j个链表栈顶元素值的算法。5 .写出计算表达式3+4/25*8-6时操作数栈和运算符栈的变化情况.凄做射表大聋教案专用页内容（标题）第3章栈和队列3.1队列的

10、逻辑结构、存储结构及其相关算法课时3课时教学目的及要教学目的：介绍队列的逻辑结构定义及在两种存储结构上如柯实现队列的基本运算。要求在掌握队列的特点的基础上，懂得在什么样的情况下能够使用队列。求重占八、难点及其处理重点：队列在两种存储结构上实现的基本运算，（2）队列的逻辑结构特点，队列与线性表的异同。顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。（4）队列的“上溢”和“下溢”的概念及其判别条件。使用数组实现的循环队列取代普通的顺序队列的原因。难点：循环队列中对边界条件的处理。队列的逻辑结构、存储结构及其相关算法。处理：通过举例来说明队列这种数据结构的使用，利用队列设计算法解决筒

11、单的应用问题。最终能够掌握队列的应用，领会队列的特点，知道什么样的情况下能够使用队列。教学片课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .赵文静.数据结构C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1 .课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素.试画出有两个元素A、B的不同存储结构的图示，及将这两个元素出队后循环队列和链表队列的状态不意图.2 .对于一个具有In个

12、单元的循环队列，写出求队列中元素个数的公式.3 .对于一个具有n个单元(n22)的循环队列，若从进入第一个元素开始，每隔11个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2tl)个时间单位处理完一个元素并令其出队。试编写一个算法，求出在第几个元素进队时将发生溢出。4 .假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。后记建做财或大专教案专用页内容（标题）第4章串课时3课时教学目的及要求教学目的：介绍串的逻辑结构、存储结构及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能，主

13、要掌握串的模式匹配算法。教学要求：掌握3上实现的模式匹配算法。重点难占八、及其处理重点：1 .串及其运算1.1 串的有关概念及基本运算。1.2 串与线性表的关系。2 .中的存储结构2 .1串的两种存储表示。3 .2串上实现的模式匹配算法及其时间性能分析。难点：掌握串上实现的模式匹配算法。处理：通过多媒体演示来展现模式匹配的过程，详细演示了KMP算法。使用C语言提供的串操作函数构造与中相关的算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述

14、）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要1 .假设所使用的字符串采用数组存储。试用C语言编写一个求字符串长度的函数定义.2 .假设所使用的字符串采用数组存储.试用C语言编写一个实现字符串复制的函数定义。3 .假设所使用的字符串采用链接存储结构，链表中每个结点存放m(m=4)个字符.试用C语言编写一个实现字符串删除的函数定义.4 .假设所使用的字符串采用数组存储。试用C语言编写一个函数，将字符中string2的头n个字符添加到字符串Stringl的尾部，并以求结束.后记建做财或大专教案专用页内容(标题)第5章数组和广义表5.

15、1多维数组5.2矩阵的压缩存储课时3课时教学目的及要求教学目的：介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法。教学要求：领会多维数组的概念掌握矩阵的压缩存储的方法熟练掌握稀疏矩阵的三元组表示法重点难占八、及其处理重点：(1)多维数组的逻辑结构特征。(2)多维数组的顺序存储结构及地址计算方式。矩阵的压缩存储方式、特殊矩阵和压缩存储时的下标变换方法。稀疏矩阵的三元组表表示方法及有关算法。难点：数组是一种随机存取结构的原因。稀疏矩阵的压缩存储表示下实现的算法。处理：通金对线性代数中矩阵的引入来理解多维数组，并结合矩阵运算来理解稀疏矩阵。教学方法课堂讲授与课下作业相结合，鼓

16、励学生自学上机实习。参献考文1 .赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆数据结构(用面向对象方法与C+描述).北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课1 .设有一个n维数组Adld2.dn,求IoC(Ail,i2,.,in)。2 .已知二维数组A46.其每个元素占三个存储单元，且A00外的存储地址为1200,试求元素A24的存储地址(分别讨论以行序和列序为主序方式进行分配时的结论).该数组共占用多少单元？3.设A和B分别为上、下三角形矩阵，每一个都有n行.试设计一个作方案，将A和B放到数组Cnn+1

17、中，井写出确定C数组元素值的算壮业ZQ4.已知An为整型数组，试写出实现下列运算的算法：(1)求数A中的最大整数。及(2)求n个整数之和。(3)求n个整数的平均值.要5.已知稀疏矩阵A65如下所示，试写出它的三元组表与十字链表.6.若稀疏矩阵采用三元组表示，请写出求两个具有相同行列数的稀疏求矩阵的相加的算法.凄做射表大聋教案专用页内容（标题）第5章数组和广义表5.3广义表课时3课时教学目的及要求教学目的：领会广义表的概念，掌握广义表的表示方法，学会广义表的基本算法。教学要求：掌握广义的两种表示方法。掌握广义表的表头表尾运算。掌握广义表的访问方法。重占/、难点及其处理重点：广义表的定义求表头和表

18、尾的运算.广义表与线性表的区别难点：广义表的有关概念及其与线性表的关系。广义表的括号表示和图形表示之间的转换。求给定的非空广义表的表头和表尾运算。处理：广义最是一种递归的结构，通过一些实例来理解广义表的构成。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1.赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆数据结构（用面向对象方法与C+描述）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1 .已知下列广义表，画出其存储结构：(I)A=(a,(b,c,d),c,(f,g)(2)B=(a)

19、(3)C=(y,(z,w),(x,z,w),a)(4)D=(x,(y),B),D)2 .写出上题中各广义表的长度及深度.3 .对上题中各广义表，写出：HEAD（八）=?TAIl（八）=?后记廛做财做大学教案专用页内容（标题）笫6章树6.1树的概念6.2二叉树课时3课时教学目的及要教学目的：介绍树的定义，树的各种存储结构，二叉树的定义、性质、存储结构、教学要求：在熟.树和二叉树的基础上，掌握二叉树的基本概念及其有关应用。求重点难占/、及其处理重点：树的概念树和二叉树的常用术语及含义二叉树的递归定义及树与二叉树的差别。二叉树的性质，了解相应的证明方法。难点：二叉树的两种存储方法、特点及适用范围二叉

20、树的性质使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。处理：“W于树的概念，通过现实中组织结构图来引入，增强对树这种结构的理解，对于二叉树要强调它本身的特点，整理归纳二叉树的术语，强调二叉树的性质。课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .黄定.数据结构与算法.广州：广东科技出版社，20002 .徐士良.实用数据结构.北京：清华大学出版社，19983 .美BrunoR.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1 .对于3个结点A,B,C,可组成多少种不同的二叉树？请画出。2 .如果一棵树有nl

21、个度为1的结点，n2个度为2的结点，nm个度为m的结点，则该树共有多少个叶子结点(n=?)?可参考二叉树性质3.的证明方法来思考m叉树问题。3 .写出图6.25中所示的树的叶子结点，非终端结点，各结点的度和树深.4 .将图6.26中的树转换为二叉树.对转换后的二叉树按先根、中根、后根次序遍历的结点序列.后记凄做射表大聋教案专用页内容(标题)第6章树6.3二叉树的遍历6.4线索二叉树课时3课时教学目的及要求教学目的：了解二叉树遍历的基本方法，遍历时访问节点的先后次序。能够掌握遍历二叉树来解决复杂的问题。教学要求：掌握二叉树的遍历算法及其有关应用。重点难占八、及其处理重点：二叉树的三种遍历算法，理

22、解其执行过程。确定三种遍历所得到的相应的结点访问序列。(3)以遍历算法为基础，设计有关算法解决简单的应用问题。二叉树线索化的目的及实质。难点：确定三种遍历所得到的相应的结点访问序列。二叉树线索化的目的及实质。在中序线索树中查找给定结点的中序前趋和中序后继的方法。查找给定结点的前序前趋和后序后继井非有效的原因。处理：通过演示二叉树的遍历过程来增强对访问节点序列的理解。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .黄定.数据结构与算法.广州：广东科技出版社，20002 .徐士良.实用数据结构.北京：清华大学出版社，19983 .美BrunoR.Preiss.数据结构与算法面

23、向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1 .写出先根遍历的非递归算法.2 .写出按层遍历二叉树的算法.3 .写一个算法求二叉树中结点总数.你能写出多少种方法？4 .现有按后根遍历二叉树的结果为C,B,A,有几种不同的二叉树可以得到这一结果？5 .现有按先根和中根遍历某二叉树的结果，试画出这棵二叉树，形状唯一吗？为什么？先根遍历：Abcdefghi,中根遍历；Bcaedghfi.后记建做财或大专教案专用页内容（标题）第6章树6.5树和森林6.6哈夫曼树及其应用课时3课时教学目的及要求教学目的：树和森林与二又树之间的转换方法。树的各种存储结构及其特点。树的两种遍历方法。

24、哈夫曼算法的思想根据给定的叶翥W及其权值构造出相应的最优二叉树教学要求：掌握树M存储方法和树和森林的转化方法。掌握哈夫曼树的构造方法，根据最优二叉树构造对应的哈夫曼编码。重点难点及其处理重点：树第森林与二又树之间的转换方法。最优二叉树和最优前缀码的概念及特点。哈夫曼算法的思想。根据给定的叶结点及其权值构造出相应的最优二叉树。根据最优二叉树构造对应的哈夫曼编码。难点：哈夫曼算法的思想哈夫曼树及其总总，根据最优二叉树构造对应的哈夫曼编码处理：通过幻灯演示哈夫曼编码的过程来加强对哈夫曼编码的理解。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .黄定.数据结构与算法.广州：广东科

25、技出版社，20002 .徐士良.实用数据结构.北京：清华大学出版社，19983 .美BrunoR.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1 .有一组数值14,21,32,15,28,画出哈夫曼树的生成过程及最后结果.2 .凡二叉树都只能用二叉链表来存储，这种说法是否正确？满二叉树和完全二叉树用什么存储结构更适合？书中哈夫曼算法的实现，用的是什么存储结构？后记建做财或大专教案专用页内容（标题）第8章查找8.1查找表的基本概念8.2线性表的查找课时3课时教学目的及要求教学目的：介招顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分

26、析。教学要求：掌握顺序查找、二分查找，查找的基本思想和算法实现。通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。重占/、难占八、及其处理重点：（1）静态查找表和动态查找表的基本概念（2）顺序查找的基本思想和算法实现。（3）二分查找的基本思想和算法实现难点：（1）顺序查找中哨兵的使用方法。（2）二分查找的算法实现。处理：通过分析线性表的查找方法，对比顺序查找的算法思想，来引入顺序查找。通过对有序表的分析，引入折半查找的思想。课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .黄定.数据结构与算法.广州：广东科技出版社，20002 .徐士良.实用数

27、据结构.北京：清华大学出版社，19983 .美BrunoR.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1 .设有一个有序文件，其中各记录的关键字为：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15）,当用折半查找算法查找关键字为2,10、17时，其比较次数分别为多少？2 .用C语言改写折半查找程序，使其成为递归过程并上机验证.3 .设单锥表的结点是按关键字从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找.4 .若对大小均为n的有序顺序表和无序顺序表分别进行查找，试就下列三种情况分别讨论两者在等查找概

28、率时，平均查找长度是否相同：（1）查找失败；（2）查找成功；（3）查找成功，表中有多个关健字等于给定值的记录，一次查找要求找出所有记录.后记凄做射表大聋教案专用页内容（标题）第8章查找8.4 树的查找8.5 散列技术课时3课时教学目的及要求教学目的：介招二叉查找树和B-树的定义和特点以及用途介绍二叉查找树的插入、删除、建树和查找算法及时间性能。了解B-树的插入、删除及查找方法的基本思想。掌握散列表、散列函数的概念和几种常用的散列函数构造方法。教学要求：掌握二叉查找树上查找以及散列表上查找的基本思想和算法实现。重占八、难点及其处理重点：二叉查找树和B一树的定义和特点以及用途（2）二叉查找树的插入

29、、删除、建树和查找算法及时间性能B一树的插入、删除及查找方法（4）散列表、散列函数、散列地址和装填因子等有关概念（5）几种常用的散列函数构造方法难点：二叉查找树的删除算法B一树上的插入和删除算法。（3）两类解决冲突的方法及其优缺点处理：举例了解散列函数的选取原则及产生冲突的原因。深入分析采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。比较散列表和其它表的本质区别。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .黄定.数据结构与算法.广州：广东科技出版社，20002 .徐士良.实用数据结构.北京：清华大学出版社，19983 .美Bruno

30、R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课1.什么叫二叉平衡树?试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况.关键字依次为；8,9,10,2,1,5,3,6,7,1119外2.已知长度为12的表，(Jan,Feb,Mar,Apr,May,Jun,Aug,Sep,Oct,Nov,Dec)o作(1)试按表中元素的顺序，依次插入一棵初始为空的二叉排序树；画出插入完成之后的二叉排序树，井求其在等查找概率情况下，查找成功的业平均查找长度。(2)若对表中元素先进行排序构成有序表，试求在等查找概率情况下，及对此有序表进行折半查找时查找成功的平均查

31、找长度.3.什么叫哈希法？哈希法中为什么会出现冲突？要4.选取哈希函数H(k)=3k%llo用开放地址法处理冲突，d=H(k),di=(di-l+7k%10+l)%ll(i=2,3,).试在OTo的散列地址空间中，求对关键字序列22,41,53,46,30,13,01,67构造哈希表，并要求在等查找概率下查找成功与不成功时的平均查找长度.廛俊财大学教案专用页内容（标题）第9章排序1.1 1基本概念1.2 插入排序1.3 交换排序课时3课时教学目的及要求教学目的：介绍插入排序和交换排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学要求：在熟泉这些内容的

32、基础上，掌握插入排序和交换排序方法的基本思想及排序过程。重占八、难点及其处理重点：（1）排序方法的分类及算法好坏的评判标准。直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析。（3）冒泡排序的基本思想。快速排序的基本思想和算法实现。难点：（1）.针对给定的输入实例，要能写出直接插入排序的排序过程。（2）针对给定的输入实例，能写出快速排序的排序过程。（3）快速排序在最坏和平均情况下的时间性能分析。处理：通过动画演示排序过程来增强学生对排序算法的理解，并分析排序中元素的移动情况，来使学生能够深入理解排序算法。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献

33、数据结构（C语言篇）习题与解析李春葆编著清华大学出版社数据结构朱晋蜀主编电子科技大学出版社数据结构一一用PaSCal语言、C+语言对照描述算法薛超英主编华中理工大学出版社数据结构秦小麟编著航空工业出版社课外作业及要求1 .根据直接插入排序的算法思路，仍以向量为存储结构，把算法91改为从第一个记录开始向后顺序比较，写出算法.2 .用链表存储结构表示待排序列的n个记录，用第1题的方法写一个直接插入排序算法。3 .用增量序列(8,4,2,1)对下列关键字序列进行希尔排序，用图示表示排序过程。56,37,59,41,98,47,94,50,63,52,42,54,60,72,86,90)4 .冒泡排序

34、有若干趟处理，当某一道之中未发生过记录交换，是否还要进行下一趟处理？为什么？5 .有一组关健字14,15,30,28,5,10),分别写出冒泡排序、快速排序过程的图示。举例说明它们的稳定性如何.后记凄做射表大聋教案专用页内容（标题）第9章排序9.4选择排序9.5归并排序9.6分配排序9.7各种排序算法的比较和选择课时3课时教学目的及要求教学目的：介绍选择排序、归并排序和分配排序的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学要求：在熟悉这些内容的基础上，掌握堆排序、归并排序和基数排序的基本思想及排序过程。重点难点及其处理重点：堆、小根堆、大根堆、堆顶等有关

35、概念和定义。（2）堆性质及堆与完全二叉树的关系。（3）直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析。（4）归并排序的基本思想和算法实现，以及时间性能分析。（5）基数排序的基本思想和算法实现，以及时间性能分析。点：（1）针对给定的输入实例，写出堆排序的排序过程。（2）针对给定的输入实例，能写出归并排序的排序过程。（3）针对给定的输入实例，能写出箱排序和基数排序的排序过程。（4）根据实际问题的特点和要求选择合适的排序方法。处理：通过动画演示排序过程来增强学生对排序算法的理解，并分析排序中元素的移动情况，来使学生能够深入理解排序算法。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实

36、习。参考文献数据结构（C语言篇）习题与解析李春葆编著清华大学出版社数据结构朱晋蜀主编电子科技大学出版社数据结构一一用PaSCal语言、C+语言对照描述算法薛超英主编华中理工大学出版社数据结构秦小麟编著航空工业出版社课外作业及要求L用31,22,97,36,47,81,16,33的关键字序列，写出初建堆过程图示,再根据初始堆写出堆排序过程图示.举例说明堆排序的稳定性如何.2 .如果一个关键字序列由n个字符串组成，每个串最多有8个小写英文字母。利用本章介绍的基数排序思路，此题目关键字有效位d=?“分配”与“收集”共几趟？基数rd=?在某一趟中分配队列个数是多少？3 .把基数排序算法的存储结构改为动态链表，试写出修改后的算法。