黄玉蕾

摘 要：数据结构是计算机科学与技术专业一门重要的专业基础课程。数据结构课程中各种算法思想包含了数学思维方法，通过学习数据结构，培养数学分析能力，同时参与数学建模过程，训练数据结构算法的编程能力，二者相辅相成。本文以数学建模的中研究生录取问题和跟导师之间的双向选择问题作为主要讨论对象，将其转化为0-1数据结构问题进行分析讨论。

关键词：数据结构； 数学建模； 课程改革； 教学方法

【分类号】G633.6

1 数学建模的特点

数学建模用数学语言描述实际现象的过程[1]。数学建模是联系数学与实际问题的桥梁，尤其在工程界格外重视，成为科技工作者的必备重要能力之一。数学建模的教学本身是一个不断探索、不断创新、不断完善和提高的过程。改变了过去以教师为中心、以课堂知识讲授为主的传统教学模式，数学建模课程创建了一个新的指导思想——以实验室为基础、以学生为中心、以问题为主线、以培养能力为目标来组织教学工作，通过教学使学生了解利用数学理论和方法分析和解决问题的全程，提高他们分析问题和解决问题的能力。使学生经常性的用数学去思考问题，利用计算机解决问题。

2 数据结构与数学建模

数学建模的基本思想方法是利用数学知识解决实际问题。而数据结构是计算机科学专业的重要的专业基础课程，有大量抽象的数学概念和理论知识[2]。在教学过程中，将数据结构的算法融入到数学建模思想中，使学生将数学的理论和方法用计算机算法程序实现，这样既可以将培养学生的编写程序的能力又能够提供数学的逻辑关系，增强了学生的动手能力，教学效果十分明显。

3 数学建模下数据结构教学讨论

本文根据研究生录取问题和跟导师之间的双向选择问题作为主要讨论对象，将此问题转化为分别转化成层次分析问题和线性规划中的0-1 规划问题[3]。

3.1 数学建模问题

首先建立研究生录取递阶层分次结构模型，定义权重比例为0.6：0.4，对每个学生的综合评价分数进行归纳，从15名候选同学中选出10位研究生。其次，用0-1 规划模型进行学生和导师之间的双向选择。建立目标函数和约束条件，用lingo软件求得：导师6分别和学生2、学生5以及学生6和学生12配对，导师3分别和学生3、学生9以及学生15配对，导师4分别和学生1、学生8配对，导师9和学生4配对。

用0-1 规划模型[3]学生和导师之间的双向选择。

1、导师的学术水平评价：

导师的学术水平是四个方面体现的，分别为发表论文数、论文检索数、编（译）著作数、科研项目数。通过查阅资料得出对研究生导师的考核标准的分析，对于导师的学术水平的衡量，以上四个方面的重视程度是不同的，其中最看重的是论文检索数、其次是科研项目数、对发表论文数和编（译）著作数看的相对较低。故权值设定为：

对于导师的学术水平各项指标 ， ， ， ，是通过具体数目给出的，在此同时采用极差变换法，即由下面公式得到各导师的相应各指标量化值：

记导师学术水平向量为 ，采用下面公式得到对第 个导师的综合水平的评价 ，即：

2、导师对学生的满意度：

根据8个专家对每一个学生的评价，转换为相应的数值4，3，2，1，然后用求算术平均的方法，得到每个学生的每项特长的综合评分，用这个综合评分与每位学生的五项特长的期望要求比较得出差异矩阵H，依据差异矩阵的数值 来划分等级，具体做法为找出最大值和最小值确定长度区间，再除以欲划分的等级数目，得到每个等级之间的等级长度：

用（很满意，满意，基本满意，不满意）来表示，由此得到每位导师对每位同学的各项特长的评价。

不满意：数值介于区间：

基本满意：数值介于区间：

满意：数值介于区间：

很满意：数值介于区间：

这四个等级就构成模糊集，取其对应的数值为1，2，3，4.

不考虑学生所报专业志愿前提下对学生的评价，考虑到导师选择学生还是要看学生的志愿。所以得出专业、导师和学生之间的可分配关系如图1所示。

3、学生对导师的满意度

学生对导师的选择，主要是根据学生自己的专业发展意愿，导师的基本情况和导师对学生的期望要求。集中体现在专业志愿和导师的学术水平上，导师的学术水平是客观存在的，可以用导师的学术水平评价 来衡量，不同的学生对导师的满意程度可以人为是取决于导师所从事的研究方向。类似的，可以通过加权方法来处理，即当导师研究方向与自己的第一志愿相同时，赋权值为1；当导师研究方向与自己的第二志愿相同是，赋权值为0.6；当导师研究方向与自己的志愿全不相同是，赋权值为0，其计算公式为：

其中志愿权值 取法同上，这时得到第 个学生对第 个导师的满意度

4、双方满意度的综合评价

确定了被录取的学生和导师双方对彼此的满意度，我们认为学生和导师彼此的满意度的和最大，两者的差越少，两者的相互选中的可能性越大，又有满意度均为正，所以这里采用几何平均的方法来综合两者的满意度，定义导师和学生两两之间的相互满意度为：

3.2 数据结构解决方法

在各个导师所带学生数量没有限制而学生只能选择一个导师的情况下，为了达到一种选择方案使得师生双方的满意度达到最大，我们可以把原问题转化成0-1整数规划问题，设决策变量为 （ 代表导师， 代表录取学生）

目标函数：

约束条件：

其中：

应用Lingo软件对上面整数规划问题求解得到目标值为7.047270，此时导师与学生的选择方案为如图2所示。

其中：导师6有四位学生，分别为学生2和学生5以及学生6和学生12，导师3有三位学生，分别为学生3和学生9以及学生15，导师4有两位学生，分别是学生1和学生8，导师9有一位学生，为学生4。

3.3 0-1问题数据结构教学方法。

根据数据结构的特点，将0-1问题设置为以下讲解方法。

1、实验内容：

设有一个背包可以放入的物品的重量为S，现有N件物品，重量分别为W1，W2，W3……Wn。问能否从这n件物品中选择若干件放入此包中，使得放入的物品的重量之和正好为S。

2、实验的目的：

深入了解栈和队列的特性，以便在实际问题背景下灵活应用，同时还将巩固对这两中结构的构造方法的掌握，接触较复杂问题的递归算法的设计。

3、实验设计思想：

（1）递归策略

在该问题中物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的，在递归实现的过程中用到一个栈来实现。

（2）非递归策略

非递归策略思想的实现与递归策略类似，只是直接用定义一个栈来实现，同样的物品质量W[n]和包所能承受的最大重量maxweight都是又用户自己任意定义的。

4 总结

通过这道题，使我们巩固了平时所学的知识，对数据结构中递归与非递归的思想有了进一步的理解和认识，更重要的是通过这个题目使我们更多的了解到数据结构在实际问题中的广泛应用，同时在数据结构课程教学中融入数学建模思想方法，能够很好地引导学生在学习的过程中善于发现问题、提出问题及解决问题，为后续课程打下坚实的基础。

参考文献

[1] 温长刚，数学建模与“数据结构”课堂教学关系的探讨与分析[J]电脑知识与技术 2014.8

[2] 景妮琴，浅谈数学在数据结构教学中的应用[J]山西师范大学学报 2010.12

[3] 吴永辉，王建德，算法设计编程实验[M]北京：机械工业出版社 2013.6