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

>>>點(diǎn)擊進(jìn)入軟考初級(jí)程序員歷年真題下載

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

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

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

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

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

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

·左、右子樹(shù)本身就是二叉查找樹(shù)。

設(shè)二叉查找樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，鏈表結(jié)點(diǎn)類(lèi)型定義如下:

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

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

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

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