问答题请简要说明下列函数的主要功能。 void func(LinkList L1，LinkList L2) {LNode*p， *q， *r； q=L2一>next； while(q) {P*L1； while(p一>next) {if(p一>next->data==q一>data) (r=P一>next；P一>next=r一>next；free(r)；} P=P一>next； } q=q一>next； } return； }【北京理工大学2006十一、2(5分)】
问答题设记录R[i]的关键字为R[i]．KEY(1≤i≤k)，树结点T[i](1≤i≤k-1)指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i](1≤f≤k)的败者树，要求除R[1．．k]和T[0一K-1]以外，只用O(1)辅助空间。【东南大学1995九(15分)】
问答题假设长度为n的顺序表A中每一个数据元素均为整型数据，请写出在该顺序表中采用顺序查找法查找值为item的数据元素的递归算法。若查找成功，算法返回item在表中的位置，否则，返回信息为一1(写成非递归算法不得分)。【北京航空航天大学2006二(10分)】
问答题有字符串次序为3*-y-a/y^2，利用栈，给出将次序改为3y-*ay2^／的操作步骤。(可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。)【东北大学2001一、4(4分)】
问答题字符运算Index(&t pos)的返回值是__________。【北京理工大学2007二、1(1分)】
问答题已知一二叉树中结点的左右孩子分别为left和right，p指向二叉树的某一结点。请用C或Pascal编一个非递归函数postfirstp)，求p所对应子树的第一个后序遍历结点。【浙江大学1998六(10分)】【上海交通大学2004二(10分)】
问答题对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边?任意两个顶点i和j之间是否有边相连?任意一个顶点的度是多少?【北京理工大学2006六、4(50／7分)】【华南理工大学2005二、5(4分)】
问答题求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10 ms，则在图的顶点数为40时，计算时间约为__________ms。【南京理工大学2000二、3(1．5分)】
问答题给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。【东南大学1993三(20分)1997三(1 8分)1998六(14分)】【东北大学2003三(20分)】
问答题已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。(1)将上述过程用递归函数表达出来(设求x除以y的余数可以用x MODy形式表示)。(2)写出求解该递归函数的非递归算法。【北京航空航天大学2001五(15分)】
问答题试叙述一维数组与有序表的异同。【西安电子科技大学1999计算机应用一、2(5分)】
问答题假设称正读和反读都相同的字符序列为“回文”，例如，‘abcba"是回文，’abcde"和"ababab"则不是回文。试写一个算法判别读入的一个以‘’为结束符的字符序列是否是“回文”。【中国海洋大学2007八(15分)】
问答题已知关键字序列(K
1
,K
2
,K
3
,…，K
n-1
)是大根堆。(1)试写出一算法将(K
1
,K
2
,K
3
,…，K
n-1
，K
n
)调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【中科院软件所1999七、2(7分)】
问答题数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。 【厦门大学1998五、1(5分)】
问答题已知完全二叉树有266个结点，则整棵树上度为1的结点数是__________。【北京交通大学2006二、3(2分)】
问答题试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2．0。并请验证你造的哈希表的实际平均查找长度是否满足要求。(CHA，CAI，LAN，WEN，LONGZHAO，WU，LIU，CHEN，LI，WANG CAO，YUN，CHANG YANG)【清华大学1996五】
问答题设有向图以邻接矩阵adj表示，每个顶点的入度用数组nodein存储，已知adj和nodein。请写出对该图进行拓扑排序的算法。【中国海洋大学2007十(15分)】
问答题已知无向图G=(V,E)，给出求图G的连通分量个数的算法。【哈尔滨工业大学2002九(9分)】【南京航空航天大学1995十一(10分)】
问答题对下列数据表，写出采用希尔排序算法的每一趟排序结果。 (100，12，20，31，1，5，44，66，61，200，30，80，150，4，8)设增量序列为：D=-{5，3，1)【中国海洋大学2007一、4(8分)】
问答题给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。【北京邮电大学2001五、3(10分)】