高級中學信息技術(shù)算法與程序設計問答題每日一練(2019.05.13)

來源：考試資料網(wǎng)

1.問答題簡單描述分治法的基本思想。

2.問答題流水作業(yè)調(diào)度中，已知有n個作業(yè)，機器M₁和M₂上加工作業(yè)i所需的時間分別為a_i和b_i，請寫出流水作業(yè)調(diào)度問題的johnson法則中對a_i和b_i的排序算法。（函數(shù)名可寫為sort（s，n））

3.問答題 有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為多少？

{1，4，8，11}

4.問答題舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明0/1背包問題與背包問題的不同）。

5.問答題輸入某年，某月，某日，判斷這一天是這一年的第幾天。