㈠ 檢索樹的應用

總結微軟筆試題和要點
第一部分選擇題主要的知識點：

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;
}