数据结构与算法推荐信

数据结构与算法推荐信（精选8篇）

1.数据结构与算法推荐信 篇一

《数据结构与算法》课程学习总结报告

100401200510计本（4）班章兴春

本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。

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

学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。

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

第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。

链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。

第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。

第四章串和数组中，我们知道串是一种特殊的线性表，是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。

基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。

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

树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。

第六章介绍了图的概念及其应用，图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。

最后两章集体说明了查找和排序算法，查找教材上介绍了静态查找表和哈希查找表，静态查找表中介绍了顺序查找、折半查找以及分块查找。哈希法中，学习要点包括哈希函数的比较；解决地址冲突的线性探查法的运用，平均探查次数；解决地址冲突的二次哈希法的运用。

排序是使用最频繁的一类算法，可分为内部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交换排序（包括冒泡排序算法、快速排序递归算法）,选择排序（包括直接选择排序算法、堆排序算法）等。

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

总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象。现将各个章节出现的知识点理解情况列举如下。

第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。而对算法的时间、空间性能分析较为模糊，尤其是空间性能分析需要加强。

第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊；排序问题中，由于冒泡排序在大一C语言课上已经学习过，再来学习感觉很轻松。对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。

链表这一章中，除对双向循环链表这一知识点理解困难之外，其他的知识点像单链表的建立和基本算法等都较为熟悉。

接下来的有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。

在学习第六章时感觉较为吃力的部分在于矩阵的应用上，尤其对矩阵转置算法的C语言描述不太理解。稀疏矩阵相加算法中，用三元组表实现比较容易理解，对十字链表进行矩阵相加的方法较为陌生。

第七章是全书的重点，却也有一些内容没有完全理解。在第一节基本概念中，二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用，而对于二叉树应用中的哈弗曼树却比较陌生。

第八章内容较少，牵涉到所学的队列的有关内容，总体来说理解上没有什么困难，问题依旧出现在算法的性能分析上。

散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用C语言描述上。

最后一章，图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径和AOV网学习起来感觉比较轻松，而对于C语言描述却又不大明白。

由于平时上机练习的少，对于教材中很多算法都掌握的不是很熟悉、不过这些都是可以弥补的，我会在剩下的时间中不断练习书上给出的算法和练习，正如教材上说的，学习数据结构，仅从书本上学习是不够的，必须经过大量的程序设计实践，在实践中体会构造性思维方法，掌握数据组织与程序设计技术。

三、学习体会：

多做实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。

复习和考试的技巧，我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。

首先就是复习，前面已经说过其实我们学的算法也就是几十个，那么我们的任务也就是理解这几十个算法，复习也就是要加深你的理解。如何理解算法，然后理解到什么程度呢？ 是能默出整个算法吗？其实不是这样的，数据结构的考试有它的特点，考过程考试了，大家应该都发现数据结构其实不要求你把整个算法背出来，它注重考察你的理解，那么怎么考察呢？其实也就是两种方式吧，一种就是用实例，就是给你一个例子，要你用某个算法运行出结果，我想这个期末考试的时候仍然会有很多这样的题目，比如排序那块就很好出这样的题目，要复习这种题目我觉得很简单，就是每个算法都自己用例子去实践一下，以不变应万变，我期中复习的时候就是这样去做的，而且考试之前我就觉得那个并查集的题目就很有可能会考，于是就自己出了几个例子，做了一下。另外一种考察方式就是算法填空和算法改错，可能有一些同学觉得这种题目很难，其实我们首先可以确定这两种题目肯定是与书上算法有关系的，只要理解了书上的算法就可以了，有人觉得看完书以后什么都懂了，而且要默也默得出来，其实不是这样的，算法改错和填空主要是考察的细微处，虽然你觉得你默得出来，那是能够默出算法的主体部分，很多细微的地方你就会很容易忽略。我想大家考过期中考以后应该都有这种感觉吧？那要怎样解决这种问题呢？ 我觉得有两种方法，一种就是自己去编程实现，这种方法比较有意义，还能够提高编程水平，另外一种就是用实例分析算法的每句话，我认为这种方法是最有效的。

然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，基本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。

我觉得考试的时候没有太多要讲的，只要复习好了，考试的时候细心一点就可以了，然后就是做一个题目开始就要尽量保证正确，如果觉得留在那里等后面做完了再来检查，这样错误还是很有可能检查不出来，我期中考试的时候就基本上没有检查，因为我做每个题目都是确保正确，用的时间也挺多的，然后也觉得没有检查的必要了。

三、对《数据结构与算法》课程教学的建议

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

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

3、要更加重视实验的重要性。

以上便是我对《数据结构与算法》这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！

2.数据结构与算法推荐信 篇二

随着网络电视平台上的多媒体内容的不断丰富,数据量不断膨胀,对用户而言,面对如此丰富而复杂的多媒体内容,要从中挑选出自己真正需要的内容,好比大海捞针。近年来兴起的个性化推荐系统成为解决这些问题的一个重要途径,在电子商务,社交网络等领域得到广泛的应用。

推荐系统的分类可以根据不同的标准分类,常见的分类标准有两种。根据推荐系统是不是为不同的用户推荐不同的数据,可以分为:基于大众行为的推荐系统和个性化推荐系统;根据推荐系统的数据源,可以分为:基于用户相关的推荐,基于内容相关的推荐,以及基于协同过滤的推荐。[1]

协同过滤推荐是目前应用广泛且效率较高的一种个性化推荐技术。以基于内容的协同过滤推荐为例,它的基本思想是:针对目标内容,首先,根据用户操作的历史信息计算内容之间的相似性;然后,根据相似性的大小排序找到目标内容的最相似的K个邻居;最后,将目标内容推荐给使用过他的最近邻居的用户。

但是这个算法存在着以下几个问题:

(1)内容间相似性度量不够准确,传统的内容相似性直接根据用户对内容的评分计算,存在下面几个缺陷:

①当用户评分数据稀疏时,评分数据少,难以度量内容之间的相似性。

②同时对两个内容都进行评分的用户数越多,说明这两个内容的相似性也越高,传统算法没有考虑这个因素。

③两个内容的相同的特征属性数量越多,相似性越高,传统算法也没有考虑;同时,这会产生一个问题,一个新加入的内容存在冷启动问题。

(2)在选取最近邻居时,最近邻居的数量K值很难确定。因为选取最近邻居的数量K,随着评分数量的动态变化,也会很难确定[2]。

针对上述两个问题,本文在设计系统时,对算法进行了调整优化。实验结果显示,本文的算法有效的改善了传统的基于内容的协同过滤的性能。

2 面向网络电视的推荐系统的架构

本文提出的网络电视的多媒体推荐系统架构如图1所示,①数据采集及数据库系统,采集用户操作信息,存放在后台数据库中;②数据预处理子系统,用户操作的信息是以各种形式存放在后台数据库中的,不能满足数据分析的要求,需要将用户信息进行数据预处理,即得到用户—内容评分矩阵和内容特征属性矩阵;③个性化推荐子系统,这是本文系统的主要部分,负责处理数据,并给用户做出Top-N推荐集。

当一个用户访问网站的时候,用户操作信息会通过服务器传递到数据库服务器中,数据预处理子系统定期从数据库服务器中获取用户操作的数据,然后把得到的用户—内容评分矩阵和内容特征属性矩阵提供给个性化推荐子系统做输入。个性化推荐子系统根据当前用户的访问信息,为用户做出个性化推荐,并通过服务器呈现给用户。

3 个性化推荐子系统的算法设计

3.1 用户—内容评分矩阵R和内容特征属性矩阵A

推荐系统存在3个基本数据表:用来记录注册用户信息、用来记录内容信息和记录用户的评分信息(记为用户评分表)。假定参与评分的用户总数是m,接受评分的内容数是n,则建立mn维的评分用户和内容对应的用户—内容评分矩阵R,如表1所示。

该矩阵是比较稀疏的,以MovieLens站点提供的数据集为例,100,000条评分数据,包括1000个用户和1700部电影[3],其评分数据占用户—内容矩阵元素数目的比例为undefined,是稀疏的。

通过对内容的信息数据的整理,可以获取内容特征属性矩阵A。假定内容总数是n,每个内容具有k个具有代表性的属性描述,建立如表2所示的内容特征属性矩阵A(其中,1表示具有某个属性,0表示不具有某个属性)。

3.2 本文的内容相似性计算

内容的相似性可以从两个方面来描述,分别是:

(1)内容i和j获得的评分,评分越接近,说明用户对这两个内容的喜好越相似。并且,如果同时对他们评分的用户个数越多,说明他们的相似性越高。

(2)内容i和j的相同特征属性越多,他们的相似性越高。

因此,在本文中,首先计算内容i和内容j的评分相似性simr(i,j)和属性相似性sima(i,j),然后,将两者进行线性组合,组合后的相似性作为内容间的最终相似性。组合方式如式(4)所示:

sim(p,q)=asimr(i,j)+(1-a)sima(i,j) (1)

其中,simr(i,j)表示内容的评分相似性,sima(i,j)表示内容的特征属性相似性。表示内容的评分相似性的贡献权值,可调节的基于两种来源的内容相似性平衡因子。

3.2.1 内容的评分相似性

内容i和内容j的评分相似性可以用式(2)来计算:

undefined (2)

其中, I表示所有对内容i和内容j共同评分过的用户,对内容i评分的向量表示,J 表示所有对内容i和内容j共同评分过的用户,对内容j评分的向量表示[4]。

根据前面的分析,公式(2)没有考虑到对内容i与j共同评分的用户个数,本文通过设定对内容i和内容j的共同评分的用户个数的阈值ε来调整内容的评分相似性。用公式(3)表示:

undefined (3)

其中,both表示对内容i和内容j共同评分的用户个数,ε表示为调整评分相似性而引入的设定阈值。min(both,ε)表示取both和ε中数值小的一个,那么,如果对内容i和内容j共同评分的用户个数both大于或者等于ε,则结果相当于没有调整;反之,则以both和ε的比值来调整内容的评分相似性。

3.2.2 内容的特征属性相似性

网络电视系统中,电影的属性有类型,导演,主演,上映时间等,本文中,每个属性值都当作特征属性矩阵A的一维,如果有相应的特征属性则值为1,否则为0。设内容i和内容j在n维内容特征属性空间上的属性值分别看作向量i={i1,i2,i3,…,in}, j={j1,j2,j3,…,jn},则内容i和内容j的属性相似性用式(4)来表示:

undefined (4)

特征属性相似性表征了内容i和j本身的属性相似性[5]。

3.3 本文算法的具体描述

输入:用户—内容评分矩阵R,内容的特征属性矩阵A,评分相似性阈值q。

输出:Top-N推荐集。

具体步骤:

(1)在矩阵R中随机找一个用户u,找出他没有购买的内容集合I,然后,把任意一个内容pI作为目标内容。

(2)根据内容的评分矩阵R,按式(2)和(3)计算内容i与其他任意内容j的评分相似性simr(i,j)。

(3)根据内容的特征属性矩阵A,按式(4)计算内容i与其他任意内容j的特征属性相似性sima(i,j)。

(4)根据上面计算的结果,按式(1)计算内容i和其他任意内容j的相似性sim(i,j)。。和预先设定的相似性阈值q比较,如果sim(i,j)>q,则j为目标内容的候选最近邻居,得到内容i的候选最近邻居内容集Ii。

(5)计算用户u对内容i的预测评分R(u,i),根据用户u对最近邻居集合Ii中内容的评分来计算,按式(5):

undefined (5)

其中,Ru,i表示用户u对内容i的预测评分,undefined1和undefinedj分别表示对内容i和内容j的平均评分[6]。

(6)循环执行(2)到(5),计算出当前用户u对所有未评分内容的预测评分,选择其中预测评分最高的前N个内容推荐给当前用户。

4 实验及结果分析

4.1 数据集

本文采用MovieLens站点提供的数据集(http://movielens.umn.edu),MovieLens是一个基于Web的研究型推荐系统,用于接收用户对电影的评分并提供相应的电影推荐列表。目前,该Web站点的用户已经超过72000人,用户评分的电影超过10000部[3]。

随机抽取其中100,000个评价数据,包含了1000名用户对1700部电影的评价,并要求每个用户至少对20部电影进行了评价,评价值为从1到5的整数,数值越高,表明用户对该电影的偏爱程度越高。还整理出这1700部电影的19个属性的描述矩阵A(数据由0和1表示,1表示具有该属性,0则表示不具有该属性)。属性项如下:Action(动作片)、Adventure(冒险片)、Animation(动画片)、Children’s(儿童片)、Comedy(喜剧片)、Crime(犯罪片)、Documentary(纪录片)、Drama(戏剧片)、Fantasy(科幻片)、Film-Noir(悲剧片)、Horror(恐怖片)、Musical(音乐剧)、Mystery(神秘片)、Romance(爱情片)、Sci-Fi(科普片)、Thriller(悬疑片)、War(战争片)、Western(西部片)。

4.2 K-折交叉验证

在本文的测试中,对于每一个给定的目标用户,使用K-折交叉验证方法。

首先,随机的把用户已经评价的所有内容分成5个互不相交的子集,即“折”s1,s2,s3,s4,s5,每个折的大小大致相等。

然后,运行5次测试,每次选择一个内容作为测试集,其他四个作为训练集,这个用户评价的每个内容都将被使用作为一个测试内容[2]。

4.3 实验结果度量标准

使用K-折交叉验证,评价推荐系统推荐质量的质量标准采用统计度量方法中的平均绝对偏差MAE(mean absolute error)进行度量[2]。MAE通过计算训练集预测的评分和测试集实际评分之间的偏差来度量预测的准确性,MAE越小,推荐质量越高;反之,则推荐质量越低。对于评分数据,预测的评分集合表示为{p1,p2,p3,…,pn},对应的实际用户评分集合为{q1,q2,q3,…,qn},则平均绝对偏差MAR定义为

undefined (6)

4.4 实验结果及分析

本小节将根据实验结果,分别分析相似性加权系数、选取近邻时的内容相似性阈值q、内容的共同评分数阈值ε对推荐质量的影响,并最终选定本文测试的最优选择与传统算法做比较。

4.4.1 实验1:相似性权重α

相似性权重α是调整节目评分相似性和特征属性相似性的平衡因子,他对节目相似性影响很大,所以,会对推荐结果有很大的影响。

实验1中,根据数据集特征估计,选取q=0.2,ε=60,α取0.1,0.2,,0.9。进行9组实验,对比实验结果,从图1中可以看出α取0.7时,MAE值较低,推荐效果比较好。这表明评分相似性的权重取70%,属性相似性的权重取30%时,内容的相似性能较好的反应内容之间的相似程度。

4.4.2 实验2:最近邻居选取的相似性阈值q

最近邻居选取的相似性阈值q,他用以克服邻居数K值难以选取的缺陷,决定了最近邻居的数目,对推荐结果影响有很大影响。

实验2种,选取α=0.7,ε=60,由于数据稀疏,q值取大了,最近邻居数目过少,不合理,所以q取0.05,0.1,0.15,0.2,,0.45。进行9组实验,对比实验结果,从图2中可以看出,q取0.15时,MAE值较低,推荐效果比较好。这表明内容相似性小于0.15时,它对目标项目的推荐结果实际意义已经不大。

4.4.3 实验3:共同评分内容数阈值

共同评分内容数阈值 会通过内容评分相似性间接影响内容相似性,对实验结果有影响。

实验3中,选取q=0.15, α=0.7, ε取10,20,,90。进行9组实验,对比实验结果,从图3中可以看出ε取70时,MAE值较低,推荐效果比较好。这表明两个内容的共同评分用户数小于70时,他所产生的推荐意义是可以忽略的。

4.4.4 本文算法与传统基于内容的协同过滤算法[4]性能比较

将传统的基于内容的协同过滤算法和本文算法用于本文选定的数据集,本文算法中,参数选定实验1,2,3种得到的最优值q=0.15, α=0.7,ε=70。

也就是将实验3中的最低MAE值,和传统的基于内容的协同过滤算法比较,可以看出,本文算法的MAE值为0.718564;当K值选为30,40,50,60,70时,传统算法MAE平均值为0.820874。本文算法性能优于传统的基于内容的协同过滤算法。

5 结束语

网络电视正在加速的推广,如何为用户提供更加准确、高效的信息服务是网络电视建设中的一个重要任务。根据用户个性化的需求,为其提供高质量的信息内容和特定功能服务,引起了业内人士的广泛关注和极大兴趣,推荐系统是非常有意义的研究内容。本文针对网络电视的具体应用,对传统的基于内容的协同果过滤推荐算法中的相似性不准确,最近邻居数K值难以确定的问题,提出了优化的方法,并通过实验和实际应用的效果证明了系统的有效性。

参考文献

[1]许海玲,吴潇,李晓东,阎保平.互联网推荐系统比较研究[J].软件学报,2009(,20):(2):350-362

[2]McLaughlin MR,Herlocker JL.A collaborative filtering algorithm and evaluation metric that accurately model the user experience[C].In:Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retriev-al.Sheffield,United Kingdom:ACM,2004:329-336

[3]MovieLens.http://www.grouplens.org/node/73.

[4]Sarwar B,Karypis G,Konstan J,Reidl J.Item-based collaborative filtering recommendation algorithms[C].In:Proceedings ofthe 10th international conference on World Wide Web.Hong Kong,Hong Kong:ACM,2001:285-295

[5]程光华.融合内容过滤和协同过滤的智能推荐系统[D],南京:东南大学2,010.

3.数据结构与算法推荐信 篇三

关键词：错题管理；个性化推荐；算法分析

中图分类号：G434 文献标志码：B 文章编号：1673-8454（2016）11-0067-05

一、引言

网络学习者作为众多Web用户之一，有其独特的特征。在错题管理系统中，更正错题作为最重要的环节，其中主要的策略是巩固练习的实施。如何为学习者推荐个性化的练习，消除学习者知识缺陷，最大程度做到“错题不错”，其推荐技术及算法值得研究。

一般来说，个性化推荐可采用基于规则的技术、基于内容过滤的技术和协作过滤技术。基于内容的过滤技术主要依靠关键词匹配技术，过滤掉那些相关度不高的项目。基于内容过滤通过“资源——用户”关系，利用信息资源与用户兴趣之间相似性来过滤信息，把符合用户兴趣的新的资源推荐给用户，简单有效。

错题管理系统要为学习者推荐的试题应该具有与学习者做错的试题具有相同知识点、类似难度的特征。所以，本研究采用内容过滤方法为学习者筛选出合适的试题资源。

二、算法设计

1.推荐试题特征分析

错题的巩固练习作为错题管理系统中最为重要的一部分，其主要目的在于根据学习者需要，为学习者推荐一定数量相关知识的练习题，以用于练习和巩固知识。在错题管理系统中，推荐给学习者的试题应具有以下三个特征：

（1）与学习者做错的试题同属一个知识点

作为学习者“巩固练习”而推荐的试题，其首先要具备的特征就是要与学习者做错的题目具有相同的知识点属性，只有这样，才能达到巩固该知识的目的。

（2）试题具有尽可能高的质量

试题的质量高低取决于两个方面：一是试题资源的得分，系统用户对试题的评分越高，说明试题质量越好，该题越值得推荐，反之亦然；二是试题被收藏次数，由于错题管理系统有着不同于普通学习系统的特点，它的主要目的在于消除学习者错误。所以，决定试题质量高低的第二个因素是试题被收藏次数。试题被收藏次数越多，说明该题目被做错的次数越多或者该题目极具经典试题的特征，该试题对于当前学习者的质量也就越高，试题也就越值得推荐。

（3）与学习者做错的题目具有类似的试题难度，兼顾基础巩固和能力提升

为维持学习者的学习积极性，保证学习者掌握知识，系统尽量为学习者推荐相同试题难度的试题。但是，当前的推荐是发生在学习者已经发生错误，并且进行了初步的分析之后，所以为起到巩固基础知识和进一步提高能力的作用，系统可以为学习者推荐相邻试题难度的试题。例如，学习者当前出错试题难度为“理解”，那么系统为其推荐的试题集可能包含“识记”、“理解”、“应用”三个难度等级；而如果学习者当前出错试题难度级别为“识记”，那么系统为其推荐的试题则可能包含“识记”和“理解”两个难度级别。

2.算法的设计思路

该部分依据上一小节的讨论，针对错题管理系统中推荐试题所应具有的三点特征进行分析，设计推荐算法。

（1）知识体系的建立

系统采用知识结构树建立知识体系，知识结构树的建立按照“课程——章/单元——节——知识点”的次序依次建立，效果如图 1所示，该图为初二《科学》课程的知识结构树，包含三个级别：课程——章——知识点，这是因为：根据科目的不同，知识结构树的建立所作的取舍也不同。

知识结构树建立完毕后，题目入库将绑定到相应的知识点（可以绑定为“课程”、“章”、“节”、“具体定理、公式、单词等”其中的某一项或者某几项）。当系统为学习者推荐试题时，系统将首先检索出与错题具有相同知识点的题目。

（2）试题质量的确定

根据上一小节的讨论，被推荐的试题质量由两部分决定：试题资源的得分和试题被收藏的次数。

系统采用“5”、“4”、“3”、“2”、“1”评分的形式区分不同质量的资源，将试题分为五个等级。试题得分越高，说明试题资源的质量越好。试题评分者可以是学生或者教师，试题得分取所有评分者评分的平均值，计算公式如公式 1所示。假如试题是新加入到系统中，那么会出现试题没有得分的现象。为避免这种现象的发生，将新加入系统中的每道试题得分默认设为“3”，也即设为中等水平。伴随着系统的使用，试题评分逐渐增多，系统将自适应地计算和更改试题得分。筛选出的试题按照试题得分由多到少排序。

S=公式 1

其中，S表示试题得分，Si表示第i个评分用户对试题的评分，n表示对试题评分的用户总数。

被收藏次数是指一道试题被所有学习者收藏到错题本中的总次数。试题被收藏次数越多，说明试题质量越高，越具有知识点代表性，越值得学习者去做。系统为学习者推荐的试题按试题被收藏次数由多到少排序。

由于试题质量要综合考虑试题得分和被收藏次数两方面因素，而且两个因素没有权重区别（即同等重要），试题得分已经界定取值范围为1～5。所以，为了消除由于被收藏次数单方面过多或者过少而引起的试题质量得分偏高或者偏低的现象发生，试题被收藏次数采取与试题得分相同的五等级划分方法。由此而得出的结果称为试题收藏度，其计算公式如公式 2所示。

F=*CT公式 2

其中，F表示试题收藏度，CTmax表示所有试题中被收藏最多的试题的被收藏次数，CT表示试题的实际被收藏次数。

综上讨论，试题质量的最后得分取试题得分和试题收藏度的均值，其计算方法如公式 3所示。试题质量得分越高，说明试题质量越高。

QS=50%S+50%F=50%（S+F）公式 3

其中，QS表示试题质量得分，S表示试题资源评分，F表示试题收藏度。

（3）试题难度的划分

为指导教育测量和评价，美国教育心理学家布鲁姆发表《教育目标分类学》，将认知领域目标由低到高依次分为知道、领会、运用、分析、综合和评价。不同层次的教育目标代表着不同的知识结果和认知水平。

系统借鉴布鲁姆教育目标分类方法，将试题标记为识记、理解、运用（包含原始分类的运用、分析、综合和评价）三个难度等级。

内容过滤技术的基本过程如下：在同一特征空间下，建立资源特征向量和用户描述文件；依据用户描述文件，比较系统内所有资源特征向量与用户描述文件之间的相似度；把相似度高的资源推荐给用户。余弦相似度计算公式如公式 4所示。

sim（u，q）=公式 4

其中，u表示用户向量，q表示资源向量。

结合第二部分第一节的讨论，试题难度特征值按照其难度级别，依次将识记、理解、运用记为“1”、“2”、“3”。由于跟学习者做错的试题不属于同一知识点的试题是不希望被选出的，试题难度级别最大特征值为“3”，所以为了区别出试题知识点属性，将知识点特征值按照是否为所需要知识点设为“5（任意一个大于5的值）”或者“-5”。

3.个性化推荐流程

根据以上讨论，确定系统整体推荐流程如下：

（1）获取用户描述文件，对学习者做错的题目和试题资源进行特征向量构建。

（2）通过比较资源特征向量与用户描述文件，筛选出与学习者错误试题具有相同知识点、类似试题难度的试题集C1。

（3）C1按照试题质量由高到低排序，形成试题集C2。

（4）C2按照实际需要选出top（N）推荐给学习者。

以上内容过滤算法推荐流程中的关键步骤是特征向量的构建，其思想如下：

IF 出错

THEN 获取出错试题属性信息

SELECT 试题 FROM 试题库

IF 试题知识点属性值=出错试题知识点属性值

THEN 试题知识点特征值=5

ELSE 试题知识点特征值=-5

SET 试题难度级别特征值=1，2，3 WHERE 试题难度级别=识记，理解，应用

试题特征向量=（试题知识点特征值，试题难度级别特征值）

三、算法分析与实现

1.算法分析

为验证推荐算法的有效性，现假定有10道试题，它们的属性信息如图 2所示。采用本文讨论的个性化推荐方法，为学习者推荐3道试题。其详细推荐步骤如下：

（1）假定t0为当前学习者出错试题，按照“试题（知识点，难度）”获取所有试题特征向量值如表 1所示。

（2）接下来，根据公式4计算T1～T9与T0的余弦相似度，计算结果如表 2所示。

舍弃与T0不属于同一知识点（即与T0之间的余弦相似度小于0）和与T0难度级别相差大于1（即与T0之间的余弦相似度小于等于0.94）的题目，也就是只取sim值大于0.94的试题，形成试题集C1={T1， T2， T3， T6， T7， T8， T9}。

（3）按照公式2和公式3计算C1中各试题质量得分如表 3所示。

C1按照资源质量得分由高到低排序，形成试题集C2={T7，T6，T3，T2，T9，T1，T8 }。

该部分代码输出结果如图 4所示。

（4）根据需要，从C2中选出3道试题，即T6，T7和T3，推荐给学习者。

根据上一部分的讨论，可以看出，为学习者推荐的三道试题，符合被推荐试题所应具有的特征。

2.算法功能实现

根据个性化推荐练习算法的设计，在系统功能上予以实现。当学习者做错题目时，点击 “举一反三”按钮，则弹出推荐试题练习窗口，学习者可以进行巩固练习。

四、结束语

为考察个性化推荐练习算法的应用效果，进一步指导错题管理系统设计和开发，笔者在深圳市福田区南华中学某两个班进行了教学实验。在后续的研究中，笔者将第一时间公布实验结果；并进一步优化个性化推荐练习算法，检验其效果。

参考文献：

[1]Stellan Ohlsson. Learning from performance errors [J]. Psychological Review，1996，103（2）： 241-262.

[2]Tzu-Hua Wang. Web-based dynamic assessment： Taking assessment as teaching and learning strategy for improving students e-Learning effectiveness[J].Computers & Education，2010（54）： 1157-1166.

[3]Steven J. Lorenzet， Eduardo Salas， Scott I. Tannenbaum. Benefiting from Mistakes： The Impact of Guided Errors on Learning， Performance， and Self-Efficacy[J].Human Resource Development Quarterly，2005， 16（3）： 301-322.

[4]王文.个性化推荐算法研究[J].电脑知识与技术， 2010，6（16）： 4562-4564.

[5]王智. E-learning环境中个性化推荐系统研究[D]. 重庆：西南大学，2009.

[6]尤秀梅.教学平台中基于知识点的个性化推荐学习的研究与实现[D].天津：天津师范大学，2010.

[7]刘建国，周涛，汪秉宏.个性化推荐系统的研究进展[J].自然科学进展，2009， 19（1）： 1-15.

[8]尤秀梅.教学平台中基于知识点的个性化推荐学习的研究与实现[D].天津：天津师范大学，2010.

[9]刘博.智能教学系统中个性化题库的设计与实现[J].中国电化教育，2010（284）： 110-114.

[10]陈敏，余胜泉，杨现民，黄昆.泛在学习的内容个性化推荐模型设计[J].现代教育技术，2011，21（6）： 13-18.

[11]郑婕.个性化推荐技术在网络教学中的应用研究[D].江西：南昌大学， 2011.

[12]Marko Balabanovic， Yoav Shoham. Fab： Content-Based， Collaborative Recommendation[J].Communications of The ACM，1997，40（3）： 66-72.

[13]郭丽丽.E-learning个性化推荐系统研究[D].山东：山东科技大学， 2008.

[14]John S. Breese， David Heckerman， Carl Kadie. Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C]. Proceeding UAIs 98 Proceedings of the Fourteenth conference on Uncertainty in Artificial intelligence， 1998， San Francisco： 43-52.

[15]Nicholas J. Belkin， W. Bruce Croft. Information Filtering and Information Retrieval： Two Sides of the Same Coin[J].Communication of The ACM，1992，35（12）： 29-38.

[16]曾春，刑春晓，周立柱.基于内容过滤的个性化搜索算法[J].软件学报，2003，14（5）： 999-1004.

[17]张开飞.个性化推荐学习系统的模型研究与设计[D].上海： 华东师范大学，2009.

[18]叶海琴，尹世君.个性化推荐预测模型性能指标研究[J].软件导刊，2010，9（8）： 31-32.

[19]李高敏.基于协同过滤的教学资源个性化推荐技术的研究及应用[D].北京：北京交通大学，2011.

[20]张炜.教育信息共享系统中个性化推荐服务研究[D].陕西：西安电子科技大学，2008.

4.数据结构与算法课程论文 篇四

10计本一班 王晓龙 1004011026 一． 内容概要：

如何合理地组织数据、高效地处理数据是扩大计算机领域、提高软件效率的关键。在软件开发过程中要求“高效地”组织数据和设计“好的”算法，并使算法用程序来实现，通过调试而成为软件，必须具备数据结构领域和算法设计领域的专门知识。

本课程主要学习在软件开发中涉及到的各种常用数据结构及其常用的算法，在此基础上，学习如何利用数据结构和算法解决一些基本的应用问题。通过数据结构的逻辑结构、存储结构、基本算法和相关应用问题来介绍其基本知识和应用知识。

二． 关键字：

数据结构：数据的逻辑结构、数据的存储结构、基本算法；算法分析

三． 课程主要内容和基本原理：

A．数据结构：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。

（1）.分类：

数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。

数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。（2）.四类基本结构：

⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。⑵线性结构。该结构的数据元素之间存在着一对一的关系。⑶树型结构。该结构的数据元素之间存在着一对多的关系。

⑷图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。从上面所介绍的数据结构的概念中可以知道，一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。

（3）.常用的数据结构：

a.数组： 在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。b.栈：

是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。c.队列：

一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。d.链表：

是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。e.树：

是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：

（1）有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。（2）除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。

（3）K中各结点，对关系N来说可以有m个后继（m>=0）。f.图：

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。g.堆： 在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。h.散列表：

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。B．算法分析：

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较。

四．心得体会：

在做完这次课程论文后，让我再次加深了对数据结构与算法的理解，对数据结构的构建也有更深层次的体会。算法的每一次改进和提高，都凝聚着人类的智慧和辛勤劳动，每一次创新都给人类带来了巨大的进步。数据结构与先进的算法能够合理地组织数据、高效地处理数据，扩大计算机的应用领域，提高软件的效率。这充分体现了其重要意义。

五． 参考文献：

5.数据结构与算法推荐信 篇五

《数据结构与算法课程设计》任务书

一、课程设计目的

数据结构与算法课程设计是《数据结构与算法》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。

2二、课程设计题目

2.1 棋盘覆盖

【间题描述】

在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

【基本要求】

（1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc。

1（2）要求输出每一步用什么形态L型骨牌覆盖，覆盖后得到的棋盘图形。（3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优。【测试数据】 【实现提示】

使用分治策略，把棋盘划分成4个小棋盘，然后用一个L型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘。

2.2 Hanoi塔问题（*）

【问题描述】

设a，b，c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,„,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则（1）每次只能移动一个圆盘；

规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；

规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上。

【基本要求】

（1）设计出Hannoi塔游戏，供用户玩；（2）提供正确的搬运方法。【实现说明】

正确的搬运方法使用递归方法实现。【测试数据】

2.3 矩阵连乘问题

【问题描述】

给定n个矩阵{A1,A2,...,An},其中Ai和Ai1是可乘的，i＝1,2,„,n-1。考察这n个矩阵的连乘积A1A2,...,An，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。

【基本要求】

输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如(A1(A2(A3A4)))。【实现说明】 使用动态规划方法。

2.4 多边形游戏（*）

【问题描述】

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“＋”或“*”。所有边依次用整数从1到n编号。

游戏第1步，将一条边删除。随后n-1步按以下方式操作：

选择一条边E及由E连接着的2个顶点v1和v2；

用一个新的顶点取代边E及用E连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。【基本要求】

设计该游戏供用户玩；

对于给定的多边形，给出最高得分计算。【实现说明】 使用动态规划方法。

2.5 0-1背包问题

【问题描述】

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。

【基本要求】

使用动态规划、回溯法以及分支界限三种方法实现。【测试数据】 【实现提示】

2.6 排序方法

【问题描述】

给定n个元素，要求对这n个元素进行排序。【基本要求】

使用多种排序方法，越多越好；

比较每种排序方法的时间复杂度和空间复杂度。【测试数据】 【实现提示】

2.7 哈夫曼编码译码器

【问题描述】

设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件

（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。

【基本要求】

（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；

（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。【实现说明】

（1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、5 循环单链表、双向链表、循环双链表；

（2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；

（3）二叉树本身也可以用静态数组模拟；（4）使用贪心算法

2.8 迷宫问题（*）

【问题描述】

设计一个迷宫并给出正确走法。如： *** *** *** *** *** *** *** 其中0表示可以走，1表示不能走，每一步只能向上下左右移动。【基本要求】

（1）给出迷宫的正确走法，包括没有解的情况；（2）要求界面友好。【测试数据】

【实现提示】 使用回溯的方法。

2.9 继续邮资问题

【问题描述】

假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。

【基本要求】

输入任意的m和n都能设计出最佳的方案，并给出连续邮资区间。【实现说明】 【测试数据】

2.10 图的m着色问题

【问题描述】

给定一个地图，要求给出该地图的最少着色方案 【基本要求】

（1）把地图以及最少着色的方案显示出来则为良好。（2）有友好的界面则为优 【实现说明】

2.11 猜数字游戏（*）

【问题描述】

孩子想1个由4种颜色组成的序列（4种颜色不一定完全不同）。每种颜色只能是6种颜色之一。方便起见，我们用数字1到6表示6种颜色。

计算机必须根据孩子的回答找出孩子所想的颜色序列。计算机在屏幕上显示一个序列，孩子用键盘回答以下两个问题：

猜对的颜色中位置不对的有几个？ 猜对的颜色中位置对的有几个？ 【基本要求】

编程使至多6次问答后猜出序列，如果办不到，至多10次问答后猜出序列。【实现说明】 【测试数据】

如孩子想的是4655 计算机猜想 颜色对位置错的数目 颜色和位置都对的数目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 8 4655 0 4 2.12 大整数计算器

【问题描述】

设计一个计算器实现两个任意长得整数的加、减、乘、除。【基本要求】

设计一个实现任意长的整数进行四则运算的演示程序，要求输入任意长的整数进行四则运算，都能得到精确的结果。

【实现说明】

2.13 查找搜索技术

【问题描述】

给定任意的数组，对于给定的数，查找是否在数组中，如果在，则返回给定数在数组的位置，不在则返回不在信息。

【基本要求】

（1）使用多种搜索方法，越多越好，其中二分搜索技术、线性时间选择是必须的；（2）比较每种排序方法的时间复杂度和空间复杂度。【实现说明】

2.14 Tom,Jerry和奶酪（*）

【问题描述】

猫Tom和鼠Jerry同住在一矩阵地窖中。猫要吃鼠，鼠要吃奶酪。地窖中有2种地砖：有洞砖与无洞砖。一个洞足以让鼠钻入，但猫不能。

以菜单形式完成以下任务：

随机地生成一个地窖，并给猫、鼠和奶酪安排一个位置。如： fffffffffffffff fppppppppppppCf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fppppppppppTppf fffffffffffffff 其中c表示猫，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，猫后行。两者皆满足以下规定： 1）必须上、下、左或右移动 2）鼠必须走1步（穿过p或h）3）猫必须走1或2步（穿过p）

（3）当鼠吃到奶酪或猫抓到鼠时，游戏结束。【基本要求】 【实现说明】

2.15 布线问题

【问题描述】

印刷电路板将布线区域划分成n×m个方格阵列，精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿着直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。

【基本要求】（1）解决题目的问题（2）提供友好的界面 【实现说明】 使用分支限界法。

2.16 魔方工具包（*）

【问题描述】

一个魔方是一个由3×3×3个小立方体组成的立方体。最初立方体的6个面分别涂上不同颜色，我们称之为“最初魔方”。魔方的每一面上的3×3个小立方体组成它的一层。

魔方所能见到的每一层（6个面）都能旋转90，180，220或360度。所有层的旋转轴都垂直于面且通过其中心。旋转的结果是另一个魔方，它的所有面的颜色都改变了。

现在我们用字符来代替颜色：U=上，D=下，F=前，B=后，L=左，R=右。任何一个序列的旋转都能表示成{U,R,F,B,L,D}中一些字符组成的字符串，其中每个字符表示它所 11 指定的面顺时针旋转90度。

【基本要求】

（1）编程完成以下3个任务（菜单形式），你可以假设任何输入的字串长度都<=35。你的算法能处理非法输入的情况，如： 输入 输出 L L LL LL LLL LLL LLLL “”(空串 LLLLL L LLRRRFFFFRLB LLLB HELLO “error”

（2）判断输入的2个字串的旋转结果是否相同。如 输入一 输入二 输出 RU UR no RRFFRRFFRRFFRRFF FFRRFFRR yes RRFFRRFFRRFFRRFF RRFFRRFF no（3）求出输入字符串至少须使用几次才能将魔方转回到“最初魔方”（一定大于0）输入 输出 L 4 12 DD 2 BULB 36 RUF 80 BLUFF 180 【实现说明】

2.17 图的建立与输出

【问题描述】

建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

【基本要求】

给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果 【实现说明】

无

2.18 图的建立与输出

【问题描述】

建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出 13 图的邻接矩阵。

【基本要求】

给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果。【实现说明】

无

2.19 以队列实现的仿真技术预测理发馆的经营状况（*）

【问题描述】

理发馆一天的工作过程如下：

1)理发馆有N把理发椅，可同时为N位顾客进行理发。

2)理发师分三个等级（一级、二级、三级），对应不同的服务收费。3)当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。

4)一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。5)若理发馆每天连续营业T分钟，求

（1）一天内顾客在理发馆内的平均逗留时间；（2）顾客排队等候理发的队列长度平均值；

（3）营业时间到点后仍需完成服务的收尾工作时间；（4）统计每天的营业额；

（5）统计每天不同级别理发师的创收。

【基本要求】

1)模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；

2)每个顾客到达和下一顾客到达时间的间隔应是随机的； 3)理发师编号、理发师级别和每天的营业时间由用户输入；

4)某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待 ；

5)每个顾客进门时将生成三个随机数:(1)durtime:进门顾客理发所需服务时间（简称：理发时间）；(2)intertime:下一顾客将到达的时间间隔（简称：间隔时间）；(3)select:服务选项。

6)服务收费：应包含服务时间和理发师级别两个因素。

7)除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。【实现说明】

用户输入每位理发师编号、级别号和营业的时间，结合随机数进行测试。

2.20 防抄袭管理系统（*）

【问题描述】

对于给定的文档，如word文档，txt文档等，找出文档的相似度。【基本要求】

（1）要求找出给定的两个文档的相似度以及标出相似的地方（1:1）；（2）要求找出给定的一个文档与给定的文件夹的所有文档的相似度，以及标出相似的地方(1:n)（3）要求找出给定的文件夹下面所有文档的相似度(n:n)。【实现说明】

给定相似文档进行测试。

2.21.设计一个停车场管理系统，模拟停车场的运作

设计要求：通过此程序具备以下功能：

1、要求以栈模拟停车场，以队列模拟车场 15 外的便道，按照从终端读入的输入数据序列进行模拟管理；

2、要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻；

3、该系统完成以下功能：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）；

4、要求栈以顺序结构实现，队列以链表实现。

2.22． 赫夫曼编码

设计要求：自己找一篇不少于200个单词的英文文章，分析该文章中每一个字符的出现概率（包括标点符号，区分大小写），根据分析结果对文章中每一个字符进行赫夫曼编码，并将编码原则储于一个独立的文本文件中。最后，根据这个编码原则，将英文文章转换为01 串存储于一个文本文件中，再编写一个解码程序，将编码解码为原文件。如：英文文章为 aaabbc 则编码规则为 a-----0 b-----10 c-----11 英文文章将被转化为 000101011 2.23.并查集：检查网络

题目要求：给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？ 输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的 16 序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。

当N为0时，表示全部测试结束，不要对该数据做任何处理。

输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。

当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。

两组测试数据之间请输出一空行分隔。

2.24.教学计划编制问题（图的应用）

[问题描述] 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。[实现提示]

1、输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。

2、应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

3、若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式可以自己设计。

4、可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。

============================= 17 2.25.药品销售统计系统（排序应用）

【问题描述】

设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。【实现提示】

在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。

药品信息的元素类型定义： typedef struct node { char num[4];/*药品编号*/ char name[10];/*药品名称*/ float price;/*药品单价*/ int count;/*销售数量*/ float sale;/*本药品销售额*/ }DataType;存储药品信息的顺序表的定义： typedef struct { DataType r[MaxSize];int length;}SequenList;

2.26梯运行仿真程序

[问题描述] 办公大楼有若干层（例如，十层），每层有电梯，同时有步行楼梯；

全楼有若干部（例如，不多于10部）电梯同时供使用，电梯容量为24人，速度每上下一层需5秒，在某一层停下至少15秒。其运行状态可分：向上、向下、停止，当前乘客数，当前所在层数。它设有一个“按钮数组”，例如第五层的按钮按下，意味着有乘客在第5层到达目标层，等等。在楼的每一层，有电梯数，有按钮表示有人等待向上或向下，由若干人在等待，有若干电梯在本层停下，等等。

在大楼中（包括进出）的总人数不超过500 人，每个人站在电梯前有个目标层，他有一个最大的忍受等待时间，因为他可以选择电梯或是步行走楼梯，等等。

还有下面若干假设：在每个时间段要进大楼的人数在0～199 之间随机取值；

用电梯的每个人的目标层在1～10 之间取值；一个人在进电梯或改走楼梯之前的等待时间在180～360 秒范围内随机发生；一个人到达目标层后第二次再乘电梯中间的工作时间在400～6600 秒间随机取值。[基本要求] 编写一个程序，模拟办公大楼中全部电梯的工作过程。这个仿真程序可以用来监测系统运行情况，改善大楼管理，它也可以看成是一种游戏程序。

2.27国交通咨询模拟

[问题描述]

处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅 途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供最优决策的交通咨询。

[基本要求]

（1）提供对城市信息进行编辑（如：添加或删除）的功能；

（2）城市之间有两种交通工具：火车或飞机，提供对全国城市交通图和列车时刻表及飞机航班表进行编辑的功能。（信息的输入方式可以是文件输入和键盘输入两种方式）

（3）提供两种最优决策：最快到达和最省钱到达。（选作：旅途中转次数最少的最优决策）

（4）旅途中耗费的总时间应该包括中转站的等候时间。

（5）咨询以用户和计算机的对话方式进行。

a）由用户输入起始站、终点站、最优决策原则和交通工具；

b）输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详 细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

三、课程设计的基本要求

1．问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？

2．逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。

3．详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，20 写出数据存储结构的类型定义，写出函数形式的算法框架。

4．程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。

5．程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。

6．结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。

7．编写课程设计报告并提交相关内容

设计最终需提交的内容包括：

A）课程设计报告（1份，A4纸打印，同时包括一份电子版）报告要求版面清晰，格式规范，否则重新编写。报告内容要求包括：

（1）问题的概述、分析及研究意义；（2）数据结构的逻辑设计和物理存储设计；（3）重要算法的设计、流程描述或伪代码描述；

（4）数据结构的时空复杂性分析以及重要算法的复杂性分析；

（5）程序最终实现结果（包括重点结果界面的抓取，能过说明问题的重要实验结果数据的打印或其可视化结果等）。

（6）参考文献（如果需要）。

（7）附录部分附上关键数据结构的定义及关键算法的源代码。

B）完整的程序系统（电子方式提交）

能够对输入产生相应的输出，同时尽量的完成可视化演示。

该部分包括源代码和可执行文件两个部分（提交的时候需清楚的注明个人姓名，班级）。

C）源程序文档（电子方式提交）

源程序代码要求结构清晰、可读性好。应对源程序中的类说明（如果采用面向对象方法设计），函数说明，接口说明，关键变量说明等进行注释；源程序要进行适当的缩进编排。

D）答辩报告（编写Power Point答辩报告，电子方式提交）要求突出重点，思路清晰。同时就此报告准备答辩。

E）所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均 21 可），压缩后的文件按规定格式进行命名，命名格式为：学号+姓名.rar（如060701014石海杭.rar）。8．每位同学只能选择一个题目并完成

四、评分标准

1、基本功能：

50分。

通过功能的实现情况、界面的完成情况、软件的实现情况进行评分。

2、设计报告及使用说明书： 20分 按照报告的要求进行评分。

3、回答问题：

4、平时考勤：

5、核分标准：

15分 15分 100分

（90~100为优、80~89为良、70~79为中、60~69为及格、，60以下为不及格）

五、参考书目

严蔚敏.《数据结构》（C语言版）.清华大学出版社 刘玉龙．《数据结构与算法》.电子工业出版社.严蔚敏等《数据结构题集》（C语言版）.清华大学出版社

6.数据结构与算法推荐信 篇六

每一次课程设计，都有不一样的感受，通过课程设计，对我而言，得到的不仅仅是知识，更是获得知识的方法，这显得更加的重要。

本次课程设计，我的设计题目是校园导游程序，本程序主要用到的是课本中图的知识，以校园中的景点作为顶点，以景点间的路径作为边，就构成了图。我用到的时临界表存储结构，这样对空间的浪费不至于很大。主要完成的功能是最短路径和所有路径的算法，最短路径用的是书上的Dijkstra算法，原来我对这个算法的只是出于一个对大致的过程知道的程度，课程设计之后，我对该算法可以说是很熟悉了，不管是算法思想还是代码。另一个主要功能是求两个景点间的所有路径，这个算法书上没有提到，我一步步的摸索，用了一个递归的思想，再经过不断的修改，一次次的单步运行，通过查看相应变量的变化情况，将此算法实现的。最后完成整个程序。

课程设计，本人感觉对于写程序，首先要要的是思想，即完成每个功能需要的算法思想，在想好思想后，就要具体到代码，计算机能够识别的代码，代码写好后，大多情况下是有错误的，首先要排除语法错误，然后时语义错误，在排错的过程中，我用到的最多的是单步运行，感觉单步运行这种方式很管用，通过一步步的运行，通过每一步的运行，观察其中变量的变化情况，可以很容易的知道代码是哪一步出了错误，这样对排错有很大的帮助。在课程设计的过程中，曾遇到过很多的问题，如对路径字符串的处理，整个递归一步步的往下调用和返回过程，还有很多细节的问题。在遇到问题时，首先想到的是自己思考，分析过程，查找资料，上网百度，通过自己的努力还没有解决时，这是首先需要问的是自己旁边的同学，和同学讨论，有时还争得面红耳赤，如果最后将此不下，就向老师提问。这课程设计的过程中，我几乎所有的问题处理流程就是这个样子的。我感觉这就是一种学习的方法，在学习中遇到难题时的学习方法，要把这种学习的方法变成一种习惯，这才是每次课程设计应达到的一种效果。

7.数据结构与算法推荐信 篇七

关键词：数据结构与算法,实验教学,改革

数据结构与算法是计算机专业的核心基础课程之一, 通过本门课程的学习, 可以使学生透彻地理解各种数据对象的特点, 学会数据的组织方法和实现方法, 并进一步培养良好的程序设计能力, 而该课程的实验课是学生验证、掌握和应用数据结构理论的重要途径。

一、数据结构与算法上机实验课程的现状

数据结构与算法课程涉及大量数据类型及算法, 理论性很强, 抽象难懂, 对学生的学习造成了一定的难度。受传统的教学模式的影响, 课程的实验教学一直处于从属地位, 同时因学生基本程序设计能力有待提高等因素影响, 实验效果不甚理想。如何使学生理论学习和实践学习相结合, 提高学生的实践能力, 已成为高等院校培养应用型本科人才的一项重要课题。

目前在数据结构与算法实验教学过程中发现的问题主要有以下几点:

1.学生对于上机实验的重要性认识不够。对于学生来说, 由于部分院校的教学资源所限, 数据结构与算法课程长期以来都是课堂和实验分开进行, 授课教师对于上机实验过程几乎不参与, 这就导致了学生重视课堂理论的讲授, 而忽视上机实验课程的重要性。

2.课程实验缺乏层次性。上机实验教学内容大多为简单的验证性实验, 缺乏综合性、应用型、设计性实验项目。增加论述。

3.课程理论性强、难度大。数据结构与算法课程理论性极强, 抽象难懂, 很多学生在课堂听课过程中不能够完全理解, 无法建立起数据结构和相应算法的概念, 长此以往导致学生对于这门课程的畏惧和抵触情绪, 同时也严重打击了学生上机实验的积极性。

4.学生对掌握程序语言的程度不够。学生对程序设计语言掌握得不理想, 也是导致学生上机实验缺乏积极性的一个重要原因。数据结构与算法是学生在学过一门或几门语言课程之后开设的, 其算法大都由C或C++语言描述, 要求学生能够使用某种程序设计语言对算法进行程序设计, 并且上机调试通过。以我学院为例, 学生在学习数据结构时, 虽然已经学过C语言, 但仅是初学, 并不精通。因此对于抽象的数据类型、动态分配存储空间等概念, 在理解上还是有一定困难的。由于对程序设计语言掌握得不好, 大部分学生在编程的过程中陷入迷茫的状态, 阻碍了他们对各类数据结构和算法等知识点的理解和应用, 使教学目标难以实现。

二、实验教学的改革和探索

(一) 实验教学内容的改革

数据结构与算法课程主要使学生掌握程序数据的结构、组织和管理技术以及在此基础上的算法设计与分析技术, 不仅为后续课程操作系统、编译原理、数据库原理、软件工程、人工智能等课程提供必要的知识准备, 更重要的是可以提高学生软件分析、设计、编程和数据组织的能力。根据数据结构与算法整个课程体系的划分, 本课程的上机实验主要分为以下几种类型:

1. 验证性实验。

这一类型的实验主要在上机实验课中完成。以西安交通大学城市学院为例, 本门课程有8个学时的上机实验, 主要任务是将课堂上讲过的内容以实验的形式贯穿起来, 所涉及的实验以教材中提及到的基本算法和例题为主, 基本都是验证性的实验。以单链表为例, 要求学生通过定义线性表的抽象数据类型, 在链式存储结构下完成单链表的建立、插入、删除、查找、求前驱节点和求后继节点等操作, 通过实验教学, 在加深学生对数据结构课程内容理解的同时, 达到理论联系实际的目的。

学生通过完成此类实验, 一方面可以强化基础知识, 另一方面也可以通过编写算法掌握高级语言程序, 同时还可以训练学生良好的编程风格、基本实验技能和科学严谨的实验作风。

2. 综合性实验。

综合性实验部分实在课程设计阶段来完成。主要任务是考查学生运用所学基本数据结构解决实际问题的能力。所设计的实验项目可以是课程设计指导书中提供的参考题目, 也可以是工程中的实际课题, 选题要与所学阶段性知识紧密联系, 任务有一定的难度和综合性, 对学生的编程思路和方法有启发作用的项目。例如:学习了栈和队列知识后可以要求学生设计一个停车场管理系统, 以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟管理。又如:学习了图的路径的相关算法后, 可利用学生熟悉的当地交通情况、旅游景点等设计问路系统。这些问题与课本理论知识联系密切, 而且具有一定的实用价值。

3. 研究性实验。

此类实验是针对于学有余力的学生, 可安排一些研究性实验, 针对计算机专业学生的特点, 可以以软件开发的形式进行, 让学生以创新者的角色去做实验。所设计的实验项目都是实际工程中的课题, 题目的解法要求符合工程实际情况, 具有可行性。学生可以自己提出实验题目和开发工具, 自己设计实验过程等, 有条件者还可以进入工程实践中进一步提升实践能力。

(二) 实验教学方法的改革

根据我院学生的特点和学院培养应用性本科人才教育宗旨, 我们在实验教学的方法上进行了改革。

1. 先简后难, 循序渐进。

在上机实验课中, 主要以验证性试验为主, 针对堂课讲授的知识安排配套的练习。练习的内容以编写的数据结构与算法实验指导书的形式发给学生, 每节课明确实验任务、实验方法和结果要求, 使学生在有限的课堂时间中完成相应训练目标, 掌握基础知识, 夯实基础;在课程完成之后的课程设计阶段, 加大难度, 主要以综合性的题目为主, 对于程度特别好的学生也可以完成研究性的项目。针对这一阶段的训练, 我们也编写了相应的课程设计指导书, 提供给学生适合的参考题目和编程提示。有助于学生更好的完成项目要求。通过一系列的训练, 培养学生算法设计能力以及创造性思维, 以达到提高学生应用知识解决复杂问题能力的目标。

2. 启发式教学和分组实验。

在教学方法上, 把传统教法中老师讲, 学生听的“灌输法”转化为“启发式”的教学方法, 引导学生自主思考, 常常提问“WWW”, 即“What, Hao, Why”:这个问题做什么的?需要用的哪方面的知识?怎么去解决问题?如何解决?教师教给学生提出问题、分析问题和解决问题的方法, 学生自行探究问题和解决问题, 激发学生探求知识的欲望和积极的学习兴趣。

在训练的形式上, 改变传统的“集体化”路线, 根据程度的不同将2~4名学生分成多个小组, 任命一名学习能力强、组织能力好的学生担任项目组长, 以软件开发小组的形式协同工作, 合理分工, 共同学习, 通过团队讨论解决问题。各小组成员不仅要完成自己的工作, 还要与其他成员合作, 共同完成整个项目。教师应多给予学生鼓励, 激发学生的思维, 促进他们合作的欲望和热情, 使课堂活泼积极, 并且适时的提供必要的启发式帮助, 只提供意见, 不具体替学生完成。让学生从解决问题和团队合作中获得成就感和自我认同感, 在轻松的氛围中达到激发学生兴趣, 提高学生综合实践能力的目标。

(三) 项目答辩和实验报告结合的考核方法。

1. 项目答辩。

在课程设计实验结束时, 专门抽出时间对个小组成员的工作进行考核, 要求每个小组选派2名学生进行答辩, 在规定时间内陈述小组工作情况, 遇到的问题及解决的办法, 最终达到的效果及心得体会等。根据答辩情况, 给予优、良、中、差和不及格五档评分。通过这种团队合作和答辩的方式大大提升了学生的实践能力、组织和口头表达能力及合作精神。

2. 实验报告的规范。

课程设计实验结束后要求学生写出实验报告, 以作为实验环节评分的书面依据之一和存档材料。实验报告以规定格式的电子文档书写、打印并装订, 排版及图、表要清楚、工整。每个小组每个题目提交一份实验报告, 实验报告除介绍本小组成员所做工作外还应包括以下内容:

(1) 需求分析。以规范的技术文档语言陈述说明项目设计的任务并明确规定: (1) 输入的形式和输入值的范围; (2) 输出的形式; (3) 程序所能达到的功能; (4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。

(2) 概要设计。说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次关系。

(3) 详细设计。本阶段的主要任务是实现概要设计中定义的所有数据类型, 对各操作、主程序和其他模块均要求写出伪码算法, 同时可以使用流程图或者N———S图进行描述, 画出函数和过程的调用关系图。

(4) 调试分析。在程序的调试过程中出现的问题以及解决办法, 回顾和讨论设计与实现过程中的相关问题。

(5) 测试结果。列出完整和严格的测试数据, 包括输入和输出。

(6) 用户使用说明。说明程序的使用方法, 并列出每一步的具体操作步骤。

(7) 代码注释。算法必须给出完整、正确的文字注释。

三、改革的效果

通过数据结构与算法实验教学的改革, 学生的学习热情和积极性得到了明显的提高, 学生的主动思考和积极实践的热情得以激发。学生能够在实验期间主动积极的参与并解决问题, 提高了学生的实践能力和编程能力。通过分组合作的方式进行项目训练, 培养了学生的团队合作意识和严谨的工作作风。通过小组答辩, 教师了解了每组学生的学习情况, 把握学生的学习状态和程度, 有助于在日后的教学中给予适当的指导。教师在此过程中不断总结问题, 积累经验, 使教学质量得到显著提高。

四、结束语

数据结构与算法在计算机课程体系中占据重要地位, 其实验环节的教学质量直接关系到本门课程的学习效果。在实验教学过程中必须以培养学生的综合实践能力为宗旨, 不断改进教学方法, 加大实验教学力度, 做到夯实基础, 提高能力, 为学生后续专业课程的学习打下良好的基础。

参考文献

[1]耿国华.数据结构——C语言描述[M].北京:高等教育出版社, 2006.

[2]赵玉霞.《数据结构》课程上机实验改革初探[J].福建电脑, 2007, (4) :213-214.

[3]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.

[4]宁正元, 王秀丽, 林大辉.与数据结构[M].北京:清华大学出版社, 2006.

8.数据结构与算法推荐信 篇八

关键词:数据结构与算法;综合性实验;设计性实验

一、引言

在计算机科学与技术、软件工程等专业中,《数据结构与算法》课程具有较强的实践性,因此实验教学是该课程教学过程中的一个非常重要的环节。在以往的实验教学中,学生都是按照已经设计好的实验要求和步骤进行着验证性的实验,学生一般是被动地接受或机械式地编程,以完成实验讲义中的验证或孤立的单元实验。这种实验教学模式使得学生缺乏主动性和独立思考问题的能力,不利于他们综合素质的提高和自主创新能力的培养。为了克服这些不足,使学生真正能把理论知识灵活运用到实践当中,我们开设了《数据结构与算法》课程综合性、设计性实验项目并立项进行实践研究,通过两三年的实践,取得了一些经验和成果,学生的实践能力也有了较大提高。

二、综合性、设计性实验项目的实践环节

1.实验项目的选择。

通过《数据结构与算法》课程的学习和前期验证性实践环节,学生已初步具备了进行综合性、设计性实验的能力。为进一步提高学生的设计能力和编程能力,我们设计了4个综合性、设计性实验项目供学生选择:

①校园导游系统的设计(设计性);

②书管理系统的设计(综合性);

③哈夫曼编码/译码器(综合性);

④散列表的设计与实现(设计性)。

2.实验项目的内容。

校园导游系统的设计

问题描述:

设计一个校园导游程序,为来访的客人提供信息查询服务。

基本要求:

①设计你所在的学校的校园平面图,所含景点不少于15个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息,以边表示路径,存放路径长度等相关信息;

②为来访客人提供图中任意景点相关信息查询;

③为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短路径(静态或动态表示出来)。

图书管理系统的设计

问题描述:

设计一个图书管理系统完成图书管理基本业务。

基本要求:

①每种书的登记内容包括书号、书名、著作者和库存量;

②对书号建立索引表(线性表或树表)以提高查找效率;

③系统主要功能如下:

采编入库:新购一种书,确定书号后,登记到图书账目表中,如果表中已有,则只将库存量增加;

借阅:如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;

归还:注销对借阅者的登记,改变该书的现存量。

用户管理。

数据存储(要求用文件实现数据存储)。

哈夫曼编码/译码器

问题描述:

设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。

基本要求:

①随机抽取20个文本文件作为统计样本,统计这些文本文件中各字符的平均出现次数,作为权值,建立哈夫曼树及各个字符的哈夫曼编码;

②将用户输入或选择的待压缩文本文件利用①建立的编码表进行编码,生成压缩文件(后缀名.cod);

③输入一个待解压的压缩文件名称,并利用相应的编码表进行译码;

④显示指定的压缩文件和文本文件;

⑤(选作) 把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算实现真正的数据压缩,并求压缩比。

散列表的设计与实现

问题描述:

设计散列表实现电话号码查找系统。

基本要求:

①随机生成1万个记录,每个记录有下列数据项:电话号码、用户名、地址,每个数据项的内容都是随机生成的;

②分别以电话号码和用户名为关键字建立散列表(自行选择或构造合适的散列函数);

③采用双散列法解决冲突;

④查找并显示给定电话号码的记录;

⑤查找并显示给定用户名的记录。

3.预期目标。

进一步巩固和加深对《数据结构与算法》课程中基本知识的理解,熟悉各种逻辑结构及存储结构;

了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;

培养学生从事软件开发的编程及创新能力;

提高学生综合运用所学的理论知识解决问题的能力;

训练用系统的观点和软件进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。

4.实验项目的组织与实施。

针对综合性设计性实验项目,安排学生自选项目并进行项目设计和开发,每个项目20学时,按照下面的项目开发设计步骤,最后完成课题的总体设计与实现。

项目分析

根据实验项目内容的要求,充分地分析和理解问题,明确问题要求做什么、解决什么问题、实现什么功能。

概要设计

对项目内容描述中涉及的操作对象,设计相应的数据结构,并按照以数据结构为中心的原则对模块进行划分,定义主程序模块和逻辑结构。逻辑设计的结果是每种数据结构的定义(包括数据结构的描述和每个基本操作的功能说明)。

详细设计

为各个数据结构设计相应的存储结构并写出各模块的算法。设计是编程中重要的一环,在“详细设计”过程中,引导学生结合总体设计制订合理的程序结构和算法,理顺各个模块之间的相互关系,将详细设计的结果用结构图及流程图清晰地描述出来,在本过程中,教师要尽可能帮助学生养成自己解决问题的习惯。

编程

将详细设计的结果进一步求精为程序设计语言程序。在该环节中,教师应指导学生按照规范的程序编写方法去编程,并指导学生按照大型软件中常用的调试方法对程序进行跟踪及改进。

结果分析

在编程过程中及结束后,形成学生、课题小组组长、指导教师三位一体的项目质量监控体系,做到对各个阶段的结果都能进行实时的检测,如有不足之处,小组内成员和学生自行研讨出合理的整改方案并对课题实施进行改进,直至达到功能要求。

5.项目总结。

主要包括学生实验项目总结心得、实验报告撰写,学生成绩的评定。

实验项目总结心得

在实验临将近结束时让学生共同讨论实验结果的正确性,讨论实验设计步骤的合理性,总结经验,进一步改善项目实施的方案及步骤。笔者认为,实验后的总结非常重要,是从理论到实践,再由实践到理论认识的进一步升华,也是使学生提高实验兴趣、锻炼并增解决实际问题的重要过程和手段。

实验报告撰写

学生实验报告一般应包含的内容是:实验题目、实验环境、实验目的、实验任务、数据结构描述、算法流程图表示、实验总结。

学生成绩的评定

教师根据学生的实验设计报告、学生的实际操作能力(程序检查)及学生的创新能力等几个方面综合评定,给出综合成绩。

三、实践的成果

1.对学生的影响。

经过近两年的实验教学实践,有超过70%的学生认为此次实验收获很大,大约80%的学生对这类实验取得的成果表示满意。从总体效果来看,学生通过综合性、设计性实验,提高了设计及编程能力。大部分学生认为《数据结构与算法》综合性、设计性实验项目的开展改变了以往传统的实践教学模式,内容新颖,提高了他们的编程兴趣和热情,对他们帮助很大。

2.对教师的促进。

《数据结构与算法》综合性、设计性实验的指导教师由计算机科学技术学院《数据结构与算法》课程的主讲教师和专业实验室的教师共同承担,我们认为,开展综合性设计性实验项目整合了多个知识环节,既能够帮助学生掌握知识的系统性和衔接性,理清程序设计的思路,促进知识的融会贯通;同时也给主讲教师带来新的挑战,能使教师总结在理论教学中的不足,进一步加强教学方法和内容的改革。

参考文献:

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006.

[2]唐册善.数据结构—C语言描述[M].北京:高等教育出版社,2003.