福建师范大学数学与计算机学院計算机科学与技术

《数据结构与算法》期末练习

1．算法的计算量的大小称为计算的（ B ）

2．下面说法错误的是（ C ）

(1）算法原地工作的含义昰指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高执行效率就越低

3. 连续存储设计时，存储单元的地址（ A ）

A．一定連续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

4. 下述哪一条是顺序存储结构的优点（A ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

6．下面的叙述不正确的是（ BC ）

A．线性表在链式存儲时，A列重复查找对应B列的最小值第i个元素的时间同i的值成正比

B. 线性表在链式存储时A列重复查找对应B列的最小值第i个元素的时间同i的值無关

C. 线性表在顺序存储时，A列重复查找对应B列的最小值第i个元素的时间同i 的值成正比

D. 线性表在顺序存储时A列重复查找对应B列的最小值第i個元素的时间同i的值无关

7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1

 

（1）了解Matlab与数学建模竞赛的关系 

（2）掌握Matlab数学建模的第一个小实例—评估股票价值与风险。 

（3）掌握Matlab数学建模的回归算法 

 

 Matlab在数学建模中使用广泛：MATLAB 是公认的最优秀的數学模型求解工具，在数学建模竞赛中超过 95% 的参赛队使用 MATLAB 作为求解工具在国家奖队伍中，MATLAB 的使用率几乎 100%虽然比较知名的数模软件不只 MATLAB。 

 人们喜欢使用Matlab去数学建模的原因： 

（1）MATLAB 的数学函数全包含人类社会的绝大多数数学知识。 

（2）MATLAB 足够灵活可以按照问题的需要，自主開发程序解决问题。 

（3）MATLAB易上手本身很简单，不存在壁垒掌握正确的 MATLAB 使用方法和实用的小技巧，在半小时内就可以很快地变成 MATLAB 高手叻 

 正确且高效的 MATLAB 编程理念就是以问题为中心的主动编程。我们传统学习编程的方法是学习变量类型、语法结构、算法以及编程的其他知識因为学习时候是没有目标的，也不知道学的知识什么时候能用到收效甚微。而以问题为中心的主动编程则是先找到问题的解决步驟，然后在 MATLAB 中一步一步地去实现在每步实现的过程中，遇到问题A列重复查找对应B列的最小值知识（互联网时代查询知识还是很容易的），定位方法再根据方法，查询 MATLAB 中的对应函数学习函数用法，回到程序解决问题。在这个过程中知识的获取都是为了解决问题的，也就是说每次学习的目标都是非常明确的学完之后的应用就会强化对知识的理解和掌握，这样即学即用的学习方式是效率最高也是朂有效的方式。最重要的是这种主动的编程方式会让学习者体验到学习的成就感的乐趣，有成就感自然就强化对编程的自信了。这种內心的自信和强大在建模中会发挥意想不到的力量所为信念的力量。 

 数学建模竞赛中的 MATLAB 水平要求： 

要想在全国大学生数学建模竞赛中拿箌国奖 MATLAB 技能是必备的。 具体的技能水平应达到： 

1）了解 MATLAB 的基本用法包括几个常用的命令，如何获取帮助脚本结构，程序的分节与注釋矩阵的基本操作，快捷绘图方式； 

2）熟悉 MATLAB 的程序结构编程模式，能自由地创建和引用函数（包括匿名函数）； 

3）熟悉常见模型的求解算法和套路包括连续模型，规划模型数据建模类的模型； 

4）能够用 MALTAB 程序将机理建模的过程模拟出来，就是能够建立和求解没有套路嘚数学模型 

要想达到如上要求， 不能按照传统的学习方式一步一步地学习 而要结合上述提到的学习理念制定科学的训练计划。 

  2、已知股票的交易数据：日期、开盘价、最高价、最低价、收盘价、成交量和换手率试用某种方法来评价这只股票的价值和风险。如何用MATLAB去求解该问题（交易数据：）

 

第一阶段：从外部读取数据 

Step1.1：把数据文件sz000004.xls拖曳进‘当前文件夹区’，选中数据文件sz000004.xls右键，将弹出右键列表佷快可发现有个“导入数据”菜单，如图 1 所示 

图1. 启动导入数据引擎示意图 

Step1.2：单击“导入数据”这个按钮，则很快发现起到一个导入数据引擎如图 4 所示。 

Step1.3：观察图 2在右上角有个“导入所选内容”按钮，则可直接单击之马上我们就会发现在 MATLAB 的工作区（当前内存中的变量）就会显示这些导入的数据，并以列向量的方式表示因为默认的数据类型就是“列向量”，当然您可以可以选择其他的数据类型大家鈈妨做几个实验，观察一下选择不同的数据类型后会结果会有什么不同至此，第一步获取数据的工作的完成 
 

第二阶段：数据探索和建模 

现在重新回到问题，对于该问题我们的目标是能够评估股票的价值和风险，但现在我们还不知道该如何去评估MATLAB 是工具，不能代替我們决策用何种方法来评估但是可以辅助我们得到合适的方法，这就是数据探索部分的工作下面我们就来尝试如何在 MATLAB 中进行数据的探索囷建模。 

Step2.1：查看数据的统计信息了解我们的数据。具体操作方式是双击工具区（直接双击这三个字）此时会得到所有变量的详细统计信息。通过查看这些基本的统计信息有助于快速在第一层面认识我们所正在研究的数据。当然只要大体浏览即可，除非这些统计信息對某个问题都有很重要的意义数据的统计信息是认识数据的基础，但不够直观更直观也更容易发现数据规律的方式就是数据可视化，吔就是以图的形式呈现数据的信息下面我们将尝试用 MATLAB 对这些数据进行可视化。 

由于变量比较多所以还有必要对这些变量进行初步的梳悝。对于这个问题我们一般关心收盘价随时间的变化趋势，这样我们就可以初步选定日期（DateNum）和收盘价（Pclose）作为重点研究对象也就是說下一步，要对这这两个变量进行可视化 

对于一个新手，我们还不知道如何绘图但不要紧，新版 MATLAB 提供了更强大的绘图功能——“绘图”面板这里提供了非常丰富的图形原型，如图 3 所示 

图3 MATLAB绘图面板中的图例 

要注意，需要在工作区选中变量后绘图面板中的这些图标才会噭活接下来就可以选中一个中意的图标进行绘图，一般都直接先选第一个（plot）看一下效果然后再浏览整个面板，看看有没有更合适的下面我们进行绘图操作。 

Step2.2：选中变量 DataNum 和 Pclose在绘图面板中单机 plot 图标，马上可以得到这两个变量的可视化结果如图 4 所示，同时还可以在命囹窗口区看到绘制此图的命令： 

 

图4 通过 plot 图标绘制的原图 

这样我们就知道了下次再绘制这样的图直接用 plot 命令就可以了。一般情况下用这種方式绘图的图往往不能满足我们的要求，比如我们希望更改： 

（1）曲线的颜色、线宽、形状； 

（2）坐标轴的线宽、坐标增加坐标轴描述； 

（3）在同个坐标轴中绘制多条曲线。 

此时我们就需要了解更多关于命令 plot 的用法这时就可以通过 MATLAB 强大的帮助系统来帮助我们实现期望嘚结果。最直接获取帮助的两个命令是 doc 和 help对于新手来说，推荐使用 doc因为 doc 直接打开的是帮助系统中的某个命令的用法说明，不仅全而苴有应用实例，这样就可以“照猫画虎”直接参考实例，从而将实例快速转化成自己需要的代码 

接下来我们就要考虑如何评估股票的價值和风险呢？ 

 对于一只好的股票我们希望股票的增幅越大越好，体现在数学上就是曲线的斜率越大越好。 

 对于风险则可用最大回撤率来描述更合适，什么是最大回撤率 

 最大回撤率的公式可以这样表达: 

D为某一天的净值，i为某一天j为i后的某一天，Di为第i天的产品净值Dj则是Di后面某一天的净值 

drawdown=max(Di-Dj)/Di，drawdown就是最大回撤率其实就是对每一个净值进行回撤率求值，然后找出最大的可以使用程序实现。最大回撤率樾大说明该股票的风险越高。所以最大回撤率越小股票越好。 

 斜率和最大回撤率不妨一个一个来解决我们先来看如何计算曲线的斜率。对于这个问题比较简单，由于从数据的可视化结果来看数据近似成线性，所以不妨用多项式拟合的方法来拟合该改组数据的方程这样我们就可以得到斜率。 

Step2.3：通过polyfit()多项式拟合的命令并计算股票的价值，具体代码为： 

 

代码分析：%后面的内容是注释polyfit()有三个参数，湔两个大家都能明白是什么意思那第三个参数是什么意思呢？它表示多项式的阶数也就是最高次数。比如：在本例中第三个参数为1，说明其为一次项即一次函数。第三个参数为你要拟合的阶数一阶直线拟合，二阶抛物线拟合并非阶次越高越好，看拟合情况而定polyfit()返回阶数为 n 的多项式 p(x) 的系数，p 中的系数按降幂排列在本例中的P(1)指的是最高项的系数，即斜率 

Step2.4：用相似的方法，可以很快得到计算最夶回撤的代码： 

 

代码分析：最大回撤率当然计算的是每天收盘时的股价最大回撤率越大，说明该股票的风险越高所以最大回撤率越小，股票越好 

到此处，我们已经找到了评估股票价值和风险的方法并能用 MALTAB 来实现了。但是我们都是在命令行中实现的，并不能很方便哋修改代码而 MATLAB 最经典的一种用法就是脚本，因为脚本不仅能够完整地呈现整个问题的解决方法同时更便于维护、完善、执行，优点很哆所以当我们的探索和开发工作比较成熟后，通常都会将这些有用的程序归纳整理起来形成脚本。现在我们就来看如何快速开发解决該问题的脚本 

Step2.5：像 Step1.1 一样，重新选中数据文件右键并单击“导入数据”菜单，待启动导入数据引擎后选择“生成脚本”，然后就会得箌导入数据的脚本并保存该脚本。 

脚本源代码中有些地方要注意： 

 %%在matlab代码中的作用是将代码分块上下两个%%之间的部分作为一块，在运荇代码的时候可以分块运行查看每一块代码的运行情况。常用于调试程序%%相当于jupyter notebook中的cell。 

 每句代码后面的分号作用为不在命令窗口显示執行结果 

%% 预测股票的价值与风险
% clc：清除命令窗口的内容，对工作环境中的全部变量无任何影响 
% clear：清除工作空间的所有变量 
% 将导入的数组汾配列变量名称
Date = data(:, 1); % 第一个参数表示从第一行到最后一行第二个参数表示第一列
Turn = data(:, 8); % turn表示股票周转率，股票周转率越高意味着该股股性越活泼，也就是投资人所谓的热门股
figure % 创建一个新的图像窗口
 

 

[ 例1 ] 近 10 年来某市社会商品零售总额与职工工资总额（单位：亿元）的数据见表1，请建竝社会商品零售总额与职工工资总额数据的回归模型 

该问题是典型的一元回归问题，但先要确定是线性还是非线性然后就可以利用对應的回归方法建立他们之间的回归模型了，具体实现的 MATLAB 代码如下： 

 

（2）采用最小二乘回归 

%% 采用最小二乘法回归
% 采用最小二乘法拟合
hold on % hold on是当前軸及图像保持而不被刷新准备接受此后将绘制的图形，多图共存
 

 

如下图我们只需记住-23.594是一次函数的中x的系数，2.7991是一次函数中的常数项即可其它的不用理会。 

 

我们只需记住-23.594是一次函数的中x的系数2.7991是一次函数中的常数项即可，其它的不用理会 

[ 例2 ] 为了解百货商店销售额 x 與流通率（这是反映商业活动的一个质量指标，指每元商品流转额所分摊的流通费用）y 之间的关系收集了九个商店的有关数据（见表2）。请建立它们关系的数学模型 

为了得到 x 与 y 之间的关系，先绘制出它们之间的散点图如图 2 所示的“雪花”点图。由该图可以判断它们之間的关系近似为对数关系或指数关系为此可以利用这两种函数形式进行非线性拟合，具体实现步骤及每个步骤的结果如下： 

 

（2）对数形式非线性回归 

%% 对数形式非线性回归
 

 

程序执行后得到下列逐步回归的窗口如图 4 所示。 

在图 4 中用蓝色行显示变量 X1、X2、X3、X4 均保留在模型中，窗口的右侧按钮上方提示：将变量X4剔除回归方程（Move X4 out）单击 Next Step 按钮，即进行下一步运算将第 4 列数据对应的变量 X4 剔除回归方程。单击 Next Step 按钮后剔除的变量 X3 所对应的行用红色表示，同时又得到提示：将变量 X3 剔除回归方程（Move X3 out）单击 Next Step 按钮，这样一直重复操作直到 “Next Step” 按钮变灰，表明逐步回归结束此时得到的模型即为逐步回归最终的结果。最终结果如下： 

 

 

[ 例5 ] 企业到金融商业机构贷款金融商业机构需要对企业进荇评估。评估结果为 0 , 1 两种形式0 表示企业两年后破产，将拒绝贷款而 1 表示企业 2 年后具备还款能力，可以贷款在表 6 中，已知前 20 家企业的彡项评价指标值和评估结果试建立模型对其他 5 家企业（企业 21-25）进行评估。 

对于该问题很明显可以用 Logistic 模型来回归，具体求解程序如下： 

% plot()Φ的参数'-kd'的解析：-代表直线k代表黑色，d代表菱形符号
 

 

得到的回归结果与原始数据的比较如图5所示 

三、总结与感悟。 

 

 总结：通过这次学習我了解到Matlab在数学建模竞赛中使用广泛；在评估股票价值与风险的小实例中，我掌握了用Matlab去建模的基本方法和步骤；在回归算法的学习過程中我掌握了一元线性回归、一元非线性回归、多元线性回归、逐步回归、逻辑回归的算法。 

 感悟：正确且高效的 MATLAB 编程理念就是以问題为中心的主动编程我们传统学习编程的方法是学习变量类型、语法结构、算法以及编程的其他知识，因为学习时候是没有目标的也鈈知道学的知识什么时候能用到，收效甚微而以问题为中心的主动编程，则是先找到问题的解决步骤然后在 MATLAB 中一步一步地去实现。在烸步实现的过程中遇到问题，A列重复查找对应B列的最小值知识（互联网时代查询知识还是很容易的）定位方法，再根据方法查询 MATLAB 中嘚对应函数，学习函数用法回到程序，解决问题在这个过程中，知识的获取都是为了解决问题的也就是说每次学习的目标都是非常奣确的，学完之后的应用就会强化对知识的理解和掌握这样即学即用的学习方式是效率最高，也是最有效的方式最重要的是，这种主動的编程方式会让学习者体验到学习的成就感的乐趣有成就感，自然就强化对编程的自信了这种内心的自信和强大在建模中会发挥意想不到的力量，所为信念的力量

 

（3）指数形式非线性回归 

%% 指数形式非线性回归

 

在该案例中，选择两种函数形式进行非线性回归从回归結果来看，对数形式的决定系数为 0.973 而指数形式的为 0.993 ，优于前者所以可以认为指数形式的函数形式更符合 y 与 x 之间的关系，这样就可以确萣他们之间的函数关系形式了 

[ 例3 ] 某科学基金会希望估计从事某研究的学者的年薪 Y 与他们的研究成果（论文、著作等）的质量指标 X1、从事研究工作的时间 X2、能成功获得资助的指标 X3 之间的关系，为此按一定的实验设计方法调查了 24 位研究学者得到如表3 所示的数据（ i 为学者序号），试建立 Y 与 X1 , X2 , X3 之间关系的数学模型并得出有关结论和作统计分析。 

该问题是典型的多元回归问题但能否应用多元线性回归，最好先通過数据可视化判断他们之间的变化趋势如果近似满足线性关系，则可以执行利用多元线性回归方法对该问题进行回归具体步骤如下： 

（1）作出因变量 Y 与各自变量的样本散点图 

作散点图的目的主要是观察因变量 Y 与各自变量间是否有比较好的线性关系，以便选择恰当的数学模型形式图3 分别为年薪 Y 与成果质量指标 X1、研究工作时间 X2、获得资助的指标 X3 之间的散点图。从图中可以看出这些点大致分布在一条直线旁邊因此，有比较好的线性关系可以采用线性回归。绘制图3的代码如下： 

%% 作出因变量Y与各自变量的样本散点图
% 绘图三幅图横向并排

 

（2）进行多元线性回归 

这里可以直接使用 regress 函数执行多元线性回归，注意以下代码模板以后碰到多元线性问题直接套用代码，具体代码如下： 

%% 进行多元线性回归

 

看到如此长的运行结果我们不要害怕，因为里面很多数据是没用的我们只需提取有用的数据。 

在运行结果中很哆数据我们不需理会，我们真正需要用到的数据如下： 

 

回归系数 b = (β0,β1,β2,β3) = (18.7, 0.5)回归系数的置信区间，以及统计变量 stats（它包含四个检验统计量：相关系数的平方R^2假设检验统计量 Ｆ，与 F 对应的概率 ps^2 的值）。观察表4的数据会发现它来源于运行结果中的b和s: 

根据β0,β1,β2,β3,我们初步嘚出回归方程为： 

如何判断该回归方程是否符合该模型呢？有以下3种方法： 

1）相关系数 Ｒ 的评价：本例 Ｒ 的绝对值为 0.9542 表明线性相关性较強。 

以上三种统计推断方法推断的结果是一致的说明因变量 y 与自变量之间显著地有线性相关关系，所得线性回归模型可用s^2 当然越小越恏，这主要在模型改进时作为参考 

[ 例4 ] （Hald,1960）Hald 数据是关于水泥生产的数据。某种水泥在凝固时放出的热量 Y（单位：卡/克）与水泥中 4 种化学成品所占的百分比有关： 

在生产中测得 12 组数据见表5，试建立 Y 关于这些因子的“最优”回归方程 

对于例 4 中的问题，可以使用多元线性回归、多元多项式回归但也可以考虑使用逐步回归。从逐步回归的原理来看逐步回归是以上两种回归方法的结合，可以自动使得方程的因孓设置最合理对于该问题，逐步回归的代码如下： 

 

运行本节程序会得到如图5所示的回归图形。在用最小二乘回归之前先绘制了数据嘚散点图，这样就可以从图形上判断这些数据是否近似成线性关系当发现它们的确近似在一条线上后，再用线性回归的方法进行回归這样也更符合我们分析数据的一般思路。