## Question 16

Which of the following is the correct order of execution of computer instructions?

a) Reading the operand → Decoding the instruction → Fetching the instruction → Executing the instruction.
b) Reading the operand → Fetching the instruction → Decoding the instruction → Executing the instruction.
c) Decoding the instruction → Fetching the instruction → Reading the operand → Executing the instruction.
d) Fetching the instruction → Decoding the instruction → Reading the operand → Executing the instruction.

## Question 15

When the algorithms shown in the following two flow charts are executed for a positive integer M, which of the conditions below should be entered into “a” to obtain equal result values for x. a) n > M
b) n > M + 1
c) n > M – 1
d) n < M

## Question 14

For integers x, y (x>y0), the function F(x,y) is defined as follows

Which of the following is the value of F(231, 15)? Here, x mod y represents the remainder obtained when dividing x by y.

 F(x,y)= x (when y=0) F(y,x mod y) (when y>0)

a) 2
b) 3
c) 5
d) 7

## Question 13

A hash table is used to control data items whose keys are natural numbers. The hash value h(x) of the key x is expressed as follows:

h(x) = x mod n

Here, n represents the hash table size and x mod n represents the remainder obtained when dividing x by n.
Under which of the following conditions will a conflict occur between the data item whose key is a and the data item whose key is b?

a) “a + b” is a multiple of “n”
b) “a – b” is a multiple of “n”
c) “n” is a multiple of “a + b”
d) “n” is a multiple of “a – b”

## Question 12

To sort a sequence of integers 1 through 8 in descending order using the heap sort method, the whole sequence is turted into a heap as follows:

1,4,2,5,8,3,6,7

Here, the first and last element are exchanged as follows:

7,4,2,5,8,3,6,1

Then, a procedure is executed to turn the underlined part into a heap. Which of the following represents the sequence just after the execution of the sort? Here, the heap is implemented as a complete binary tree in which the first (leftmost) element of the sequence is the root and the children of the ith element of the sequence are the 2ith and (2i + 1)th elements.

a) 2,4,3,5,8,7,6,1
b) 4,2,5,8,3,6,7,1
c) 7,4,5,8,3,6,2,1
d) 8,7,6,5,4,3,2,1

## Question 11

The following procedures show sorting of a one-dimensional array using the shell sort method. To sort a data array “7,2,8,3,1,9,4,5,6” in accordance with the procedures (1) through (4) below, how many times will procedure (3) be repeated to complete sorting? Here, the value in brackets ([ ]) represents a result value whose fractional part is truncated.

[Procedures]

(1) [Number of data items ÷ 3] → H
(2) separate the array into two sub arrays the corresponding elements of which are H elements apart ( in the original array) and sort each sub array using the insertion method.
(3) [H ÷ 3] → H
(4) If H is 0, sorting of the data array is completed. If not 0, return to (2).

a) 2
b) 3
c) 4
d) 5

## Question 10

There are two data structures: stack and queue. When the following procedures are executed sequentially, which of the following data is put into variable x? Here, the following have the meanings indicated below.
Push(y): to put data y into a stack
Pop(): to take out data from a stack
enq(y): to put data y into a queue
deq(): to take out data from a queue

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x ←  pop()

a) a
b) b
c) c
d) d

## Question 9

A rooted tree is composed of branches and nodes. Branches (edges) diverge at the special node called the “root”. At the end of each branch, new nodes where branches (edges) further diverge are added. This process is repeated to construct a rooted tree.Each node (v) of a rooted tree has three types of pointers.

Parent [v] ; Pointer to the parent of the node v
FirstChild [v] : Pointer to the first child of the node v
NextBrother [v] : Pointer to the next brother of the node v The value of the pointer that has nothing to point to is set to the value represented by the symbol NIL. Which of the following procedures is entered in when all brothers including the node v are output ? Here, the node v is not a root and “reportx” is a procedure to output the node x. While x NIL do
Report x
x ← Nextbrother [x]

a) x ← FirstChild [v]
b) x ← FirstChild [Parent [v]]
c) x ← NextBrother [v]
d) x ← NextBrother [Parent [v] ]

## Question 8

There is a program that requires T(n) seconds to solve an n-size question. The maximum size of a question which can be solved within 104 seconds using this program is about 3.2 times as large as the maximum size of a question which can be solved within 103 seconds using this program. Which of the following expressions represents T(n)?

a) 100n
b) 5n2
c) n3/2
d) 2n

## Question 7

The expression “Y=(A – B) x C” is expressed as “YAB–Cx=” in postfix notation (also known as “Reverse Polish notation”)

Which of the expressions below is equivalent to the following expression below ?
Y = (A + B) x (C – D ÷ E)

a) YAB + CDE ÷ – x =
b) YAB + C – DE ÷ x =
c) YAB + EDC ÷ – x =
d) YBA + CD – E ÷ x =