《算法与数据结构》课程教学大纲

《算法与数据结构》教学大纲课程英文名AlgorithmandDataStructure课程代码03M0096学分4总学时64理论学时52实验/实践学时12课程类别学科基础课课程性质必修课先修课程计算机导论、Java语言程序设计适用专业计算机科学与技术开课学院信息工程一、课程地位与课程目标（一）课程地位算法与数据结构是计算机专业的学科基础课。课程通过介绍常用的数据结构和算法，要求学生掌握线性表、堆栈、队列、数组、字符串、树等典型数据结构的建立和实现方法，熟悉常用的递归、排序和查找方法，理解算法的设计步骤、能从时间和空间复杂性两个角度对算法的进行评估，为信息系统的设计和开发奠定良好的算法分析基础。通过本课程的教学我们希望能够使学生在理解常用数据结构和算法原理的基础上，能运用Java等面向对象程序设计语言进行实现，初步具备用计算机程序解决现实世界中较复杂问题的能力。（二）课程目标1．掌握常用数据结构和算法的基本原理与实现方法；2．熟悉算法的正确性、时间复杂性和空间复杂性分析；3．学会运用基本的递归、排序和查找算法解决具体问题；4．了解线性表、堆栈、队列、数组、字符串、树等典型数据结构。二、课程目标达成的途径与方法课堂授课采用多媒体教室，理论知识讲授和程序验证相结合，以便学生加深印象。算法与数据结构课程是一门实践性很强的课程，必须通过上机操作才能掌握所学的知识，所以强调讲授与上机操作相结合。重点加强课程实验教学环境和内容的建设，同时布置一个较大课外编程练习，建议按2人一组共同完成。三、课程目标与相关毕业要求的对应关系课程目标课程目标对毕业要求的支撑程度（H、M、L）毕业要求2毕业要求4毕业要求5课程目标1HMM课程目标2HHM课程目标3HHM四、课程主要内容与基本要求1IntroductionKnowtheconceptionofdatastructure，knowwhytolearndatastructuresandalgorithms,masterhowtoanalyzealgorithms’timeandspacecomplexity。2Listknowlist’sconceptionandoperations,understandlist’ssequentialandlinkedstorage,masterthebasicoperationsoftheabovetwostorage,knowthedifferencesoftwokindlists。3stackandqueueUnderstandtheconceptionsofstackandqueue,knowtheapplicationsofthem,mastertheoperationsofthem4treeandbinarytreeUnderstandtheconceptionsoftreeandthebinarytree,masterthetraversalalgorithmsofthebinarytree，knowthethreadedbinarytree，masterthebinarysearchtree。7graphUnderstandtheconceptionofgraph，mastertwostoragestructuresofgraph，mastertwotraversalalgorithmsofgraph，understandthealgorithmoftheshortestpath。8searchknowtheconceptionsofstaticsearchtableandthedynamicsearchtable,masterbasicsearchalgorithmsofthesequentialsearchandthebinarysearch,masterthehashtable。9internalsortingMasterthesortingalgorithmsofinsertion,shell,quick,merge。10SetandMapMastertheusagesofSetandMap.五、课程学时安排章节号教学内容学时数学生任务对应课程目标1.introductionMathematicsReview

ABriefIntroductiontoRecursion

ImplementingGenericComponentsPre-Java5ImplementingGenericComponentsUsingJava5Generics

412.ListAbstractDataTypes(ADTs)TheListADTSimpleArrayImplementationofListsSimpleLinkedListsListsintheJavaCollectionsAPICollectionInterfaceImplementationofArrayListImplementationofLinkedList12(2)ImplementationofArrayListImplementationofLinkedList2,43.stackandqueueTheStackADTStackModelImplementationofStacksApplicationsTheQueueADTQueueModelArrayImplementationofQueuesApplicationsofQueues10(2)ImplementationofStacksArrayImplementationofQueues2,44.treeandthebinarytreePreliminariesImplementationofTreesTreeTraversalswithanApplicationBinaryTreesImplementationAnExample:ExpressionTrees12(2)ImplementationOftheExpressionTrees2,45.graphDefinitionsRepresentationofGraphsTopologicalSortShortest-PathAlgorithmsUnweightedShortestPathsDijkstra’sAlgorithmGraphswithNegativeEdgeCostsAcyclicGraphsAll-PairsShortestPathShortest-PathExample6(2)ImplementofDijkstra’sAlgorithm2,46.searchstaticsearchtabledynamicsearchtablebasicsearchalgorithmsofthesequentialsearchandthebinarysearchhashtable。10(2)37.internalsortingInsertionSortSimpleSortingAlgorithmsShellsortHeapsortMergesortQuicksort8(2)38.SetandMapTheusageofsetTheusageofmap24六、实践环节及基本要求序号实验项目名称学时基本要求学生任务实验性质实验类别1List2Mastertheimplementsofallkindsoflist上机编程验证性必做2stackandqueue2Masterstackandqueue’soperations上机编程验证性必做3thebinarytree2Masterthebinarytree’soperations上机编程验证性必做4graph2Masterthegraph’soperations上机编程验证性必做5search2Mastersearchalgorithms上机编程验证性必做6internalsorting2Masterinternalsortingalgorithms上机编程验证性必做注：1.实验性质指演示性、验证性、设计性、综合性等；2.实验类别指必做、选做等。七、考核方式及成绩评定考核内容考核方式评定标准（依据）占总成绩比例过程考核到课率、平时作业点名册和作业批改30%期末考核闭卷