西安交大计算方法B2017大作业

西安交通大学17年3月课程考试《运筹学》作业考核试题一、单选题（共37道试题，共74分。

）V 1. 不满足匈牙利法的条件是•问题求最小值•效率矩阵的元素非负•人数与工作数相等•问题求最大值标准答案：2. 运输问题可以用（）法求解。

•定量预测•单纯形•求解线性规划的图解•矢键线路标准答案：3. 可行解是满足约束条件和非负条件的决策变量的一组取值。

（）•正确•错误•不一定•无法判断标准答案：4. 下列变量组是一个闭回路.{x11,x12,x23,x34,x41,x13}.{x21,x13,x34,x41,x12}.{x12,x32,x33,x23,x21,x11}.{x12,x22,x32,x33,x23,x21}标准答案：5. 下列正确的结论是•最大流等于最大流量•可行流是最大流当且仅当存在发点到收点的增广链•可行流是最大流当且仅当不存在发点到收点的增广链•调整量等于增广链上点标号的最大值标准答案：() 6. 通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题•非线性问题的线性化技巧•静态问题的动态处理•引入虚拟产地或者销地•引入人工变量标准答案：7. 线性规划模型中，决策变量（）是非负的。

•一定不•不一定•无法判断标准答案：8. 对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正( )•换出变量•换入变量•非基变量•基变量标准答案：9. 运输问题•是线性规划问题•不是线性规划问题•可能存在无可行解•可能无最优解标准答案：10. 事件j的最早时间T(j )是指.以事件j为开工事件的工序最早可能开工时间•以事件j为完工事件的工序最早可能结束时间.以事件j为开工事件的工序最迟必须开工时间•以事件j为完工事件的工序最迟必须结束时间标准答案：11 •下列错误的结论是•容量不超过流量•流量非负•容量非负•发点流出的合流等于流入收点的合流标准答案：12. 下列说法正确的是.割集是子图•割量等于割集中弧的流量之和•割量大于等于最大流量•割量小于等于最大流量标准答案：13. 求最短路的计算方法有•加边法•Floy算法•破圈法.For-Fulkrs on 算法标准答案：14. 连通图G有n个点，其部分树是T,则有•T有n个点n条边•T的长度等于G的每条边的长度之和・T有n个点n— 1条边.T有n — 1个点n条边标准答案：15. 动态规划的核心是什么原理的应用（）•最优化原理•逆向求解原理•最大流最小割原理•网络分析原理标准答案：16. 用单纯形法求解线性规划时，不论极大化或者是极小化问题，基变均用最小比值原则确定出量。

西安交通大学17年9月课程考试《计算机应用基础》作业考核试题-(含主观题)100分答案一、单选题（共20道试题，共40分。

）1.启动幻灯片切换可以通过（）命令。

A.格式/幻灯片切片B.幻灯片放映/幻灯片切换C.插入/幻灯片切换D.工具/幻灯片切换正确答案：B2.PowerPoint2003中“文件”菜单中的“保存”命令其快捷键是（）。

A.Ctrl+PB.Ctrl+OC.Ctrl+ND.Ctrl+S正确答案：D3.与Internet相连的计算机，不管是大型的还是小型的，都称为()。

A.工作站B.主机C.服务器D.客户机正确答案：B4.Word常用工具栏中的“显示比例”选择框，是用于（）的。

A.字符缩放B.字符缩小C.字符放大D.上述均不是正确答案：A5.在Word中，要插入一些比较复杂的图形，用户可以通过()来完成。

A.“自选图形”按钮B.“矩形”按钮C.“椭圆”按钮D.“插入艺术字”按钮正确答案：A6.多媒体计算机系统的两大组成部分是（）。

A.多媒体功能卡和多媒体主机B.多媒体通信软件和多媒体开发工具C.多媒体输入设备和多媒体输出设备D.多媒体计算机硬件系统和多媒体计算机软件系统正确答案：D7.在IE浏览器访问FTP服务器时，下列地址中属于有效的FTP地址格式的是()。

正确答案：A8.水平标出现在Word文档工作区的（）。

A.左侧B.底部C.右侧D.顶部正确答案：D9.PowerPoint2003中“文件”菜单中的“保存”命令其快捷键是（）。

A.Ctrl+PB.Ctrl+OC.Ctrl+ND.Ctrl+S正确答案：D10.以下选项中，()不是从技术上讲的计算机安全的三大特征。

B.网络安全C.系统安全D.信息安全正确答案：B11.以下格式中，不属于视频文件格式的是()。

A.MPEGB.AVIC.MIDID.RM正确答案：C12.以下说法正确的是（）。

A.在Word中新建文档会替代原来的窗口B.每次选择“保存”命令都会打开“另存为”对话框C.使用Alt+F4组合键可以关闭Word窗口D.以上都不对正确答案：C13.当用户正在编辑文档时，突然死机或断电，将会使正在编辑的文档（）。

并行计算与程序设计作业班级：姓名：学号：1.1至1.3节作业1.调试课件中的所有程序，并完成作业，同时在程序结果中需要输出个人信息；代码：Program mainwrite(*,*)'班级：', 'write(*,*)'姓名：',' 'print *,'学号：',''end2.编写一个数值求解方程的程序，方程为4.1x3 −5.3x=11.8，求解区间为（1，5），误差小于1e-6。

代码：a=1b=5if(f(a)*f(b).LT.0) thenwrite(*,*)'inter:(',a,',',b,')'Loop1: do while((abs(f(a)-f(b)).gt.10e-6).and.$ (abs(a-b).gt.10e-6))c=(a+b)/2if(f(a)*f(c).le.0)thenb=celsea=cend ifend do Loop1write(*,*)'x=',celsewrite(*,*)'Please input real interval'end ifendreal function f(x)f=4.1*x**3-5.3*x-11.8end结果：1.4节作业1.采样简单离散求和法求下面积分值：∫x2sin(x)+1dx 1代码：read(*,*) a,b,nh=(b-a)/(2.0*n)s=0.0x=a+hf2=0.0f4=0.0loop1: do i=1,n-1x=x+hf2=f2+f(x)x=x+hf4=f4+f(x)end do loop1s=h/3.0*(f(a)+f(b)+4.0*f4+2.0*f2)write(*,150) s100 format(1x,'a=',f8.2,2x,'b=',f8.2,$ 2x,'n=',i4)150 format(1x,'s=',f16.7)endreal function f(x)f=x**2/(sin(x)+1)endd ouble precision i,ai,ydouble precision sum=0i=1do 10 while(1/sum=1/i+sumi=i+110 continuewrite(*,*) 'sum=',sumend结果：1.6节作业1.调试课本中的所有程序；（结果略）2.用双精度型数据计算：∑1i=11+12+13+⋯+1nni=1直到1n≤10−5代码：double precision sum=0i=1do 10 while(1/sum=1/i+sumi=i+110 continuewrite(*,*) 'sum=',sumend结果：3.已知三角形三个顶点的坐标分别为A(1.5,2.5),B(-2.5,1), C(1,-1)，采用复型数据类型求三角形的面积和重心。

西安交通大学17年3月课程考试《数据结构》作业考核试题一、单选题（共30 道试题，共60 分。

）1. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A. 存储结构B. 逻辑结构C. 算法D. 操作正确答案：B2. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

A. 8B. 7C. 6D. 5正确答案：B3. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

A. O(n)B. O(nlog2n)C. O(n)D. O(1og2n)正确答案：C4. 栈的插入和删除操作在（）进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置正确答案：A5. 二路归并排序的时间复杂度为（）。

A. O(n)B. O(n)C. O(nlog2n)D. O(1og2n)正确答案：C6. 设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A. n(n-1)B. n+1C. nD. n(n+1)正确答案：C7. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（）A. A[1]，A[2]，A[3]，A[4]B. A[1]，A[14]，A[7]，A[4]C. A[7]，A[3]，A[5]，A[4]D. A[7]，A[5]，A[3]，A[4]正确答案：C8. 下列各种排序算法中平均时间复杂度为O（n）是（）。

A. 快速排序B. 堆排序C. 归并排序D. 冒泡排序正确答案：D9. 如下陈述中正确的是（）A. 串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串正确答案：A10. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。

A. 688B. 678C. 692D. 696正确答案：C11. 适于对动态查找表进行高效率查找的组织结构是（）A. 有序表B. 分块有序表C. 三叉排序树D. 线性链表正确答案：C12. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

西安交通大学17年3月课程考试《计算机图形学》作业考核
试题100分答案
西安交通大学17年3月课程考试《计算机图形学》作业考核试题试卷总分：100? ? ? ?测试时间：--
一、单选题（共?30?道试题，共?60?分。

）
1. 在计算机的二维造型软件系统中，提供给用户多种图形的输入方式，但不包含( )。

A. 交互方式
B. 参数化方式
C. 事件方式
D. 识别方式
答案:C
满分：2 分
2. 计算机图形学中的光栅算法主要用于( )。

A. 三维图形的输入
B. 三维图形的输出
C. 二维图形输入
D. 二维图形输出
答案:D
满分：2 分
3. 在光照模型中，( )对于镜面光的处理不够好，会形成马赫带效应，针对这一问题，可以采用法向插值算法进行改进。

A. 恒定明暗处理
B. 光强插值算法
C. 法向插值算法
D. 光线跟踪
答案:B
满分：2 分
4. 用转角法判别点在区域的内外。

将点M与边界上一点P连接，
当P沿边界移动一周时，M 点处于区域外的是( )。

A. MP与给定的某条直线夹角变化值为0；
B. MP与给定的某条直线夹角变化值为2π；
C. MP与给定的某条直线夹角变化值为π；
D. MP与给定的某条直线夹角变化值为3π
答案:A
满分：2 分
5. 在三维几何变换中的透视投影中灭点最多可以有( )。

A. 4
B. 3
C. 2
D. 1
答案:B。

西安交通大学17年9月课程考试《运筹学》作业考核试题
一、单选题（共37道试题，共74分。

）
1.下列结论正确的有
A.运输问题的运价表第r行的每个Cij同时加上一个非零常数k，其最优调运方案不变
B.运输问题的运价表第p列的每个Cij同时乘以一个非零常数k，其最优调运方案不变
C.运输问题的运价表的所有Cij同时乘以一个非零常数k,其最优调运方案变化
D.不平衡运输问题不一定存在最优解
正确答案：A
2.m+n－1个变量构成一组基变量的充要条件是
A.m+n－1个变量恰好构成一个闭回路
B.m+n－1个变量不包含任何闭回路
C.m+n－1个变量中部分变量构成一个闭回路
D.m+n－1个变量对应的系数列向量线性相关
正确答案：B
3.运输问题的数学模型属于
A.0-1规划模型
B.整数规划模型
C.网络模型
D.以上模型都是
正确答案：C
4.用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（）
A.正确
B.错误
C.不一定
D.无法判断
正确答案：B
5.设P是图G从vs到vt的最短路，则有
A.P的长度等于P的每条边的长度之和
B.P的最短路长等于vs到vt的最大流量
C.P的长度等于G的每条边的长度之和
D.P有n个点n-1条边
正确答案：A
6.动态规划求解的一般方法是什么？（）
A.图解法
B.单纯形法
C.逆序求解
D.标号法
正确答案：C
7.线性规划模型中，决策变量（）是非负的。

A.一定
B.一定不
C.不一定。

西安交通大学17年9月课程考试《离散数学》作业考核试题一、单选题（共20 道试题，共40 分。

）1. 整数集合Z关于数的加法“+”和乘法“?”构成的代数系统<Z,+，?>是（）。

A. 域B. 域和整环C. 整环D. 有零因子环正确答案：C2. 任何一个有限群在同构的意义下可以看作是（）。

A. 循环群B. 置换群C. 变换群D. 阿贝尔群正确答案：B3. 设集合A={a,b,c},2A上的包含关系是（）。

A. 自反的、反对称的、传递的B. 自反的、对称的、传递的C. 反自反的、对称的、传递的D. 反自反的、对称的、非传递的正确答案：A4. 无向图G有6条边，各有一个3度和5度顶点，其余均为2度顶点，则G的阶数是（）。

A. 2B. 3C. 4D. 5正确答案：C5. 如下语句中，真命题是（）。

A. 10能被2整除，3是偶数B. 如果2+2=6，则5是奇数C. 下午到办公室来开会D. 15是素数正确答案：B6. 下列各命题中。

哪个是真命题？（）A. 若一个有向图是强连通图，则是有向欧拉图B. n（n≥1）阶无向完全图Kn都是欧拉图C. n（n≥1）阶有向完全图都是有向欧拉图D. 二分图G=〈V1,V2,E〉必不是欧拉图正确答案：C7. 对以下定义的集合和运算，哪个不构成代数系统？（）。

A. 实数集R和数的加法运算“＋”B. 自然数集N和数的减法运算“-”C. 集合A的幂集P(A)和集合的并、交运算D. n×n实矩阵的全体组成的集合和矩阵的加法运算“＋”正确答案：B8. 只含有有限个元素的格称为有限格，有限格必是（）。

A. 分配格B. 有补格C. 布尔格D. 有界格正确答案：D9. 量词的约束范围称为量词的（ ）。

A. 定义域B. 个体域C. 辖域D. 值域正确答案：C10. 函数的复合满足（）。

A. 交换率B. 结合率C. 幂等率D. 分配率正确答案：B11. 函数的复合运算“ο”满足（）。

计算方法（A）大作业姓名：班级：专业：学号：共轭梯度法一、算法原理共轭梯度法是把求解线性方程组的问题转化为求解一个与之等价的二次函数极小化的问题，因此从任意给定的初始点出发，沿一组关于矩阵A的共轭方向进行线性搜索，在无舍入无差的假定下，最多迭代n(其中n为矩阵A的阶数）次就可求得二次函数的极小点，也就求得了线性方程组Ax=B的解。

下述定理给出了求系数矩阵A是对称正定矩阵的线性方程组Ax=b的解与求二次函数f(x)=12x T Ax−b T x极小点的等价性。

定理3.4.1设A是n阶对称正定矩阵，则x∗是方程组Ax=b的解的充分必要条件是x∗是二次函数f(x)=12x T Ax−b T x的极小点，即Ax∗=b⟺f(x∗)=minx∈R nf(x)证明：充分性.设x∗是f(x)的极小点，则由无约束最优化问题最优解的必要条件知∇f(x∗)=Ax∗−b即x∗是方程组Ax=b的解。

必要性. 若x∗是方程组Ax=b的解，即A x∗=b，注意到A是对称正定矩阵，故∀x∈R n有f(x)−f(x∗)=12x T Ax−b T x−12x T Ax∗+b T x∗=12(x T Ax−2b T x+x∗T Ax∗)−x∗T Ax∗+b T x∗=12(x T Ax−2(Ax∗)T x+x∗T Ax∗)−(Ax∗−b)T x∗=12(x−x∗)T A(x−x∗)≥0即x∗是f(x)的极小点，进而由A是正定矩阵知，x∗是f(x)的最小点。

证毕。

共轭梯度法在形式上具有迭代法的特征，在给定初始值情况下，根据迭代公式：x(k+1)=x(k)+αk d(k)产生的迭代序列x(1),x(2),x(3)…在无舍入误差假定下，最多经过n次迭代，就可求得f(x) 的最小值，也就是方程Ax=b的解。

共轭梯度法中关键的两点是，确定迭代格式中的搜索向量d(k)和最佳步长αk （αk≥0）。

实际上，搜索方向d(k)是关于矩阵A的共轭向量，在迭代中逐步构造之。

计算方法B上机报告姓名：学号：班级：学院：任课教师：2017年12月29日题目一：1.1题目内容某通信公司在一次施工中，需要在水面宽度为20米的河沟底部沿直线走向铺设一条沟底光缆。

在铺设光缆之前需要对沟底的地形进行初步探测，从而估计所需光缆的长度，为工程预算提供依据。

已探测到一组等分点位置的深度数据(单位:(1)(2)估算所需光缆长度的近似值，并作出铺设河底光缆的曲线图；1.2 实现题目的思想及算法依据首先在题目（1）中要实现的是数据的拟合，显然用到的是我们在第三章中数据近似的知识内容。

多项式插值时，这里有21个数据点，则是一个20次的多项式，但是多项式插值随着数据点的增多，会导致误差也会随之增大，插值结果会出现龙格现象，所以不适用于该题目中点数较多的情况。

为了避免结果出现大的误差，同时又希望尽可能多地使用所提供的数据点，提高数据点的有效使用率，这里选择分段插值方法进行数据拟合。

分段插值又可分为分段线性插值、分段二次插值和三次样条插值。

由于题目中所求光缆的现实意义，而前两者在节点处的光滑性较差，因此在这里选择使用三次样条插值。

根据课本SPLINEM 算法和TSS 算法，采用第三种真正的自然边界条件，在选定边界条件和选定插值点等距分布后，可以先将数据点的二阶差商求出并赋值给右端向量d ，再根据TSS 解法求解三对角线线性方程组从而解得M 值。

求出M 后，对区间进行加密，计算200个点以便于绘图以及光缆长度计算。

对于问题（2），使用以下的公式:20=()L f x ds ⎰20(f x =⎰191(k kk f x +==∑⎰1.3 算法结构1. For n i ,,2,1,0⋅⋅⋅=1.1 i i M y ⇒2. For 2,1=k2.1 For k n n i ,,1, -=2.1.1 i k i i i i M x x M M ⇒----)/()(13. 101h x x ⇒-4. For 1-,,2,1n i =4.1 11++⇒-i i i h x x4.2 b a c c h h h i i i i i i ⇒⇒-⇒+++2;1;)/(11 4.3 i i d M ⇒+165. 0000;;c M d M d n n ⇒⇒⇒λn n n b a b ⇒⇒⇒2;;20μ6. 1111,γμ⇒⇒d b7. For m k ,,3,2 = ! 获取M 的矩阵元素个数，存入m7.1 k k k l a ⇒-1/μ 7.2 k k k k c l b μ⇒⋅-1- 7.3 k k k k l d γγ⇒⋅-1- 8. m m m M ⇒μγ/9. For 1,,2,1 --=m m k9.1 k k k k k M M c ⇒⋅-+μγ/)(110. k ⇒1 ! 获取x 的元素个数存入s 11. For 1,,2,1-=s i11.1 if i x x ≤~then k i ⇒；break else k i ⇒+112. xx x x x x h x x k k k k ˆ~;~;11⇒-⇒-⇒--- y h x h M y x h M y x M x M k k k k k k ~/]ˆ)6()6(6ˆ6[2211331⇒-+-++---1.4 matlab 源程序n=20; x=0:n;y=[9.01 8.96 7.96 7.97 8.02 9.05 10.13 11.18 12.26 13.28 13.32 12.61 11.29 10.22 9.15 7.90 7.95 8.86 9.81 10.80 10.93];M=y; %用于存放差商，此时为零阶差商 h=zeros(1,n+1); c=zeros(1,n+1); d=zeros(1,n+1); a=zeros(1,n+1); b=2*ones(1,n+1); h(2)=x(2)-x(1);for i=2:n %书本110页算法SPLINEM h(i+1)=x(i+1)-x(i);c(i)=h(i+1)/(h(i)+h(i+1)); a(i)=1-c(i); enda(n+1)=-2; %计算边界条件c(0),a(n+1),采用的是第三类边界条件 c(1)=-2;for k=1:3 %计算k 阶差商 for i=n+1:-1:k+1M(i)=(M(i)-M(i-1))/(x(i)-x(i-k)); endif(k==2) %计算2阶差商 d(2:n)=6*M(3:n+1); %给d 赋值 endif(k==3)d(1)=(-12)*h(2)*M(4); %计算边界条件d(0),d(n),采用的是第三类边界条件 d(n+1)=12*h(n+1)*M(n+1); end endl=zeros(1,n+1); r=zeros(1,n+1); u=zeros(1,n+1); q=zeros(1,n+1); u(1)=b(1); r(1)=c(1); q(1)=d(1);for k=2:n+1 %利用书本49页算法TSS求解三对角线性方程组r(k)=c(k);l(k)=a(k)/u(k-1);u(k)=b(k)-l(k)*r(k-1);q(k)=d(k)-l(k)*q(k-1);endp(n+1)=q(n+1)/u(n+1);for k=n:-1:1p(k)=(q(k)-r(k)*p(k+1))/u(k);endfprintf('三对角线性方程组的解为：');disp(p);%求拟合曲线x1=0:0.1:20; %首先对区间进行加密,增加插值点n1=10*n;x2=zeros(1,n1+1);x3=zeros(1,n1+1);s=zeros(1,n1+1);for i=1:n1+1for j=1:nif x1(i)>=x(j)&&x1(i)<=x(j+1) %利用书本111页算法EVASPLINE求解拟合曲线s(x)h(j+1)=x(j+1)-x(j);x2(i)=x(j+1)-x1(i);x3(i)=x1(i)-x(j);s(i)=(p(j).*(x2(i)).^3/6+p(j+1).*(x3(i)).^3/6+(y(j)-p(j).*((h(j+1)).^2/6)).*x2( i)+...(y(j+1)-p(j+1).*(h(j+1)).^2/6).*x3(i))/h(j+1);endendendplot(x,-y,'x') %画出插值点hold onplot(x1,-s) %画出三次样条插值拟合曲线hold ontitle('三次样条插值法拟合电缆曲线');xlabel('河流宽度/m');ylabel('河流深度/m');Length=0;for i=1:n1L=sqrt((x1(i+1)-x1(i))^2+(s(i+1)-s(i))^2); %计算电缆长度Length=Length+L;endfprintf('电缆长度(m)=');disp(Length);1.5 结果与说明铺设海底光缆的曲线如图1.1所示图1. 1三次样条插值法拟合海底光缆曲线由上图可以看出，所得到的曲线光滑，能够较好得反映实际的河沟底部地势形貌。