2012年下半年程序員考試下午真題：

>>>點擊進入軟考初級程序員歷年真題下載

● 閱讀以下說明和流程圖，填補流程圖中的空缺(1)~(5)，將解答填入答題紙的對應欄內(nèi)。
【說明】
本流程圖用于計算菲波那契數(shù)列 {a₁=1，a₂=1，…，a_n=a_n-1+n_n-2|n=3，4，…}的前n 項 ( n≥2) 之和 S。例如，菲波那契數(shù)列前6 項之和為 20。計算過程中，當前項之前的兩項分別動態(tài)地保存在變量 A 和 B 中。
【流程圖】

● 閱讀以下說明和C函數(shù)，填充函數(shù)中的空缺，將解答填入答題紙的對應欄內(nèi)。
【說明】
如果矩陣A中的元素A[i,j]滿足條件: A[i,j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。
一個矩陣可能存在多個馬鞍點，也可能不存在馬鞍點。下面的函數(shù)求解并輸出一個矩陣中的所有馬鞍點，最后返回該矩陣中馬鞍點的個數(shù)。

● 閱讀以下說明和C函數(shù)，填充函數(shù)中的空缺，將解答填入答題紙的對應欄內(nèi)。
【說明】
函數(shù)Insert_key(*root ，key)的功能是將鍵值 key 插入到*boot指向根結(jié)點的二叉查找樹中(二叉查找樹為空時 *root 為空指針)。若給定的二叉查找樹中已經(jīng)包含鍵值為 key 的結(jié)點，則不進行插入操作井返回 0；否則申請新結(jié)點、存入 key 的值并將新結(jié)點加入樹中，返回1。
提示:

·二叉查找樹又稱為二叉排序樹，它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：

·若它的左子樹非空，則其左子樹上所有結(jié)點的鍵值均小于根結(jié)點的鍵值；

·若它的右子樹非空，則其右子樹上所有結(jié)點的鍵值均大于根結(jié)點的鍵值；

·左、右子樹本身就是二叉查找樹。

設二叉查找樹采用二叉鏈表存儲結(jié)構(gòu)，鏈表結(jié)點類型定義如下:

● 閱讀以下說明和 C 函數(shù)，填充函數(shù)中的空缺，將解答填入答題紙的對應欄內(nèi)。
【說明】
己知兩個整數(shù)數(shù)組 A 和 B 中分別存放了長度為 m 和 n 的兩個非遞減有序序列，函數(shù) Adjustment(A,B，m，n)的功能是合并兩個非遞減序列，并將序列的前m個整數(shù)存入A中，其余元素依序存入 B 中。
例如：

合并過程如下:從數(shù)組 A 的第一個元素開始處理。用數(shù)組 B 的最小元素 B[O]與數(shù)組 A 的當前元素比較，若 A 的元素較小，則繼續(xù)考查 A 的下一個元素；否則，先將A的最大元素暫存入temp ，然后移動A中的元素挪出空閑單元并將 B[O]插入數(shù)組 A ，最后將暫存在temp 中的數(shù)據(jù)插入數(shù)組B的適當位置(保持 B的有序性)。如此重復，直到A中所有元素都不大于B中所有元素為止。

● 閱讀以下說明和c++代碼，填充代碼中的空缺，將解答填入答題紙的對應欄內(nèi)。
【說明】
下面的程序用來計算并尋找平面坐標系中給定點中最近的點對(若存在多對，則輸出其中的一對即可)。程序運行時，先輸入點的個數(shù)和一組互異的點的坐標，通過計算每對點之間的距離，從而確定出距離最近的點對。例如，在圖 5-1 所示的8個點中，點(1，1) 與(2，0.5)是間距最近的點對。

● 閱讀以下說明和 Java 程序，填充程序中的空缺，將解答填入答題紙的對應欄內(nèi)。
【說明】
下面的程序用來計算并尋找平面坐標系中給定點中最近的點對(若存在多對，則輸出其中的一對即可)。程序運行時，先輸入點的個數(shù)和一組互異的點的坐標，通過計算每對點之間的距離，從而確定出距離最近的點對。例如，在圖6-1所示的8個點中，點（1,1）與（2,0.5）是間距最近的點對。