当前位置：首页 > 工作总结 > 其他总结> 数据结构课程总结

数据结构课程总结

时间：2022-10-19 07:23:11 其他总结收藏本文下载本文

数据结构课程总结（精选13篇）由网友“ZhGRLes”投稿提供，下面是小编整理过的数据结构课程总结，希望能帮助到大家!

数据结构课程总结

篇1：数据结构课程总结

数据结构与算法是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。通过学习，先报告如下：

一、数据结构与算法知识点

本学期学的《数据结构与算法》这本书共有十一个章节：

第一章的内容主要包括有关数据、数据类型、数据结构、算法、算法实现、C语言使用中相关问题和算法分析等基本概念和相关知识。其中重点式数据、数据类型、数据结构、算法等概念；C语言中则介绍了指针、结构变量、函数、递归、动态存储分配、文件操作、程序测试与调试问题等内容。

第二章主要介绍的是线性逻辑结构的数据在顺序存储方法下的数据结构顺序表（包括顺序串）的概念、数据类型、数据结构、基本运算及其相关应用。其中重点一是顺序表的定义、数据类型、数据结构、基本运算和性能分析等概念和相关知识。二是顺序表的应用、包括查找问题（简单顺序查找、二分查找、分块查找）、排序问题（直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、归并排序）、字符处理问题（模式匹配）等内容。本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。

第三章主要介绍的是线性逻辑结构的数据在链接存储方法下数据结构链表的相关知识。主要是单链表、循环链表的数据类型结构、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。本章未完全掌握的是循环链表的算法问题和C的描述。

第四章介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。本章主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。本章堆栈算法思想较为简单，所以能较好掌握。

第五章主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。顺序队列(重点是循环队列）和链队列的概念、数据类型描述、数据结构和基本运算算法及其性能分析等。本章同堆栈有点类似，算法思想较为简单，所以能较好掌握；但难点重在循环队列队空、队满的判断条件问题。第六章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及其基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。

第七章“二叉树及其应用”的知识结构主要是：非线性结构数据二叉树的定义、性质、逻辑结构、存储结构及其各种基本运算算法，包括二叉树的建立、遍历、线索化等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。

第八章“树和森林及其应用”介绍树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树之间的转换算法等，在此基础上介绍树的应用---B-树，应用B-树来实现数据元素的动态查找。本章基本掌握树和森林的概念和性质、数据结构、树的基本算法及性能分析，树和二叉树间的转换及其算法，并用应用B-树来实现数据元素的动态查找未能掌握好。

第九章“散列结构及其应用”是逻辑结构“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列函数的概念、散列结构的概念、散列存储结构的概念---散列表、散列函数和散列表中解决冲突的处理方法---开放定址法、链地址法以及散列表的基本算法及其性能分析。本章概念较为多，所以掌握不太好。

第十章“图及其应用”是逻辑结构为“图形”的数据结构及其应用知识内容，主要介绍图的定义和基础知识，图的2种存储结构。图的基本算法以及图的典型应用问题（最小生成树、最短路径、拓扑排序和关键路径等）。

二、对各知识点的掌握情况

我对各知识点的掌握情况总结如下：

第一章不太难，能基本掌握。但关系全书的时间性能分析有些未能全部掌握。第二章本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。本章未掌握的为希尔排序、快速排序、归并排序的时间复杂度分析。第三章，对链表掌握还好，对其数据结构进行了分析，有循环链表，掌握的不是很好，对其中一些用法不熟练。第四章堆栈，本章堆栈算法思想较为简单，所以能较好掌握，但表达式计算问题未掌握好的。第五章的循环队列队空、队满的判断条件问题掌握的不是很好。第六章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。第七章对二叉树掌握较好，其概念，存储，遍历有很好的掌握。就是对二叉排序树有点生疏，它的生成算法不是很会。第八章树树与二叉树之间的转换，森林与二叉树的转换算法思想基本掌握。第九章散列的一些知识，没有深入学习，大概了解了散列存储结构散列表，散列函数，冲突的处理方法。第十章了解了图的逆邻接表的存储结构，关键路径求解算法未能掌握好，不能灵活运用图的不同数据结构和遍历算法解决复杂的应用问题。

三、学习体会

通过学习数据结构与算法，让我对程序有了新的认识，也有了更深的理解。同时，也让我认识到，不管学习什么，概念是基础，所有的知识框架都是建立在基础概念之上的，所以，第一遍看课本要将概念熟记于心，然后构建知识框架。并且，对算法的.学习是学习数据结构的关键。在第二遍看课本的过程中，要注重对算法的掌握。对于一个算法，读一遍可能能读懂，但不可能完全领会其中的思想。掌握一个算法，并不是说将算法背过，而是掌握算法的思想。我们需要的是耐心。每看一遍就会有这一遍的收获。读懂算法之后，自己再默写算法，写到不会的地方，看看课本想想自己为什么没有想到。对算法的应用上，学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。

四、对课程教学的建议

1、感觉上课时的气氛不是很好，虽然大部分人都在听，可是效果不是很好。所以希望老师能在授课中间能穿插一些活跃课堂氛围的话题，可以是大家都非常关心的一些内容，这样既让大家能在思考之余有一个放松，也能够提高学生的学习积极性和学习效率。

2、学习的积极性很重要，有时候我们花了很长时间去写实验报告，也很认真的去理解去掌握，可是最后实验报告可能就只得了一个C，抄的人反而得A，这样的话很容易打击学生的积极性，在后面的实验报告中没动力再去认真写。所以希望老师能在这方面有所调整。3、虽然讲课的时间很紧，但是还是希望老师能在讲述知识点的时候能运用实际的调试程序来给我们讲解，这样的话能让我们对这些内容有更深刻的印象和理解。

篇2：数据结构课程总结

一、知识点概述

1、数据结构和算法

本章作为全书的导引，全面介绍了相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构；数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类；最后介绍算法的时间性能分析以及算法的空间性能分析。

2、顺序表及其应用

本章主要介绍的是线性逻辑结构的数据在顺序存储下的数据结构表的概念、数据类型、数据结构、基本运算及相关问题

一、主要介绍顺序表的定义，基本算法和时间性能的分析；

二、主要介绍一些简单的查找算法和排序算法

3、链表及其应用

本章主要介绍的是线性逻辑结构的数据在链接存储下的数据结构链表的相关知识，本章主要介绍单链表、循环链表的数据类型的定义及一些对数据的操作的算法和时间性能的分析。以及链表的应用主要有多项式相加，归并问题、箱子排序问题等方面。

4、堆栈及其应用

本章介绍了两种不同的存储结构下设计的堆栈，即顺序栈和链栈；分别对顺序栈和链栈的数据类型定义和对数据的操作比若说取栈顶元素和元素入栈等算法。最后介绍了堆栈的应用如：汉诺塔和火车车厢重排问题。

5、队列及其应用

本章介绍了的是队列的定义和逻辑结构、基本算法。队列也有两种存储方式，链队列和顺序队列，其中顺序队列包括顺序队列和顺序循环队列；最后介绍了基数排序问题

6、特殊矩阵、广义表及其应用

本章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题

7、二叉树及其应用

本章在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序

8、树和森林及其应用

树和森林的概念和性质、数据结构、树的基本算法及性能分析，树与二叉树之间的转换和森林与二叉树之间的转换及其相应的算法。其次还有树和森林的遍历和树的存储结构，包括双亲表示法，孩子表示法，孩子兄弟表示法。

9、散列结构及其应用

本章主要介绍了：散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析10、图及其应用

本章主要介绍图的定义和基础知识，图的四种存储结构，图的基本算法以及图的典型应用问题如：最小生成树，最短路径，拓扑排序和关键路径等。

二、学习体会

刚接触这门课时，我却是以为这门课就是一门C语言编程课，也看不到学习这门课到底有啥用，无非就是在上一次C语言，但经过一段时间的学习和老师在课堂上的讲解，我发现，理想和现实始终都是有差距的，数据结构教会我们我们的不仅仅是单纯的编程，还有那一个个算法，教会我们如何通过设计算法来解决某一问题，如何合理的组织数据、高效率的处理数据。学会分析问题，通过设计算法来解决问题。其实只要懂得那些算法的设计思想，一个程序无论采用哪种语言，只要思想正确，一样可以设计出一个好的算法。三、教学建议

1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。

2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。

篇3：数据结构课程建设论文提纲参考

一般不超过1520字。必要时可使用副标题。

以中学英语教学法方向为例，则须说明要解决英语教与学，理论与实践等方面的哪些问题，这些问题应是在教学实践中比较突出又难以解决的问题;或是前人从未解决的，并且能填补某一领域的空白的问题。

国内外学者对该选题曾作过哪些方面的相关研究，本课题在国内外研究中处于何等地位?是属于未开拓的领域，还是在前人已经研究过的基础上作深层次的研究?国内外有哪些论文、论著涉及到本选题的内容?

提出本选题的根据是什么?为什么提出这个选题?本选题的研究有什么意义?从理论的角度看，本选题有哪些方面的突破，其价值取向是什么?本选题与相关领域之间的关系如何?对英语教学会起什么作用?从实践的角度看，本选题是否有助于英语教师和学生把握教与学的动向，使人们在英语教与学的过程中少走弯路，是否有利于提高英语教学质量?

本选题研究有哪几个重要观点，其特点是什么?研究的重点在哪几个方面?研究的难点在何处?怎样从理论与实践出发，对英语教学进行更深入的理论探讨?如何结合英语教学实际对改进英语教学作对策思考?本选题有哪几个新观点?是否填补了国内外同行业研究中的空白?

篇4：高职《数据结构》课程的设计与实现

高职《数据结构》精品课程的设计与实现

该文就高职<数据结构>精品课程的设计与实现作了初步的探讨,同时,简要介绍我们在尝试数据结构案例教学中的.一些体会.

作者：王科 WANG ke 作者单位：湖北省荆州职业技术学院,信息技术系,湖北,荆州,434020 刊名：电脑知识与技术英文刊名：COMPUTER KNOWLEDGE AND TECHNOLOGY 年，卷(期)： 5(23) 分类号：G434 关键词：数据结构案例教学法工作过程导向

篇5：数据结构课程难点讲授方法与知识

数据结构课程难点讲授方法与必备知识

陈燕，屈莉莉，李桃迎

（大连海事大学，辽宁大连116026）

摘要：数据结构是计算机等相关专业重要的专业基础课，各大高校都十分重视该课程的教学效果。捋顺数据结构的先修后继课程，构建该课程的知识体系结构，凝练线性与非线性两大分类知识点，有助于形成该课程的系统化教学体系。将理论学习与工程实践的紧密结合作为讲授课程的侧重点，提高学生解决实际问题的能力。注重培养学生阅读和编制程序的技能，将是突破课程难点的重要方法。

关键词：数据结构；知识点；课程体系；程序设计

项目资助：辽宁省普通高等学校本科创新人才培养机制项目（UPRPI034）；教育教学改革研究项目（UPRP20140605）作者简介：陈燕（1952-），女（汉族），辽宁大连人，教授，博导，信息管理与信息系统专业。

一、引言

《数据结构》一直被认为是计算机、信息管理与信息系统、电子商务等专业重要的基础课程之一。该课程的知识涉及到多学科与多专业，掌握该课程将对学生后续课程的学习起到重要的知识链接作用。数据结构课程的主要知识点包括：①线性表的顺序存储结构与链式存储结构及对应算法；②栈的顺序存储与链式结构及对应算法；③队列的顺序存储与链式结构及对应算法；④串的顺序与链式存储结构及对应算法；⑤数组和广义表的存储结构及对应算法；⑥树和二叉树的顺序与链式存储结构及对应算法；⑦查找方法；⑧排序方法等。为学好这门课程，必须依据课程体系，明确数据结构课程中的概念与术语，灵活运用这些知识点，以达到扎实掌握该课程难点的目的。

二、数据结构的先修后继课程及知识体系结构

1.掌握数据结构课程的先修与后继课程。以信息管理与信息系统专业课程体系为例，清晰了解和掌握与数据结构相关联的先修与后继课程（如图1所示）。

先修课程主要有：计算机信息处理概论、汇编语言程序设计、高级语言程序设计（C、C++、Java等）、计算机组成原理、离散数学、运筹学、图论等。后续课程主要有：数据库原理、信息系统开发方法、编译原理、信息检索、数据仓库与数据挖掘、操作系统、信息集成技术及应用、电子商务与物流信息管理、大数据分析等相关课程。

2.数据结构课程实施框架体系的创新模式。围绕如下页图2所示的数据结构课程实施框架体系的创新模式讲授数据结构课程。明确数据结构课程的知识体系和主要知识点。该模式的优势在于：能够使学生快速掌握数据结构的概念、术语，客观世界问题对应在计算机外部的表示方式，在计算机内部的存储方式，以及如何对它们进行操作（运算）；除此之外，还能够严格按照数据结构课程的各个知识点进行梳理，清楚地归纳出数据结构与其他相关课程的关联关系。

三、运用归纳总结方法对数据结构课程的知识点进行分类

以严蔚敏教授出版的.数据结构经典教材为例，将数据结构的知识点进行分类：第一类将第二章“线性表”、第三章“栈与队列”、第四章“串”、第五章“广义表”划分为数据的线性结构部分；第二类将第六章“树与二叉树”、第七章“图”划分为数据的非线性结构部分。

将自然界的线性问题对应的数据结构实例例举出来，形成数据结构问题的感性和直观的认识；然后再由浅入深地掌握其相关的知识点。例如：①为使管理人员快速找到客户相关信息，用计算机处理该业务应首先确定所使用的数据结构形式，如果希望将电话号码作为关键字，姓名的拼音作为次关键字，那么，会容易地查找出“陈”性拼音顺序排在“周”性之前的线性关系。②到银行办理业务对应的数据结构形式是队列模式，即满足“先来先服务，后来后服务”的服务规律。③对字符串进行存储与处理时，其存储结构具有紧凑和非紧凑形式，因此需按照形式的不同，进行分类处理后，再对其进行操作（如：插入、删除、查找、模式串匹配等）。④到图书馆借书时，图书管理员检索的模式与图书的存放形式有关。

与线性结构相比，非线性结构要复杂得多，即线性表的数据结构中数据元素的逻辑结构与物理结构之间存在一一对应的顺序关系；而非线性的数据结构中数据元素的逻辑结构与物理结构之间不存在一一对应的顺序关系，它们之间的顺序是任意的，也就是说非线性的数据结构中数据元素之间不存在前驱和后继的顺序关系，为使初学者掌握其存储结构对应的操作等相关知识点，必须将数据结构教科书中关于树与图的遍历进行深入而细腻的讲授。以二叉树的遍历问题为例，说明非线性结构应该着重讲授的知识点与教学方式。一般遍历某二叉树的原则是：先确定树根，然后按照树的递归原则进行先序、中序和后序等遍历，下图3所示。从三种遍历的序列可以看出，其每种遍历的结果序列都有其唯一的前驱和后继结点。这个规律说明一个道理：任何的非线性结构的结点元素都可以通过先确定遍历的名称，然后通过遍历方便地对其进行访问，比如：在前序遍历的序列“-+a*b-cd/ef”仿照线性表的定义找出它们之间的前驱与后继之间的关系；另外，同样中序和后继的遍历结果也可以仿照线性表的定义找出它们之间的前驱与后继之间的关系。同时，注意对学生发散性思维的培养，可通过三种遍历结果，进一步解释难以理解的概念推理，推论一：若已知一棵二叉树的前序序列和中序序列，则可以唯一地确定这棵二叉树；推论二：若已知一棵二叉树的后序序列和中序序列，则也可以唯一地确定这棵二叉树。在讲授该本课程知识点的同时，应考虑对后继课程的铺垫与衔接，上述三种遍历结果，对后续《编译原理》课程的前缀码、中缀码、后缀码等概念的理解与掌握将起到重要作用。

四、运用灵活的教学方式讲授难点章节

由于数据结构课程设计到多学科（专业）知识点，因此，教与学的过程中，难免存在难点、“瓶颈”问题和难以理解的算法。为解决此问题，在教学中应注重选用具有代表性的例子，如：在第七章的许多工程类例子与运筹学的例子非常相似，因此，在讲授此章节时，注重教材例子与运筹学学习的重点，但不同专业基础课程的侧重点不同。

1.非线性数据结构的讲授方法。以第七章为例，该章的相关知识内容有：图论、数据的逻辑结构及其对应的物理结构、算法实现的技巧与方法、优化问题、非线性问题的映射方法。主要存在如下难点：①非线性问题的逻辑表示方法。根据工程类例子的实际需求，找出该问题的逻辑表示方法是解决问题的核心。如：将符合多种方案选择的工程类的工序问题（如：排课问题、具有先后时间次序的问题），运用有向图的知识点将该问题表示清晰；应该标明该数据元素属于邻接表还是顺序存储形式。②非线性问题的物理表示方法。通过问题的逻辑表示方法可以将工程类的工序问题转换成有向图的存储方式，然后再选择图的存储结构，如：数组（顺序）存储、邻接表（链式）存储等方式。

③如何编制实现解决非线性问题的算法（程序）。上述的逻辑结构确定了之后，再根据实际问题的要求进行实现程序的核心部分即算法的编制工作，当算法太复杂时，则先设计算法流程图然后再编写实现算法的程序。

2.非线性数据结构的上机实践方法。最为有效的方法是选择学生日常生活中与工程类算法处理流程相近的例子。如在拓扑排序的上机实践选择的题目是给某专业课程进行排序，这个例子的选课过程正好符合工程类工序（周期）施工排序的案例；设计报文或字符编码时，按照第六章中的哈弗曼树的存储结构对报文进行编码；选择顺序线性表的上机例子是在一张学生登记表中进行插入和删除运算；选择链式线性表的上机例子是在一张按照拼音顺序进行插入和删除运算的线性表。

五、阅读程序的技巧与必备知识

数据结构的大量算法都要靠其对应的程序来验证，那么，如何针对数据结构经典算法来编程并且阅读这些经典的算法（程序）呢？这也是学好数据结构这门课程的关键。

1.让学生通过阅读程序，了解如何科学选取一个好的程序（算法）。由于程序是依靠“算法+数据结构”实现的，对一个实际问题来说，可以有不同的程序来实现。仅以一个简单的例子说明，如：运用计算机进行n的平方计算，有3种方法：n的平方=n n；n的平方=1+3+…+2n-1；高级语言自带的求平方函数，如doublepow（n，2）。上述算法一个采用乘法，一个采用加法，一个是高级语言自带的，究竟哪种方法好呢？主要还是看其运算精度、算法的复杂度和空间复杂度等综合指标。

2.让学生通过阅读程序，了解和掌握相关知识点。应补充程序设计分类的相关知识。程序包括：直接程序设计，条件控制的程序，循环控制的程序（计数器控制的循环结构程序的算法、条件控制的循环结构程序的算法、变量控制的循环结构程序的算法）。还应该向学生介绍算法转换为运行程序的经验，如：数据的初始化如何处理；程序中的循环计数器与判断条件以及检验结果如何检验；递归程序中的出口条件判断问题；逻辑变量、精度、机器零、数值零、文本非结构化等归一问题。

3.快速阅读程序的必备知识。按照数据结构的课程要求，必须在读懂经典算法的基础上，才能够编制一个逻辑结构严谨的程序。但是，在教学中发现，有的学生学习方法不当，导致阅读程序的能力低而不能系统掌握数据结构课程的知识点。为了解决这一“瓶颈”问题，在讲授数据结构第一章绪论内容中，增加了程序设计方法、编制算法流程图的标准与规定、算法与程序的区分、如何选用大O来计算算法的时间复杂度和空间复杂度等知识点。递归程序的阅读是数据结构中较难掌握的内容。为让学生顺利阅读递归程序，必须在阅读递归算法之前，补充相关的知识，如：计算机原理“中断”的概念；程序设计中的过程调用的步骤和阅读方法；递归程序本身的特点，以及递归过程与一般过程的区别等。

六、小结

数据结构课程是计算机相关专业重要的基础课程之一，但课程学习难度较大，为提高该课程的教学质量和教学效果，本文梳理了数据结构的先修后继课程，构建了课程的知识体系结构，提炼出数据结构知识点分类的线性与非线性两条主线，强调将理论学习与工程实践的有机结合，提出实现程序设计与具备阅读程序的技巧是解决课程难点的重要手段。

参考文献：

[1]严蔚敏，吴伟民。数据结构[M].北京：清华大学出版社，.

[2]陈燕，等。数据结构[M].北京：科学出版社，2014.

[3]陈志珍，等。数据结构算法应用―基于Floyd算法的医院选址问题求解[J].教育教学论坛，2014，（36）：280-281.

[4]陈燕，等。数据结构教学方法的探讨[J].教育教学论坛，，（49）：82-84.

篇6：数据结构课程中的个性化教学的论文

数据结构课程中的个性化教学的论文

1个性化教学在理论课堂中的应用

在课堂教学中，我们结合当前讲授内容，把硕士入学考试，国家软件水平考试，程序设计、软件开发岗位的招聘考试等试题作为例题或习题引入教学中，并且在课程网站上开设考研专栏、面试和软考专栏、高级专题、竞赛专栏等，以此满足学生就业、考研、自主学习的需要[2-3]。

2个性化教学在作业布置中的应用

在作业布置环节，我们设置必做题和选做题。必做题注重基本知识的巩固和运用，满足共性化教学的需要；选做题往往难度更大，更具开放性，需要查阅更多的资料，甚至要与人讨论，上机实验才能完成。这样做的目的是激发能力强学生的探索和创新欲望，训练其综合运用所学知识解决实际问题的能力。

3个性化教学在实验教学中的应用

实验教学是课程学习的重要环节，我们首先应强调理性实践，督促学生养成分析和思考的习惯，减少实验中的盲目性，强调课前准备、课后总结分析的重要性[4]。几年的教学实践表明，学生的专业素养得到了明显提高。实验教学的设计思想是以个性化培养为基础，以创新能力培养为目标，系统地设计实验教学内容。

3.1提供3个难度等级的实验题目

为满足学生不同需求，教师每次实验提供3个难度等级的题目，要求学生选择其一完成。对于能力强的学生，教师鼓励选择难度大的题目，同时允许学生自己提出选题，目的是开展“创造型应用”实践。难度较低的题目主要是验证型和部分设计型实验，这类题目侧重基本技能和基本理论的训练，要求同学必须熟练掌握数据结构的基本理论、基本概念和基本方法，偏重于对课程内容的理解。难度较大的题目主要是综合型和部分设计型实验。这类实验题力图通过实践培养学生分析问题、找出原理与应用的结合点，使学生学会把书本上学到的知识综合起来解决实际问题，并且在实践中进行反思和领悟。教学实践表明，难度大的综合性实验能够使学生更好地理解和掌握算法设计的有关技术，提升学生组织数据及编写大型程序的能力，为整个专业学习打下更全面、起点更高的基础。

3.2开展面向问题求解能力的实践教学

开展面向问题求解能力实践教学的出发点是以问题为中心引导学生针对实际问题进行数据抽象，分析其特征，力图将其归结为某种理论课已经研究过的数据结构，再以这种数据结构的典型算法为基础，设计出针对实际问题的算法，并利用所学知识对算法的时间效率、空间效率做出估算和评判，最终编写出正确、高效的程序。教师在实验课中引导能力较强的学生选择设计型和综合型的'题目，以问题为中心引导学生组成研究小组。例如，教师在讲完“栈和队列”之后，要求学生运用学过的知识，设计一个模拟食堂售饭的系统，统计每天中午学生在食堂停留的时间；在讲完图的遍历和最短路径之后，要求学生就学校三水校区设计一个校园导游系统，自己确定校园景点，测绘景点之间的路径与距离，建立校园景点地图，设计一个算法使得游客走最少的路，却能遍历全部景点。设置这种只给出问题，而没有细致方案的实验题目，目的是充分调动学生的积极性，让学生自己去分析实际需求，找出所要解决的问题与所学数据结构课程之间的联系，并且最终运用数据结构的知识去解决它。这一教学设计的目标是培养学生综合运用所学理论知识解决实际问题的能力，在解决问题的同时加深对理论的理解，发现创新点，提升创新能力。

4个性化教学在课外学习环节中的应用

4.1以宿舍为单位组成学习小组

作为共性化教学的延伸，教师要求学生以宿舍为单位组成学习小组，就作业和实验等问题开展讨论，以小组为单位完成某些实验项目和大作业，对其中优秀作品进行表扬和展示，以此增强学生的协助精神和竞争意识[5]。

4.2面向问题组成课外学习小组

实验课时毕竟有限，面向问题组成课外学习小组是面向问题求解能力的实践教学的延伸，也是个性化教学的延伸。教师以一个比较复杂的实际问题为中心，组织有兴趣的学生组成研究小组，其目的是针对能力较强的学生，培养综合运用所学理论知识解决实际问题的能力，在解决问题的同时加深对理论的理解，发现创新点，提升创新能力。为了拓展题目的来源，我们组织学生申报校级学生科研课题，参加ACM大学生程序设计等各种竞赛。在申报前，我们提供选题指导；在申报成功后，进行动态辅导。由于数据结构课程组的老师大多职称高、学历高、科研能力强、课题多、档次高，让学生参加老师的课题也是一条满足个性化需求的途径。

4.3网上自主学习

为鼓励学生进行网上自主学习，我们将网络学习作为平时成绩的一部分，考核的内容包括学生在讨论版上的发帖数和回帖数，老师平时发现好的帖子还会直接奖励适当的分数。课程网站在服务共性化与个性化相结合的教学模式方面进行了有益的尝试。首先，课程网站和大多数其他课程网站一样，具有教学大纲、课件、精选题库等栏目，以此满足共性化教学的需要。考虑到有的学生准备参加全国计算机技术与软件专业技术资格（水平）考试，有的计划考研，有的要参加公司的面试等，课程网站还设置了以下栏目：①考研专栏，包括最新考纲、近几年考研真题及参考答案、按章复习、全真试卷；②面试和软考试题专栏，针对学生就业面试和参加国家软件水平考试的需要，收集各公司招聘程序设计、软件测试、系统开发等岗位的试题以及国家软件水平考试的试题，整理和汇集到面试和软考试题栏目；③高级专题和竞赛专栏；④课程社区针对考研、面试、软考设置专门的讨论区；⑤实验指导栏目，就3个难度等级的实验题目进行指导，对优秀作品进行展示。

5结语

为了满足不同层次的学生需求，我们尝试了教学网站服务共性化与个性化相结合的教学模式，几年的教学实践表明，这些做法取得了良好的效果。一方面，课堂变得更加活跃，在标准化命题的前提下考试成绩普遍提高，这说明我们的教学改革并没有牺牲学生的共性化需要；另一方面，学生在软件水平考试、各类程序设计竞赛、就业面试中的表现也有明显提高，课外学习小组、面向问题的研究小组凝聚了一群有进取心的学生，做出了一些优秀作品，带动了整个学院的学习氛围，这表明我们的个性化教学取得了一定效果。

篇7：数据结构课程双语教学的模式和实践

数据结构课程双语教学的模式和实践

数据结构课程在整个计算机相关专业的课程体系中处于承上启下、相互渗透的中心地位,而双语教学又是社会发展对中国高等教育特别是计算机相关专业提出的新要求.本文结合我校正在开展的数据结构课程双语教学的实践,首先分析了双语教学的目标、层次及其与常规教学的区别,然后着重探讨了以学生为中心、注重情感因素的教学模式和以激发学生自主性和创新能力为目的`的实践环节的实施.学生反馈信息表明,数据结构课程双语教学取得了较为满意的效果,达到了双语教学的预期目标.

作者：胡平王忠群 HU Ping WANG Zhong-qun 作者单位：安徽工程科技学院计算机科学与工程系,241000 刊名：中国科技信息英文刊名：CHINA SCIENCE AND TECHNOLOGY INFORMATION 年，卷(期)： “”(3) 分类号：G71 关键词：数据结构双语教学教学模式实践

篇8：数据结构实验报告

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

S.top=S.base;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.base==S.top)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return S.top-S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

p=(ElemType *)malloc(sizeof(ElemType));

if(!p) return ERROR;

p=S.top;

while(p!=S.base)//S.top上面一个...

{

p--;

printf(“%d ”,*p);

}

return OK;

}

Status Compare(SqStack &S)

{

int flag,TURE=OK,FALSE=ERROR;

ElemType e,x;

InitStack(S);

flag=OK;

printf(“请输入要进栈或出栈的元素：”);

while((x= getchar)!='#'&&flag)

{

switch (x)

{

case '(':

case '[':

case '{':

if(Push(S,x)==OK)

printf(“括号匹配成功!nn”);

break;

case ')':

if(Pop(S,e)==ERROR || e!='(')

{

printf(“没有满足条件n”);

flag=FALSE;

}

break;

case ']':

if ( Pop(S,e)==ERROR || e!='[')

flag=FALSE;

break;

case '}':

if ( Pop(S,e)==ERROR || e!='{')

flag=FALSE;

break;

}

if (flag && x=='#' && StackEmpty(S))

return OK;

else

return ERROR;

}

链队列：

Status InitQueue(LinkQueue &Q)

{

Q.front =Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if (!Q.front) return ERROR;

Q.front->next = NULL;

return OK;

}

Status DestoryQueue(LinkQueue &Q)

{

while(Q.front)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

return OK;

}

Status QueueEmpty(LinkQueue &Q)

{

if(Q.front->next==NULL)

return OK;

return ERROR;

}

Status QueueLength(LinkQueue Q)

{

int i=0;

QueuePtr p,q;

p=Q.front;

while(p->next)

{

i++;

p=Q.front;

q=p->next;

p=q;

}

return i;

}

Status GetHead(LinkQueue Q,ElemType &e)

{

QueuePtr p;

p=Q.front->next;

if(!p)

return ERROR;

e=p->data;

return e;

}

Status ClearQueue(LinkQueue &Q)

{

QueuePtr p;

while(Q.front->next )

{

p=Q.front->next;

free(Q.front);

Q.front=p;

}

Q.front->next=NULL;

Q.rear->next=NULL;

return OK;

}

Status EnQueue(LinkQueue &Q,ElemType e)

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof (QNode));

if(!p)

return ERROR;

p->data=e;

p->next=NULL;

Q.rear->next = p;

Q.rear=p; //p->next 为空

return OK;

}

Status DeQueue(LinkQueue &Q,ElemType &e)

{

QueuePtr p;

if (Q.front == Q.rear)

return ERROR;

p = Q.front->next;

e = p->data;

Q.front->next = p->next;

if (Q.rear == p)

Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)

free (p);

return OK;

}

Status QueueTraverse(LinkQueue Q)

{

QueuePtr p,q;

if( QueueEmpty(Q)==OK)

{

printf(“这是一个空队列!n”);

return ERROR;

}

p=Q.front->next;

while(p)

{

q=p;

printf(“%d<-n”,q->data);

q=p->next;

p=q;

}

return OK;

}

循环队列：

Status InitQueue(SqQueue &Q)

{

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base)

exit(OWERFLOW);

Q.front=Q.rear=0;

return OK;

}

Status EnQueue(SqQueue &Q,QElemType e)

{

if((Q.rear+1)%MAXQSIZE==Q.front)

return ERROR;

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

return OK;

}

Status DeQueue(SqQueue &Q,QElemType &e)

{

if(Q.front==Q.rear)

return ERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

return OK;

}

int QueueLength(SqQueue Q)

{

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

Status DestoryQueue(SqQueue &Q)

{

free(Q.base);

return OK;

}

Status QueueEmpty(SqQueue Q) //判空

{

if(Q.front ==Q.rear)

return OK;

return ERROR;

}

Status QueueTraverse(SqQueue Q)

{

if(Q.front==Q.rear)

printf(“这是一个空队列!”);

while(Q.front%MAXQSIZE!=Q.rear)

{

printf(“%d<- ”,Q.base[Q.front]);

Q.front++;

}

return OK;

}

篇9：数据结构实验报告

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵Huffman树。

2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select遍历n个字符，找出权值最小的两个

c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC

总结

1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i

附：

//动态分配数组存储郝夫曼树

typedef struct{

int weight; //字符的权值

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

//动态分配数组存储郝夫曼编码

typedef char* *HuffmanCode;

//选择n个(这里是k=n)节点中权值最小的两个结点

void Select(HuffmanTree &HT,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && HT[i].parent!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&HT[i].weight

}

//下面选出权值次小的结点，用s2指向其序号

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1&&HT[i].weight

}

//构造Huffman树，求出n个字符的编码

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n个叶子n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元

HuffmanTree p=HT+1;

w++; //w的号单元也没有值，所以从号单元开始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

for(i=n+1;i<=m;i++)

{

Select(HT,i-1,s1,s2); //选出当前权值最小的

HT[s1].parent=i;

HT[s2].parent=i;

HT[i].lchild=s1;

HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

//从叶子到根逆向求每个字符的郝夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间

cd[n-1]='';//编码结束符

for(i=1;i<=n;i++) //逐个字符求郝夫曼编码

{

start=n-1; //编码结束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码

{

if(HT[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(HC[i],&cd[start]);//从cd复制编码到HC

}

free(cd); //释放工作空间

}

void main

{ int n,i;

int* w; //记录权值

char* ch; //记录字符

HuffmanTree HT;

HuffmanCode HC;

cout<<“请输入待编码的字符个数n=”;

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用

ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用

cout<<“依次输入待编码的字符data及其权值weight”<

for(i=1;i<=n;i++)

{

cout<<“data[”<

}

篇10：数据结构试题答案

数据结构试题答案

一、单项选择题（每题2分，共30分）

1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A) 单链表 B) 双链表 C) 单向循环链表 D) 顺序表

2.串是任意有限个（）。

A) 符号构成的序列 B) 符号构成的集合

C) 字符构成的序列 D) 字符构成的集合

3.设矩阵A的任一元素aij(1≤i,j≤10)满足：

aij≠0；(i≥j,1≤i,j≤10)

aij=0； (i

现将A的所有非0元素以行序为主序存放在首地址为的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（）。

A) 2340 B) 2336 C) 2164 D) 2160

4.如果以链表作为栈的存储结果，则出栈操作时（）。

A) 必须判别栈是否为满 B) 对栈不作任何判别

C) 必须判别栈是否为空 D) 判别栈元素的类型

5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为（）。

A) front = front+1 B) front = (front+1) % m

C) rear = (rear+1) % m D) front = (front+1) % (m+1)

6.深度为6(根的层次为1)的二叉树至多有（）结点。

A) 64 B) 32 C) 31 D) 63

7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（）。

A) 24 B) 25 C) 23 D) 无法确定

8.设有一个无向图和，如果为的生成树，则下面不正确的说法是（）。

A) 为的子图 B) 为的连通分量

C) 为的极小连通子图且 D) 为的一个无环子图

9.用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）。

A) 一定都是同义词 B) 一定都不是同义词

C) 多相同 D) 不一定都是同义词

10.二分查找要求被查找的表是（）。

A) 键值有序的链接表 B) 链接表但键值不一定有序

C) 键值有序的顺序表 D) 顺序表但键值不一定有序

11.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）。

A) B) C) D) n－1

12.堆是一个键值序列 ,对，满足（）。

A) B)

C) 且 ( ) D) 或 ( )

13.使用双向链表存储数据，其优点是可以（）。

A) 提高检索速度 B) 很方便地插入和删除数据

C) 节约存储空间 D) 很快回收存储空间

14.设计一个判别表达式中左右括号是否配对出现地算法，采用（）数据结构最佳。

A) 线性表地顺序存储结构 B) 栈

C) 队列 D) 线性表达的链式存储结构

15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（）。

A) k + 1 B) 2k C) 2k - 1 D) 2k + 1

二、填空题（每空2分，共28分）

1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____________________________________________r=s;r->next=NULL。

2.在单链表中，指针p所指结点为最后一个结点的条件是___________________。

3.设一个链栈的栈顶指针是ls，栈中结点格式为，栈空的条件为_____________。如果栈不为空，则出栈操作为p=ls;______________;free(p)。

4.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的'结点，则该树有________个叶子结点。

5.树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________。

6.n个顶点的连通图的生成树有__________条边。

7.一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点的相对位置为___________。

8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，________最省时间，__________最费时间。

9.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。

Typedef struct pnode

{ int key;

struct node * left, * right;

}

Void search (int x; pnode t )

{ if (_____________)

{p = malloc (size);

p->key=x;p->left=NULL;

p->right=NULL;

t=p;

}

else

if (xkey) search (x,t->left)

else _________________

}

10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________，可根据需要在前后两个方向上方便地进行查找。

三、应用题（每题10分，共30分）

1.在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)

2.已知待排序文件各记录的排序码顺序如下：

72 73 71 23 94 16 05 68

请列出快速排序过程中每一趟的排序结果。

四、算法题(共12分)

编写算法，实现单链表上的逆置运算(说明：即将单链表中的元素次序反转)

参考答案：

一、单项选择题（每题2分，共30分）

1.D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C 11.D 12.C 13.A 14.B 15.C

二、填空题（每空2分，共28分）

1. r->next=s; 2. p->next=NULL;

3. ls = = NULL; ls=ls->link。 4. 12

5. 双亲表示法 6. n-1

7. i,j,k 8. 冒泡排序，快速排序

9. t= =NULL，search（x,t->right）； 10.循环链表，双向链表

三、应用题（每题10分，共30分）

1．new(q)；

q↑.llink ← p；

q↑.rlink ← p↑.rlink；

p↑.rlink↑.llink ← q；

p↑.rlink ← q。

评分细则：按顺序每对一个给2分，全对计10分。

2．各趟结果如下：

[68 05 71 23 16] 72 [94 73]

[16 05 23] 68 [71] 72 [94 73]

[05] 16 [23] 68 [71] 72 [94 73]

05 16 [23] 68 [71] 72 [94 73]

05 16 23 68 71 72 [94 73]

05 16 23 68 71 72 [73] 94

05 16 23 68 71 72 73 94

四．算法题(共12分)

void invert（ pointer head）

{p=NULL;

while ( headNULL)

{u=head;

head=head->next;

u->next=p;

p=u;

}

head=p;

}

篇11：数据结构简历

目前所在：天河区年龄： 20

户口所在：汕头国籍：中国

婚姻状况：未婚民族：汉族

诚信徽章：未申请身高： 157 cm

人才测评：未测评体重：

人才类型：在校学生

应聘职位：幼教/保育员，家教，销售主管/销售代表/客户代表

工作年限： 1 职称：

求职类型：兼职可到职日期：随时

月薪要求：面议希望工作地区：天河区,越秀区,广州

工作经历

无起止年月：-10 ～ -05

公司性质：所属行业：

担任职位：作业指导

工作描述：辅导小学生作业，照顾小学生

广州地铁起止年月：2012-04 ～ 2012-05

担任职位：地铁志愿者

工作描述：

毕业院校：广东交通职业技术学院

最高学历：大专获得学位: 毕业日期： -06

专业一：软件技术专业二：

起始年月终止年月学校（机构）所学专业获得证书证书编号

语言能力

外语：英语良好粤语水平：一般

其它外语能力：

国语水平：优秀

工作能力及其他专长

熟悉计算机办公软件操作、C语言，数据结构，数据库原理，汇编语言，软件工程等Windows编程、网页制作

个人自传

性格开朗，成绩优良,乐于助人；善于与人交流、适应能力强、具有团体协作精神；喜欢运动

篇12：数据结构面试

1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：

例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link

{

int data;

link* next;

};

bool IsLoop(link* head)

{

link* p1=head, *p2 = head;

if (head ==NULL || head->next ==NULL)

{

return false;

}

do{

p1= p1->next;

p2 = p2->next->next;

} while(p2 && p2->next && p1!=p2);

if(p1 == p2)

return true;

else

return false;

}

2,链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {

int data;

linka* next;

};

void reverse(linka*& head)

{

if(head ==NULL)

return;

linka*pre, *cur, *ne;

pre=head;

cur=head->next;

while(cur)

{

ne = cur->next;

cur->next = pre;

pre = cur;

cur = ne;

}

head->next = NULL;

head = pre;

}

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*& head)

{

if(p == NULL || p->next == NULL)

{

head=p;

return p;

}

else

{

linka* tmp = reverse(p->next,head);

tmp->next = p;

return p;

}

3,判断两个数组中是否存在相同的数字给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？

这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：

bool findcommon(int a[],int size1,int b[],int size2)

{

int i;

for(i=0;i

{

int start=0,end=size2-1,mid;

while(start<=end)

{

mid=(start+end)/2;

if(a[i]==b[mid])

return true;

else if (a[i]

end=mid-1;

else

start=mid+1;

}

return false;

}

后来发现有一个 O(n)算法，

因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

bool findcommon2(int a[], int size1, int b[], int size2)

{

int i=0,j=0;

while(i

{

if(a[i]==b[j])

return true;

if(a[i]>b[j])

j++;

if(a[i]

i++;

}

return false;

}

4,最大子序列问题：

给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大

例如：

整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。

对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：

int max_sub(int a[],int size)

{

int i,j,v,max=a[0];

for(i=0;i

{

v=0;

for(j=i;j

{

v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]

if(v>max)

max=v;

}

return max;

}

那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：

int max_sub2(int a[], int size)

{

int i,max=0,temp_sum=0;

for(i=0;i

{

temp_sum+=a[i];

if(temp_sum>max)

max=temp_sum;

else if(temp_sum<0)

temp_sum=0;

}

return max;

}

在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。

5, 找出单向链表的中间结点这道题和解判断链表是否存在环，我用的是非常类似的方法，只不过结束循环的条件和函数返回值不一样罢了。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。

link* mid(link* head)

{

link* p1,*p2;

p1=p2=head;

if(head==NULL || head->next==NULL)

return head;

do {

p1=p1->next;

p2=p2->next->next;

} while(p2 && p2->next);

return p1;