応用情報(旧ソフ開）の過去問の一部が理解できません

2009/04/11 15:56

このQ&Aのポイント

平成20年秋の午後I、問５の設問５の(1)について、二分木におけるheap_correctの計算量と再帰的呼び出しについての疑問があります。
平成20年秋の午後I、問５の設問５の(2)について、降順にソートされた配列におけるheap_makeの計算量についての疑問があります。
平成20年秋の午後I、問６の設問４の(２)について、座席指定券を購入後に始発駅で一度出場した場合のデータ出力条件について疑問があります。

応用情報(旧ソフ開）の過去問の一部が理解できません。

質問タイトルのままですが、次の所が理解できません。平成20年秋の午後I、問５の設問５の(1) →二分木の根に対してheap_correctを実行した場合の、heap_correctの　計算量。このとき、二分木の根の子ノードを根とする部分は、条件２を　満たしているものとする。　（ ※ なぜ、親＞＝子の条件を満たしており再帰的呼び出しがないのに　　計算量がlogNとなるのか、ルートで1回呼び出しただけで終了でないか）平成20年秋の午後I、問５の設問５の(2) →配列のAの要素が降順にソートされている場合のheap_make(A)の計算量　がNとなるのか、　（heap_makeからheap_correctを計算した場合に、降順に整列されている　　のに、なぜN回の計算量と考えられるのか、二分木のノードが15個だ　　とするならば、７から１まで見ていく＆　降順に整列されているた　　め７回の計算量、N/2で終わってしまいそうな気がします。）平成20年秋の午後I、問６の設問４ →座席指定券購入後に始発駅でいったん出場した場合のデータを出力しな　いようにするためには、図2の条件１～３のいずれか一つの条件を修正　すればよい。次の（１）、（２）に答えよ。　この（２）がわかりません。解答：入場時刻が、座席指定券を購入した列車の始発駅発車時刻よりも　　　小さい。となっておりますが、これでは＞座席指定券購入後に始発駅でいったん出場した場合のデータを出力しな　いようにするためにはの条件を満たさないような気がします。座席指定券を購入後にの始発駅でいったん出場した場合と、いざ列車に乗ろうと戻ってきて入場→目的駅で出場した場合の両方ともデータが出力されそうな気がします。僕的には： (1) 入場駅コードと出場駅コードが等しくない (2) 出場時刻が始発駅発時刻より大きいが正しいのではないかと感じてしまいます。理解できないものは以上です。過去問はこちらです↓（ＩＰＡ） http://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2008h20.html#20aki よろしくお願いします。