ITパスポート

【ITパスポート】データ構造(配列/リスト/キュー/スタック/木構造)

  1. HOME >
  2. 情報処理 >
  3. ITパスポート >

【ITパスポート】データ構造(配列/リスト/キュー/スタック/木構造)

今回のテーマは「データ構造」についてです。

データ構造?

本記事で学べること

  • データ構造(配列/リスト/キュー/スタック/木構造)について学ぶ
  • ITパスポート過去問の解き方を学ぶ

スポンサーリンク

データ構造

データ構造とは、データの集まりをコンピュータが扱いやすように、特定の形式で整理して格納する方法のことです。

複数のデータを整理して格納する入れ物のようなものです。

データ構造には、主に次のようなものがあります。

  • 配列
  • リスト
  • キュー
  • スタック
  • 木構造

配列

配列は、複数のデータ同じのデータを連続的に並べたデータ構造です。

次の図は、配列のイメージ例です。

配列のイメージ例

配列の各要素には、先頭から0、1、2、3、・・・と要素番号が付けられており、配列の変数名[要素番号]で、配列に格納されている要素を取り出せます。

例えば、上の例では a[2]で、「データ3」を取り出せます。

リスト

リストは、データ部とポインタ部で構成され、ポインタをたどることで、データを取り出せるデータ構造です。

次の図は、リストのイメージ例です。

リストのイメージ例

リスト構造のデータには「ポインタ」が付与されており、この「ポインタ」をたどることで、リスト内の各データにアクセスできます。

リストは、ポインタを書き換えるだけで、データをつなぎ替えることができるので、データの追加・挿入・削除が容易です。

キュー

キューは、データを順番に格納し、先に格納したデータから順に取り出す、先入れ先出し(FIFO:First-In First-Out)方式のデータ構造です。

次の図は、キューのイメージ例です。

キューとは

キューにデータを追加する操作を「enqueue」(エンキュー)、キューからデータを取り出す操作を「dequeue」(デキュー)といいます。

キューにデータを追加するときは末尾に追加し、キューからデータを取り出すときは先頭のデータから順番に取り出します。

お店に並ぶ行列と同じイメージです。(あとから来た人は行列の末尾に並び、行列の先頭から順番にお店に入る)

スタック

スタックは、データを順番に格納し、最後に格納したデータから順に取り出す、後入れ先出し(LIFO:Last-In First-Out)方式のデータ構造です。

スタック

スタックにデータを追加する操作を「PUSH」(プッシュ)、スタックからデータを取り出す操作を「POP」(ポップ)といいます。

スタックにデータを追加するときは順番に格納し、スタックからデータを取り出すときは、最後に格納したデータから順番に取り出します。

最後に乗った人から降りるエレベーターと同じイメージです。

木構造

木構造(読み:きこうぞう)は、木のような階層構造でデータを管理するデータ構造です。

次の図は、木構造のイメージ例です。

木構造

木構造の要素部分を節(ノード)といい、親のない最上位の節を根(ルート)、子のない節を葉(リーフ)、そして 節と節を繋ぐ線のことを枝(ブランチ)といいます。

ハードディスクのファイルシステム(フォルダの下にフォルダやファイルがぶら下がっている)などは、木構造を用いて管理しています。

スポンサーリンク

練習問題

ITパスポート平成30年春期 問96

問題

先入れ先出し(First-In First-Out,FIFO)処理を行うのに適したキューと呼ばれるデータ構造に対して"8","1","6","3"の順に値を格納してから,取出しを続けて2回行った。2回目の取出しで得られる値はどれか。

ア:1  イ:3  ウ:6  エ:8

ITパスポート平成30年春期 問96

キューは、データを順番に格納し、先に格納したデータから順に取り出す、先入れ先出し(FIFO:First-In First-Out)方式のデータ構造です。

キューに"8","1","6","3"の順に値を格納すると、次のようになります。

キューへenqueue

このキューに対して、取出しを続けて2回行うと、1回目は「8」、2回目は「1」が取り出せます。

キューからdequeue

2回目の取出しで得られる値は「1」なので、「ア」が正解です。

ITパスポート令和元年秋期 問62

問題

下から上へ品物を積み上げて,上にある品物から順に取り出す装置がある。この装置に対する操作は,次の二つに限られる。

 PUSH x:品物xを1個積み上げる。

 POP:一番上の品物を1個取り出す。

スタック

最初は何も積まれていない状態から開始して,a,b,cの順で三つの品物が到着する。
一つの装置だけを使った場合,POP操作で取り出される品物の順番としてあり得ないものはどれか。

ア:a,b,c  イ:b,a,c  ウ:c,a,b  エ:c,b,a

ITパスポート令和元年秋期 問62

スタックは、データを順番に格納し、最後に格納したデータから順に取り出す、後入れ先出し(LIFO:Last-In First-Out)方式のデータ構造です。

POP操作で取り出される品物の順番としてあり得ないものはどれか、ア~エを順番に確認していきます。

ア:a,b,c

以下の手順で可能です。

  • PUSH a → [a]
  • POP → [] (aを取り出す)
  • PUSH b → [b]
  • POP → [] (bを取り出す)
  • PUSH c → [c]
  • POP → [] (cを取り出す)

イ:b,a,c

以下の手順で可能です。

  • PUSH a → [a]
  • PUSH b → [a, b]
  • POP → [a](bを取り出す)
  • POP → [] (aを取り出す)
  • PUSH c → [c]
  • POP → [] (cを取り出す)

ウ:c,a,b

POP操作で取り出される品物の順番としてあり得ません。

  • PUSH a → [a]
  • PUSH b → [a, b]
  • PUSH c → [a, b, c]
  • POP → [a, b](cを取り出す)
  • POP操作を行うとbが取り出され、aを取り出すことはできません。

エ:c,b,a

以下の手順で可能です。

解答エ
  • PUSH a → [a]
  • PUSH b → [a, b]
  • PUSH c → [a, b, c]
  • POP → [a, b](cを取り出す)
  • POP → [a] (bを取り出す)
  • POP → [] (aを取り出す)

ITパスポート令和4年 問90

問題

ディレクトリ又はファイルがノードに対応する木構造で表現できるファイルシステムがある。ルートディレクトリを根として図のように表現したとき,中間ノードである節及び末端ノードである葉に対応するものの組合せとして,最も適切なものはどれか。ここで,空のディレクトリを許すものとする。

木構造
ディレクトリディレクトリ 又は ファイル
ディレクトリファイル
ファイルディレクトリ 又は ファイル
ファイルディレクトリ

ITパスポート令和4年 問90

木構造は、木のような階層構造でデータを管理するデータ構造です。

木構造の要素部分を節(ノード)といい、親のない最上位の節を根(ルート)、子のない節を葉(リーフ)、そして 節と節を繋ぐ線のことを枝(ブランチ)といいます。

ファイルシステムは、次のように木構造で管理しています。

ディレクトリとは、ファイルや別のディレクトリを格納する箱のようなもので、Windowsではフォルダと呼ばれます。

ディレクトリにはファイルや別のディレクトリを格納できますが、ファイルの中に別のファイルやディレクトリを格納することはできません。

そのため、節には「ディレクトリ」、葉には「ディレクトリ 又は ファイル」が入ります。

「ア」が正解です。

ITパスポートおすすめの参考書・問題集

いちばんやさしい ITパスポート試験に合格することを目的に企画・構成された対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。
ITパスポート超効率の教科書スキマ時間で効率的にITパスポートの試験対策ができる対策本。動画とテキスト、小テストと過去問を組み合わせた、効果的な4ステップ学習で、合格へと導く。
かやのき先生のITパスポート教室ITパスポート受験者のためのやさしいオールインワンタイプの参考書&問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。
かんたん合格ITパスポート過去問題集信頼と実績の過去問題集。ITパスポート試験合格を最短で目指す人は必携の1冊!
出るとこだけ!ITパスポート「ITパスポート」に効率よく合格したい人のため対策本。フルカラーで見やすく「出るとこだけ」を効率的に学習できる1冊!
キタミ式イラストIT塾 ITパスポートすべての解説をイラストベースで行っているため,とてもわかりやすい解説本。いちばん最初に読むITパスポート試験関連の書籍を探している人におすすめ!

helpful

-ITパスポート