1、給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么b是a的兄弟單詞，比如的單詞army和mary互為兄弟單詞。
現在要給出一種解決方案，對于用戶輸入的單詞，根據給定的字典找出輸入單詞有哪些兄弟單詞。請具體說明數據結構和查詢流程，要求時間和空間效率盡可能地高。
字典樹的典型應用，一般情況下，字典樹的結構都是采用26叉樹進行組織的，每個節點對應一個字母，查找的時候，就是一個字母一個字母的進行匹配，算法的時間復雜度就是單詞的長度n，效率很高。因此這個題目可以定義一個字典樹作為數據結構來查詢的，時間效率會很高，這樣就轉化為在一棵字典樹中查找兄弟單詞，只要在字典樹中的前綴中在存儲一個vector結構的容器，這樣查找起來就是常數級的時間復雜度了，效率很高的。。
數據結構可以定義如下：
[cpp] view plaincopy
1. struct word
2. {
3. vector
4. word *next[26]; // 字典樹中每個節點代表一個字符，并指向下一個字符
5. };
如上述數據結構所示，字典樹的建立是在預處理階段完成的，首先根據字典中的單詞來建立字典樹，建立的時候，需要稍微特殊處理一下，就是比如pots、stop和tops互為兄弟單詞，那么在字典中按照首字母順序的話，應該先遇到pots單詞，那么我首先對其進行排序，結果是opts，那么字典樹中就分別建立4個節點，分別為o->p->t->s，當然這個是不同層次的，在節點s處的vector容器brother中添加單詞pots，遇到stop的時候，同樣的方法，排序是opts，此時發現這4個節點已經建立了，那么只需要在第四個節點s處的vector容器brother中添加單詞stop，tops單詞的處理方法是同樣的。
這樣建立完字典樹后，查詢兄弟單詞的效率就會很高了，比哈希的效率還要高；查到tops的兄弟的單詞的時候，首先排序，那么就是opts，然后在字典樹中查找opts，在s處將其vector容器brother中的的單詞輸出就是tops的所有兄弟單詞。
2、系統中維護了若干數據項，我們對數據項的分類可以分為三級，首先我們按照一級分類方法將數據項分為A、B、C......若干類別，每個一級分類方法產生的類別又可以按照二級分類方法分為a、b、c......若干子類別，同樣，二級分類方法產生的類別又可以按照是三級分類方法分為i、ii、iii......若干子類別，每個三級分類方法產生的子類別中的數據項從1開始編號。我們需要對每個數據項輸出日志，日志的形式是key_value對，寫入日志的時候，用戶提供三級類別名稱、數據項編號和日志的key，共五個key值，例如，write_log（A,a,i,1,key1），獲取日志的時候，用戶提供三級類別名稱、數據項編號，共四個key值，返回對應的所有的key_value對，例如get_log（A,a,i,1,key1），
請描述一種數據結構來存儲這些日志，并計算出寫入日志和讀出日志的時間復雜度。
3、C和C++中如何動態分配和釋放內存？他們的區別是什么？
malloc/free和new/delete的區別，
4、數組al[0,mid-1]和al[mid,num-1]是各自有序的，對數組al[0,num-1]的兩個子有序段進行merge，得到al[0,num-1]整體有序。要求空間復雜度為O(1)。注：al[i]元素是支持'<'運算符的。
[cpp] view plaincopy
1. /*
2. 數組a[begin, mid] 和 a[mid+1, end]是各自有序的，對兩個子段進行Merge得到a[begin , end]的有序數組。 要求空間復雜度為O(1)
3. 方案：
4. 1、兩個有序段位A和B，A在前，B緊接在A后面，找到A的第一個大于B[0]的數A[i]， A[0...i-1]相當于merge后的有效段，在B中找到第一個大于A[i]的數B[j]，
5. 對數組A[i...j-1]循環右移j-k位，使A[i...j-1]數組的前面部分有序
6. 2、如此循環merge
7. 3、循環右移通過先子段反轉再整體反轉的方式進行，復雜度是O(L), L是需要循環移動的子段的長度
8. */
9. #include
10. using namespace std;
11.
12. void Reverse(int *a , int begin , int end ) //反轉
13. {
14. for(; begin < end; begin++ , end--)
15. swap(a[begin] , a[end]);
16. }
17. void RotateRight(int *a , int begin , int end , int k) //循環右移
18. {
19. int len = end - begin + 1; //數組的長度
20. k %= len;
21. Reverse(a , begin , end - k);
22. Reverse(a , end - k + 1 , end);
23. Reverse(a , begin , end);
24. }
25.
26. // 將有序數組a[begin...mid] 和 a[mid+1...end] 進行歸并排序
27. void Merge(int *a , int begin , int end )
28. {
29. int i , j , k;
30. i = begin;
31. j = 1 + ((begin + end)>>1); //位運算的優先級比較低，外面需要加一個括號，剛開始忘記添加括號，導致錯了很多次
32. while(i <= end && j <= end && i
33. {
34. while(i <= end && a[i] < a[j])
35. i++;
36. k = j; //暫時保存指針j的位置
37. while(j <= end && a[j] < a[i])
38. j++;
39. if(j > k)
40. RotateRight(a , i , j-1 , j-k); //數組a[i...j-1]循環右移j-k次
41. i += (j-k+1); //第一個指針往后移動，因為循環右移后，數組a[i....i+j-k]是有序的
42. }
43. }
44.
45. void MergeSort(int *a , int begin , int end )
46. {
47. if(begin == end)
48. return ;
49. int mid = (begin + end)>>1;
50. MergeSort(a , begin , mid); //遞歸地將a[begin...mid] 歸并為有序的數組
51. MergeSort(a , mid+1 , end); //遞歸地將a[mid+1...end] 歸并為有序的數組
52. Merge(a , begin , end); //將有序數組a[begin...mid] 和 a[mid+1...end] 進行歸并排序
53. }
54.
55. int main(void)
56. {
57. int n , i , a[20];
58. while(cin>>n)
59. {
60. for(i = 0 ; i < n ; ++i)
61. cin>>a[i];
62. MergeSort(a , 0 , n - 1);
63. for(i = 0 ; i < n ; ++i)
64. cout<
65. cout<
66. }
67. return 0;
68. }
5、線程和進程的區別及聯系？如何理解“線程安全”問題？
答案：進程和線程都是由操作系統所體會的程序運行的基本單元，系統利用該基本單元實現系統對應用的并發性。
1、簡而言之,一個程序至少有一個進程,一個進程至少有一個線程.
2、線程的劃分尺度小于進程，使得多線程程序的并發性高。
3、另外，進程在執行過程中擁有獨立的內存單元，而多個線程共享內存，從而極大地提高了程序的運行效率。
4、線程在執行過程中與進程還是有區別的。每個獨立的線程有一個程序運行的入口、順序執行序列和程序的出口。但是線程不能夠獨立執行，必須依存在應用程序中，由應用程序提供多個線程執行控制。
5、從邏輯角度來看，多線程的意義在于一個應用程序中，有多個執行部分可以同時執行。但操作系統并沒有將多個線程看做多個獨立的應用，來實現進程的調度和管理以及資源分配。這就是進程和線程的重要區別。
