基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成19年 秋期 基本情報技術者 午後 問08
問08   Java

次の Java プログラムの説明及びプログラムを読んで,設問1,2に答えよ。

( Java プログラムで使用する API の説明は,この冊子の末尾を参照してください。)

〔プログラムの説明〕

 クラス WeightedQueue は,次の規則に従う待ち行列を実現するプログラムである。

(1) 待ち行列に入る要素には,重みが付けられる。重みは正の整数とする。ただし, この待ち行列に null を挿入することはできない。

(2) 要素の挿入位置は,末尾の要素からの重みの合計が,挿入する要素の重み未満で, 最も先頭寄りとする。ただし,重みの合計が Long.MAX_VALUE を超えたときの動作は保証しない。 要素を挿入する例を図1に示す。

   図1 要素を挿入する例

(3) 要素を取り出すときは,その時点で先頭にある要素が取り出される。

〔待ち行列の使用例〕

 この待ち行列に,優先度の高いタスク(重みの値が大きい要素)を挿入すると, このタスクは先に挿入されていた幾つかの優先度の低いタスクよりも,先に取り出されるようになる。 この性質を利用して,この待ち行列と,優先度に応じたタスクのスケジューリングに使うことができる。

 テスト用クラスWeightedQueueTester の実行結果を図2に示す。

a      
b     
c     
d     

図2 実行結果
〔プログラム1〕

import java.util.LinkedList;

public class WeightedQueue<E> {
   private final LinkedList<QueueElement> queue =
      new LinkedList<QueueElemeent>();
   // 要素を待ち行列に挿入する。(element:要素, weight:重み)
   public void offer(E element, long weight) {

      if (element == null) {
         throw new NullPointerException();
      }

      int pos;
      long sum = 0;
      // 末尾の要素からの重みの合計が weight 以上になるか,先頭に達するまで
      // 前方に向かって走査する。待ち行列の先頭位置は0
      for (pos = queue.size(); pos > 0; pos--) {
         sum += queue.get(  ).weight;
         if (sum  weight) {
            break;
         }
      }
      queue.add(pos,  );
   }
   public E poll() {
      QueueElement e = queue.poll();
      if (e == null) {
         return null;
      } else {
         return e.element;
      }
   }

   // 要素と重みの組 
   private class QueueElement {
      private final E element; 
      private final long weight;

      private QueueElement(E element, long weight) {
         this.element = element; 
         this.weight = weight; 
      }
   }
}

〔プログラム2〕 

public class WeightedQueueTester { 
   public static void main(String[] args) {
      WeightedQueue<String> wq = new WeightedQueue<String>();
      String[] s = {"a","b","c","d"};
      long[] w = {3, 2, 4, 8};
      for (int i = 0; i < s.length; i++) {
         wq.offer(s[i], w[i]);
      }
      String data;
      while ((data = wq.poll()) != null) {
         System.out.println(data);
      }
   }
}
設問1 プログラム1中の に入れる正しい答えを,解答群の中から選べ。

a に関する解答群

ア pos     イ pos - 1      ウ pos + 1
エ sum     オ sum - 1      カ sum + 1

b に関する解答群

ア !=      イ <=      ウ ==      エ >=

c に関する解答群

ア new QueueElement(element, sum)
イ new QueueElement(element, weight)
ウ QueueElement(element, sum)
エ QueueElement(element, weight)
解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

基本情報技術者試験


設問2 クラス WeightedQueue のメソッド poll に関する記述として正しいものを, 解答群の中から選べ。

解答群

ア 待ち行列の先頭要素の取得及び削除をする。ただし,待ち行列に要素がないときは null を返す。
イ 待ち行列の先頭要素の取得及び削除をする。ただし,待ち行列に要素がないときは例外を投げる。
ウ 待ち行列の先頭要素を取得する。要素の削除はしない。ただし, 待ち行列に要素がないときは null を返す。
エ 待ち行列の先頭要素を取得する。要素の削除はしない。ただし,待ち行列に要素がないときは例外を投げる。
解答 ←クリックすると正解が表示されます

[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]