選擇題：

　　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

　　問(wèn)答題：

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

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

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

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

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

　　const 有什么用途?

　　1、可以定義 const 常量

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

　　volatile問(wèn)題：

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

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

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

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

　　.一個(gè)中斷服務(wù)子程序中會(huì)訪問(wèn)到的非自動(dòng)變量(Non-automatic variables);

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

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

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

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

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

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

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

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

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

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

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

　　編程題：

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

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

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

　　}

　　代碼如下：

　　/*

　　* 測(cè)試樣例

　　* 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};//分別為第一個(gè)匹配和最后一個(gè)匹配

　　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)

　　{//如尋找第一個(gè)匹配，right向左移動(dòng)

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

　　方法一：排序

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

　　方法二：維持一個(gè)hash表

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

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

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

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

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

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

　　方法三：位圖

　　用位圖。類似方法二。

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

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

　　方法四：維持兩個(gè)hash表

　　維持兩個(gè)hash表tables：

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

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

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

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

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

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

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

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

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

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

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

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

　　實(shí)例分析：

　　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：{}

　　開(kāi)始遍歷數(shù)組：

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

　　Start table：{(10,1)}

　　End table：{(10,1)}

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

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

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

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

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

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

　　22：22-1=21存在于end表中需要進(jìn)行更新。

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

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

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

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

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

　　2：兩個(gè)數(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：兩個(gè)數(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：兩個(gè)數(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：兩個(gè)數(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：兩個(gè)數(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)造兩個(gè)簡(jiǎn)陋的hash表，一個(gè)是用來(lái)查詢數(shù)字是否存在，一個(gè)用于標(biāo)記數(shù)字是否使用過(guò)

　　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)計(jì)過(guò)，就跳過(guò)

　　if(hash_used[j])

　　continue;

　　//標(biāo)記本身

　　n = 1;

　　hash_used[j] = 1;

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

　　while(++j <= maxnum)

　　{

　　if(hash_exist[j])

　　{

　　n++;

　　hash_used[j] = 1;

　　}

　　else

　　break;

　　}

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

　　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;

　　}