2020 年度「アルゴリズムとデータ構造」試験問題

2021-02-09

問題文は 1〜2 ページにある。問題で参照するコードは 2〜5 ページにある。
問題 1. 三角形 ABC のナーゲル点を Na とし、A, B, C, Na の座標を

A = (xA , yA ),B = (xB , yB ),C = (xC , yC ),Na = (xNa , yNa )とおくと、((xNa , yNa ) =(s − a)xA + (s − b)xB + (s − c)xC (s − a)yA + (s − b)yB + (s − c)yC,ssである。ただし、a, b, c は辺の長さ、すなわち、a = |BC|,b = |CA|,)c = |AB| とし、s = (a + b + c)/2とする。
三角形の各頂点の座標からナーゲル点の座標を求める計算を C の関数 nagel_point として実装せよ。関数は計算のみを行い、入出力などそれ以外の動作はいっさい行ってはならない。

(1) 図 1 のインターフェースで実装せよ。
(2) 図 2 のインターフェースで実装せよ。
/* 平面上の点 */struct point {double x;/* x 座標 */double y;/* y 座標 */};/* 平面上の三角形 */struct triangle {struct pointA;/* 頂点 A */struct pointB;/* 頂点 B */struct pointC;/* 頂点 C */};/* ナーゲル点の計算 */struct point
nagel_point(struct triangle tri);/* tri に三角形のデータが格納されている。 *//* 返値がナーゲル点のデータである。 */図1

ナーゲル点を計算する関数のインターフェース (1)/* 平面上の点 */struct point {double coordinates[2]; /* 順に、x 座標、y 座標 */};/* 平面上の三角形 */struct triangle {struct pointvertices[3];/* 順に、頂点 A、頂点 B 、頂点 C */};/* ナーゲル点の計算 */voidnagel_point(const struct triangle *tri, struct point *center);/* tri の指す先に三角形のデータが格納されている。 *//* center の指す先にナーゲル点のデータを格納する。 */図2

ナーゲル点を計算する関数のインターフェース (2)1/52020 年度「アルゴリズムとデータ構造」試験問題

2021-02-09

問題 2. コード 1, 2, 3, 4 は、long 型のデータの集まりに対してその要素の総和を C の関数として実装したものである。それぞれのコードでデータの集まりを実装するデータ構造は、キャプションに書かれたとおりである。

(1) 空欄を埋めよ。
問題 3. コード 5 は、ヒープソートを C の関数 lal heapsort() として実装したものである。第一引数は構
造体 struct lal の配列の先頭を指すポインタ、第二引数はその配列の大きさである。二つの引数で定められた配列を昇順にソートする。
以下を前提とする。

• 構造体 struct lal はファイル lal.h 内で定義されている。
• 関数 lal swap() と lal less() は、形式がvoidlal_swap(struct lal *, struct lal *);int

lal_less(const struct lal *, const struct lal *);であり、外部で定義され、そのプロトタイプ宣言がファイル lal.h 内でなされている。

– 関数 lal swap() は、第一引数の指す先と第二引数の指す先の値を交換する。
– 関数 lal less() は、第一引数の指す先と第二引数の指す先で値を比較し、前者が小さければ 0 でない整数を返し、さもなくば 0 を返す。

(1) 空欄を埋めよ。
(2) 関数 lal heapsort() の第二引数は size t 型であるが、これを unsigned int 型にするとどのような不都合があり得るか説明せよ。

(3) 最悪時間計算量の観点からは、クイックソートよりもヒープソートが優れている。にもかかわらず、クイックソートがヒープソートよりもよく使われる理由を論ぜよ。
コード 1 配列の要素の総和（添字を小さいほうから大きいほうへ動かす）#include <stdlib.h>longarray_sum(const long *array, size_t size){longs = 0;

size_ti;(あ)for (i =s +=; i <( え)( い);;}
return s;}

2/5( う)) {2020 年度「アルゴリズムとデータ構造」試験問題

2021-02-09

コード 2 配列の要素の総和（ポインタを小さいほうから大きいほうへ動かす）#include <stdlib.h>voidarray_sum(const long *array, size_t size){
longs = 0;

const long*p;(お)for (p =( く)s +=( か); p <;( き)) {;}
return s;}

コード 3 単方向線形リストの要素の総和（ダミーセルなし。終端は NULL ポインタ）#include <stdlib.h>
struct cell {struct cell*next; /* 次のセルを指すポインタ */longvalue; /* セルに格納された値 */};
long
slist_sum(const struct cell *head){longs = 0;

const struct cell(け)for (p =s +=*p;; p != NULL;( さ)(こ);}return s;}3/5) {

2020 年度「アルゴリズムとデータ構造」試験問題

2021-02-09

コード 4 二分木の節のラベルの総和（再帰的に計算）#include <stdlib.h>
struct node {/* 左子節を指すポインタ */struct node*left;

struct node*right; /* 右子節を指すポインタ */longvalue;/* 節にラベルづけられた値 */};
longbintree_sum(const struct node *root){
longs = 0;

if (root != NULL) {s =(し);

s += bintree_sum((す));s += bintree_sum((せ));}return s;}

4/5

2020 年度「アルゴリズムとデータ構造」試験問題

2021-02-09

コード 5 ヒープソートの実装#include <stdlib.h>#include "lal.h"static inline voidsift(struct lal *a, size_t m, size_t n){size_ti, j;for (i = m; (j = i * 2 + 1) < n; i = j) {(そ),( つ))) {if (j + 1 < n && lal_less((た)j ++;}
if (lal_less(( ち),(て)lal_swap(,(と)} else
break;}}
void
lal_heapsort(struct lal *a, size_t n){size_ti;if (n <= 1)
return;for (i = n / 2; i > 0;) {i --;sift(a, i, n);}for (i = n - 1; i > 0; i --) {lal_swap((な),(に)sift(a, 0, i);}}5/5););)) {