## 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