㈠ 检索树的应用

总结微软笔试题和要点
第一部分选择题主要的知识点：

1、临界变量critical section的概念（还有semaphore，thread类似的这些）。

2、存储器cache写穿透和写返回的概念（复习一下高体的cache）。

3、数据库技术里的几种隔离级别，一般是可重复的读、读稳定性等。可重复的读最高。

4、Java的内存管理机制，包括沙箱和garbage collector。

5、C++的内存管理机制，注意和上面的区别，new操作和delete操作的作用方式，以及和alloc与free的区别，内存不足时怎么办。

6、计算机网络IP地址和子网掩码的知识，怎样判断两个ip地址和对应子网掩码是否能通信。

7、C++里虚函数的概念，非常重要。另外，const的用法，虚继承和内联函数各自的好处和不好，等等这些基础的知识要掌握。

8、一个对象在内存里是怎样存储的，注意虚继承和有虚函数的情况。

9、对字符串的操作，应该注意哪些问题，包括拷贝，访问，等等。

10、基本的数据结构，如堆（注意最大值堆和最小值堆的操作和建堆的过程）、栈、连表、队列、二叉树（注意二叉检索树的相关操作）、图，这些知识和相关的算法要掌握。

二、逻辑部分，不用复习了，没啥必要，一般是推理题，总会做出来的，只是时间问题。但说实话，我觉得在这里浪费时间来求准确性是非常重要的，因为后面的大题很难拿分，与其后面的题目写了一堆，不如在这里多花些时间求准确性，以为答对一个就是1.5分

三、程序设计 第二次笔试是两个题目，一个是求一个数组的最大公约数，知道展转相除的话很简单，但要把自己主要的思想用一句话哪怕是中文写在题目旁边，这样看的人就知道你会做这个题目了。程序都是很乱的，而且一个人不容易读懂另一个人的程序，所以这点我觉得有用。 第二个，是让你对一个英文字典建立一个抽象数据类型（就是一个C++类），然后对给定的前缀打印出所有的单词。trie树是一个数据结构，简单地，它可以有任意多个子结点。那么对字典建立trie树即可。对于给定的前缀，只要顺序搜索子结点，然后递归打印出所有的叶结点就OK了。知道了想法也就简单。 总结一下，就是这部分的题目其实都不难，但纸张的空间有限，而且基本都要求写完程序之后写测试用例，所以其实挑主要的写就可以了。注意尽可能的精简就成。

四、设计 一般这个题目，是给你一个场景，如M$的MSN或者outlook或者office等，问你有哪些不足，需要增加哪些功能你觉得，然后举一个你最想增加的功能，并说明给你3个月你怎么实现。随便bla吧，但如果你应聘的是PM，那么这个题目相当重要。

五、测试 两个题目，都是写测试用例和第三大题不同，虽然第三大题也让你写完算法程序后写测试用例，但这个要详细一些。一般是先挑bug，再写测试用例。所谓的测试用例，就是给定的输入参数和期望的输出结果。一般让你挑bug的，都是对字符串进行操作的，所以一定要仔细检查，是否有操作空指针、是否检查了输入参数、是否有指针越界。 上次笔试是给定的两个题目是一个检查函数中操作字符串的bug并写测试用例，一个是给一个函数int system(char* command)，让你写测试用例。黑箱测试了。 不知道为什么第二次的时间变短了，改成了2个半小时，不知道这次是多少小时，时间方面可能要抓紧一下，否则写不完。感觉还是要把前面的题目尽量做对，否则如果某个题目没达到他们最低的要求，人家就不向下看了。0分和第一次的负分就是这么出来的，选择题没过。

㈡ 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \5 7 9 11因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。分析：主要考查对二元查找树的理解。在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。#include #include int check_walk(int A[], int length) { int i = 0; int j; int left = 1; int right = 1; int x = A[length-1]; while(A[i]

㈢ 判断数组是不是某二叉搜索树的后序遍历结果

输入一个整数数复组，制判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \5 7 9 11因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。#include #include int check_walk(int A[], int length) { int i = 0; int j; int left = 1; int right = 1; int x = A[length-1]; while(A[i]

㈣ 判断两序列是否为同一二叉搜索树序列 input 开始一个数n，表示有n个需

题目描述：
判断两序列是否为同一二叉搜索树序列
输入：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：
如果序列相同则输出YES，否则输出NO
样例输入：
2
567432
543267
576342
0

样例输出：
YES
NO

㈤ 搜索树在人工智能中是什么样一个概念，处于一个什么样的地位

搜索抄树是一种用来搜索解决袭方案的技术，搜索树的根是对应于初始状态的搜索节点， 第一步判断该节点是否为目的节点，如果是，结束，如果不是，展开当前节点，搜索子节点是否为目标状态，遍历节点有很多技术的，最后直到找到目标状态才停止。
它是属于 Problem solving agent里的一种机制，算是人工智能中一个方向的核心技术~

㈥ 输入一个整数数组，判断该数组是不是某二叉搜索树的

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \5 7 9 11因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。#include #include int check_walk(int A[], int length) { int i = 0; int j; int left = 1; int right = 1; int x = A[length-1]; while(A[i]

㈦ 验证一颗树是否为有效的二叉搜索树bst，比如，二叉树

满意答案望远镜8级2010-03-22完全二叉树看是几层的，比如3层完全二叉树，就有7个结点，结点总数是（的3次方）减1个；叶子结点数是2的（3减1次方）个，就是4个。如果是n层完全二叉树，结点总数是（2的n次方）减1个；叶子结点数是2的（n减1次方）个；会了就非常简单。这回你明白了吗？追问：如果完全二叉树700个结点，有多少叶子结点回答：所谓完全二叉树，是不可能有700个结点的，完全二叉树的第N层，都会是2的N-1次幂个结点，而上一层，则是N-2次幂个结点，所以总节点数应该是2N次幂减1，700不是一个这样的数，所以不会有700个结点。如果是两层，那应该是4－1＝3个结点，三层，是8－1＝7个结点四层，是16－1＝15个结点五层，是32－1＝31个结点六层，是64－1＝63个结点七层，是128－1＝127个结点八层，是256－1＝255个结点九层，是512－1＝511个结点十层，是1024－1＝1023个结点。。。。因此，不会出现700个结点的完全二叉树。追问：可是我做到这个题了啊！回答：你确定是完全二叉树吗？有“完全”二字吗？追问：题目中确实有啊，答案是350回答：正好是总结点数的一半！那这个好记了

㈧ 二叉树查找树算法实现

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int ElemType;
typedef int Status;
typedef struct TElemType{
int key;
int num;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) { p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status SearchBST1(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) {
printf("%d %d",p->data.key,p->data.num);
p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status InsertBST(BiTree &T,TElemType e){
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return OK;
}
}
Status Output(TElemType e){
printf("%d ",e.key);
printf("%d\n",e.num);
}
Status PreOrderTraver( BiTree T){//二叉树先序遍历
if(T==NULL) return ERROR;
else{
Output(T->data);
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchild);}
return OK;
}
int main()
{
BiTree T,f=NULL,q;
TElemType a;
int i,n,b;
printf("请输入你要创建的二叉排序树的结点个数:\n");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",a.key);
scanf("%d",a.num);
InsertBST(T,a);
}
printf("请输入你要查找的关键字: ");{
scanf("%d",b);
if(SearchBST1(T,b,f,q)) printf("查找成功！\n");
else printf("查找失败！\n");}
printf("二叉树的先序遍历:\n");
PreOrderTraver(T);
system("pause");
return 0;
}
这个就是！希望可以帮助你！

㈨ 数组，判断该数组是不是某二叉搜索树的后序遍历的结果

// 二叉搜索树的遍历序列.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

bool isPostBST(int sequence[], int length) //注意这里传入的sequence就是指向序列的第一个结点
{
//1.容错性
if (sequence==NULL||length<=0)
return false;

//2.先要找到序列的分界点,此时因为对左子树进行了遍历所以也相当于对左子树进行了判断
int i; //分界点
for (i = 0; i < length - 1; i++)
{
if (sequence[i]>sequence[length - 1])
break;
}
//3.对序列的右子树进行判断
for (int j = i; j < length-1; j++)
{
if (sequence[j] < sequence[length - 1])
return false;
}
//4.当左右子树都满足的时候就要进行递归
if (i >= 1)//左边至少有两个点的时候
return isPostBST(sequence, i);

if (i <= length - 3)//右子树至少有两个点的时候
return isPostBST(sequence + i, length -i-1);//i是左子树的数目，1是根节点的数目

return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
//int s[] = {7,4,6,5};
//int s[] = { 7, 8, 6, 5 };
int s[] = { 5,7,6,9,11,10,8 };
if (isPostBST(s,7))
cout<< "输入的数组为某个二叉搜索树的后序遍历！" << endl;
else
cout<< "输入的数组不是任何二叉搜索树的后序遍历！" << endl;
return 0;
}