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