数据结构与算法课程项目-k8凯发旗舰

（英文）projects for data structures and algorithms

课程编码

21h24120

课程性质

■必修£选修

课程类型

£通识教育£大类教育■专业教育£师范教育

所属模块（通识选修课填写，限选1项）

£创新创业£艺术修养£文化传承£社会研究

£科学思维£多元文化£道德推演

适用专业

计算机类各本科专业

开课部门

计算机学院

课程负责人

陈卫东

学时学分

学分:1

总学时:32

理论:0

实验:0

实践:32

授课语言

中文

先修课程

程序设计基础、离散数学、数据结构、算法设计与分析

lo2

2 问题分析:能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机领域的复杂工程问题，以获得有效结论。

2.2能够基于数学、自然科学和工程数学的基本原理和数学模型，通过文献研究分析工程问题特性。

m

lo1

lo2

2 问题分析:能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机领域的复杂工程问题，以获得有效结论。

2.3 能认识到计算机领域复杂工程问题的多种影响因素以及复杂工程问题的多种k8凯发旗舰的解决方案，证实k8凯发旗舰的解决方案的合理性并得到有效结论。

h

lo2

lo3

3 设计/开发k8凯发旗舰的解决方案:设计/ 开发k8凯发旗舰的解决方案:能够设计计算机领域的复杂工程问题的k8凯发旗舰的解决方案，设计满足特定需求的系统、子系统或算法流程，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。

3.1能够按用户需求和复杂工程需求，确定计算机系统、单元（组件）与过程的设计目标。

h

lo1

lo2

lo3

5 使用现代工具:能够针对计算机领域的复杂工程问题，开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具，包括对计算机领域的复杂工程问题的预测与模拟，并能够理解其局限性。

5.3根据复杂工程问题中的各种制约条件，能够选用或开发满足特定需求的现代工具，模拟和预测各种复杂场境，并能够分析其局限性。

h

主要内容

1.在ccf cspk8凯发旗舰官网(https://www.cspro.org/)的模拟考试模块(http://118.190.20.162/)进行编程实训，要求在规定时间内完成最近3次csp认证真题中每套试题的前3题的编程实现。前3题主要是通过解决简单实际问题的编程实践，训练熟练使用各种数据结构实现基本算法的技能。

2. 每位同学独立完成，完成后写出解题报告，包括问题分析过程、基本算法思路及实现途径。

学习目标

1. 训练基本数据处理能力，包括数组上进行递推、大小比较、计数、排序等。

2. 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找、字符串简单处理等。

3. 训练基于stl的复杂字符串处理、日期处理、进制处理、递推、排序、查找等技能，并具备问题抽象和建模的初步能力，能用所学方法解决实际问题。

学生课前阅读材料与其他准备

1. 参考书目:

[1]殷人昆编著. 数据结构(c语言版)(第2版). 北京:清华大学出版社,2017

[2]m.h.alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010

[3]苏小红等编. 程序设计实践教程(c语言版),北京: 机械工业出版社,2021

[4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016

[5]thomas h.cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012

2. 思考问题:

[1] 使用stl 相对于自己写程序处理字符串有何优势?

[2] 基本算法的多种实现时空效率有何差异?

3. 其他课前准备:在ccf cspk8凯发旗舰官网注册，在学者网注册并加入课程组，在pta平台注册并加入课程组。

教学方式

1. 实训教学:

一周内在cspk8凯发旗舰官网上在线编程解决试题中对应的简单实际问题，并写出解题报告，包括解题分析过程、基本算法思路及实现途径等。

2. 思政教育:

算法运行时间与算法空间开销一个主要区别是时间不可重复使用，空间可重复使用。引导学生感悟时间的宝贵，逝去的青春不再来，要珍惜现在读书学习的好时光。

课后作业

一周内在cspk8凯发旗舰官网上通过在线编程解决试题中对应的简单实际问题，并写出解题的书面报告上传到学者网课程作业中。

单元二:数据结构与算法的实际应用

学时:10

支撑课程目标:lo2,lo3

主要内容

1. 在ccf cspk8凯发旗舰官网(https://www.cspro.org/)的模拟考试模块(http://118.190.20.162/)进行编程实训，要求在规定时间内完成最近3次csp认证真题中每套试题的最后2题的编程实现。最后2题主要是通过对较复杂实际问题的求解，训练问题分析、建模、算法设计及其实现的能力。

2. 每位同学独立完成，完成后写出解题报告，包括解题分析过程、基本算法思路及实现途径等。

学习目标

1. 熟悉经典算法，包括并查集、最短路径、强连通分支、最小生成树、欧拉序列、动态规划、贪心算法、深度优先搜索、广度优先搜索、回溯剪枝等；能够分析算法的时间复杂度、空间复杂度和算法稳定性；熟练理解并使用stl来优化算法的时间复杂度。

2. 熟练使用高级、复杂数据结构，包括后缀数组、树状数组、线段树、静态kdtree等；能够灵活利用经典算法思想解决较复杂实际问题，包括如:剪枝、分治、状态压缩动态规划、快速矩阵幂、计算几何、图论高级应用（包括最大流、最小费用流）等；能够解决复杂的模拟问题，编写并调试代码量较大的程序；培养缜密的科学思维和计算思维。

学生课前阅读材料与其他准备

1. 参考书目:

[1]殷人昆编著. 数据结构(c语言版)(第2版). 北京:清华大学出版社,2017

[2]m.h.alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010

[3]苏小红等编. 程序设计实践教程(c语言版),北京: 机械工业出版社,2021

[4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016

[5]thomas h.cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012

2. 思考问题:

[1] 如何实现图的基本算法(包括图的遍历、最小成生数、最短路径等)?

[2] 如何解决复杂的模拟问题?

3. 其他课前准备:在ccf cspk8凯发旗舰官网注册，在学者网注册并加入课程组，在pta平台注册并加入课程组。

教学方式

1. 实训教学:

一周内在cspk8凯发旗舰官网上在线编程解决试题中对应的较复杂实际问题，完成后写出解题报告，包括解题分析过程、基本算法思路及实现途径等。

2. 思政教育:

通过编程实训，让学生感悟到解决问题有多种算法且同一算法的不同实现往往有不同的时空复杂度；算法设计与分析目的是为了用较少的资源解决问题。由此增强学生节约资源、提高效率意识。

课后作业

一周内在cspk8凯发旗舰官网上通过在线编程解决试题中对应较复杂的实际问题，完成后写出解题报告并上传到学者网课程作业中。

单元三:数据结构与算法的编程测试

学时:4

支撑课程目标:lo1,lo2 lo3

主要内容

1. 在历年csp认证真题中随机抽取5道试题移植到pta平台，其中3道题是关于数据结构和算法的基本编程题，2道是关于用数据结构和算法知识编程解决较复杂的实际问题。试题结构与csp认证真题相仿，每题分值也是100分，共计500分。

2. 在pta系统实时在线考核（4学时），学生独立完成。

学习目标

1. 熟悉各种数据结构、经典算法的基本思路及其效实现途径。

2. 熟练使用各种数据结构和经典算法解决简单实际问题。

2. 能够灵活利用各种算法思想解决较复杂的实际问题。

学生课前阅读材料与其他准备

1. 参考书目:

[1]殷人昆编著. 数据结构(c语言版)(第2版). 北京:清华大学出版社,2017

[2]m.h.alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010

[3]苏小红等编. 程序设计实践教程(c语言版),北京: 机械工业出版社,2021

[4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016

[5]thomas h.cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012

2. 思考问题:无

3. 其他课前准备:在pta平台注册并加入课程组。

教学方式

1. 在线编程实践考核:4学时内在pta平台上在线编程解决试题中对应实际问题。

2. 思政教育:诚信考试，独立思考完成。

课后作业

查找资料了解如何编写程序来识别处理图像中数字串（比如图书isbn中识别出数字串）。注意:不能用现有的工具软件。

单元四:数据结构与算法的工程实践

学时:10

支撑课程目标:lo1,lo2,lo3

主要内容

1. 给出一个较复杂的实际应用问题（开放类型问题），比如识别isbn图片中的数字串，文档的自动摘要等。引导学生通过分析将该复杂问题的求解过程分解为若干模块任务来解决，这些模块任务是简单的，能够用基本数据结构和算法知识来编程求解。分析模块任务之间的逻辑关系，画出任务关系图，并通过拓扑排序得到解决任务的次序。

2. 每一个模块任务在pta上对应设置一道编程题目，要求学生在给定的时间内独立在线编程解决。

3. 每3位同学一组，每组同学讨论每个模块任务的最佳算法及实现途径，探讨如何集成这些模块的求解算法来得到解决原问题的一个小型应用软件。要求展示每一小组的软件及应用效果。

学习目标

1. 培养学生探求解决较复杂实际问题的能力，即对问题进行分析、建模、算法设计及编程实现的能力。

2. 锻炼学生的程序设计与实现能力、对项目整体把控能力，培养学生的计算思维和团队协作精神。

学生课前阅读材料与其他准备

1. 参考书目:

[1]殷人昆编著. 数据结构(c语言版)(第2版). 北京:清华大学出版社,2017

[2]m.h.alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010

[3]苏小红等编. 程序设计实践教程(c语言版),北京: 机械工业出版社,2021

[4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016

[5]thomas h.cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012

2. 思考问题:

通过小组完成项目的编程实践，如何理解计算思维和团队协作精神?

3.其他课前准备:在pta平台注册并加入课程组。

教学方式

1. 教师讲解:

针对较复杂实际问题的编程求解，让学生清楚完成整个项目的基本思路。

2. 学生实践:

通过小组合作方式，让每位学生清楚项目的整体思路，以及如何协作完成项目、分工撰写项目报告和制作项目答辩ppt。最终项目的所有工作分工合作完成。

3. 思政教育:

通过小组合作方式完成项目，让学生感悟到分工合作才能挑战复杂问题。

课后作业

根据各小组展示和汇报情况，完善小组的展示报告，并上传到学者网课程作业中。

编程实训

(单元一)

编程实训的成绩评分标准(见附表1)

25

lo1

50

lo2

50

编程实训

(单元二)

编程实训的成绩评分标准(见附表1)

25

lo2

50

lo3

50

编程考核

(单元三)

编程考核的成绩评分标准(见附表2)

20

lo1

30

lo2

40

lo3

30

编程实践

(单元四)

编程实践的成绩评分标准(见附表3)

30

lo1

20

lo2

40

lo3

40

进度及任务完成进度

(权重0.4)

按时提交且任务完成进度80%以上

按时提交且任务完成进度60%以上

按时提交且任务完成进度40%以上

补交完成

掌握程度

(权重0.4)

掌握80%以上

掌握60%以上

掌握40%以上

掌握40%以下

创新性

(权重0.2)

提出不同解决办法

只有一种解决办法

能提出不同办法，但可靠性不足

不能提出有效解决办法

总分

完成进度

(权重0.6)

提前提交

按时提交

延时提交

补交完成

展示效果

(权重0.2)

程序能正常运行，在80%以上测试用例上运行结果正确

程序能正常运行，在60%以上测试用例上运行结果正确

程序能正常运行，在40%以上测试用例上运行结果

程序未能运行，或在40%以下测试用例上运行结果不正确

项目报告 (权重0.2)

完整且有深入细化分析和描述

完整且但深入细化分析和描述不够

较为完整、深入细化分析和描述不够

不完整、缺乏细节分析和描述

总分