平成18年  春  問10(本サイトに解説なし)

さだおさん  
(No.1)
タイトルの問題について質問です。
解説が載っていなかったのですが、自分なりに考えてみたので
この考え方であっているのかを伺いたいです。

・まず内部データ構造の要素①によって、配列なので(ウ)の木構造は×
(エ)の優先度キューは配列より木構造で使うのが一般的だが、
配列もなくはないのでとりあえず△
・内部データ構造の要素②によって、配列の添え字を格納するための変数が
2つ用意されているため、LIFOのスタックは×
また、優先度キューも、優先度順に取り出すキューのため変数は一つでいい(?)ので×

上記の考察から消去法で(ア)が答えになりました。
優先度キューははじめてみた用語なので調べてみましたが、
この問題に関してはこのような解釈でよろしいでしょうか?
2019.07.19 11:49
guestさん 
AP シルバーマイスター
(No.2)
***図1***********************
      X→→→→Y
   0 1 2 3 ……… 9
A[工工工工工工工工工]
※n=10、XとYとi=0~9
******************************
配列Aにおいて、キューの先頭(卒業間近)の要素の添え字がX、キューの末尾(最近入学)の要素の添え字がYということなのだと思います。キューからの卒業生がでるとXが+1、キューに入学生がくるとYが+1、Yが9のときにまた入学生がくるとカンストではなく(i+1)%n=0が末尾になるという具合(つまりキューは、←要素8←要素9←要素0←要素1…のようになっている)。
***図2***********************
  →→Y      X→→→
   0 1 2 3 ……… 9
A[工工工工工工工工工]
※n=10、XとYとi=0~9
******************************
Yがどんどん+1されXに追いつくというケースについては、条件dでそのようなことは発生しないものとするとしています。

次にさだおさんの考えがあっているかについてですが、、、
【木構造は配列では実現できない】
私も詳しくありませんがW〇kipedia(リンクは載せられず恐縮です)によるとそうでもないようです。
【変数が2つだからスタックは×】
あっていると思います。先頭を表すXは不要ですね。
【優先度キューも、優先度順に取り出すキューのため変数は一つでいい】
優先度キューについて私も初めて知りました。でも変数1つは難しい気がします。。。
[実装法1]キュー内を優先度順にソートしてあとは普通のキューと同様の使い方をする
条件bcで無理そう。
[実装法2]優先度を無視していったん格納しておいて取り出すときに優先度を気にする方式
キュー内の各要素の優先度を格納する配列Bが要りそう。

※あくまで個人的見解。大嘘ついていたらすみません。
2019.07.19 16:07
guestさん 
AP シルバーマイスター
(No.3)
No.2への補足
図1,2での矢印は、実際に配列に値が格納されていく方向を示しています。
図1,2の間にある文章「←要素8←要素9←要素0←要素1…」での矢印は、一般に「キュー」といわれて頭に想像するイメージ図で要素がキューから押し出されていく方向を示しています。

***イメージ図********************
OUT  ------------  IN
←  [要素][要素][要素]      ←[要素]
      ------------
*******************************
2019.07.19 16:20
さだおさん  
(No.4)
>guestさん

レスありがとうございます!
参考にさせていただきます!
2019.07.21 21:33

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop