数据结构 75分
一、下列算法时间复杂性?
void fun(int m,int n)
{
int i=0,j=0;
while(i<m)
if(j<n) j++;
else
{
j=0;
i++;
}
}
二、
1 void String::fail ( ) { // 计算模式p ( *this)的失败函数
2 int LengthP= Length( ); f[0]= -1;
3 for (int j = 1; j < LengthP; j++) { // 计算f[j]
4 int i = f[j-1];
5 while ((*(str+j)!=*(str+i+1)) && (i>=0)) i=f;
6 if ( *(str+j) == *(str+i+1)) f[j] = i+1;
7 else f[j] = -1;
8 }
9 }
问：第5句的作用是？执行第6句时i可以小于0吗？执行第7句时i一定小于0吗？
三、 R0，R1，R2，R3，R4，R5，R6建败着树（数据两两不相等，自己编哈） （考过）
四、论述在克鲁斯卡尔算法中，如何利用并查集判断所选边<u,v>是否会成环。（书上有，仔细看书）
五、（书上有，不错过每一细节）
树的定义：一棵树是由一个或多个结点组成的有限集合，且其中
（1） 存在一个称为根的特定结点；
（2） 剩余结点被划分为n≥0个不相交集合T1, …, Tn，且Ti（1≤i≤n）也是一棵树。T1, …, Tn 称为根结点的子树。
问：为什么树不能为空啊？为什么二叉树可以啊？
六、快排序和堆排序都不稳定，举例说明。（书上习题）
(我选的是(a0,a1,a2),其中a0=a1=a2,这个好记哈。。。)
七、给了一棵3阶B树，画图描述连续删除两个数，再在原图上连续插入两个数过程。
八、
struct Element{int key;};
struct TreeNode
{
TreeNode *LeftChild,*RightChild;
Element data;
}
利用上面两个结构给出判断一棵根为t的二叉树是否为AVL树的递归算法。
bool Tree::IsAVL()
{
return IsAVL(t);
}
bool Tree::IsAVL(TreeNode * cur)
{
if(!cur) return true;
//...下面自己写哈
}
int Tree::Height(TreeNode * cur)
{
//...
}
