點擊查看：2018年軟件水平考試《程序員》練習題及答案匯總

　　-求1+2+...+n

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

　　分析：這道題沒有多少實際意義，因為在軟件開發中不會有這么變態的限制。但這道題卻能有效地考查發散思維能力，而發散思維能力能反映出對編程相關技術理解的深刻程度。

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

　　我們仍然圍繞循環做文章。循環只是讓相同的代碼執行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數組，那么該類的構造函數將確定會被調用n次。我們可以將需要執行的代碼放到構造函數里。如下代碼正是基于這個思路：

　　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();

　　}

　　-在排序數組中查找和為給定值的兩個數字

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

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

　　分析：如果我們不考慮時間復雜度，最簡單想法的莫過去先在數組中固定一個數字，再依次判斷數組中剩下的n-1個數字與它的和是不是等于輸入的數字�？上н@種思路需要的時間復雜度是O(n2)。

　　我們假設現在隨便在數組中找到兩個數。如果它們的和等于輸入的數字，那太好了，我們找到了要找的兩個數字;如果小于輸入的數字呢?我們希望兩個數字的和再大一點。由于數組已經排好序了，我們是不是可以把較小的數字的往后面移動一個數字?因為排在后面的數字要大一些，那么兩個數字的和也要大一些，就有可能等于輸入的數字了;同樣，當兩個數字的和大于輸入的數字的時候，我們把較大的數字往前移動，因為排在數組前面的數字要小一些，它們的和就有可能等于輸入的數字了。

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

　　問題是這樣的思路是不是正確的呢?這需要嚴格的數學證明。感興趣的讀者可以自行證明一下。

　　參考代碼：

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

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

　　}

　　-查找鏈表中倒數第k個結點

　　題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。鏈表的倒數第0個結點為鏈表的尾指針。鏈表結點定義如下：

　　struct ListNode

　　{

　　int m_nKey;

　　ListNode* m_pNext;

　　};

　　分析：為了得到倒數第k個結點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。

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

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

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

　　如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個指針保持不動;在第k-1步開始，第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1，當第一個(走在前面的)指針到達鏈表的尾結點時，第二個指針(走在后面的)指針正好是倒數第k個結點。

　　這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個結點從硬盤導入到內存一次。因此這一方法的時間效率前面的方法要高。

　　思路一的參考代碼：

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

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

　　}

　　相關推薦：

　　各地2018年計算機軟件水平考試報名時間匯總

　　各地2018年軟件水平考試準考證打印/領取時間匯總

　　各地2018年計算機軟件水平考試費用匯總

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

　　考試吧特別策劃：2018年計算機軟考報考指南專題

　　計算機軟件水平考試各科目精選試題匯總

　　2018年計算機軟件水平考試各科目復習知識點匯總