已选分类
工学计算机科学与技术
试题题型
问答题求函数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分）
问答题试找出分别满足下面条件的所有二叉树：
(1)前序序列和中序序列相同。
(2)中序序列和后序序列相同。
(3)前序序列和后序序列相同。
(4)前序、中序、后序序列均相同。
问答题对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
问答题欲用4种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色(点相交不算相邻)。
(1)试用一种数据结构表示地图上各国相邻的关系；
(2)描述涂色过程的算法。(不要求证明)
问答题若g(x)是f(x)以x0，x1，…，xn-1为插值节点的(n-1)次插值多项式，h(x)是f(x)以x1，x2，…，xn为插值节点的(n-1)次插值多项式．证明函数是f(x)以x0，x1，…，xn为插值节点的n次插值多项式．
问答题求一个不超过3次的多项式p(x)，使曲线y=p(x)与曲线y=sinx在点(0,0)处相交，且在点处相切，并证明
问答题用简单迭代法求非线性方程x-lnx=2在(2，+∞)内的根，要求精确至6位有效数字，并说明所用迭代格式为什么是收敛的．
问答题设，∈C
4
[a，a+2]，求一个3次多项式H(x)，使之满足H(a)=f(a)， H(a+1)=f(a+1)， H(a+2)=f(a+2)，H"(A)=f"(a)，并写出插值余项f(x)-H(x)的表达式．