"百度笔试题：树比较与数组查找"

个人整理了部分年度的百度笔试题目，以下是其中三道题目的描述和解决方案。 题目1：请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。数据结构为： typedef struct_TreeNode{ char c; TreeNode *leftchild; TreeNode *rightchild; }TreeNode; 函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2); 题目2：写一段程序，找出数组中第 k 大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是 7，位置在 4。第二大、第三大的数都是 4，位置在 1、3 随便输出哪一个均可。 函数接口为：int find_orderk(const int* narry,const int n,const int k) 题目3：已知一个字串由 GBK 汉字和 ansi 编码的数字字母混合组成，编写 c 语言函数实现从中去掉所有 an; 解答： 题目1： 思路：首先判断两棵树的根节点是否相等，如果不相等就返回其他值。如果相等，则递归检查左子树和右子树是否相等或者互相转换相等。如果左子树和右子树都相等，则返回相等的值，否则返回其他值。 算法复杂度：假设两棵树的节点数分别为m和n。对于每个节点，我们需要检查其左右子树是否相等，所以总的时间复杂度为O(m+n)。 题目2： 思路：首先对数组进行排序，然后找到第k个最大的数，并记录其位置。 算法步骤： 1. 对数组进行排序，可以选择使用快速排序或者堆排序等快速的排序算法。 2. 找到第k个最大的数，即数组排序后的第n-k个数。 3. 遍历数组，找到第n-k个数的位置。 算法复杂度：排序算法的平均时间复杂度为O(nlogn)，加上遍历数组的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn)。 题目3： 思路：遍历字符串，判断每个字符的类型，如果是ansi编码的数字字母，则保留，否则去掉。 算法步骤： 1. 遍历字符串，判断每个字符的类型。 2. 如果是ansi编码的数字字母，则保留，否则去掉。 3. 重新组合保留下来的字符，形成去掉所有ansi编码的数字字母的字符串。 算法复杂度：假设字符串长度为n，遍历字符串的时间复杂度为O(n)。 以上是个人对部分年度的百度笔试题目的整理和解答，希望对您有帮助。