已选分类
工学计算机科学与技术
试题题型
问答题设抛物型方程初边值问题有光滑解u(x，t)，其中ψ(0)=α(0)，ψ(1)=β(0)．取正整数M和N，并记h=1／M，τ=T/N，r=τ/h2；xi=a+ih，0≤i≤M；tk=kτ，0≤k≤N．设有求上述定解问题的差分格式1)写出上述差分格式的截断误差表达式；2)将差分格式写成矩阵和向量的形式；3)证明当r≤1／2时差分格式在∞范数下的收敛性．
问答题假定图G=(V，E)是有向图，V={1，2，…，N}，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组。如果i到j有边，则A[i，j]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n2)。
问答题分析方程sinx+1=x
2
存在几个实根；用迭代法求出这些实根(要求精确至2位有效数字)，并说明所用迭代格式为什么是收敛的．
问答题已知A，B∈Rn×n，其中A非奇异，B为奇异矩阵，试证明
问答题设从键盘输入一整数的序列：a
1
，a
2
，a
3
，…，a
n
，试编写算法实现：用栈结构存储输入的整数，当a
i
≠-1时，将a
i
进栈；当a
i
=-1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。
问答题求a，b，使得取最小值，并求该最小值．
问答题已知无向图G=(V，E)的邻接表，给出求图G的连通分量个数的算法。
问答题已知函数f(x)∈C3[0，3]，试确定参数A，B，C，使下面的求积公式≈Af(0)+Bf(1)+Cf(2)代数精度尽可能高，并给出此时求积公式的截断误差表达式．
问答题给定线性方程组其中a，b，c均为正数．证明：求上述方程组的Jacobi迭代格式和Gauss-Seidel迭代格式同时收敛同时发散，并且当收敛时，Gauss-Seidel迭代格式的收敛速度比Jaboci迭代格式的收敛速度快．
问答题试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Ui到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)
问答题图的D-搜索类似于BFS(广度优先搜索)，不同之处在于用栈代替BFS中的队列，入、出队列的操作改为入、出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。请用邻接表作为存储结构，写一个D-搜索算法。
问答题利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。
问答题在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?
问答题作一个3次多项式H(x)，使得H(a)=b
3
，H(b)=a
3
，H"(a)=6b，H"(b)=6a．
问答题编写一个算法，将一个无向图的邻接矩阵转换成邻接表。
问答题某个任务的数据模型可以抽象为给定的k个集合：S
1
，S
2
，…，S
k
。其中S
i
(1≤i≤k中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。
(1)构造数据结构，并且说明选择的理由。
(2)若一组数据模型为S
1
={10.2，1.7，4.8，16.2}，S
2
={1.7，8.4，0.5}，S
3
={4.8，4.2，3.6，2.7，5.1，3.9}，待插入的元素二元组为(2，11.2)和(1，5.3)，按你的设计思想画出插入元素前后的数据结构状态。
问答题考虑积分I(f)=1)写出计算I(f)的Simpson公式S(f)；2)用多项式插值的思想推导出S(f).3)写出复化梯形公式和复化Simpson公式之间的关系式．
问答题对一个具有7个记录的文件进行快速排序，请问：
(1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
问答题作一个3次多项式H(x)，使得H(a)=0，H"(a)=b，H(b)=0，H"(b)=a．
问答题二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。