2025年大连理工大学计算机科学与技术（工程计算）本科考试试卷及答案

2025年大连理工大学计算机科学与技术（工程计算）本科考试试卷及答案考试时间：______分钟总分：______分姓名：______一、简答题（每题6分，共30分）1.解释什么是数据结构？在计算机科学与技术（特别是工程计算）领域中，为什么掌握数据结构知识至关重要？2.描述快速排序算法的基本思想。简述其在平均情况和最坏情况下的时间复杂度，并说明其是一种不稳定的排序算法。3.什么是数值算法的收敛性？在求解线性方程组或非线性方程时，如何判断算法是否可能收敛？简述影响收敛速度的因素。4.简述浮点数表示法的基本原理。在工程计算中，使用浮点数进行计算时可能遇到哪些主要问题（如舍入误差、数值稳定性）？如何理解“病态问题”？5.什么是递归算法？请举例说明递归算法在解决工程计算问题（如计算阶乘、斐波那契数列、树的遍历等）中的应用优势。同时，简述使用递归算法可能带来的问题。二、编程题（每题15分，共30分）1.编写一个函数，该函数接受一个字符串作为输入，返回该字符串中所有唯一字符的列表。字符串仅包含小写字母。要求不使用额外的库函数，并尽可能优化时间复杂度。请描述你的主要思路，并给出相应的代码实现。2.编写一个函数，实现矩阵的快速幂运算。即给定一个nxn的实数矩阵A和一个正整数k，计算A的k次幂（A^k）。假设k是非负整数。请描述你的主要思路，并给出相应的代码实现。说明你的算法在时间复杂度上的优势。三、计算题（每题17分，共34分）1.考虑求解方程x^3-x-2=0在区间[1,3]内的根。请使用二分法查找该根，要求误差不超过10^-4。请写出详细的迭代过程，并在每一步记录当前的区间、中点值、函数值以及区间长度。2.给定线性方程组：3x+0.1y-0.2z=7.850.1x+7y-0.3z=-19.30.3x+10y-7z=71.4请使用高斯消元法（无需回代过程，只需进行消元步骤）将增广矩阵化为行阶梯形矩阵。写出每一步消元操作后的增广矩阵。---试卷答案一、简答题1.数据结构是计算机存储、组织数据的方式。它是指相互关联的数据元素的集合，以及这些数据元素之间的关系。在计算机科学与技术（特别是工程计算）领域中，掌握数据结构知识至关重要，因为它关系到算法的效率。合理选择和设计数据结构可以显著提高算法的性能，优化内存使用，简化程序设计，从而更高效地解决复杂的工程计算问题，如大规模数据处理、计算模型的构建与优化等。2.快速排序算法的基本思想是分治法。它选择一个基准元素（pivot），然后将数组划分为两个子数组，使得左子数组的所有元素都不大于基准元素，右子数组的所有元素都大于基准元素（或小于、等于，取决于具体实现），然后递归地在两个子数组上重复这个过程。平均情况下的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)（当基准选择不当时，如已排序数组选择首元素为基准）。它是一种不稳定的排序算法，因为相等元素的相对顺序可能在排序过程中发生变化。3.数值算法的收敛性是指当算法的迭代次数趋于无穷时，其解逐渐接近真实解（或预定精度）的性质。在求解线性方程组时，可以通过判断迭代矩阵的谱半径是否小于1来判断Jacobi或Gauss-Seidel迭代法是否收敛。在求解非线性方程时，可以通过判断导数的绝对值在根附近是否小于1来判断牛顿法或类似方法的局部收敛性。影响收敛速度的因素包括初始值的选取、算法本身的性质、问题的固有特性（如病态性）等。4.浮点数表示法是一种用于表示实数的近似方法，通常采用IEEE754标准。它由符号位、指数部分和尾数（有效数字）三部分组成。使用浮点数进行计算时可能遇到的主要问题包括舍入误差（每次运算都可能引入小的误差累积）和数值稳定性（某些算法对初始值或输入数据的微小变化非常敏感，导致结果产生大的偏差）。浮点数表示的精度有限，无法精确表示所有实数，导致“病态问题”中求解过程误差可能被急剧放大。5.递归算法是一种函数调用自身的算法设计技巧。它将问题分解为规模更小的相同问题，并通过组合子问题的解来得到原问题的解。递归算法在解决工程计算问题（如计算阶乘n!=n*(n-1)!、计算斐波那契数列F(n)=F(n-1)+F(n-2)（n>=2）、树的遍历等）中的应用优势在于代码简洁、结构清晰，易于理解和实现。但使用递归算法可能带来的问题是可能导致大量的函数调用开销，消耗栈空间，对于深度过大的递归可能导致栈溢出，且可能不是最优的时间复杂度选择（如递归计算阶乘或斐波那契数列）。6.（本试卷原第5题已改为第6题，此处补充第6题解析）递归算法是一种函数调用自身的算法设计技巧。它将问题分解为规模更小的相同问题，并通过组合子问题的解来得到原问题的解。递归算法在解决工程计算问题（如计算阶乘n!=n*(n-1)!、计算斐波那契数列F(n)=F(n-1)+F(n-2)（n>=2）、树的遍历等）中的应用优势在于代码简洁、结构清晰，易于理解和实现。但使用递归算法可能带来的问题是可能导致大量的函数调用开销，消耗栈空间，对于深度过大的递归可能导致栈溢出，且可能不是最优的时间复杂度选择（如递归计算阶乘或斐波那契数列）。二、编程题1.思路：使用哈希集合（或布尔数组，因仅含小写字母）记录遍历过的字符。遍历输入字符串，对于每个字符，检查是否已在集合中记录。若未记录，则添加到集合，并将其加入结果列表。最后返回结果列表。代码实现（伪代码）：```functionuniqueCharacters(inputString):charSet=newHashSet()//或boolean[26]初始化为falseresult=newList()//结果列表forifrom0tolength(inputString)-1:c=inputString[i]ifnotcharSet.contains(c)://或!charSet[c]charSet.add(c)//或charSet[c]=trueresult.add(c)returnresult```2.思路：利用矩阵乘法的结合律(A^(k+1)=A^k*A)和分治思想。当k=0时，结果为单位矩阵I。当k=1时，结果为A。对于k>1，若k为偶数，则A^k=(A^(k/2))^2；若k为奇数，则A^k=A*(A^(k-1))。递归计算A^(k/2)，然后根据k的奇偶性组合结果。代码实现（伪代码）：```functionmatrixFastPower(A,k):n=size(A)//A是nxn矩阵ifk==0:returnidentityMatrix(n)//单位矩阵ifk==1:returnAhalfPower=matrixFastPower(A,k/2)result=matrixMultiply(halfPower,halfPower)ifk%2!=0://k为奇数result=matrixMultiply(A,result)returnresultfunctionmatrixMultiply(A,B)://实现矩阵乘法//...```三、计算题1.二分法求根：方程f(x)=x^3-x-2=0。初始区间[a,b]=[1,3]。f(1)=1-1-2=-2<0f(3)=27-3-2=22>0f(a)f(b)<0，根在[1,3]内。迭代过程：1.中点c=(1+3)/2=2。f(2)=8-2-2=4>0。区间[1,2]。区间长度=2-1=1。2.中点c=(1+2)/2=1.5。f(1.5)=3.375-1.5-2=-0.125<0。区间[1.5,2]。区间长度=2-1.5=0.5。3.中点c=(1.5+2)/2=1.75。f(1.75)=5.359375-1.75-2=1.609375>0。区间[1.5,1.75]。区间长度=1.75-1.5=0.25。4.中点c=(1.5+1.75)/2=1.625。f(1.625)=4.296875-1.625-2=0.671875>0。区间[1.5,1.625]。区间长度=1.625-1.5=0.125。5.中点c=(1.5+1.625)/2=1.5625。f(1.5625)=3.796875-1.5625-2=-0.365234375<0。区间[1.5625,1.625]。区间长度=1.625-1.5625=0.0625。6.中点c=(1.5625+1.625)/2=1.59375。f(1.59375)=4.02734375-1.59375-2=0.333984375>0。区间[1.5625,1.59375]。区间长度=1.59375-1.5625=0.03125。7.中点c=(1.5625+1.59375)/2=1.578125。f(1.578125)=3.820800781-1.578125-2=-0.05732421875<0。区间[1.578125,1.59375]。区间长度=1.59375-1.578125=0.015625。8.中点c=(1.578125+1.59375)/2=1.5859375。f(1.5859375)=3.923828125-1.5859375-2=0.137890625>0。区间[1.578125,1.5859375]。区间长度=1.5859375-1.578125=0.0078125。达到误差要求|1.5859375-1.578125|=0.0078125<=10^-4。停止迭代。根的近似值为1.5859375。2.高斯消元法化行阶梯形（仅消元过程）：增广矩阵：```[30.1-0.2|7.85][0.17-0.3|-19.3][0.310-7|71.4]```第一步：用第一行消去第二行和第三行第一列的元素。R2=R2-(0.1/3)*R1R3=R3-(0.3/3)*R1=R3-0.1*R1```[30.1-0.2|7.85][07-0.2-19.3-(0.1/3)*7.85][010-7-71.4-0.1*7.85]``````[30.1-0.2|7.85][07-0.2-19.3-0.261666...][010-7-71.4-0.785]``````[30.1-0.2|7.85][07-0.2-19.566666...][010-7-72.185]```第二步：用第二行消去第三行第二列的元素。R3=R3-(10/7)*R2```[30.1-0.2|7.85][07-0.2-19.566666...][010-7-72.185-(10/7)*(-19.566666...)]``````[30.1-0.2|7.85][07-0.2-19.