已选分类
工学
试题题型
问答题写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。
将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。 算法如下： typedef struct{ KeyType key; InfoType otherinfo; }RecType; typedef struct{ RecType Rec[MaxNum]; //MaxNum是一个常量 int len; }SeqList; HeapInsert(SeqList R, KeyType key){ int i,j; R.Rec[++R.len].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.len/2; j=R.len; while(i＞0){ //调整为堆 if(R.Rec[i].key＜R.Rec[j].key){ R.Rec[0]=R.Rec[i]; R.Rec[i]=R.Rec[j]; R.Rec[i]=R.Rec[0]; } j=i; i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h，则满足h≤log2R.len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log2R.len)。
问答题给定线性方程组1)写出Gauss-Seidel迭代格式；2)分析此迭代格式的收敛性
问答题分析方程sin
2
x+1=x存在几个实根；用迭代法求出这些实根(要求精确至4位有效数字)，并说明所用迭代格式为什么是收敛的．
问答题冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。
问答题给定方程x
3
+2x-1=0，判别该方程有几个实根，并用迭代法求出方程所有实根，精确到4位有效数字．
问答题设计一个算法，输出图G中经过某个顶点vi的长度为L的所有环。
问答题求参数a，b，使达到最小．
问答题假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，求平衡二叉树的高度。
问答题设f(x)=2x-x
2
，x∈[0，1]，求f(x)的1次最佳平方逼近多项式．
问答题已知x=3．456和y=0．1234是具有4位有效数字的近似值，试分析x—y及x
2
y的绝对误差限和相对误差限．
问答题用列主元Gauss消去法求下面线性方程纽的解：
问答题试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。
问答题给定常微分方程初值问题取正整数n，记xi=a+ih，i=0，1，2，…，n；yi≈y(xi)，i=1，2，…，n，y0=η．1)用数值积分方法构造形如yi+1=yi-1+h[Af(xi+1十1，yi+1)+Bf(xi，yi)+Cf(xi-1，yi-1)]的数值求解公式，并写出该求解公式的阶数和局部截断误差表达式；2)改进的Euler公式与上述公式构造一个预测-校正公式．
问答题给定求积公式1)求该求积公式的代数精度；2)证明：存在η∈(a，b)，使得
问答题用C语言或PASCAL编写一用链接表(Linked List)解决冲突的哈希表插入函数。
问答题求y=｜x｜在[-1，1]上形如c
0
+c
1
x
2
的最佳平方逼近多项式．
问答题对有5个结点{A，B，C，D，E)的图的邻接矩阵(1)画出逻辑图；(2)基于邻接矩阵写出图的深度、广度优先遍历序列；(3)计算图的关键路径。
问答题给定边值问题其中={(x，y)｜0＜x＜1，0＜y＜1}，是Ω的边界．取正整数M，记h=1／M，xi=ih(0≤i≤M)，yj=jh(0≤j≤M)．假设上述问题存在光滑解，试构造求解上述边值问题的一个差分格式，要求截断误差为O(h2)，并写出截断误差表达式．
问答题什么是日志文件？简述利用日志文件进行事务恢复的过程。（8分）
问答题给定线性方程组1)写出求解该方程组的Jacobi迭代格式；2)取初始向量x(0)=(1，1，1)T，用Jacobi迭代求方程组的解，精确到2位有效数字．