已选分类
工学
问答题在二叉链表表示的二叉树中，增设一个指针域，初值为空，试给出算法在不使用堆栈又不破坏原二叉树的情况下，前序遍历该二叉树。【北京邮电大学2004五、2(15分)】
问答题在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点?
问答题选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选一个值最小的元素，将其与未排好的那些元素的第一个元素交换位置。根据这个原理，请写出对一个带有头结点的单链表按数据域从小到大进行选择排序的算法。约定：链结点构造为(data，link)，每一个链结点的数据域中存一个整型数，但是头结点数据域中不存放任何信息；设头结点指针为list。限制：排序过程中不得不申请任何链结点空间，也不得改变任何链结点的数据域内容。【北京航空航天大学2006三(10分)】
问答题按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林；(3)用后根序遍历该森林，写出遍历后的结点序列。【北京邮电大学1996五(10分)】
问答题两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m，n)。估算最优的r(m，n)，并简要说明理由。【北京工业大学1996_、5(6分)】
问答题请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x)：元素x入ST栈；POP(ST x)：ST栈顶元素出栈，赋给变量x；Sempty(ST：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue：插入一个元素入队列；dequeue：删除一个元素出队列；queue一empty：判队列为空。(请写明算法的思想及必要的注释。)【上海交通大学1999二(12分)】【厦门大学2005六(15分)】
问答题若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有__________棵树。【哈尔滨工业大学2005一、7(1分)】
问答题
问答题给定常微分方程初值问题(B)取正整数n，记h=(b—a)／n，xi=a+ih，i=0，1，2，…，n．给定求初值问题(B)的多步方法：yi+1=--4yi+5yi-1+h[β1f(x1，y1)+β2f(xi+1，yi+1)]．(C)1)试确定公式(C)中的参数β1，β2，使求解公式具有尽可能高的阶数，写出局部截断误差表达式并指出最高阶数；2)利用Euler公式和公式(C)构造一个预测-校正公式．
问答题如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的l都集中到对角线以上?【清华大学1999一、5(2分)】
问答题任务状态段的作用是什么?
问答题给定椭圆边值问题其中Ω={(x，y)｜0＜0＜1，0＜y＜1)，是Ω的边界．记h=1／m，xi=ih，i=0，1，…，m；yj=jh，j=0，1，…，m．设uij是u(xi，yj)的近似值．1)写出解上述边值问题的五点差分格式及差分格式的截断误差；2)将五点差分格式朋矩阵和向量表示为一个线性方程组，并简述该方程组的求解方法．
问答题设T是一棵满二叉树，写一个把T的后序遍历序列转换为先序遍历序列的递归算法。【中科院研究生院2003十(15分)】
问答题对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。【吉林大学1999一、2(4分)】
问答题已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。
问答题设有一个具有n个单元的循环队列，头指针为front，尾指针为rear，试写出一个算法，求队列中元素的个数。
问答题试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入：(a
1
，a
2
，a
3
，…，a
n
)，n≥0，其中a
t
或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。【北京工业大学1998十(15分)】
问答题编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参left和right，分别指定算法在本层之下时的奁找区间均左、右端点。当查找成功时函数返回查找到的元素的存放位置；当查找不成功时函数返回-1。
递归算法的首部为int binarySearch1(seqList&L,DataType x,int left,int right)。主程序的调用方式为int loc=binarySearch1(L,x,0,L.n-1)。
问答题试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(Linklist&L)。【北京理工大学2001年】
问答题给出在一个递增有序表A中采用二分查找算法查找值为x的元素的递归算法。