試題一：閱讀下列說明和c代碼，回答問題 1 至問題 3，將解答寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
假幣問題：有n枚硬幣，其中有一枚是假幣，己知假幣的重量較輕?，F(xiàn)只有一個天平，要求用盡量少的比較次數(shù)找出這枚假幣。
【分析問題】
將n枚硬幣分成相等的兩部分:
(1)當(dāng)n為偶數(shù)時，將前后兩部分，即 1...n/2和n/2+1...0，放在天平的兩端，較輕的一端里有假幣，繼續(xù)在較輕的這部分硬幣中用同樣的方法找出假幣:
(2)當(dāng)n為奇數(shù)時，將前后兩部分，即1..(n -1)/2和(n+1)/2+1...0，放在天平的兩端，較輕的一端里有假幣，繼續(xù)在較輕的這部分硬幣中用同樣的方法找出假幣；若兩端重量相等，則中間的硬幣，即第 (n+1)/2枚硬幣是假幣。
【c代碼】
下面是算法的c語言實(shí)現(xiàn)，其中:
coins[]： 硬幣數(shù)組
first，last：當(dāng)前考慮的硬幣數(shù)組中的第一個和最后一個下標(biāo)

#include

int getcounterfeitcoin(int coins[]， int first，int last)
{
int firstsum = 0，lastsum = 0;
int ì;
if(first==last-1){       /*只剩兩枚硬幣*/
if(coins[first]< coins[last])
return first;
return last;
}

if((last - first + 1) % 2 ==0){      /*偶數(shù)枚硬幣*/
for(i = first;i<( 1 );i++){
firstsum+= coins[i];
}
for(i=first + (last-first) / 2 + 1;i< last +1;i++){
lastsum += coins[i];
}
if(   2   ){
return getcounterfeitcoin(coins,first,first+(last-first)/2;)
}else{
return getcounterfeitcoin(coins,first+(last-first)/2+1,last;)
}
}
else{      /*奇數(shù)枚硬幣*/
for(i=first;i<="" p="">
firstsum+=coins[i];
}
for(i=first+(last-first)/2+1;i
lastsum+=coins[i];
}
if(firstsum
return getcounterfeitcoin(coins,first,first+(last-first)/2-1);
}else if(firstsum>lastsum){
return getcounterfeitcoin(coins,first+(last-first)/2-1,last);
}else{
return(  3   )
}
}
}
【問題一】
根據(jù)題干說明，填充c代碼中的空（1）-（3）
【問題二】
根據(jù)題干說明和c代碼，算法采用了（   ）設(shè)計策略。
函數(shù)getcounterfeitcoin的時間復(fù)雜度為（   ）（用o表示）。
【問題三】
若輸入的硬幣數(shù)為30，則最少的比較次數(shù)為（  ），最多的比較次數(shù)為（   ）。

查看答案

試題二：閱讀下列說明和圖，回答問題1至問題4，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
某巴士維修連鎖公司欲開發(fā)巴士維修系統(tǒng)，以維護(hù)與維修相關(guān)的信息。該系統(tǒng)的主要功能如下：
1)記錄巴士id和維修問題。巴士到車庫進(jìn)行維修，系統(tǒng)將巴士基本信息和id記錄在巴士列表文件中，將待維修機(jī)械問題記錄在維修記錄文件中，并生成維修訂單。
2)確定所需部件。根據(jù)維修訂單確定維修所需部件，并在部件清單中進(jìn)行標(biāo)記。
3)完成維修。機(jī)械師根據(jù)維修記錄文件中的待維修機(jī)械問題，完成對巴士的維修，登記維修情況：將機(jī)械問題維修情況記錄在維修記錄文件中，將所用部件記錄在部件清單中，并將所用部件清單發(fā)送給庫存管理系統(tǒng)以對部件使用情況進(jìn)行監(jiān)控。巴土司機(jī)可查看已維修機(jī)械問題。
4)記錄維修工時。將機(jī)械師提供的維修工時記錄在人事檔案中，將維修總結(jié)發(fā)送給主管進(jìn)行績效考核。
5)計算維修總成本。計算部件清單中實(shí)際所用部件、人事檔案中所用維修工時的總成本；將維修工時和所用部件成本詳細(xì)信息給會計進(jìn)行計費(fèi)。
現(xiàn)采用結(jié)構(gòu)化方法對巴士維修系統(tǒng)進(jìn)行分折與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。

【問題1】（5分）

使用說明中的詞語，給出圖1一1中的實(shí)體e1?e5的名稱

【問題2】（4分）

使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲di?d4的名稱。

【問題3】（3分）

說明圖1-2中所存在的問題。

【問題4]（3分）

根據(jù)說明和圖中術(shù)語，采用補(bǔ)充數(shù)據(jù)流的方式，改正圖1—2中的問題。要求給出所補(bǔ)充數(shù)據(jù)流的名稱、起點(diǎn)和終點(diǎn)。

查看答案