问答题给定方程xe
x
+x-1=0，判别该方程有几个实根，并用迭代法求方程所有实根，精确到4位有效数字．
问答题求函数f(x)=在[0，1]上的一次最佳平方逼近多项式P1(x)=a+bx．
问答题假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=0(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。
问答题给定如下抛物方程初边值问题：取步长用古典隐格式计算u(x，t)在点处的近似值．
问答题设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。)
问答题给定下面的线性方程组试写出求解该方程组的Gauss-Seidel迭代格式，并分析Gauss-Seidel迭代格式的收敛性．
问答题给定求解线性方程组Ax=b的迭代格式Bx(k+1)+ωCxk=b，其中试确定ω的值使上述迭代格式收敛．
问答题求函数f(x)=在[0，1]上的一次最佳平方逼近多项式p1(x)=c0+c1x．
问答题两个整数序列A=a1，a2，a3，…，an和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。
问答题设线性表A=(a
1
，a
2
，a
3
，…，a
n
)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a
2
，a
4
，…，a
n-1
，a
1
，a
3
，…，a
n
)，当n为偶数时A=(a
2
，a
4
，…，a
n
，a
1
，a
3
，…，a
n-1
)。
问答题关于堆的一些问题：
(1)堆的存储表示是顺序的，还是链接的?
(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?
问答题分析以下各程序段的时间复杂度。
问答题自由树(即无环连通图)T=(V，E)的直径是树中所有点对点之间最短路径长度的最大值，即T的直径定义为d(u，v)的最大值(其中u，v∈V)。这里d(u，v)表示顶点u到顶点v的最短路径长度(路径长度为路径中包含的边数)。如图所示为一棵自由树，其直径为18。试写算法求T的直径，并分析算法的时间复杂度。
问答题给定初边值问题取正整数M，N，记h=1／M，T=1／N，xi=ih(0≤i≤M)，tk=kt(0≤k≤N)．试构造求解上述初边值问题的一种显式差分格式，要求截断误差为O(T2+h2)．
问答题给定方程e
x
=2-x，证明该方程存在唯一实根x
*
，并用迭代法求x
*
的近似值，精确到3位有效数字．
问答题线性表(a1，a2，a3…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。
问答题键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PASCAL语言编写一个在键树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
问答题用简单迭代法求方程sinx-x
2
+2=0的正根，精确到4位有效数字，并验证迭代法的收敛性．
问答题有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
设计实现计数排序的算法。对于有n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?
问答题什么是数据的物理独立性和逻辑独立性？在数据库系统中是如何实现数据独立性的？（7分）