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