超星 - 练习作业（方便大家做题看答案，成绩不计入作业成绩） - 查题吧

简答题

在二叉树中查找值为x的结点，试编写算法（用C语言）打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度（若不加分析，直接写出结果，按零分算）。【上海交通大学1998 五】

简答题

对于二叉树的链接实现,完成非递归的中序遍历过程。【中山大学 1999 五、(15分)】

简答题

设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。【福州大学1998 四、2 (10分)】

简答题

设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。【东北大学2001 三(15分)】

简答题

已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。【东北大学1999 六、3 （12分）】

简答题

两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。【北京工业大学1996 一、5 (6分)】

简答题

描述以下概念的区别：空格串与空串。【大连海事大学1996 三、2保存并返回、（1）(2分)】

简答题

KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?【大连海事大学1996三、1((2分)】

简答题

设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？【大连海事大学 2001 四(8分)】

简答题

设有一组字符｛a,b,c,d,e,f,g,h,i,j｝,权为{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}，试画出其哈夫曼树，求得每个字符的编码，并计算WPL的值。（在纸上画图，然后拍照上传）

1