计算机专业课程与计算思维关联分析研究毕业论文.doc

长 治 学 院2013届学士学位毕业论文计算机专业课程与计算思维关联分析研究 以数据结构为例 学 号： 09407112 姓 名： 指导教师： 专 业： 计算机科学与技术 系 别： 计算机系 计算机专业课程与计算思维关联分析研究 以数据结构为例摘 要：计算思维是当前国际计算机教育界关注的热点，也是当前计算机教育需要重点研究的重要课题，为了培养大学生计算思维能力，提高大学生运用计算思维解决实际问题的能力，并促进大学生更好的学习计算机专业课程，需要对计算思维与计算机专业课程知识点的关联进行研究。本文首先对本课题的研究背景和意义进行阐述，然后对计算思维基本概念和数据结构知识体系进行阐述，最后以数据结构课程为例，通过两个实例重点分析研究递归和分治思想在数据结构课程知识点中的运用。通过本课题的研究，可以使我们真正理解计算思维方法在数据结构课程中是怎样体现的，并且更深入的掌握数据结构课程，进而提高计算思维能力。关键词：计算思维；数据结构；关联目 录1 引言12 计算思维基本概念13 数据结构课程的知识体系13.1 数据结构课程的主要内容13.2 数据结构的四类基本结构及其特点24 计算思维与数据结构课程的关联34.1 递归方法的应用实例44.2 分治方法的应用实例55 总结7参考文献7致谢9计算机专业课程与计算思维关联分析研究 以数据结构为例1 引言计算思维是当前国际计算机界广为关注的一个重要概念，也是当前计算机教育需要重点研究的重要课题。计算思维是必须具备的思维能力，就如同所有人都具备“读、写、算”能力一样，当计算思维真正融入到人们的生活中时，它作为一个解决问题的有效工具。近年来，计算思维能力的培养成为国际和国内关注的热点。文中通过实例研究计算思维方法在数据结构课程知识点中的体现，让学生真正理解计算思维与数据结构课程中知识点的关联，促进学生更好地学习计算机专业课程，并且训练和培养学生的计算思维能力，使学生学会用计算思维去思考问题和解决问题。2 计算思维基本概念计算思维是卡内基·梅隆大学计算机科学系主任周以真（JeannetteM.Wing）教授首先提出的。计算思维运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解的涵盖计算机科学的一系列思维活动。计算思维方法主要有：递归思维方法，直接或间接的调用自身的思维方法；分治思维方法，将一个规模为n的复杂问题分解为k个规模较小的容易解决的子问题的思维方法；抽象思维方法，利用概念、判断和推理的形式，借助语言符号来进行的思维方法；归纳思维方法，从观察一类事物中的一部分具有某种属性，经分析判断得出该类事物都具有这种属性的思维方法；类比思维方法，借助于两类不同本质事物之间的相似性，通过比较把一种已掌握的对象的知识平移到另一种新的对象上去的推理方法；逆向思维方法，运用反证法来进行推理得到问题的结论的思维方法。3 数据结构课程的知识体系3.1 数据结构课程的主要内容数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构课程中研究的主要内容如下表1所示：表1 数据结构课程的主要内容结构主要内容线性表 顺序表，线性链表，循环链表，双向链表栈 顺序栈，链式栈队列 抽象数据类型队列，链队列，循环队列串 定长顺序存储，堆分配存储，块链存储数组 顺序表示，压缩存储广义表 链式存储树和二叉树 顺序存储，链式存储，遍历二叉树，线索二叉树图 存储结构，图的遍历（深度优先搜索，广度优先搜索）查找 静态查找表，动态查找表3.2 数据结构的四类基本结构及其特点在任何问题中，数据元素都不是孤立存在的，在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有四种基本结构：线性结构、树形结构、图形结构、集合，这四种基本结构的概念、特点及关系图如表2所示：表2 数据结构的四种基本结构概念特点关系图线性结构各个数据元素组成的结点按逻辑关系依次排成一条链。每个结点只有一个直接前驱（除第一个结点之外）和一个直接后继（除最后一个结点）；各元素之间的逻辑关系是线性关系。树形结构具有分支、层次结构，其形态有点像自然界中的树。每个结点只有一个直接前驱（除根结点之外），每个结点可以有多个直接后继（除叶子结点之外）；各元素之间的逻辑关系是非线性的。图形结构结点按逻辑关系相互缠绕在一起，任何两个结点都可以相邻。每个结点都可以有任意多个直接前驱和任意多个直接后继；各元素之间的逻辑关系是非线性的。集合各结点之间无任何逻辑关系。组织形式松散；任何两个结点之间都没有任何逻辑关系。4 计算思维与数据结构课程的关联计算思维的本质是抽象化和自动化，抽象化是指将实际问题转化为数据结构中的线性、树形、图形、集合四种基本结构，自动化是指设计算法和编程实现，最后在实际的计算机中运行并求解。数据结构课程中分别运用四种基本结构解决问题时所体现的计算思维方法如表3所示：表3 数据结构中体现的计算思维方法基本结构体现的计算思维方法线性结构 抽象思维、递归思维、分治思维、类比思维树形结构 递归思维、抽象思维图形结构 递归思维、抽象思维、类比思维集合 抽象思维、归纳思维数据结构中的很多知识点都能够体现计算思维方法，下面举两个实例分析计算思维与数据结构课程知识点的关联。4.1 递归方法的应用实例递归法的基本思想：把问题转化为规模缩小了的同类问题的子问题，然后直接或间接的调用自身。用函数自身给出定义的函数称为递归函数。运用递归算法的条件包括：确定递归公式；确定边界条件。图的深度优先搜索遍历问题：已知无向图G如图1所示，采用深度优先搜索遍历求图中顶点访问序列。图1 无向图G在图1中，将整个无向图的所有顶点的遍历看作一个复杂的问题，将图中每个顶点的访问看成这个复杂问题的子问题，对每个顶点的访问为一个递归的过程。分析问题：从图中某个顶点Vi出发，访问此顶点，然后依次从Vi的未被访问的邻接点出发，有多个邻接点时，从序号为最小值的开始进行深度优先遍历，当无路径可走时，顺原路返回到上一个邻接点，进行递归的搜索另一个未被访问的邻接点，直至图中所有和Vi有路径相同的顶点都被访问到。该无向图的深度优先搜索过程如图2所示, 图中从V1开始访问，带箭头的实线表示遍历时的搜索路径，带箭头的虚线表示回溯的路径，即递归过程，图中的小圆圈表示已被访问过的邻接点，小圆圈中的数字表示访问顶点的先后顺序。图2 深度优先搜索的过程由上述分析可知，无向图G深度优先搜索遍历的顶点访问序列为：V1V2V4V8V5V3V6V74.2 分治方法的应用实例分治法的基本思想是将一个规模为n的复杂问题分解为k个规模较小的容易解决的子问题，这些子问题相互独立且与原问题相同，折半查找法能够体现分治法的思想。问题：有一组成绩，现要在这组成绩中查找分数为21和85的成绩是否存在。抽象过程：将这组成绩抽象为一个有序线性表，每个分数抽象为线性表中的数据元素，分数21和85抽象为要查找的关键字，所以该问题可以抽象为有序表查找问题。有序表查找问题：已知如下11个数据元素的有序表：（05,13,19,21,37,56,64，75,80,88,92），现要查找关键字为21和85的数据元素。分析问题：有序表的查找采用折半查找法，其基本思路：首先定义待查元素所在范围的下界low和上界high,指针mid指示区间的中间位置，中间位置数据元素的关键字ST.elemmid.key（ST表示有序表名，elem表示数组名）与给定值key（关键字）比较，确定区间范围。当关键字ST.elemmid.key与给定值key相等时，查找成功；当下界low大于上界high时,说明该线性表中没有关键字等于key的数据元素，所以查找不成功。流程图如图3：图3 折半查找问题流程图运用分治法将一个复杂的实际问题转化为多个相同的简单的子问题并用程序化语言表示，最终由机器执行完成，在很大程度上提高了工作效率。5 总结通过对计算机专业课程和计算思维关联分析研究，可以使学生真正理解计算思维与数据结构课程之间的关联，进而帮助学生更好的将计算思维运用于其他计算机专业课程的学习中，并提高学生的计算思维能力，使学生体会到学习计算机专业课程的乐趣，形成一个良性循环，极大地提高学生学习其他课程的积极性和主动性。文中主要研究了递归和分治方法在数据结构课程知识点中的体现，在研究过程中遇到一些问题而不能得到理想结果，通过反复查找错误，修改，最终得到正确结果。另外，文中提到的其他计算思维方法在数据结构课程知识点中的体现仍是值得探讨的问题。参考文献1 教育部高等学校计算机基础课程教学指导委员会.高等学校计算机基础教学发展战略研究报 告暨计算机基础课程教学基本要求M,北京:高等教育出版社.2009.2 中国高等院校计算机基础教育改革课题研究组,中国高等院校计算机基础教育课程体系 2008M,北京:清华大学出版社.2008.3 严蔚敏,吴伟民.数据结构(c语言版)M,北京:清华大学出版社.2010.4 董荣胜,古天龙.计算思维与计算机方法论J,计算机科学.2009(1):1-4.5 陈杰华.程序设计课程中强化计算思维训练的实践探索J,计算机教育.2009(20):84-85.6 王震江,何英,吴绍兵.数据结构M,昆明:云南大学出版社.2008.7 杨晓光.数据结构实例教程M,北京:清华大学出版社.2008.8 贾茹,郝长胜,裴衣非.Visual Basic程序设计课程的计算思维教学实践J,电脑知识与技术.2011(25):6266-6268. 9 吴绍兵.计算思维和程序设计能力的培养J,计算机教育.2011(16):11-14.10 于晓强,赵秀岩,闫丕涛.计算机程序设计课程中计算思维能力的培养J,计算机教育. 2011(13):18-21.The study on the analysis of computer professionalcourses and associated computational thinking A case study of data structureMajor: Computer science and technology Name: Li PingStudent ID: 09407112 Supervisor: Guo YongmeiAbstract: Computational thinking is the hot spot in the current international computer education circle, and is the important topic of computer education that needs to focus on research in the current. In order to calculate the college students thinking ability, improve the ability of college students using computational thinking to solve practical problems, and promote college students better learning computer professional course, you need to study on the analysis of computer professional courses and associated computational thinking. This subject at first, this paper elaborates the research background and significance, then the basic concepts of computational thinking and data structure of knowledge, the data structure course, for example, through two examples analyzed studies recursive and partition in the application of data structure course knowledge point. Through this topic research, we can really understand how the thinking method in the data structure course is to reflect, and to further master data structure course, computational thinking ability can be improved. Keywords: computational thinking; data structure; associate致谢经过一段时间的不懈努力，终于将这篇论文写完，在我写论文的过程中遇到了无数的困难和障碍，但都在同学和老师的帮助下渡过了，在此向帮助和指导过我的各位老师表示最忠心的感谢！这篇论文能够顺利完成，首先要感谢我的论文指导老师郭咏梅老师，开始写论文郭老师给我下载很多文献资料，并帮助和指导我对整篇论文的写作有了清晰的思路，之后在撰写论文的过程中又对我进行了无私的指导和帮助，不厌其烦的帮助我对论文进行修改和改进，再次对指导我的郭老师表示最诚挚、最衷心的感谢！感谢各位计算机专业课老师，是他们教给了扎实的计算机基础知识，使我能够顺利完成这篇论文；同时还要感谢我的同学和朋友，在我写论文的过程中给予我了很多素材，还在论文的撰写和排版等过程中提供热情的帮助。另外我要感谢这篇论文所涉及到的各位学者，本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文的写作。由于我的学术水平有限，所写论文会有不足之处，恳请各位老师批评和指正！