Information Science 情 報 基 礎

For each question, choose one correct answer and write its symbol (A–E) in the box.

以下の各問に対して正しい答えを選び，その記号

(A–E)

Q16. Select the output of the following C program.

以下の

C

#include <stdio.h>

int main() {

int n = 0;

while ( n++ < 5 ) printf("%d ", n);

return 0;

}

(A) 1 2 3 4 5 (B) 5 4 3 2 1 (C) 0 1 2 3 4 (D) 4 3 2 1 0 (E) None of these

Q17. Select a value that is the closest to the value output by the following C program.

以下の

C

#include <stdio.h>

#include <math.h>

double fx(double x) { return exp(x); }

double intf(double (*f)(double), double a, double b, int n) {

double sum, h;

int i;

h = (b - a) / n;

sum = (f(a) + f(b))/ 2.0;

for ( i = 1; i < n; i += 1 ) { sum += f(a + h * i);

}

return sum * h;

}

int main() { printf(‘‘%f\n’’, intf(&fx, 0.0, 1.0, 10)); return 0;}

(A) e

(B) e

(C) e − 1 (D) (e + 1) · 0.4 (E)

Q18. When the following Java program is executed, what value will be output?

以下の

Java

class TClass {

private int val = 0;

public void func(int num) { if (num % 3 != 0) val += num; else val = -val; } public int get() { return val; }

}

class Sample {

public static void main(String args[]){

TClass t = new TClass();

for (int i = 1; i <= 10; i++) t.func(i);

System.out.println(t.get());

} }

(A) 5 (B) 1 (C) − 1 (D) − 5 (E) None of these

Q19. There are 5 algorithms (with input size n) A, B, C, D, E such that the time complexity of each algorithm is as follows. Which algorithm has the largest time complexity?

入力サイズ

n

5

A, B, C, D, E

(A) Θ ( n

log n )

(B) Θ (n log n) (C) Θ (log n!) (D) Θ (n log log n) (E) Θ ( n

log log n )

Q20. Define a Boolean function f using ¯ (negation), ∧ (conjunction), and ∨ (disjunction) by f (p, q) = (p ∨ q) ∧ (p ∧ q). Which Boolean function is equal to f ?

否定

(¯)，論理積 ( ∧ )，論理和 ( ∨ )

f (p, q) = (p ∨ q) ∧ (p ∧ q)

(A) p (B) p (C) q (D) q (E) None of these

Q21. Let f be the Boolean function given by f = x

x

x

∨ x

x

x

∨ x

x

x

∨ x

x

x

. Suppose that we can use NOT gates, AND gates of fan-in two and OR gates of fan-in two to form a circuit. What is a minimum number of gates in a circuit that computes f ?

ブール関数

f

f = x

x

x

∨

x

x

x

∨

x

x

x

∨

x

x

x

f

Q22. Select a repeating decimal number that has no terminating decimal representation.

10

(A)

√ 5

10 (B) 256

999 (C) 256

1000 (D) 256

1024 (E) None of these

Q23.

Let n be a natural number, and define T(n) by the following recurrence equation:

T (n) = {

1, if n = 1,

T ( ⌊ n/2 ⌋ ) + 2n, if n ≥ 2.

Which is the closest to T (1024)?

自然数

n

(n)

T(n) = {

1, n = 1

T ( ⌊ n/2 ⌋ ) + 2n, n ≥ 2

T (1024)

(A) 2

(B) 2

(C) 2

(D) 2

(E) 2

Q24. Let L be a language defined by the regular expression “1

2

3”. Which word does not belong to L?

次の正規表現

“1

2

3”

L

L

(A) 3 (B) 123 (C) 1233 (D) 11223 (E) 111113

Q25. For a regular expression E, L(E) denotes the language defined by E. Choose one which satisfies the condition: L(E) ⊆ { x ∈ { 0, 1 }

| ♯

(x) is an odd number } , where ♯

(x) denotes the number of 0’s contained in x.

正規表現

E

E

L(E) ⊆ { x ∈ { 0, 1 }

| ♯

(x)

}

(x)

x

0

(A) E = ∅

+ 0

(B) E = 00

0

(C) E = 0

00

(D) E = 0(1

01

0)

(E) E = 0(0 + 1 + 0)

Q26. Select a bit string which means 8-bit two’s complement representation of − 5.

8

− 5

2

(A) 00000101 (B) 11111010 (C) 01111011 (D) 11111001 (E) None of these

Q27. What is the transposed matrix of the following matrix A

A = (

A

A

A

A

)

,

where A

(i, j ∈ { 1, 2 } ) is a submatrix of A and A

is the transposed matrix of A

?

A

A = (

A

A

A

A

) ,

ここで,

A

(i, j ∈ { 1, 2 } )

A

A

A

(A) (

A

A

A

A

)

(B) (

A

A

A

A

)

(C) (

A

A

A

A

)

(D) (

A

A

A

A

)

(E) None of these

Q28. A database designer defined the following functional dependencies on the relation R(A, B, C, D, E, F, G). What is a candidate key on R ?

Functional dependencies: A → B, BC → E, E → F , D → F G

データベース設計者が関係

R(A, B, C, D, E, F, G)

R

関数従属性:

A → B, BC → E, E → F, D → F G

(A) { A, C, D } (B) { B, C, D } (C) { B, D } (D) { A, D } (E) None of these

Q29. Let X and Y be independent random variables exponentially distributed with rate λ and µ as P (X ≤ x) = 1 − e

, and P (Y ≤ y) = 1 − e

. Let the random variable T = min(X, Y ). How is P (T ≤ t) given?

X, Y

λ, µ

P (X ≤ x) = 1 − e

P (Y ≤ y) = 1 − e

T = min(X, Y )

≤ t)

(A) 1 − e

(B) e

(C) (1 − e

)(1 − e

) (D) e

(E) None of these

Q30. Choose a probability distribution that can be encoded into the two Huffman codes: { 00, 01, 10, 11 } and { 0, 10, 110, 111 } .

ふたつのハフマン符号

{ 00, 01, 10, 11 }

{ 0, 10, 110, 111 }

(A) { 0.4, 0.35, 0.15, 0.1 } (B) { 0.35, 0.3, 0.25, 0.1 } (C) { 0.3, 0.3, 0.3, 0.1 } (D) { 0.25, 0.25, 0.25, 0.25 }

(E) None of these