数据结构教学大纲与考核要求

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

《数据结构》授课内容与学时分配建议教材:《数据结构》(C语言版)第二版,李云清,杨庆红,揭安全编著,人民邮电出版社撰写人:揭安全、李云清、杨庆红、化志章、钟林辉、石海鹤章节内容基本内容学时进度第1章,概论数据的逻辑结构与存储结构★重点为算法时间复杂度分析。数据类型与抽象数据类型算法和算法分析★学习要求与建议,考核方式说明本章建议学时4学时第2章,线性表及其顺序存储线性表★重点为线性表的特点,顺序表的算法实现,栈和队例的实现与应用。顺序表★栈★队列★栈与队列的应用(表达式求值等)★补充:顺序表的应用举例(如有序合并等)★★本章建议学时8学时第3章,线性表及其链式存储链式存储★重点是带头结点的单链表查找、插入、删除结点的方法。基于带头结点单链表常见算法实现。此处为历年考研常考题。单链表(查找,插入,删除,建表)★带头结点的单链表的基本操作(查找,插入,删除)★★补充:带头结点单链表的应用(头插法建表,尾插法建表,链表倒置,链表归并,链表排序等)★★循环单链表双链表链式栈与链式队列★本章学时建议10学时第4章,字符串与特殊矩阵字符串难点是快速模式匹配算法的思想,next[]向量的求解方法模式匹配★快速模式匹配(KMP)算法★特殊矩阵的压缩存储本章学时建议4学时第5章,递归递归程序设计重点是递归程序的执行过程分析,复杂递归到非递归程序的转换递归程序执行过程分析★递归程序到非递归程序的转换(重点介绍中点优先输出问题的转换方法,背包问题可让学生课后阅读)★递归程序应用举例★另补充一些基于线性表的递归问题举例(如求线性表的最大数,链表倒序输出,线性表倒置等)★本章建议学时4学时以上教学学时建议合计62节理论学时,加上节假日因素,教学内容尽量控制在16周(64节)完成。第16或第17周上机考试,第17周复习答疑,18-19(20)周学校期末考试。★为重点内容,◎为要求学生课后自学内容(建议教师提问考核)章节内容基本内容学时进度第6章,树型结构树的基本概念重点是树的存储结构,树的遍历及其特点树的存储表示★树的遍历★树的线性表示(括号表示)树的线性表示(层号表示)◎本章建议学时4学时第7章,二叉树二叉树的基本概念重点是二叉树的遍历(递归与非递归)基于二叉树的递归算法二叉树的存储结构★二叉树的遍历递归算法(程序实现)★★二叉树遍历的非递归实现(程序实现)★★二叉树上的其它运算(递归程序实现)★★穿线二叉树(思想与方法)★树、森林与二叉树的相互转换方法★本章建议学时4学时第8章,图图的概念重点:图的遍历,最小生成树,最短路径,拓扑排序,关键路径算法的思想图的存储结构(邻接矩阵,邻接表)★图的遍历(BFS,DFS)★★最小生成树★★最短路径★★拓扑排序★关键路径算法★本章学时建议10学时第9章,检索顺序表检索重点是二叉排序树、Huffman树与散列表二叉排序树★★平衡二叉排序树(AVL树)★最佳二叉排序树◎Huffman树及其应用★★B-树★散列★本章学时建议8学时第10章,排序排序的基本概念重点掌握算法思想,算法程序实现,算法时间性复杂性与稳定性分析。直接插入排序、二分插入排序、Shell排序★★直接选择排序(C语言学过)、堆排序★★冒泡排序(C语言学过)、快速排序★★归并排序★基数排序本章学时建议6学时附1、《数据结构》考研大纲【考查目标】1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储三、树与二叉树(一)树的概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树(三)树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树的应用1.等价类问题2.哈夫曼(Huffman)树和哈夫曼编码四、图(一)图的概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用及其复杂度分析1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径五、查找(一)查找的基本概念(二)顺序查找法(三)折半查找法(四)B-树(五)散列(Hash)表及其查找(六)查找算法的分析及应用六、内部排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubblesort)(四)简单选择排序(五)希尔排序(shellsort)(六)快速排序(七)堆排序(八)二路归并排序(mergesort)(九)基数排序(十)各种内部排序算法的比较(十一)内部排序算法的应用【知识点解析】1.线性表线性表是一种最简单的数据结构,在线性表方面,主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面,要掌握的是线性表的存储结构,包括顺序存储结构和链式存储结构,特别是链式存储结构,是考查的重点。另外,还要掌握线性表的基本应用。2.栈、队列和数组栈和队列是两种特殊的线性表,在这方面,要求我们掌握栈和队列的基本概念,以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解,对于栈和队列的应用,例如,排队问题、子程序调用问题、表达式问题等,要搞清楚。一维数组属于线性表范畴,但多维数组不属于线性表。在这方面,主要掌握数组的存储结构,例如按行优先、按列优先等,某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。3.树与二叉树二叉树和树是两种不同的概念,这一点是必须要搞清楚的。在这个部分,我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面,特别是链式存储结构,因为很多应用都是建立在链式存储基础上,例如,二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。在特殊的二叉树中,完全二叉树的概念是必须要搞清楚的,其次,线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用,特别是二叉排序树的基本性质和特点要能很好地理解。多棵独立的树就组成了森林,树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识,也要有了了解。最后就是树的应用,通常会作为综合应用类试题出现,包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。4.图在数据结构中,图的结构是最复杂的,这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。图的存储及基本操作主要有邻接矩阵法和邻接表法,我们要掌握这有向图和无向图的这2种存储方法,要清楚图的连通和存储方法之间的关系。例如,一个顶点的出度和临界矩阵中1的个数有什么关系,等等。图的遍历方法有深度优先搜索和广度优先搜索,我们要掌握这2种遍历方法的算法实现。给出一个具体的图,要能知道它的遍历次序。在数据结构课程中,图的基本应用是最多的,也是最复杂的,我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中,我们要会利用已知条件,求出上述应用的结果。5.查找在给定的数据集合中查找某个关键值就是查找,查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表,我们要掌握它们的基本概念和方法,例如散列表的碰撞如何解决,装载因子的概念等。另外,我们要掌握各种查找算法的分析及应用,最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。6.内部排序根据考试大纲,只考查内部排序。所谓内部排序,就是在内存中进行排序。在这一部分中,主要要掌握直接插入排序、折半插入排序、冒泡排序(bubblesort)、简单选择排序、希尔排序(shellsort)、快速排序、堆排序、二路归并排序(mergesort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程,以及它们之间的区别。在这个知识点,一个很重要的考查点就是各种内部排序算法的比较,一般的书上都会有这样的一个表格,列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度,这个表是需要我们记下来的。当然,如果我们能掌握复杂度的计算方法,自己能推算出来,那就更好了。最后,就是要掌握内部排序算法的基本应用,以及算法的实现。附2、《数据结构》期末考试笔试样题2007-2008学年上学期《数据结构》期末考试试题B课程代号:262208注意事项:请将答案全部写到答题纸上,并注明题号!一、单项选择题(每小题2分,共16分)1.若将数据结构形式定义为二元组(K,R),其中K是数据元素的有限集合,则R是K上()A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合2.在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若p-next-next=head,则()A.p指向头结点B.p指向尾结点C.*P的直接后继是尾结点D.*p的直接后继是头结点3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是()A.O(1)B.O(n)C.O(nlogn)D.O(n2)4.队列和栈的主要区别是()A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同5.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为()A.4B.5C.6D.76.一棵含18个结点的二叉树的高度至少为()A.3B.4C.5D.67.在一个带权连通图G中,权值最小的边一定包含在G的()A.最小生成树中B.深度优先生成树中C.广度优先生成树中D.深度优先生成森林中8.已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个数为有序子序列。对这些子序列进行一趟长度为2的两两归并的结果是()A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}二、算法阅读题(每小题8分,共16分)1.带头结点的单链表存储结构定义如下:typedefstructnode{intdata;structnode*next;}linknode;typedeflinknode*linklist;阅读算法fun(linklisthead),回答:(1)该算法的主要功能是什么?(2)对如下所示的单链表head,画出执行fun(head)单链表的状态。(3)该算法的时间复杂度是多少?voiddelete(linklisthead){linklistpre,p,q;p=head-next;while(p){pre=p;q=p-next;while(q){while(q&&q-data!=p-data)/*查找与p结点相同的结点*/{pre=q;q=q-next;}if(q)/*查找到了*/{pre-next=q-next;/*删除结点q*/free(q);q=pre-next;}}p=p-next;}}2.已知二叉树的存储结构为二叉链表,阅读下面算法。typedefstructnode1{chardata;structnode1*next;}listnode;typedeflistnode*linklist;linklistleafhead=NULL;linklistinorder(

1 / 12
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功