下载文档原格式
2022年西北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5B.6C.8D.92、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.333、以下与数据的存储结构无关的术语是（）。
A.循环队列B.链表C.哈希表D.栈4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、设X是树T中的一个非根结点，B是T所对应的二叉树。
在B中，X是其双亲的右孩子，下列结论正确的是（）。
A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。
n个结点的正则二叉树中有（）个叶子。
A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
题目1：使用神经网络对三叶草分类问题进行仿真答：1.分类问题描述：已知三种类型的三叶草：白三叶，红三叶，杂三叶，将其记为类型1、2、3，现有它们的4种特征数据，要求根据三叶草的特征数据，对其进行分类。
2.数据集描述：数据集共包含150组数据，挑选其中的75组作为训练数据，其余75组作为测试数据，数据集的每行的前4个数据为三叶草特征数据，最后1个数据为三叶草种类。
（详细数据见，最后部分打印）3.前馈神经网络设计：利用MATLAB 中newff( )，函数创建神经网络，神经网络结构如下：图1-1 神经网络结构图输入层：4输入（分别对应4个特征）隐含层：10输出层：3输出（分别对应该样本属于某一品种的可能性大小），输出节点中可能性最大的节点，对应测试样本的种类；隐含层激活函数为：对数S形转移函数输出层激活函数为：线性函数f(x) = x数据处理归一化函数为：y = ( x - min )/( max - min ) ,其中min,max为x的最小、最大值。
神经网络参数：目标误差为0.01，最大迭代次数1000次，学习率0.01.4.仿真结果展示及分析：（1）由仿真性能图1-2可以看出处，在迭代次数达到200次左右，网络的训练趋于收敛；效果。
但是，当遇到非线性或特征数据维度更高的分类问题时，神经网络将会变得非常庞大，网络各层的权值等参数的调试，也会变得复杂。
同时，耗费在网络训练上的时间也会更高，相应的准确率也会降低。
图1-2 三叶草分类神经网络，仿真结果展示图=============================代码实现===============================%读取训练数据fid = fopen('trainData.txt');trainData = textscan(fid , '%f%f%f%f%f');fclose(fid);[f1,f2,f3,f4,class] = trainData{:};[input,minI,maxI] = premnmx( [f1 , f2 , f3 , f4 ]') ; %对训练数据进行归一化len = length( class ) ; %构造输出矩阵output = zeros( len , 3 ) ;for i = 1 : lenoutput( i , class( i ) ) = 1 ;end%创建神经网络net = newff( minmax(input) , [10 3] , { 'logsig' 'purelin' } , 'traingdx' ) ;%设置训练参数net.trainparam.show = 50 ;net.trainparam.epochs = 1000 ;net.trainparam.goal = 0.01 ;net.trainParam.lr = 0.01 ;%开始训练net = train( net, input , output' ) ;%读取测试数据fid = fopen('testData.txt');testData = textscan(fid, '%f%f%f%f%f');fclose(fid);[t1,t2,t3,t4,c] = testData{:};%测试数据归一化testInput = tramnmx ( [t1,t2,t3,t4]' , minI, maxI ) ;%进行仿真Y = sim( net , testInput );%统计识别正确率[s1 , s2] = size( Y ) ;hitNum = 0 ;for i = 1 : s2[m , Index] = max( Y( : , i ) ) ;if( Index == c(i) )hitNum = hitNum + 1 ;endendsprintf('识别率是%3.3f%%',100 * hitNum / s2 )=============================训练数据集=============================== 5.1 3.5 1.4 0.2 14.9 3 1.4 0.2 14.7 3.2 1.3 0.2 14.6 3.1 1.5 0.2 15 3.6 1.4 0.2 15.4 3.9 1.7 0.4 14.6 3.4 1.4 0.3 15 3.4 1.5 0.2 14.4 2.9 1.4 0.2 14.9 3.1 1.5 0.1 15.4 3.7 1.5 0.2 14.8 3.4 1.6 0.2 14.8 3 1.4 0.1 14.3 3 1.1 0.1 15.8 4 1.2 0.2 15.7 4.4 1.5 0.4 15.4 3.9 1.3 0.4 15.1 3.5 1.4 0.3 15.7 3.8 1.7 0.3 15.1 3.8 1.5 0.3 15.4 3.4 1.7 0.2 14.6 3.6 1 0.2 15.1 3.3 1.7 0.5 1 4.8 3.4 1.9 0.2 1 7 3.2 4.7 1.4 26.4 3.2 4.5 1.5 2 6.9 3.1 4.9 1.5 25.5 2.3 4 1.3 26.5 2.8 4.6 1.5 25.7 2.8 4.5 1.3 26.3 3.3 4.7 1.6 2 4.9 2.4 3.3 1 2 6.6 2.9 4.6 1.3 2 5.2 2.7 3.9 1.4 2 5 2 3.5 1 25.9 3 4.2 1.5 26 2.2 4 1 2 6.1 2.9 4.7 1.4 25.6 2.9 3.6 1.3 26.7 3.1 4.4 1.4 2 5.6 3 4.5 1.5 25.8 2.7 4.1 1 26.2 2.2 4.5 1.5 2 5.6 2.5 3.9 1.1 25.9 3.2 4.8 1.8 26.1 2.8 4 1.3 2 6.3 2.5 4.9 1.5 2 6.1 2.8 4.7 1.2 2 6.4 2.9 4.3 1.3 2 6.3 3.3 6 2.5 3 5.8 2.7 5.1 1.9 37.1 3 5.9 2.1 3 6.3 2.9 5.6 1.8 36.5 3 5.8 2.2 37.6 3 6.6 2.1 3 4.9 2.5 4.5 1.7 3 7.3 2.9 6.3 1.8 36.7 2.5 5.8 1.8 37.2 3.6 6.1 2.5 3 6.5 3.2 5.1 2 3 6.4 2.7 5.3 1.9 3 6.8 3 5.5 2.1 3 5.7 2.5 5 2 3 5.8 2.8 5.1 2.4 36.5 3 5.5 1.8 37.7 3.8 6.7 2.2 37.7 2.6 6.9 2.3 36 2.2 5 1.5 36.9 3.2 5.7 2.3 35.6 2.8 4.9 2 37.7 2.8 6.7 2 36.3 2.7 4.9 1.8 36.7 3.3 5.7 2.1 3=============================测试数据集=============================== 5 3 1.6 0.2 15 3.4 1.6 0.4 15.2 3.5 1.5 0.2 15.2 3.4 1.4 0.2 14.7 3.2 1.6 0.2 14.8 3.1 1.6 0.2 15.4 3.4 1.5 0.4 15.2 4.1 1.5 0.1 15.5 4.2 1.4 0.2 14.9 3.1 1.5 0.2 15 3.2 1.2 0.2 15.5 3.5 1.3 0.2 14.9 3.6 1.4 0.1 14.4 3 1.3 0.2 15.1 3.4 1.5 0.2 15 3.5 1.3 0.3 14.5 2.3 1.3 0.3 14.4 3.2 1.3 0.2 15 3.5 1.6 0.6 15.1 3.8 1.9 0.4 14.8 3 1.4 0.3 15.1 3.8 1.6 0.2 14.6 3.2 1.4 0.2 15.3 3.7 1.5 0.2 15 3.3 1.4 0.2 16.6 3 4.4 1.4 26.8 2.8 4.8 1.4 26.7 3 5 1.7 26 2.9 4.5 1.5 25.7 2.6 3.5 1 25.5 2.4 3.8 1.1 25.5 2.4 3.7 1 25.8 2.7 3.9 1.2 26 2.7 5.1 1.6 25.4 3 4.5 1.5 26 3.4 4.5 1.6 2 6.7 3.1 4.7 1.5 2 6.3 2.3 4.4 1.3 2 5.6 3 4.1 1.3 2 5.5 2.5 4 1.3 25.5 2.6 4.4 1.2 26.1 3 4.6 1.4 2 5.8 2.6 4 1.2 2 5 2.3 3.3 1 2 5.6 2.7 4.2 1.3 2 5.7 3 4.2 1.2 25.7 2.9 4.2 1.3 26.2 2.9 4.3 1.3 2 5.1 2.5 3 1.1 2 5.7 2.8 4.1 1.3 27.2 3.2 6 1.8 3 6.2 2.8 4.8 1.8 3 6.1 3 4.9 1.8 36.4 2.8 5.6 2.1 37.2 3 5.8 1.6 3 7.4 2.8 6.1 1.9 3 7.9 3.8 6.4 2 3 6.4 2.8 5.6 2.2 3 6.3 2.8 5.1 1.5 36.1 2.6 5.6 1.4 37.7 3 6.1 2.3 3 6.3 3.4 5.6 2.4 3 6.4 3.1 5.5 1.8 3 6 3 4.8 1.8 3 6.9 3.1 5.4 2.1 3 6.7 3.1 5.6 2.4 3 6.9 3.1 5.1 2.3 35.8 2.7 5.1 1.9 36.8 3.2 5.9 2.3 3 6.7 3.3 5.7 2.5 3 6.7 3 5.2 2.3 3 6.3 2.5 5 1.9 3 6.5 3 5.2 2 3 6.2 3.4 5.4 2.3 3 5.9 3 5.1 1.8 3题目2: 使用遗传算法解决TSP问题答：1.TSP问题描述：TSP(Traveling Salesman Problem,“旅行商问题”)可简单描述为: 一位销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条.2.TSP数据规模：本问题中共包含51个城市，其x坐标和y坐标分别为：city_x=[37 49 52 20 40 21 17 31 52 51,...42 31 5 12 36 52 27 17 13 57,...62 42 16 8 7 27 30 43 58 58,...37 38 46 61 62 63 32 45 59 5,...10 21 5 30 39 32 25 25 48 56,...30];city_y=[52 49 64 26 30 47 63 62 33 21,...41 32 25 42 16 41 23 33 13 58,...42 57 57 52 38 68 48 67 48 27,...69 46 10 33 63 69 22 35 15 6,...17 10 64 15 10 39 32 55 28 37,...40];3.遗传算法的设计：遗传算法的流程图如下，具体各部分的实现见下部分详细说明。
参考答案 第一章1 *1x =1.7； *2x =1.73； *3x =1.732 。
2．3． （1） ≤++)(*3*2*1x x x e r 0.00050； （注意：应该用相对误差的定义去求） （2） ≤)(*3*2*1x x x e r 0.50517； （3） ≤)/(*4*2x x e r 0.50002。
4．设6有n 位有效数字，由6≈2.4494……，知6的第一位有效数字1a =2。
令3)1()1(1*1021102211021)(-----⨯≤⨯⨯=⨯=n n r a x ε 可求得满足上述不等式的最小正整数n =4，即至少取四位有效数字，故满足精度要求可取6≈2.449。
5. 答：（1）*x (0>x )的相对误差约是*x 的相对误差的1/2倍；（2）nx )(* 的相对误差约是*x 的相对误差的n 倍。
6． 根据********************sin 21)(cos 21sin 21)(sin 21sin 21)(sin 21)(c b a c e c b a c b a b e c a c b a a e c b S e r ++≤=******)()()(tgcc e b b e a a e ++ 注意当20*π<<c 时，0**>>c tgc ，即1*1*)()(--<c tgc 。
则有)()()()(****c e b e a e S e r r r r ++<7．设20=y ，41.1*0=y ，δ=⨯≤--2*001021y y 由 δ1*001*111010--≤-=-y y y y ，δ2*111*221010--≤-=-y y y yMδ10*991*10101010--≤-=-y y y y即当0y 有初始误差δ时，10y 的绝对误差的绝对值将减小1010-倍。
而11010<<-δ，故计算过程稳定。
一、考试内容线性方程组和非线性方程（组）的求解、矩阵特征值和特征向量的计算、微积分的计算、微分方程定解问题的求解等，都是工程、科技、统计等实际问题中大量碰到的数学问题，这些问题的精确解很难求出。
而《计算方法》则是一门适合于计算机计算求解的数值方法，它简单可行，能有效求出上述数学问题的近似解。
通过本课程的学习，要求学生能掌握利用计算机求解基本数学问题常用的数值计算方法，学会构造基本的计算格式，并能作一定的误差分析，使学生具备基本的科学计算能力。
主要有：1.了解计算方法的认务和特点；2.熟练掌握方程的的近似解法，包括二分法、迭代法、牛顿迭代法和弦割法3.熟练掌握线性代数方程组的解法，直接解法中的高斯消去法、矩阵的直接三角分解法，平方根分解法，解三对角方程组的追赶法；解线性方程组的迭代法，简单迭代法，雅可比迭代法，赛德尔迭代法，SOR方法及其收敛性4.熟练掌握矩特征值和特征向量的计算，乘幂法与反幂法，古典雅可比方法，雅可比过关法5.熟练掌握插值法，拉格朗日插值法，牛顿插值法，等距节点插值法，埃尔米特插值法，三次样条插值法6.熟练掌握最小二乘法与曲线拟合，掌握矛盾方程组与最小二乘法，数据的多项式拟合，可化为线性拟合模型的曲线拟合7.熟练掌握数值积分与数值微分，包括牛顿-柯特斯求积公式、复化求积公式、龙贝格求积算法、高斯型求积公式和数值微分；8. 熟练掌握常微分方程初值问题数值解法，包括欧拉法与梯形法、泰勒展开法与龙格-库塔法、线性多步法2006-2007第一学期一. 填空1） 近似数253.1*=x 关于真值249.1=x 有____位有效数字；2） 设有插值公式)()(111k nk k x f A dx x f ⎰∑-=≈，则∑=nk kA1=______；（只算系数）3） 设近似数0235.0*1=x ，5160.2*2=x 都是有效数，则相对误差≤)(*2*1x x e r ____； 4） 求方程x x cos =的根的牛顿迭代格式为______；5） 矛盾方程组⎪⎩⎪⎨⎧-=+=-=+1211212121x x x x x x 与⎪⎩⎪⎨⎧-=+=-=+121222212121x x x x x x 得最小二乘解是否相同______。
西北工业大学智慧树知到“计算机科学与技术”《计算方
法》网课测试题答案
（图片大小可自由调整）
第1卷
一.综合考核(共10题)
1.利用待定系数法可以得出各种求积公式，而且可以具有尽可能高的代数精度。
()
A.正确
B.错误
2.判断参数值是否正确{图}。
()
A.正确
B.错误
3.牛顿迭代法的基本思想是将非线方程f(x)=0逐步转化为线性议程来求解。
()
A.正确
B.错误
4.雅可比方法的主要特点是什么()
A.精度高
B.算法稳定
C.稀疏性
D.求得的特征向量正交性好
5.议程的近似方法有()
A.迭代法
B.牛顿法
C.弦截法
D.二分法
6.{图}1
A.正确
B.错误
7.直接法是在理论上没有舍入误差的前提下经过有限步运算即可得到方程组的精确解。
() A.正确
B.错误
8.{图}1
A.D
B.C
C.B
D.A
9.列主元素消元法不是直接法中常用的方法。
()
A.正确
B.错误
10.乘幂法主要是用来求矩阵的主特征值(按模最大的特征值)及相应的特征向量。
()
A.正确
B.错误
第1卷参考答案
一.综合考核
1.参考答案：A
2.参考答案：A
3.参考答案：A
4.参考答案：ABD
5.参考答案：ABCD
6.参考答案：A
7.参考答案：A
8.参考答案：D
9.参考答案：B
10.参考答案：A。
西工大20年10月机考计算方法作业试卷总分:100 得分:96要答an：网叫福到（这四个字的拼音）一、单选题 (共 30 道试题,共 60 分)1.舍入误差是( )产生的误差。
A.只取有限位数B.模型准确值与用数值方法求得的准确值C.观察与测量D.数学模型准确值与实际值正确答案:2. {A.2B.3C.4D.5正确答案:3.用 1+x近似表示ex所产生的误差是( )误差。
A.模型B.观测C.截断D.舍入正确答案:4.解线性方程组的主元素消去法中选择主元的目的是( )。
A.控制舍入误差B.减小方法误差C.防止计算时溢出D.简化计算正确答案:5.舍入误差是(?? ?)产生的误差。
A.只取有限位数B.模型准确值与用数值方法求得的准确值C.观察与测量D.数学模型准确值与实际值正确答案:6. {A.{<img ">B.{<img g">C.0D.1正确答案:7.( )是解方程组Ax=b的迭代格式x(k+1)=Mx(k)+f收敛的一个充分条件；A.{<img ">B.{<img ">C.{<img ">D.{<img >正确答案:8.-324.7500是舍入得到的近似值，它有( )位有效数字。
A.5B.6C.7D.8正确答案:9. {A.舍入B.观测C.模型D.截断正确答案:10. {A.-1B.1C.{<img ">D.0正确答案:11. {A.{<img ">B.{<img >C.{<img >D.0正确答案:12. {A.1B.2C.4D.3正确答案:13. {A.A的各阶顺序主子式不为零B.{<img ">C.{<img ">D.{<img pg">正确答案:14. {A.0B.1C.2D.{<img ">正确答案:15. {A.0B.{<img ">C.2D.1正确答案:16. {A.0B.1C.{<img s>D.{<img s>正确答案:17. 三点的高斯型求积公式的代数精度为()。
2002-2003第一学期一．计算及推导（5*8）1．已知* 3.141,x x π==，试确定*x 近似x 的有效数字位数。
2．有效数***1233.105,0.001,0.100x x x =-==，试确定***123x x x ++的相对误差限。
3．已知3()0.50.12f x x x =++，试计算差商[]0,1,2,3f 4．给出拟合三点(0,1),(1,0)A B ==和(1,1)C =的直线方程。
5．推导中矩形求积公式''31()()()()()224b aa b f x dx b a f f b a η+=-+-⎰ 6．试证明插值型求积公式()()nbi i ai f x dx A f x =≈∑⎰的代数精确度至少是n 次。
7．已知非线性方程()x f x =在区间[],a b内有一实根，试写出该实根的牛顿迭代公式。
8．用三角分解法求解线性方程组123121022331302x x x ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥--⎣⎦⎣⎦⎣⎦要用二次插值多项式计算(0.63891)f 的近似值，试选择合适的插值节点进行计算，并说明所选用节点依据。
（保留5位有效数字）（12分） 三． 已知方程ln 0x x +=在(0,1)内有一实根α（1）给出求该实根的一个迭代公式，试之对任意的初始近似0(0,1)x ∈迭代法都收敛，并证明其收敛性。
（2）00.5x =试用构造的迭代公式计算α的近似值n x ，要求3110n n x x ---≤。
四． 设有方程组112233131232a x b a x b a x b ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦当参数a 满足什么条件时，雅可比方法对任意的初始向量都收敛。
写出与雅可比方法对应的高斯赛德尔迭代公式。
（12分） 五．用欧拉预估校正法求解初值问题 '2 (00.2)(0)1x y y x y y ⎧=-≤≤⎪⎨⎪=⎩ 取h=0.1，小数点后保留5位。
西北工业大学考试试题（A卷）2004 —2005学年第一学期一、填空题：（每题3分，共计30分）1. __________________________________________________________________ 塑性是指：____________________________________________________________________________2. 金属的超塑性可分为________ 超塑性和________ 超塑性两大类。
3. 金属单晶体变形的两种主要方式有：____________ 和________ 。
4. 影响金属塑性的主要因素有：__________ ，_______ ，_______ ，_______ ，_______ 。
5. 等效应力表达 _____________________________________________________________ 。
6. 常用的摩擦条件及其数学表达式：_____________________________________________ ，。
7. n 平面是指：____________________________________________________________________8. 一点的代数值最大的________________ 的指向称为第一主方向，由第一主方7T向顺时针转N所得滑移线即为__________ 线。
9. 平面变形问题中与变形平面垂直方向的应力（Tz= ____________________10. 在有限元法中：应力矩阵[S]= ____________________________ ，单元内部各点位移{U}=[ ]{ }二、简答题（共计30分）1. 提高金属塑性的主要途径有哪些？（8分）2. 纯剪切应力状态有何特点？（6分）3. 塑性变形时应力应变关系的特点？（8分）4. Levy-Mises 理论的基本假设是什么？（8分）三、计算题（共计40分）_0 172 C _172 0 01、已知金属变形体内一点的应力张量为L °°“°」Mpa ,求：（18 分）（1）计算方向余弦为1=1/2 ，m=1/2 ，n='的斜截面上的正应力大小。
西工大计算方法作业答案参考答案 第一章1 *1x =1.7； *2x =1.73； *3x =1.732 。
2．3． （1） ≤++)(*3*2*1x x x e r 0.00050； （注意：应该用相对误差的定义去求） （2） ≤)(*3*2*1x x x e r 0.50517； （3） ≤)/(*4*2x x e r 0.50002。
4．设6有n 位有效数字，由6≈2.4494……，知6的第一位有效数字1a =2。
令3)1()1(1*1021102211021)(-----⨯≤⨯⨯=⨯=n n r a x ε 可求得满足上述不等式的最小正整数n =4，即至少取四位有效数字，故满足精度要求可取6≈2.449。
5. 答：（1）*x (0>x )的相对误差约是*x 的相对误差的1/2倍； （2）n x )(* 的相对误差约是*x 的相对误差的n 倍。
6． 根据********************sin 21)(cos 21sin 21)(sin 21sin 21)(sin 21)(c b a c e c b a c b a b e c a c b a a e c b S e r ++≤ =******)()()(tgcc e b b e a a e ++ 注意当20*π<<c 时，0**>>c tgc ，即1*1*)()(--<c tgc 。
则有)()()()(****c e b e a e S e r r r r ++<7．设20=y ，41.1*0=y ，δ=⨯≤--2*001021y y由 δ1*001*111010--≤-=-y y y y ，δ2*111*221010--≤-=-y y y yδ10*991*10101010--≤-=-y y y y即当0y 有初始误差δ时，10y 的绝对误差的绝对值将减小1010-倍。
而11010<<-δ，故计算过程稳定。
