2013年专业课

二、算法分析题

2、试写一个算法，借助堆栈和队列判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool PalindromeTest(){
        InitStack(S);
        InitQueue(Q);

        while((c=getchar())!='@'){
            Push(S,c);  EnQueue(Q,c);     //同时入栈和入队
        }

        while(!StackEmpty(S)){
            Pop(S,a);DeQueue(Q,b);    //同时出栈和出队列，判断出来的字符是不是相同
            if(a!=b) return false;
        }
        return true;
}

3、设计在链式结构上交换二叉树中所有节点左右子树的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
void swapbitree(TreeNode *root)
{
	TreeNode *temp;
	if(root)
	{
		return NULL;
	}
	swapbitree(root->lchild);//递归左子树
	swapbitree(root->rchild);//递归右子树
	temp=root->lchild;
	root->lchild=root->rchild;
	root->rchild=temp;
}