點(diǎn)擊查看：2018年軟件水平考試《程序員》練習(xí)題及答案匯總

　　-求1+2+...+n

　　題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語(yǔ)句(A?B:C)。

　　分析：這道題沒(méi)有多少實(shí)際意義，因?yàn)樵谲浖�開發(fā)中不會(huì)有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對(duì)編程相關(guān)技術(shù)理解的深刻程度。

　　通常求1+2+…+n除了用公式n(n+1)/2之外，無(wú)外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if語(yǔ)句或者條件判斷語(yǔ)句來(lái)判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語(yǔ)句了。

　　我們?nèi)匀粐�繞循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達(dá)到這個(gè)效果。比如定義一個(gè)類，我們new一含有n個(gè)這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會(huì)被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個(gè)思路：

　　class Temp

　　{

　　public:

　　Temp() { ++ N; Sum += N; }

　　static void Reset() { N = 0; Sum = 0; }

　　static int GetSum() { return Sum; }

　　private:

　　static int N;

　　static int Sum;

　　};

　　int Temp::N = 0;

　　int Temp::Sum = 0;

　　int solution1_Sum(int n)

　　{

　　Temp::Reset();

　　Temp *a = new Temp[n];

　　delete []a;

　　a = 0;

　　return Temp::GetSum();

　　}

　　-在排序數(shù)組中查找和為給定值的兩個(gè)數(shù)字

　　題目：輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。

　　例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。

　　分析：如果我們不考慮時(shí)間復(fù)雜度，最簡(jiǎn)單想法的莫過(guò)去先在數(shù)組中固定一個(gè)數(shù)字，再依次判斷數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字。可惜這種思路需要的時(shí)間復(fù)雜度是O(n2)。

　　我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個(gè)數(shù)字;如果小于輸入的數(shù)字呢?我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。由于數(shù)組已經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后面移動(dòng)一個(gè)數(shù)字?因?yàn)榕旁诤竺娴臄?shù)字要大一些，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了;同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候，我們把較大的數(shù)字往前移動(dòng)，因?yàn)榕旁跀?shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。

　　我們把前面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng);當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng);當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。

　　問(wèn)題是這樣的思路是不是正確的呢?這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一下。

　　參考代碼：

　　///////////////////////////////////////////////////////////////////////

　　// Find two numbers with a sum in a sorted array

　　// Output: ture is found such two numbers, otherwise false

　　///////////////////////////////////////////////////////////////////////

　　bool FindTwoNumbersWithSum

　　(

　　int data[], // a sorted array

　　unsigned int length, // the length of the sorted array

　　int sum, // the sum

　　int& num1, // the first number, output

　　int& num2 // the second number, output

　　)

　　{

　　bool found = false;

　　if(length < 1)

　　return found;

　　int ahead = length - 1;

　　int behind = 0;

　　while(ahead > behind)

　　{

　　long long curSum = data[ahead] + data[behind];

　　// if the sum of two numbers is equal to the input

　　// we have found them

　　if(curSum == sum)

　　{

　　num1 = data[behind];

　　num2 = data[ahead];

　　found = true;

　　break;

　　}

　　// if the sum of two numbers is greater than the input

　　// decrease the greater number

　　else if(curSum > sum)

　　ahead --;

　　// if the sum of two numbers is less than the input

　　// increase the less number

　　else

　　behind ++;

　　}

　　return found;

　　}

　　-查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

　　題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下：

　　struct ListNode

　　{

　　int m_nKey;

　　ListNode* m_pNext;

　　};

　　分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再?gòu)奈捕嘶厮輐步�？墒禽斎氲氖菃蜗蜴湵�，只有從前往后的指針而沒(méi)有從后往前的指針。因此我們需要打開我們的思路。

　　既然不能從尾結(jié)點(diǎn)開始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來(lái)。假設(shè)整個(gè)鏈表有n個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)(從0開始計(jì)數(shù))。如果我們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù)n，那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。如何得到結(jié)點(diǎn)數(shù)n?這個(gè)不難，只需要從頭開始遍歷鏈表，每經(jīng)過(guò)一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。

　　這種思路的時(shí)間復(fù)雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點(diǎn)個(gè)數(shù)n，第二次得到從頭結(jié)點(diǎn)開始的第n­-k-1個(gè)結(jié)點(diǎn)即倒數(shù)第k個(gè)結(jié)點(diǎn)。

　　如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點(diǎn)個(gè)數(shù)很多，有可能不能一次性把整個(gè)鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個(gè)結(jié)點(diǎn)需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時(shí)間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1?如果可以，將能有效地提高代碼執(zhí)行的時(shí)間效率。

　　如果我們?cè)诒闅v時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個(gè)指針保持不動(dòng);在第k-1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。由于兩個(gè)指針的距離保持在k-1，當(dāng)?shù)谝粋�(gè)(走在前面的)指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針(走在后面的)指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。

　　這種思路只需要遍歷鏈表一次。對(duì)于很長(zhǎng)的鏈表，只需要把每個(gè)結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時(shí)間效率前面的方法要高。

　　思路一的參考代碼：

　　///////////////////////////////////////////////////////////////////////

　　// Find the kth node from the tail of a list

　　// Input: pListHead - the head of list

　　// k - the distance to the tail

　　// Output: the kth node from the tail of a list

　　///////////////////////////////////////////////////////////////////////

　　ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)

　　{

　　if(pListHead == NULL)

　　return NULL;

　　// count the nodes number in the list

　　ListNode *pCur = pListHead;

　　unsigned int nNum = 0;

　　while(pCur->m_pNext != NULL)

　　{

　　pCur = pCur->m_pNext;

　　nNum ++;

　　}

　　// if the number of nodes in the list is less than k

　　// do nothing

　　if(nNum < k)

　　return NULL;

　　// the kth node from the tail of a list

　　// is the (n - k)th node from the head

　　pCur = pListHead;

　　for(unsigned int i = 0; i < nNum - k; ++ i)

　　pCur = pCur->m_pNext;

　　return pCur;

　　}

　　相關(guān)推薦：

　　各地2018年計(jì)算機(jī)軟件水平考試報(bào)名時(shí)間匯總

　　各地2018年軟件水平考試準(zhǔn)考證打印/領(lǐng)取時(shí)間匯總

　　各地2018年計(jì)算機(jī)軟件水平考試費(fèi)用匯總

　　2018年計(jì)算機(jī)軟件水平考試時(shí)間及具體安排(全年)

　　考試吧特別策劃：2018年計(jì)算機(jī)軟考報(bào)考指南專題

　　計(jì)算機(jī)軟件水平考試各科目精選試題匯總

　　2018年計(jì)算機(jī)軟件水平考試各科目復(fù)習(xí)知識(shí)點(diǎn)匯總