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