Sample Exam #1
==============
1. Read this program carefully, and then answer the questions that
come after it.
% Return index of Key in List(1),...,List(N), if Key is present.
% Otherwise, return -1.
% Assumes List contents are sorted.
function triSearch (List:array 1..* of string, Key:string, N:int) : int
var first := 1
var last := N
loop
exit when first > last
const third := (last - first + 1) div 3
const border1 := first + third
const border2 := first + 2 * third
put "looking:", third, " ", border1, " ", border2
if Key < List(border1) then
last := border1 - 1
elsif Key = List(border1) then
result border1
elsif Key < List (border2) then
first := border1 + 1
last := border2 - 1
elsif Key = List (border2) then
result border2
else
first := border2 + 1
end if
end loop
result -1
end triSearch
const A : array 1..9 of string := init ("ant","bee","cat","dog",
"elk","fox","gnu","hog","imp")
var what : string
var howmuch : int
get what, howmuch
put triSearch (A,what,howmuch)
(a) Here are some possible inputs for the program.
For each input, indicate the corresponding output.
dog 9
cat 9
pig 9
dog 3
cat 3
ant 1
(b) If triSearch is asked to search a list of N items,
approximately how many times on average will the
function need to go through its loop? Circle the
correct answer.
2 3
N 2N N/3 N/log N N/log N log N log N N N
2 3 2 3
In one sentence, explain your answer.
2. The program below runs without errors, at least for the input
specified in part (a) and (we hope) for all other inputs that
contain no 0's. Read the program and answer the questions.
var N : int
get N
var X : array 1..N of real
for i : 1..N
get X(i)
end for
var A : array 1..N, 1..N of real
for i : 1..N
A(i,i) := X(i)
for j : i+1..N
A(i,j) := A(i,i) * X(j)
end for
for decreasing j : i-1..1
A(i,j) := A(i,i) / X(j)
end for
end for
for i : 1..N
for j : 1..N
put A(i,j), " "..
end for
put ""
end for
(a) Suppose the input is: 4 4.0 2.0 -10.0 2.4
What is the output?
In the next four parts, we want to evaluate how long the program
will take to run, by counting the number of times selected
statements are executed. In parts (b) and (c), the statements
counted are input and output commands ("get" and "put");
in parts (d) and (e), we are interested in real-number
operations instead.
(b) i. For the input specified in part (a), how many times is a
"get" statement executed? (Count ALL the "get" statements
in the program.)
ii. And how many times is a "put" statement executed?
(c) Give a formula expressing the total number of "get" and "put"
commands executed, in terms of N, the size of the array A.
(d) i. For the input specified in part (a), how many times are
real-number multiplications executed?
ii. And how many times are real-number divisions executed?
(e) Give a formula expressing the total number of real-number
operations (multiplications and division together)
executed, in terms of N, the size of the array A.
3. One of the standard predefined functions in Object Oriented Turing
is "strintok", which examines a string to see if it can be converted
to an integer. It returns true if the conversion can be done, and
false otherwise.
For example, strintok("99") is true, and so are strintok(" -5")
and strintok("+123"), but strintok("hi") and strintok("4.0") are
both false.
You can write your own function equivalent to strintok by examining
the string parameter to see if it is a valid representation of an
integer. A function myStrintok that does this is begun below.
COmplete it, without using strintok itself. (You cannot use
"strint" either, of course, because it causes an error message if
its string parameter does not represent an integer.)
You may assume that, if the string parameter does contain an
integer, it is not followed by any blank characters. Also, ther are
no blanks between the sign characters and the first digit. Even if
a sign is present, there must be at least one digit.
function myStrintok (S : string) : boolean
end myStrintok