已选分类
工学计算机科学与技术
试题题型
问答题考虑积分及对应的求积公式1)证明：求积公式Q(f)是以x0=0，x1=1，x2=2为求积节点的插值型求积公式；2)求求积公式I(f)≈Q(f)的代数精度；3)设f(x)∈C3[0，3]，求截断误差I(f)-Q(f)形如αf(β)(ξ)的表达式，其中ξ∈(0，3)，α，β为常数。
问答题设从键盘输入一个整数的序列：n，a
1
，a
2
，…，a
n
，其中n表示连续输入整数的个数。
(1)试编写一程序按整数值建立一个二叉排序树。
(2)在(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。
问答题假设图采用邻接表存储，编写一个函数，利用深度优先搜索算法，求出无向图中通过给定点v的所有简单回路。
问答题在单链表中，每个结点含有5个正整型的数据元素(若最后一个结点的数据元素不满5个，以值0充)，试编写一算法查找值为n(n＞0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
问答题用最小二乘法确定经验公式u=a+bex中的参数a和b，使该曲线拟合下面的数据：
问答题给出折半查找的递归算法，并给出算法时间复杂度分析。
问答题设f(x)=x
4
—3x
3
+x
2
-10，x
0
=1，x
1
=3，x
2
=-2，x
3
=0．
1)求f(x)以x
0
，x
1
，x
2
，x
3
为节点的3次Lagrange插值多项式L
3
(x)；
2)求f(x)以x
0
，x
1
，x
2
，x
3
为节点的3次Newton插值多项式N
3
(x)；
3)给出以上插值多项式的插值余项表达式．
问答题假设以带头结点的单链表表示有序表，单链表的类型定义如下：
typedef struct node{
DataType data：
struct node *next
}LinkNode， *LinkList；
编写算法，从有序表A中删除所有和有序表B中元素相同的结点。
问答题使用散列函数：
H(k)=3k mod 11
并采用链地址法处理冲突。试对关键字序列(22，41，53，46，30，13，01，67)构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。
问答题G=(V，E)是一个带有权的连通图，如图所示。(1)什么是G的最小生成树?(2)G如图所示，请找出G的所有最小生成树。
问答题什么是对象-关系数据库？它的主要特点是什么？（8分）
问答题有一个不带头结点的单链表list，链表中结点都有两个域：数据域data和指针域link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
问答题已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。
问答题给定整型数组B[0，…，M][0，…，N]。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。设计一个程序段，找出一对满足B[i][j]=x的i，j值，找到后输出i和j的值，要求比较次数不超过M+N。
问答题斐波那契数列Fn定义如下：F0=0，F1=1，Fn=Fn-1+Fn-2，n=2，3，…就此斐波那契数列，回答下列问题。
问答题给定常微分方程初值问题取正整数n，并记h=(b-a)/n，xi=a+ih，0≤i≤n．试分析求解公式yi+1=yi+hf(yi+f(yi))的局部截断误差，并指出它是一个几阶的公式．
问答题设x
0
，x
1
，x
2
为互异节点，a，b，m为已知实数．试确定x
0
，x
1
，x
2
的关系，使满足如下三个条件p(x
0
)=a， p"(x
1
)=m，p(x
2
)=b的二次多项式p(x)存在且唯一，并求出这个插值多项式p(x)．
问答题最小最大堆(minmaxHeap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。(1)画出在图中插入关键字为5的结点后的最小最大堆。(2)画出在图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。
问答题编写一个实现连通图G的深度优先遍历(从顶点v出发)的非递归函数，可以用伪代码描述。
问答题设有求解线性方程组Ax=b的迭代格式Bx(k+1)+Cx(k)=b，k=0，1，…，(A)其中试确定实参数ξ和η的取值范围，使迭代格式(A)收敛．