Homework Answers

The following algorithm is designed to print the beginning of what is known as the

Fibonacci sequence. Identify the body of the loop. Where is the initialization step for the

loop control? The modification step? The test step? What list of numbers is produced?

Last ← 0;

Current ← 1;

while (Current < 100) do

(print the value assigned to Current;

Temp ← Last;

Last ← Current; and

Current ← Last + Temp)

Describe a tree structure that can be used to store the genealogical history of a family. What operations are performed on the tree? If the tree is implemented as a linked structure, what pointers should be associated with each node? Design procedures to perform the operations you identified above, assuming that the tree is implemented as a linked structure with the pointers you just described. Using your storage system, explain how one could find all the siblings of a person.

The following program segment is an attempt to compute the quotient (forgetting any remainder) of two positive integers (a dividend and a divisor) by counting the number of times the divisor can be subtracted from the dividend before what is left becomes less than the divisor. For instance, 7⁄3 should produce 2 because 3 can be subtracted from 7 twice. Is the program correct? Justify your answer.

Count ← 0;

Remainder ← Dividend;

repeat (Remainder ← Remainder – Divisor;

Count ← Count + 1)

until (Remainder < Divisor)

Quotient ← Count.