選擇題：

　　1、二維數(shù)組int a[3][4]，下列能表示a[1][2]的是?

　　A.*(*(a+1)+2) B.*(a+3) C.(&a[0]+1)[2] D.(a[0]+1)

　　2、short a[100]，則sizeof(a)的值是?

　　A.2 B.4 C.200 D.400

　　問答題：

　　1、解釋說明static、const和volatile兩個關(guān)鍵字的作用?

　　關(guān)鍵字static有三個明顯的作用：

　　1、在函數(shù)體，一個被聲明為靜態(tài)的變量在這一函數(shù)被調(diào)用過程中維持其值不變。

　　2、 在模塊內(nèi)(但在函數(shù)體外)，一個被聲明為靜態(tài)的變量可以被模塊內(nèi)所有函數(shù)訪問，但不能被模塊外其它函數(shù)訪問。它是一個本地的全局變量。

　　3、在模塊內(nèi)，一個被聲明為靜態(tài)的函數(shù)只可被這一模塊內(nèi)的其它函數(shù)調(diào)用。那就是，這個函數(shù)被限制在聲明它的模塊的本地范圍內(nèi)使用。

　　const 有什么用途?

　　1、可以定義 const 常量

　　2、const可以修飾函數(shù)的參數(shù)、返回值，甚至函數(shù)的定義體。被const修飾的東西都受到強制保護，可以預(yù)防意外的變動，能提高程序的健壯性。

　　volatile問題：

　　volatile的作用: 作為指令關(guān)鍵字,確保本條指令不會因編譯器的優(yōu)化而省略,且要求每次直接讀值。。。

　　volatile的語法與const是一樣的，但是volatile的意思是“在編譯器認(rèn)識的范圍外，這個數(shù)據(jù)可以被改變”。不知何故，環(huán)境正在改變數(shù)據(jù)(可能通過多任務(wù)處理)，所以，volatile告訴編譯器不要擅自作出有關(guān)數(shù)據(jù)的任何假設(shè)——在優(yōu)化起家這是特別重要的。如果編譯器說：“我已經(jīng)把數(shù)據(jù)讀入寄存器，而且在沒有與寄存器接觸。”在一般情況下，它不需要再讀入這個數(shù)據(jù)。但是，如果數(shù)據(jù)是volatile修飾的，編譯器則是不能做出這樣的假定，因為數(shù)據(jù)可能被其他進程改變了，編譯器必須重新讀這個數(shù)據(jù)而不是優(yōu)化這個代碼。就像建立const對象一樣，程序員也可以建立volatile對象，甚至還建立const volatile對象。這個對象不能被程序員改變，但可通過外面的工具改變。

　　volatile對象每次被訪問時必須重新讀取這個變量的值，而不是用保存在寄存器中的備份。下面時volatile變量的幾個例子：

　　.并行設(shè)備的硬件寄存器(如狀態(tài)寄存器);

　　.一個中斷服務(wù)子程序中會訪問到的非自動變量(Non-automatic variables);

　　.多現(xiàn)成應(yīng)用中被幾個任務(wù)共享的變量。

　　一個參數(shù)可以const同時也是volatile，一個指針也是可以為volatile的，但是具體編程時要小心，要保證不被意外修改。

　　1、static關(guān)鍵字的作用，個人經(jīng)驗主要有以下幾種：1)函數(shù)局部static變量，第一次函數(shù)調(diào)用被初始化，后續(xù)每次調(diào)用將使用上次調(diào)用后保存的值;2)全局變量中static變量，可以防止被其他文件的代碼使用這個變量，有點將這個全局變量設(shè)置為private的意味;3)對于static函數(shù)來說，效果和2中的變量相同;4)C++類中static方法，不需要實例化訪問;5)C++定義static類成員變量，不需要實例化訪問，不過需要先定義，定義的時候可以初始化數(shù)組。

　　2、volatile用來聲明一個變量，并強制程序在每次使用變量的重新從變量地址讀取數(shù)據(jù)，這是為了防止變量在其他地方被改變，而程序仍然使用沒有更新的數(shù)據(jù)。

　　2、說明C++內(nèi)存分配方式有幾種?每種使用都有哪些注意項?

　　1.從靜態(tài)存儲區(qū)域分配。內(nèi)存在程序編譯的時候就已經(jīng)分配好，這塊內(nèi)存在程序的整個運行期間都存在。例如全局變量，static變量。

　　2.在棧上創(chuàng)建。在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放。棧內(nèi)存分配運算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限。

　　3.從堆上分配，亦稱動態(tài)內(nèi)存分配。程序在運行的時候用malloc或new申請任意多少的內(nèi)存，程序員自己負(fù)責(zé)在何時用free或delete釋放內(nèi)存。動態(tài)內(nèi)存的生存期由我們決定，使用非常靈活，但問題也最多。

　　----------------------------------------

　　一般所說的堆棧(stack)往往是指棧，先進后出，它是一塊內(nèi)存區(qū)。用以存放程序的局部變量，臨時變量，函數(shù)的參數(shù)，返回地址等。在這塊區(qū)域中的變量的分配和釋放由系統(tǒng)自動進行。不需要用戶的參與。

　　而在堆(heap,先進先出)上的空間則是由用戶進行分配，并由用戶負(fù)責(zé)釋放

　　編程題：

　　1、給定一個升序排列的自然數(shù)數(shù)組，數(shù)組中包含重復(fù)數(shù)字，例如：[1,2,2,3,4,4,4,5,6,7,7]。問題：給定任意自然數(shù)，對數(shù)組進行二分查找，返回數(shù)組正確的位置，給出函數(shù)實現(xiàn)。注：連續(xù)相同的數(shù)字，返回第一個匹配位置還是最后一個匹配位置，由函數(shù)傳入?yún)��?shù)決定。

　　分析：既然是二分查找的變形，那么先寫個正確的二分查找吧：

　　#include

　　using namespace std;

　　int bin_search(int arr[],int n,int value)

　　{

　　if(arr==NULL||n<1)

　　return -1;

　　int left=0;

　　int right=n-1;

　　while(left<=right)

　　{

　　int mid=left+((right-left)>>1);

　　if(arr[mid]>value)

　　{

　　right=mid-1;

　　}

　　else if(arr[mid]

　　{

　　left=mid+1;

　　}

　　else

　　return mid;

　　}

　　return -1;

　　}

　　int main()

　　{

　　int arr[]={1,2,3,4,5,6,7,8,9};

　　int b=bin_search(arr,9,9);

　　cout<

　　system("pause");

　　return 0;

　　}

　　代碼如下：

　　/*

　　* 測試樣例

　　* 11

　　* 1 2 2 3 4 4 4 5 7 7 7

　　*/

　　#include

　　#include

　　#define MAX 20

　　int n;

　　int sets[MAX];

　　enum MATCH_POS{PRE,POST};//分別為第一個匹配和最后一個匹配

　　int bi_search(int *arr,int b,int e,int v,MATCH_POS pos)

　　{

　　int left,right,mid;

　　left=b-1;right=e;

　　while(left+1 < right)

　　{

　　mid=left+(right - left)/2;

　　if(v < arr[mid])

　　{

　　right = mid;

　　}else if(v > arr[mid])

　　{

　　left=mid;

　　}else

　　{

　　if(pos==PRE)

　　{//如尋找第一個匹配，right向左移動

　　right = mid;

　　}

　　else

　　left = mid;

　　}

　　}

　　if(arr[right] == v)

　　return right;

　　else if(arr[left] == v)

　　return left;

　　return -1;

　　}

　　int main(){

　　int i;

　　int sets[]={1, 2, 2, 3, 4, 4, 4, 5, 7, 7, 7};

　　int t=bi_search(sets,0,10,7,PRE);

　　printf("%d\n",t);

　　system("pause");

　　return 0;

　　}

　　2、一個無序自然數(shù)數(shù)組，比如[100,2,1,3]求在0(n)時間復(fù)雜度內(nèi)求出最大的連續(xù)自然數(shù)個數(shù)：輸出應(yīng)該是3，要求算法的時間復(fù)雜度為O(n)

　　方法一：排序

　　可以采用一些排序方法比如基數(shù)排序、桶排序、記數(shù)排序等先進行排序。然后遍歷一遍所有元素即可。當(dāng)前這些排序有一些限制條件的。

　　方法二：維持一個hash表

　　維持一個hash表，大小為最大整數(shù)。遍歷一次數(shù)組，用hash表記錄出現(xiàn)在原始數(shù)組中的數(shù)。

　　然后設(shè)置四個個指示變量start，end，length，bestLength = 0。初始，start = end = 數(shù)組中第一個數(shù)，length = 1。然后不斷執(zhí)行下列操作：

　　end = end + 1.然后ziahash表中尋找end，如果能夠找到，說明end存在原始數(shù)組中。一直到找不到end位置。

　　然后設(shè)置length = end - start。如果length大于bestLength，則更新：bestLength = length。

　　然后將start和end都設(shè)置為剛才為查找到的那個數(shù)，length = 1，接著重復(fù)上面的操作，最終的bestLength 便是最大的連續(xù)自然數(shù)個數(shù)。

　　由于hash的查找等操作都能在O(1)時間復(fù)雜度內(nèi)完成，因此hash方法能夠滿足O(n)時間復(fù)雜度。

　　方法三：位圖

　　用位圖。類似方法二。

　　位圖大小和最大的整數(shù)有關(guān)。位圖中每一位為0或者1。位圖某個位置index上為1表示index出現(xiàn)在原始數(shù)組中，反之不存在。遍歷一遍原始數(shù)組建立位圖之后，采用類似方法二中遍歷hash表的方法遍歷位圖，找出最大的連續(xù)自然數(shù)個數(shù)。

　　位圖的方法存在一個問題就是：可能最大的數(shù)很大，但是數(shù)的數(shù)目有很小，這時候要申請的位圖的空間依然是很大，時候復(fù)雜度不是O(n)。

　　方法四：維持兩個hash表

　　維持兩個hash表tables：

　　Start表，其中的條目都是如下格式(start-point,length)，包含的某個連續(xù)序列起始數(shù)以及序列長度。

　　End表，其中的條目都是如下格式(end-point,length)，包含的某個連續(xù)序列結(jié)束數(shù)以及序列長度。

　　掃描原始數(shù)組，做如下操作：

　　對于當(dāng)前值value，

　　判斷value + 1是否存在于start表中。

　　如果存在，刪除相應(yīng)的條目，創(chuàng)建一個新條目(value,length + 1)，同時更新end表相應(yīng)條目，結(jié)束數(shù)不變，該對應(yīng)長度加一。

　　判斷value - 1是否存在于end表中。

　　如果存在，刪除相應(yīng)的條目，創(chuàng)建一個新條目(value,length + 1)，同時更新start表相應(yīng)條目，開始數(shù)不表，該對應(yīng)長度加一。

　　如果在兩個表中都存在，則合并兩個已經(jīng)存在的連續(xù)序列為一個。將四個條目刪除，新建兩個條目，每兩個條目代表一個連續(xù)序列。

　　如果都不存在，則只需要在兩個表中創(chuàng)建一個新的長度為1的條目。

　　一直這樣等到數(shù)組中所有元素處理完畢，然后掃描start表尋找length值最大的那個即可。

　　這里要達到O(n)時間復(fù)雜度，start表和end表都用hash表實現(xiàn)，而且必須滿足相關(guān)操作查找/添加/刪除能夠在O(1)時間復(fù)雜度內(nèi)完成。

　　實例分析：

　　int[] input = {10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101};

　　初始化狀態(tài)：

　　Start table：{}

　　End table：{}

　　開始遍歷數(shù)組：

　　10：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)}

　　End table：{(10,1)}

　　21：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,1)}

　　End table：{(10,1)，(21,1)}

　　45：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,1)，(45,1)}

　　End table：{(10,1)，(21,1)，(45,1)}

　　22：22-1=21存在于end表中需要進行更新。

　　Start table：{(10,1)，(21,2)，(45,1)}

　　End table：{(10,1)，(22,2)，(45,1)}

　　7：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(7,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(7,1)}

　　2：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)}

　　67：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)}

　　19：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}

　　13：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}

　　45：兩個數(shù)組中都不存在，添加條目。

　　Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}

　　End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}

　　12：12+1=13存在start表中，更新。

　　Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(12,2)}

　　End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,2)}

　　11：11+1=12都存在，合并。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}

　　18：18+1=19存在start表中，更新。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)}

　　16：都不存在，添加條目。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)，(16,1)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)，(16,1)}

　　17：都存在，合并。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)}

　　100：都不存在，添加條目。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)}

　　201：都不存在，添加條目。

　　Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)，(201,1)}

　　End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)，(201,1)}

　　20：都存在，合并。

　　Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}

　　End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}

　　101：都存在，合并。

　　Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(101,1)}

　　End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(201,1)}

　　最后搜索start表，找到length值最大的，為7.連續(xù)自然數(shù)序列是：(16,17,18,19,20,21,22).

　　結(jié)束。

　　#include

　　int array[]={100, 2, 1, 3, 8, 5, 4};

　　int size = sizeof(array) / sizeof(int);

　　//構(gòu)造兩個簡陋的hash表，一個是用來查詢數(shù)字是否存在，一個用于標(biāo)記數(shù)字是否使用過

　　char hash_exist[1024];

　　char hash_used[1024];

　　int main()

　　{

　　int i, j, n, max = 0, maxnum = array[0], minnum = array[0];

　　for(i = 0; i < size; i++)

　　{

　　//標(biāo)記數(shù)字存在

　　hash_exist[array[i]] = 1;

　　//找出數(shù)組最大元素

　　if(maxnum < array[i]) maxnum = array[i];

　　//找出數(shù)組最小元素

　　if(minnum > array[i]) minnum = array[i];

　　}

　　for(i = 0; i < size; i++)

　　{

　　j = array[i];

　　//如果已經(jīng)統(tǒng)計過，就跳過

　　if(hash_used[j])

　　continue;

　　//標(biāo)記本身

　　n = 1;

　　hash_used[j] = 1;

　　//比array[i]大的連續(xù)元素統(tǒng)計

　　while(++j <= maxnum)

　　{

　　if(hash_exist[j])

　　{

　　n++;

　　hash_used[j] = 1;

　　}

　　else

　　break;

　　}

　　//比array[i]小的連續(xù)元素統(tǒng)計

　　j = array[i];

　　while(--j >= minnum)

　　{

　　if(hash_exist[j])

　　{

　　n++;

　　hash_used[j] = 1;

　　}

　　else

　　break;

　　}

　　//更新最大連續(xù)數(shù)字

　　if(n > max) max = n;

　　}

　　printf("%d\n", max);

　　return 0;

　　}