历年运筹学考研试题及答案试题：一、单项选择题（每题2分，共10分）1. 线性规划问题的标准形式是：A. 所有变量非负B. 目标函数为最小化C. 约束条件为等式D. 所有变量非负，约束条件为等式和不等式2. 在单纯形法中，如果某个非基变量的检验数为负，则：A. 该变量不能进入基B. 该变量可以进入基C. 该变量必须进入基D. 以上都不对3. 对于运输问题，当供应量等于需求量时，我们称其为：A. 平衡运输问题B. 不平衡运输问题C. 线性运输问题D. 非线性运输问题4. 在动态规划中，最优子结构性质意味着：A. 问题的最优解包含子问题的最优解B. 问题的所有解都包含子问题的最优解C. 问题的一个解包含子问题的最优解D. 以上都不对5. 网络最大流问题中，Ford-Fulkerson算法的核心思想是：A. 寻找增广路径B. 寻找最短路径C. 寻找最长路径D. 寻找最小割二、简答题（每题10分，共20分）1. 简述线性规划的几何意义及其在实际问题中的应用。
2. 解释什么是灵敏度分析，并说明其在解决线性规划问题中的作用。
三、计算题（每题15分，共30分）1. 假设有以下线性规划问题：Max Z = 3x + 4ySubject to:2x + y ≤ 6x + 2y ≤ 7x, y ≥ 0请用图解法找到该问题的最优解。
2. 给定一个网络流问题，网络中有三个节点A, B, C，以及三条边(A,B), (B, C), (A, C)，每条边的容量分别为10, 5, 8。
要求从节点A到节点C的最大流量。
使用Ford-Fulkerson算法求解。
四、论述题（每题20分，共20分）1. 论述动态规划与分治法在解决组合优化问题时的异同，并给出一个适合使用动态规划法解决的实际问题例子。
答案：一、单项选择题1. D2. C3. A4. A5. A二、简答题1. 线性规划的几何意义是在n维空间中寻找一个多边形的顶点，这个多边形由约束条件定义，而目标函数则定义了一个目标方向。
一九九六年上海海运学院攻读硕士学位研究生入学考试试题数据结构一判断下列叙述的正确性，将判断的结果填在括号中，正确的填√，不正确的填×。
（本题满分10分，每小题1分）。
1 顺序存贮方式的优点是存储密度大，且插入删除效率高。
（）2 栈和队列的存储方式，既可以是顺序方式，有可是链式方式。
（）3 数组是同类型的集合。
（）4 负载因子是散存储的一个重要参数，它反映散列表的装满程度。
（）5 用链表(llink-rlink)存储包含几个结点的二叉树，结点的2n个指针区域中有n-1个空指针。
（）6 一棵一般树的结点的前序遍历和后序遍历分别于它相应二叉树的结点前序遍历和后序遍历是一致的。
（）7 线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
（）8 用邻接矩阵存储一个图时，再不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。
（）9 快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n). （）10 任意查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
（）二从供选择的答案中选出应填入下列叙述中____内的正确答案。
（本题满分25分，每小题5分）1 有一个二维数组A[0..8,1..5],每个数组元素用相邻的四个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是____。
若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是 ____ 和_____。
若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是____和____。
供选择的答案：A-E: ① 28 ② 44 ③ 76 ④ 92 ⑤ 108 ⑥ 116 ⑦ 132 ⑧ 176⑨ 184 ⑩ 1882 只能在一端删除结点，另端插入结点的线索表是______ ；只能在端点对结点进行删除，插入操作的线性表是_____,所有插入和删除均在一端进行，而另端不允许插入或删除的线性表是_____,其中的结点已按中序次序分类好的树是______,其中每个结点的左右子树的高度差都不大于1树是_____; 所有后件数小于2的结点均在最下面二层的树是______。
解：按月份将问题分为四个阶段，阶段变量，设状态变量为第k 月末的工人数，决策变量表示第k 月招聘或解聘的工人数（招聘为正，解聘为负），允许决策集合为，表示第k 个月所需的工人数，状态转移方程为。
为第1个月至第k 个月的最小总花费。
动态规划的基本方程为：3．某公司有资金4百万元，可向A 、B 、C 三个分公司增加投资，已知各分公司增加不同数量资金后增加的相应效益如表9-2所示，问如何分配资金可使公司总效益最大？（提示：用动态规划方法）（北京交通大学2009年研）表9-2解：将问题按分公司分为三个阶段，将A 、B 、C 三个分公司分别编号1、2、3。
设为分配给第k 个分公司至第3个分公司的投资。
为分配给第k 个分公司的投资。
表示分配给第k 个分公司的投资为后增加的效益。
表示为的投资分配给第k 个分公司至第3个分公司时所增加的最大效益。
可写出递推关系式：k=3时，，其数值计算如表9-3所示：表9-30 1 2 3 4 0 0 0 0 126 261240 40 2 358583 468 684当k=2时，，其数值计算如表9-4所示：表9-40 1 2 3 4 00 0 0 1 0+2622+026 0 2 0+40 22+2637+048 1 3 0+58 22+40 37+26 55+063 2 40+6822+5837+4055+2666+813当k=1时，，其数值计算如表9-5所示： 表9-50 1 2 3 4 40+81 21+63 35+48 50+26 60+841所以，得到最优解为：。
4．某公司有五台新设备，将有选择地分配给三个工厂，所得的收益如表9-6所示：表9-6表9-6中“—”表示不存在返样的方案。
请用动态规划求出收益最大的分配方案。
（北京理工大学2001年研） 解：将问题按工厂的个数分为3个阶段， 设表示为分配给第k 个工厂到第n 个工厂的新设备数目，表示为分配给第k 个工厂的新设备数目， 则为分配给第k+1个工厂至第n 个工厂的设备数目， 表示为个新设备分配给第k 个工厂所得的收益，表示为个设备分配给第k 个工厂到第n 个工厂时所得到的最大收益。
在上述两个约束条件中分别减去剩余变量，再加入人工变量，得其中，是一个任意大的正数，应用单纯形法进行计算如表2-10所示：表2-10可得问题的最优解，最优目标函数值。
因为非基变量的检验数中，所以该线性规划问题有无穷多最优解。
②两阶段法在上述线性规划问题的约束条件中分别减去剩余变量，再加上人工变量，得第一阶段的数学模型为：第一阶段的求解过程如表2-11所示：表2-11上述线性规划问题最优，其目标函数最优值，可以继续进行第二阶段计算。
第二阶段初始单纯形表如表2-12所示：表2-12已满足所有检验数非负，可得问题的最优解，最优目标函数值。
因为非基变量的检验数中，故此线性规划问题有无穷多最优解。
2.7 求下述线性规划问题目标函数z的上界和下界。
其中:。
解：（1）要求z的上界，则应取其最大值；应取其最小值，此时，得到的线性规划问题为在上述问题的第一个约束条件中加入松弛变量，第二个约束条件左右两边同时除以2再加入松弛变量，得到该线性规划问题的标准型单纯形法的计算过程如表2-13所示：表2-13解得最优解，目标函数z的上界。
（2）要求z的下界，则应取其最小值；应取其最大值，此时，得到的线性规划问题为在上述问题的第一个约束条件中加入松弛变量，第二个约束条件左右两边同时除以2再加入松弛变量，得到该线性规划问题的标准型单纯形法的计算过程如表2-14所示：表2-14解得最优解，目标函数z的下界2.8 表2-15是某求极大化线性规划问题计算得到的单纯形表。
表中无人工变量，为待定常数。
试说明这些常数分别取何值时，以下结论成立。
（1）表中解为惟一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，为对解改进，换入变量为，换出变量为。
表2-15解：（1）当时，表中解为惟一最优解；（2）当且=0时，表中的解为最优解，且原问题有无穷多个最优解；（3）当时，该线性规划问题具有无界解；（4）当时，表中的解非最优，对解进行改进，换入变量为，换出变量为。
