Information Science 情報基礎

(1)

What codes should be inserted to X and Y in Program 2, in order for the following two programs to generate the same output?

次に示す二つのプログラムが同じ出力になるためには，

Program 2

の

X

および

Y

の部分をどのように書けばよいか．

Program 1

#include <stdio.h>

int main(void) {

int i;

for(i = 10; i > 0; i--) printf("%d\n", i);

return 0;

}

Program 2

#include <stdio.h>

int main(void) {

int i;

i = 10;

while( X ) { printf("%d\n", i); Y ; } return 0;

}

(A) X: i < 10 Y: i = i + 1

(B) X: i < 10 Y: i = i - 1

(C) X: i < 10 Y: i = 10

(D) X: i > 0 Y: i = i - 1

(E) X: i > 0

Y: i = 10

(2)

The following program outputs a list of students (IDs and names). Choose program fragments for the blanks X and Y, which makes the program output to be the below Output.

次のプログラムが

Output

に示すような学生名簿

(

番号と氏名

)

を出力するために

X

と

Y

に入れるべきコードは以下のうちどれか．

#include <stdio.h>

int main(void) {

int i;

typedef struct stu { char name[10];

int id;

} student;

student data[] = {{"Kitagawa", 1001}, {"Minamide", 1002}, {"Higashino", 1003}};

student *p;

p = data;

for (i = 0; i < 3; i++) {

printf("%4d: %6s\n", X , Y );

p++;

}

return 0;

}

Output

1001: Kitagawa 1002: Minamide 1003: Higashino

(A) X: p[i].id

Y: p[i].name (B) X: p.id

Y: p.name (C) X: p->id Y: p->name

(D) X: p[i]->id

Y: p[i]->name (E) None of these

(3)

What is the output of the following Java program?

プログラムの出力は何か．

abstract class Expr { int f() { return 0; } }

class BinOpExpr extends Expr { private char op;

private Expr arg1;

private Expr arg2;

BinOpExpr(char op, Expr arg1, Expr arg2) {

this.op = op; this.arg1= arg1; this.arg2 = arg2;

}

int f() {

return arg1.f() + arg2.f() + ((op == ’+’)?1:0);

} }

class ConstExpr extends Expr { int val;

ConstExpr(int val) { this.val = val;

} }

class VarExpr extends Expr { String name;

VarExpr(String name) { this.name = name;

} }

class Test {

public static void main(String[] args) { Expr e =

new BinOpExpr(’+’,

new BinOpExpr(’+’, new VarExpr("x"), new ConstExpr(1)), new BinOpExpr(’*’, new ConstExpr(2), new ConstExpr(3)));

System.out.println(e.f());

}

(4)

For a complete binary tree B with n nodes, what is the average depth of nodes in B? Answer the order (on n) of the average.

頂点数が

n

の完全

2

分木

B

に対して，頂点の深さの平均を

n

のオーダーで答えよ．

(A) log n (B) n (C) n log n (D) n ² (E) None of these

Q20. Tick to answer this question.

この問題を解答する場合チェックを付ける．

Select a regular expression corresponding to the language of all strings over { 0, 1 } that contain only one occurrence of the string 00. Note that 000 contains two occurrences of 00.

部分列

00

を一つのみ含む

{ 0, 1 }

上の全ての列の言語を表す正規表現はどれか．ただし

000

は

00

の部分列を二つ含む．

(A) 1 ^∗ 001 ^∗

(B) (00 + 01) ^∗ (00 + 10) ^∗ (00 + 10) ^∗ (00 + 11) ^∗ (C) (1 + 01) ^∗ 00(1 + 101) ^∗

(D) (00) ^∗ (1 + 11) ^∗

(E) None of these

(5)

Consider a logical function f (X, Y, Z) = (X + Y + ¯ Z ) · (X + ¯ Y +Z ) · ( ¯ X +Y + Z), where “ · ” denotes logical conjunction, “+” denotes logical disjunction, and “ ¯ ” denotes negation. Answer a logical function g which satisfies g(X, Y, Z) = f (X, Y, Z).

論理積を

“ · ”

，論理和を

“+”

，否定を

“ ¯ ”

で表すこととする．論理式

f (X, Y, Z) = (X + Y + ¯ Z ) · (X + ¯ Y + Z) · ( ¯ X + Y + Z)

について，

g(X, Y, Z) = f (X, Y, Z)

を満たす

g

を答えよ．

(A) g(X, Y, Z) = ¯ X · Y ¯ · Z ¯ + ¯ X · Y · Z + X

(B) g(X, Y, Z) = ¯ Y · Z ¯ + ¯ X · Y · Z + X · Y + X · Z (C) g(X, Y, Z) = ¯ X · Y · Z + X · Y + X · Y ¯ · Z

(D) g(X, Y, Z) = ¯ X · Y ¯ · Z ¯ + Y · Z + X · Y + X · Y ¯ · Z (E) None of these

Q22. Tick to answer this question.

Select an iteration formula to find the approximate value of √

³

5 by Newton’s method.

√

3

5

の近似値をニュートン法で求めるときの反復の式を選べ．

(A) x _n+1 =

√

3

5x _n

5 (B) x _n+1 = x _n − x ³ _n

3x ² _n + 5 (C) x _n+1 = 2x ³ _n + 5 3x ² _n (D) x n+1 = x n − 3x ² _n + 3

√

3

5x n

(E) None of these

(6)

Consider four jobs A, B, C and D processed by an operating system. The processing times of the jobs are shown in the following table. Assume that the switching time of jobs is negligible. Find the waiting time of job D if the operating system uses the Shortest-Job-First (SFJ) scheduling algorithm.

あるオペレーティングシステムで処理される

4

つのジョブ

A, B, C, D

を考える．ジョブの処理時間が次の表のように与えられている．ジョブの切り替え時間は無視できるとする．オペレーティングシステムが最短ジョブ優先方式を用いる場合，ジョブ

D

の待ち時間を求めよ．

Job Processing time in milliseconds

A 7

B 4

C 1

D 5

(A) 1ms (B) 4ms (C) 5ms (D) 7ms (E) 10ms

(7)

A constant voltage V ( ̸ = 0) is applied across the circuit shown in the figure, where R and r indicate resistance values, and S indicates a switch. Answer the condition that the total current I is constant regardless of whether the switch S is open or closed.

図の回路に一定の電位差

V ( ̸ = 0)

が与えられているとする．図中の

R, r

は抵抗値を表し，

S

はスイッチを表す．

S

の開閉にかかわらず全電流

I

が一定であるための条件を選べ．

V

R R

R r

I S

(A) r = R (B) r = 2R (C) r = R/2 (D) r = 3R (E) r = 0

Q25. Tick to answer this question.

Find the order of T (n) = 4T (n/2) + 2n ² , T (1) = 1.

T (n) = 4T (n/2) + 2n ² , T (1) = 1

のオーダーを求めよ．

(8)

Consider two diﬀerent CPUs P ₁ and P ₂ , with the same instruction set. There are four classes of instruc- tions in the instruction set. The clock rate and CPI of each class for each CPU is given below. Let the frequency of instructions of each class executed in a certain program be A:40%, B:30%, C:20%, D:10%, and the execution time of the program with each CPU be T (P 1 ) and T (P 2 ), respectively. Find T (P 1 )

T (P 2 ) .

同じ命令セットを持つ二つの

CPU P 1

と

P 2

を考える．命令セットは

4

つのクラスに分けられ，各

CPU

のクロック周波数とクラス毎の

CPI

は以下のとおりである．あるプログラムの各クラスの命令の出現頻度が

A:40%, B:30%, C:20%, D:10%

であり，このプログラムの各

CPU

による実行時間をそれぞれ

T (P 1 )

と

T(P 2 )

とするとき，

T (P ₁ )

T (P 2 )

^{を求めよ．}

CPU clock rate CPI

class A class B class C class D

P 1 2.0GHz 1 2 3 4

P 2 4.0GHz 2 3 3 2

(A) 0.4 (B) 0.625 (C) 1.6 (D) 2.5 (E) None of these

(9)

For the following graph, when applying Dijkstra’s algorithm to find all shortest paths from v ₁ to the other vertices, select the vertex whose shortest path from v ₁ is found at the fifth step. Note that v ₁ isn’t counted.

次のグラフに関して，

v 1

から他の各点への最短路を

Dijkstra

のアルゴリズムで求めるとき，

5

番目に

v 1

からの最短路が見つかる点はどれか．ただし

v ₁

はカウントしない．

v 1

v 2

v 3

v 4

v 5

v 6

v 7

v 8

v 9

v 10

10 2

5 8

4 6

6

2 2 5

7 10 7

6 5

3 9

9 8

(A) v 4 (B) v 5 (C) v 6 (D) v 7 (E) v 8

Q28. Tick to answer this question.

Let C be binary (5, 2) linear code with generator matrix G =

( 1 0 1 0 1

0 1 0 1 1

)

. Which of the following

codeword is not contained in C?

(10)

Suppose that P(n, t) is the probability of queue length n at time t in the M/M/1 queueing system, in which the arrival rate per unit time and the service rate per unit time are equal to λ and µ, respectively.

Also, we assume λ < µ. Select the appropriate expression for the ratio P(1, ∞ )/P (0, ∞ ), where P (n, ∞ ) means the probability of queue length n at the stationary state.

単位時間あたりの到着率

λ

，サービス率

µ

の

M/M/1

待ち行列システムにおける時刻

t

の待ち行列の長さ

n

の確率を

P (n, t)

とする．また，

λ < µ

とする．

P(n, ∞ )

を定常状態における待ち行列の長さ

n

の確率としたとき，比

P (1, ∞ )/P (0, ∞ )

はどれになるか．

(A) µ

λ (B) λ

µ (C) λ

µ − λ (D) µ

µ − λ (E) None of these

Q30. Tick to answer this question.

Assume 0 < a 1 < a 2 < · · · < a n . Which is optimal for the following linear programming problem?

0 < a ₁ < a ₂ < · · · < a _n

を仮定する．次の線形計画問題の最適解として，正しい選択肢を選べ．

Information Science 情 報 基 礎

What codes should be inserted to X and Y in Program 2, in order for the following two programs to generate the same output?

Program 2

X

Y

Program 1

#include <stdio.h>

int main(void) {

int i;

for(i = 10; i > 0; i--) printf("%d\n", i);

return 0;

}

Program 2

#include <stdio.h>

int main(void) {

int i;

i = 10;

while( X ) { printf("%d\n", i); Y ; } return 0;

}

(A) X: i < 10 Y: i = i + 1

(B) X: i < 10 Y: i = i - 1

(C) X: i < 10 Y: i = 10

(D) X: i > 0 Y: i = i - 1

(E) X: i > 0

Y: i = 10

The following program outputs a list of students (IDs and names). Choose program fragments for the blanks X and Y, which makes the program output to be the below Output.

Output

(

)

X

Y

#include <stdio.h>

int main(void) {

int i;

typedef struct stu { char name[10];

int id;

} student;

student data[] = {{"Kitagawa", 1001}, {"Minamide", 1002}, {"Higashino", 1003}};

student *p;

p = data;

for (i = 0; i < 3; i++) {

printf("%4d: %6s\n", X , Y );

p++;

}

return 0;

}

Output

1001: Kitagawa 1002: Minamide 1003: Higashino

(A) X: p[i].id

Y: p[i].name (B) X: p.id

Y: p.name (C) X: p->id Y: p->name

(D) X: p[i]->id

Y: p[i]->name (E) None of these

What is the output of the following Java program?

Java

abstract class Expr { int f() { return 0; } }

class BinOpExpr extends Expr { private char op;

private Expr arg1;

private Expr arg2;

BinOpExpr(char op, Expr arg1, Expr arg2) {

this.op = op; this.arg1= arg1; this.arg2 = arg2;

}

int f() {

return arg1.f() + arg2.f() + ((op == ’+’)?1:0);

} }

class ConstExpr extends Expr { int val;

ConstExpr(int val) { this.val = val;

} }

class VarExpr extends Expr { String name;

VarExpr(String name) { this.name = name;

} }

class Test {

public static void main(String[] args) { Expr e =

new BinOpExpr(’+’,

new BinOpExpr(’+’, new VarExpr("x"), new ConstExpr(1)), new BinOpExpr(’*’, new ConstExpr(2), new ConstExpr(3)));

System.out.println(e.f());

}

}

For a complete binary tree B with n nodes, what is the average depth of nodes in B? Answer the order (on n) of the average.

n

Information Science 情報基礎

(A) log n (B) n (C) n log n (D) n ² (E) None of these

(A) 1 ^∗ 001 ^∗

(B) (00 + 01) ^∗ (00 + 10) ^∗ (00 + 10) ^∗ (00 + 11) ^∗ (C) (1 + 01) ^∗ 00(1 + 101) ^∗

(D) (00) ^∗ (1 + 11) ^∗

(A) x _n+1 =

5x _n

5 (B) x _n+1 = x _n − x ³ _n

3x ² _n + 5 (C) x _n+1 = 2x ³ _n + 5 3x ² _n (D) x n+1 = x n − 3x ² _n + 3

Find the order of T (n) = 4T (n/2) + 2n ² , T (1) = 1.

T (n) = 4T (n/2) + 2n ² , T (1) = 1