Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説!

応用プログラミングスキルチェック本番レベル模試を作ってみた

こんにちは、ももやまです。
今回は応用プログラミングのスキルチェック問題(C言語)を作ってみました。

問題と解答用紙はこちらからダウンロードできます!!
ぜひチャレンジしてください!!

チェックするスキルは

  • 基礎的なプログラミング力
  • 構造体について
  • プロトタイプ宣言
  • エラー処理
  • 再帰関数
  • 外部データ読み込み
  • 配列・連結リスト
  • 抽象データ型

をチェックします。

試験時間は90分で120点満点です。

次のページからは問題と解説を載せています。

1回解いてから答え合わせをしてください。

共通の採点基準
プログラムを書く問題の場合、特に指示がなければ1つのミスに対して-2(セミコロン忘れは-1)とし、同じミスの減点は重複しない。

1.構造体とプロトタイプ宣言


つぎの(1)〜(3)の問いに答えなさい。(配点 20)

(1) 行基本変形サークルで解析・線形代数・微分方程式・確率統計の4分野の模試を行うことにする。このとき、行基本変形サークルの成績を保存するための構造体を定義しなさい。
変数名は好き勝手に決めてよい。

★成績データの仕様★

  • 成績データは、受験番号、ペンネーム、4科目の各得点が記載されている。
  • 受験番号は8桁の数字のみで構成される。なお、最上位に0が来ることはない
  • 例えば01145149)のような受験番号は最上位が0なので存在しない。
  • ペンネームは20桁以内の英数字とし、日本語や特殊記号は考えない。
  • 各4科目はそれぞれ100点満点で0〜100点の1点刻みで採点される

(2) 受験者の成績データから4科目の平均点を出すプログラムを作成したい。

受験者の成績が保存された構造体から、4科目の平均点を出すプログラムを作成しなさい。
(例えば受験者の解析が89点、線形代数が95点、微分方程式が78点、確率統計が81点の場合、4科目の平均点である85.75が返される)

(3) (2)で作成したプログラムのプロトタイプ宣言をしなさい。


★解説★

(1) [7点]
構造体の作成をする問題。
変数名は何でもいいのですが、なるべくわかりやすい変数名をつけておかないと自分で構造体を用いてプログラムを書く際に苦戦します。

※(2)で(1)の構造体を利用するのですが、模範解答はこちらの構造体を使って書いていきます。

struct result {
    int id; // char id[9]; でもOK (忘れ-3)
    char name[21]; /* `\0`を忘れずに(`\0`忘れは-2、行まるごと書き忘れは-3) */
    int kai,sen,bi,kaku; // 要素不足-3
} ;

もちろん下のように typedef をつけてもOKです。

typedef struct result { // typedefの場合はこの行のresultを省略してもOK
    int id;
    char name[21]; /* `\0`を忘れずに */
    int kai,sen,bi,kaku; // 要素不足-3
} RESULT;

最後のセミコロンを忘れやすいので注意しましょう。

(2) [7点]
(1)で定義した構造体を使う問題です。
4科目の平均点は、4科目の合計点を4で割ると出すことが出来ます。
割り算をする際にキャストを忘れないように!!(キャスト忘れ-2)

double avg(struct result st) {
    return (st.kai + st.sen + st.bi + st.kaku) / 4.0;
// OK: return (double)(st.kai + st.sen + st.bi + st.kaku) / 4;
}

(3) [6点]
(2)で作成した関数のプロトタイプ宣言をするだけです。
セミコロンを忘れないように!!(セミコロン忘れ-2)

double avg(struct result a); // 変数名は実際に定義したときの変数名でなくてもOK
// OK: double avg(struct result );

2.総合問題(エラー処理・関数作成・外部データ入力)

今回の一番のメインの問題がこちらになります。


つぎの問いに答えなさい。(配点 35)

某Y音楽能力検定の指導グレードの成績を処理するプログラムと成績を保存されたファイル5kyu_result.csvがある。

指導グレードの成績はソルフェージュ(solf)・鍵盤実技(key)・調音(choon)・楽典(gakuten)・コード(chord)の5つがある(成績は0点〜100点の1点刻み)。

なお、現時点での成績データ5kyu_result.csvには次のような情報が順番に格納されている。(受験番号はid、名前はnameに保存されている。)

f:id:momoyama1192:20190724091145g:plain

プログラムリスト

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100

typedef struct result {
    int id; // 受験番号
    char name[20]; // 名前
    int solf,key,choon,gakuten,chord; // 別々に4つ書いてもOK
// それぞれソルフェージュ・鍵盤実技・調音・楽典・コード進行のスコア
} RESULT;



int minSum_over_pAve(RESULT x[], int len);
int isPass(RESULT x);
int find_id (RESULT x[],int len, int myid);


void checkPF(RESULT result_list[],int len) {
    int myid,list_num;
    printf("Enter your ID: ");
    scanf("%d",&myid);
    list_num = find_id(result_list,num_data,myid);
    if(list_num != -1) {
        if(isPass(result_list[list_num])) {
            printf("Congratulations!!  You pass!!\n");
        }
        else {
            printf("Oh, no.  You failed..\n");
        }
    }
}

// ファイルを読み込み、データの数を返す
int file_read(RESULT result_list[]) {
    FILE *fp;
    fp = // (2) ここに入る1行を書きなさい。
    int id,solf,key,choon,gakuten,chord;
    char name[20];

    int num_data = 0;
    if(fp == [あ]) {
        printf("Can't open the file\n");
        exit(1);
    }
    while(fscanf(fp,"%d,%[^,],%d,%d,%d,%d,%d",&id,name,&solf,&key,&choon,&gakuten,&chord) != [い]){
        result_list[num_data].id      = id;
        strcpy(result_list[num_data].name,name);
        result_list[num_data].solf    = solf;
        result_list[num_data].key     = key;
        result_list[num_data].choon   = choon;
        result_list[num_data].gakuten = gakuten;
        result_list[num_data].chord   = chord;

        num_data += 1;
    }
   
    return num_data;
}

int main(void) {
    RESULT x[N];
    int len = file_read(x);

minSum_over_pAve(x,len);
checkPF(x,len);
}

(1) 受験番号が1番である人の成績データは5kyu_result.csv内ではどのように記述されているか答えなさい。

(2) fp = // (2) の部分の fp = につづく式を書きなさい。

(3) プログラム中の[あ]・[い]に当てはまるものの組み合わせとして正しいものを①〜④の中から記号で選びなさい。

1: [あ] NULL [い] NULL  
2: [あ] NULL [い] EOF
3: [あ] EOF  [い] NULL
4: [あ] EOF [い] EOF

(4) 現在の成績データ5kyu_result.csvの状況であれば本プログラムは問題なくうごくが、成績データがある条件を満たすとプログラムが正しく動作しなくなる。

(a) プログラムが正しく動作しなくなる場合の成績データの状況
(b) (a)の状況を満たしていても正しくプログラムを動かすためにプログラムの前後に追加すべきプログラムの内容。

を書きなさい。

(5) つぎの (a)〜(c) の関数を作成しなさい。引数はプロトタイプ宣言を参考にすること。

(a) 受験者リスト内x(要素数len)において、実技科目2つ(ソルフェージュ・鍵盤実技)の合計の点数が平均点以上の人の中で、5種目の総合得点が最低点の人の5種目の合計点数を返すプログラムminSum_over_pAveを作成しなさい。

(b) 受験者リストx(要素数len)から、与えられた受験番号myidの成績データがどこにあるのかを配列の添字(番号)で返すfind_idを作成しなさい。ただし、見つからない場合は-1を返すこと。

(c) 1人の成績データxを与えると、その人の合否を判定する関数isPassを作成しなさい。

★指導グレードの合格条件★

  • それぞれの項目の平均点が75点以上あること
  • 5つの項目のうち、60点未満の項目が1つもないこと

上のcsvファイルの例の場合、合格しないのは60点未満の科目が存在する受験番号3番の人とそれぞれの項目の平均点が75点未満の受験番号4番の人である。


★解説★

(1) [3点]
5kyu-result.csv 受験番号1を見るとデータが書かれているので、そのデータを fscanf の部分に合うように書いてあげればよい。

注意するのが %[^,] で、これはコンマが来るまでの文字列をすべて読み取るという意味である。
(正規表現の ^ は否定を表す)

答えは、

1,Dashijiru,63,72,81,100,92

となる。(1要素おかしいごとに-1)

(2) [4点]
ファイルの開き方の問題。ファイルを開くためには、fopen 関数を使えばよい。

fopen関数は、最初の引数にファイル名(""で囲うこと)、2つめの引数にモード(読み取りモードr、書き込みモードw、追加モードr)を設定する(""で囲うこと)。

今回は 5kyu-result.csv を読み取りモード(書き込みがないので)で開けばよいので答えは、

fopen("5kyu_result.csv","r");

となる。(""がない -2、権限モードが違う(もしくはない) -2、ファイル名スペルミス -1)

(3) [4点]
穴埋め問題。
fopenはファイルの読み込みに失敗(例えば該当ファイルが存在しない)すると NULLを返す。
fscanfでファイルを読み取っていくと、データの

(4) [6点(各3点]
エラー処理問題。

配列の上限(100)を超えた場合でも配列にデータが挿入され、予期せぬ動作(Segmentation Faultなど)をする可能性がある。 なので(a)の答えは、

(a) 101人以上の成績データを読み込むとき。(一定数以上の成績データを読み取ることが読み取れていればOK)

となる。また、101人以上の成績データを読みこんでも予期せぬ動作をしないようにするためには、101人以上のデータを読み込もうとしたときにエラーを出せばよい。よって(b)の答えは、

(b) while文の最初(result_listに代入する前)に以下の文を追加すればよい。

if(num_data >= N) { // >= が > なら -2点
fprintf(stderr,"Error:: Size over\n"); // エラー文は出したほうがいいけどなくても減点はなし
    exit(1); // return num_data; でももちろんOK
}

となる。

(5) [19点]
プログラムを記述する問題。

(a) [7点]
条件つきの最低点を求める関数を作る問題。

1.実技種目の平均点を出す部分 1.平均点以上の最低点を求める部分

のように2ステップにわけてプログラムを書いていけばよい。

なお、最初の人(0番目の人)が実技種目の平均点以上あるかはわからないいため、最低値の初期化を0番目の合計点を行うのはNG。

int sum_over_pAve(RESULT x[],int num_data) {
    // (3点)
    int sub_sum = 0,count = 0,sum, min_sum = 501; // 初期値注意(初期化忘れ-2)
    double sub_ave;
    for(int i = 0; i < num_data; i += 1) {
        sub_sum += x[i].solf + x[i].key;
        count += 1;
    }
    sub_ave = sub_sum * 1.0 / count; // キャスト忘れずに

    // (4点)
    for(int i = 0; i < num_data; i += 1) {
        if(sub_ave <= x[i].solf + x[i].key)
        {
            sum = x[i].solf + x[i].key + x[i].choon + x[i].gakuten + x[i].chord;
            if(sum < min_sum) {
                min_sum = sum;
            }
        }
    }

    return min_sum;
}

(b) [6点]
線形探索を行うプログラムを記述すればよい。
なお、データは受験番号順などにソートされているとは限らないため、二分探索を行うのはNG。

int find_id(RESULT result_list[],int num_data, int myid) {
    for(int i = 0; i < num_data; i += 1) {
        if(result_list[i].id == myid) {
            return i; // 見つけたらiを返す (4点)
        }
    }
    return -1; // 見つからなければ-1を返す (2点)
}

(c) [6点]
条件式を正しくプログラムにできるかどうかを試す問題。
orやandを適切に組み合わせること。

★採点基準★

  • 60点未満が不合格にならない -2
  • それぞれの平均点が75点以上なのに合格にならない人がいる -2
  • それぞれの平均点が75点未満なのに合格になる人がいる -2

で採点。

int isPass(RESULT x) {
    if(x.solf < 60 || x.key < 60 || x.choon < 60 || x.gakuten < 60 || x.chord < 60) {
        return 0; // まず60点以下があれば不合格 (2点)
    }

    // 5で割って平均を求めるのもOKだがこちらのほうがキャスト考慮が不要
    if(x.solf + x.key + x.choon + x.gakuten + x.chord >= 75 * 5) {
        return 1; // 平均が75点であれば合格 (2点)
    }

    return 0; // もちろん平均75点なければ不合格(2点)
}

3.抽象データ型


つぎの(a), (b)の問いに答えなさい。(配点 25)

(a) 分数を扱うプログラムを作成するために有理数のデータ型を次のように定義する。

typedef struct rat {
    int bunshi;  // 分子
    unsigned int bunbo;  // 分母
} RAT;

このデータ型で、負の数を表すときは必ず分子側(bunshi)をマイナスにし、分母は必ず正にすること。

(1) 2つの整数型a,bの最大公約数を求めるプログラムを作成しなさい。 必要なら以下のアルゴリズムを用いてもよい。


★ユークリッドの互除法★

a=bq+r において、a と b の最大公約数と b と r の最大公約数は等しい。 また、r が0のときの最大公約数は b である。


(2) (1)を用いて有理数型で表されたデータxを既約分数にするプログラムを作りなさい。 ヒント:それぞれの分子、分母を最大公約数で割ると既約分数となる。

(b) 有理数を表すRAT型に次のような操作関数がrat.hで与えられているとする。

// rat.h

RAT ratAdd(RAT a, RAT b); // 有理数の加算 a + b を行う
RAT ratSub(RAT a, RAT b); // 有理数の減算 a – b を行う
RAT ratMul(RAT a, RAT b); // 有理数の乗算 a * b を行う
RAT ratDiv(RAT a, RAT b); // 有理数の除算 a / b を行う

上記の操作関数を用いて、「有理数を要素とする2次元ベクトル」を扱うプログラムを考える。

#include<stdio.h>
// (1) HERE

typedef struct vec {
    RAT x; // x座標
    RAT y; // y座標
} VEC;

VEC vecAdd(VEC a, VEC b);
RAT vecProd(VEC a, VEC b);

VEC newVec(RAT a, RAT b) {
    VEC v = {a,b};
    return v;
}

(1) 操作関数を呼び出すのには (1) HEREの部分にある文を書く必要がある。その文を答えなさい。

(2) 2つのベクトルa,bを加算する関数vecAddをnewVec関数を用いて作成しなさい。 プロトタイプ宣言と関数の型に注意すること。

(3) 2つのベクトルa,bの内積を求める関数vecProdを作成しなさい。 プロトタイプ宣言と関数の型に注意すること。


★解説★

(a-1) [5点]

ユークリッドの互除法をそのままプログラムに落とし込む問題。
再帰法を使うとあっという間に書ける。

模範解答

int gcd(int a, int b) {
    if(b == 0) {
        return a; // 初期値忘れ -3
    }
    else {
        return gcd(b, a % b); // 式が違う -2
    }
}

[別解](処理効率的にはすごい悪いが……)

aとbの小さい方からfor文を回し、両者とも割り切れたらその値が最大公約数という強引に求めるやり方もある。

int gcd(int a, int b) {
    int min;
    if(a > b) {
        min = b;
    }
    else {
        min = a;
    }
    // 必ず min → 1 のfor文にすること(逆方向だと求めた数が最大公約数か不明、3点減点)
    for(int i = min; i >= 1; i -= 1) {
        if(a % i == 0 && b % i == 0) {
            return i; // 最初に割り切れたものが最大公約数
        }
    }

    return 1;
}

(a-2) [5点]
分子と分母を最大公約数で共に割ると自動的に既約分数となる。

RAT reduction(RAT x) {
    int t = gcd(x.bunshi,x.bunbo);

    x.bunshi /= t;
    x.bunbo  /= t;

    return x;
}

(b) (a)で作成したデータ型を使ってさらに別のデータ型を作る問題。

(b-1) 自分で作ったデータ型を読み込む(includeする)処理をかけばよい。
答えは

#include "rat.h"

となる。なお <rat.h> はNGなので注意(4点減点)。

(b-2)
有理数を要素とするベクトルの足し算。
ベクトルの足し算はそれぞれの要素の足し算となる。

なお、int型やdouble型ではないので ratAdd を使わず直接 + で足し込むのは絶対にNG(5点減点×)。

答えは、

VEC vecAdd(VEC a, VEC b) {
    return newVec(ratAdd(a.x,b.x),ratAdd(a.y,b.y));
}

となる。

(b-3)
ベクトルの内積を求める問題。

内積は、それぞれの成分の積の和で表すことができる。

答えは、

RAT vecProd(VEC a, VEC b) {
    return ratAdd(ratMul(a.x,b.x),ratMul(a.y,b.y));
}

となる。

4.配列・連結リストの操作


つぎの(1), (2)の問いに答えなさい。(配点 20)

(1) 次の(a), (b) の配列操作に関するプログラムを指示に従って書きなさい。
ただし、下に定義されている変数のみを使うこと(勝手に定義しないこと)。

int a[1000];
int i,j,len,pos,x;

(a) 配列の0番目から順番にlen(要素1000未満と仮定してよい)個の要素が入っている配列aのpos番目(添字pos)に要素xを挿入するプログラムを書きなさい。
ただし、pos番目以後に挿入されているデータは1つ先の配列にシフトさせること。
(例えばpos = 4番目にデータを挿入するとする。すると、5番目のデータは6番目に、6番目のデータは7番目に…… となる。)

(b) 配列の0番目から順番にlen(要素1000未満と仮定してよい)個の要素が入っている配列aのpos番目(添字pos)の要素を削除するプログラムを書きなさい。 ただし、pos番目以後に挿入されているデータは1つ前の配列にシフトさせること。
(例えばpos = 4番目のデータを削除したとする。すると、5番目のデータは4番目に、6番目のデータは5番目に…… となる。)

  (2) 次の(a), (b) の連結リストnpの操作に関するプログラムを指示に従って書きなさい。 ただし、下に定義されている変数のみを使うこと(勝手に定義しないこと)。

typedef struct node {
    struct node *next;
    int val;
} NODE;

NODE *np,*p,*q;

(a) ノードpの直後にノードqを挿入するプログラムを書きなさい。
(例:挿入前のノードpの直後がノードがrになっている場合、ノードpの直後にノードqを挿入すると、ノードpの直後はノードq、ノードqの直後はノードrになる。)

(b) ノードpの直後のノードを削除し、削除されたノードをfree関数で解放するプログラムを書きなさい。
(例えばノードpの直後のノードがqであり、ノードqの直後のノードがrであるとすると、ノードpの直後のノード、つまりノードqを削除するとノードpの直後のノードはrとなる。)


★解説★

(1-a) [5点]
forループの方向に要注意(ループ方向ミスは-4)!!

まず、データを挿入するために、該当する場所以降の配列を1つシフトさせて上げる必要がある。

その際にfor文を用いてシフトさせるのだが、データをシフトする際のfor文の向き(++か--か)を間違えてしまうと、他のデータを上書きしてしまうことになり、うまくデータが挿入されない。

今回の場合、降順(大きい順に確認、i--)で確認するのだが、間違えて昇順で行うとすでにあるデータを上書きしてしまうため正しくデータをシフトさせてあげることができない。

手順としては

  1. pos番目までのデータをfor文でシフト(降順で)
  2. データを代入
  3. 要素数lenを1足す

となります。

解答

// 4点
for(i = len - 1; i >= pos; i -= 1) {
    a[i+1] = a[i]; // ループの回数のミス、この行のミスは-2
}
// 1点
a[pos] = x; 
len += 1; // 意外と忘れがち(なければ-1点)

動きをアニメーションにしました

f:id:momoyama1192:20190722171642g:plain

(1-b) [5点] 同じくfor文のシフトだが、(1-a)と同じくデータをシフトさせるときのforループの方向に要注意(ループ方向ミスは-4)。
今度は逆に昇順でシフトをさせないとデータを上書きしてしまい、正しくシフトしてあげることができません。

手順としては

  1. pos+1番目以降のデータを1つfor文でシフト(昇順で)
  2. 要素数lenを1引く(

となります。

// 4点
for(i = pos + 1; i <= len - 1; i += 1) {
    a[i-1] = a[i]; // ループの回数のミス、この行のミスは-2
}
// 1点
len -= 1; // なければ-1点

動きをアニメーションにしました

f:id:momoyama1192:20190722171635g:plain

(2-a) [5点] 今度は連結リストの問題。
連結リストの挿入の場合は(1)のようなforループを考える必要はない。

q->next = p->next;
p->next = q;

こちらもアニメーションにしました

f:id:momoyama1192:20190722171655g:plain

(2-b) [5点] 連結リストの削除問題。
forループなどは一切不要。

q = p->next;
p->next = q->next;
free(q);

アニメーションはこちら

f:id:momoyama1192:20190722171649g:plain

ちなみによくある間違いの例として、

p->next = p->next->next;
free(p->next); // p->next はアニメーションでいうrに相当するため

があります(-3点)。

5.抽象データ型


抽象データ型に関する問いに答えなさい。(配点 20)

スタックを操作するプログラムがつぎのように与えられているとする。

typedef struct stack {
    int data[100];
    int num; // 要素数
} STACK;

void stackPush(STACK *st, int a); // スタックのpush操作(aをpush)
int stackpop(STACK *st); // スタックのpop操作
int isStackEmpty(STACK *st); // スタックが空(0)なら1、そうでなければ0を返す
int isStackFull(STACK * st); // スタックが満杯(100)なら1、そうでなければ0が返す

(1) 抽象データ型の説明として、正しいものを1〜4の中から1つ選びなさい。
[ソフトウェア開発技術者平成17年春期 午前問37]

  1. 同じ構造をもつデータを1列に並べて定義したものであり、各データへのアクセスはポインタを用いて行う。
  2. 異なった型のデータを組み合わせて定義したものであり、各データへのアクセスはデータの組に与えられた名前で修飾して行う。
  3. データとそれに対する操作を一体化して定義したものであり、データへのアクセスは定義された操作を用いて行う。
  4. 同一の型のデータを指定された個数だけ並べて定義したものであり、各データへのアクセスはインデックスを用いて行う。

(2) 抽象データ型の利用者、開発者それぞれにとっての利点を書きなさい。

(3) スタックsが空かどうかを判定するのに抽象データ型を使わずにs->num == 0のように直接数式で比べるのは、よいかよくないか。理由も書きなさい。

(4) スタックsにちょうど1つだけデータが入っていることを確認したい。どのように確認(プログラムを書く)のがいいか。


★解説★

(1) [4点]
解答:3

抽象データ型は、データの構造とそれに関連する手続きなどを1つにまとめてカプセル化したものとなります。

利用者にはデータのインターフェース(操作手続き)だけが公開される(プログラムの内部は隠ぺいしている)ので抽象データの実装方法などが変更されてもプログラムには一切影響を与えません。

ちなみに

  1. 連結リストの説明
  2. 構造体の説明
  3. 抽象データ型の説明
  4. 配列の説明

です。

(2) [3点×2 = 6点]
赤色部分が大切。

[利用者にとってのメリット]
データのインターフェースを知るだけで必要な処理を行える。

[開発者にとってのメリット]
利用者はプログラムの内部実装を知らないため、必要な処理さえ行うことができれば、実装方法などを自由に変更できる

(3) [5点]
良くない(2点)

理由(3点、いずれか1つ)
* s->num == 0num が何をさしているのか他の利用者がわからないかもしれないから。 * スタックが空なのは0とは限らず、内部仕様がこっそり変更された場合に修正が必要だから。

(4) [5点]

Step1: isStackEmpty関数でスタックが空でないかを確認し、空でなければstackPopで値を引き出す。
Step2 : もう1回isStackEmptyを実行し、スタックが空かどうかを確認する。

プログラムっぽく書くと

int isStack1(STACK *st) {
    int x;
    if(isStackEmpty(st)) {
        return 0;
    }
    else {
        x = stackpop(st);
        if(isStackEmpty(st)) {
            stackPush(st,x);
            return 1;
        }
        else {
            stackPush(st,x);
            return 0;
        }
    }
}

となる(関数でなくても流れがしっかりとかけていればOK)。

ただし、確認せずにpopしている答案は-2点。

6.さいごに

今回はプログラミングのスキルチェック問題とその解説を作成してみました。

採点基準が少し雑ですがご了承ください。

簡単な問題から難しい問題まで様々な問題を入れましたが、120点中90点以上取ることができたらプログラミング強いと言っていいと思います。