UNIVERSITY OF TORONTO Faculty of Arts and Science April/May Examinations, 1993 CSC 108S Duration: 2 Hours No Aids Allowed Note that the marks on this exam total 90. When the response to a question requires you to write a program, your marks will depend on the style of your program as well as its correctness. 1. [10 marks] Put the letter of the item that best matches the term. __ open a. Connect program to a file __ bind b. Known only in the current scope __ write c. Returns the next integer above or equal to its argument __ Shell sort d. Locates a substring in a string __ dynamic array e. Order of expression evaluation __ local variable f. Output to a file, using internal format __ procedure g. Similar to remainder __ function h. Largest pixel position to the right __ upper i. Give a new name to a variable __ pre j. Its returned value can be used in an expression __ include k. Has blanks on left to given width __ ceil l. No more characters (bytes) in the file __ boolean m. Can be used as a statement (is defined by programmer __ mod n. Size of array (if lower bound is 1) __ right justified o. Standard encoding of characters __ index (function) p. A type for true/false values __ eof q. Copies a file so it becomes part of your program __ maxx r. Must be true at beginning of subprogram __ ASCII s. Its size not known until run time __ precedence t. Fast method of putting an array in order 2. [10 marks] Beneath this program, show what it outputs when it runs. var i : int :=70 var x : real :=128.0 loop if x < 50.0 then x :=4.0 * x i :=i + 10 end if if i > 15 then x :=x / 2.0 i :=i - 20 end if put i:3, x:3 exit when i < = 0 end loop put "All done" ____________________ Give the program's output here: 3. [10 marks] Beneath this program, show what it outputs when it runs. var stuff : string := "1, 2, Buckle my shoe" var letter : string (1) for i : 1 .. length (stuff) const L := stuff (i) put L .. if index ("0123456789",L) not= 0 then stuff := stuff (1 .. i - 1) + "n" + stuff (i + 1 .. *) put "->n" .. elsif "A" <= L and L<= "Z" then letter := chr (ord (L) - ord ("A") + ord ("a") ) stuff := stuff (1 .. i - 1) + letter + stuff (i + 1 .. *) put "->", letter .. end if end for put skip, stuff ____________________ Give the program's ouput here: 4. [10 marks] Beneath this program, show what it outputs when it runs. procedure good (var loc : array 1 .. * of int, name : array 1 .. * of string (*) ) assert upper (loc) = upper (name) for decreasing i : upper (loc) - 1 .. 1 for j : 1 .. i if name (loc (j) ) < name (loc (j + 1) ) then % Swap loc (j) and loc (j + 1) const t := loc (j) loc (j) := loc (j + 1) loc (j + 1) := t end if end for put i + 1, " ", loc (i+1), " ", name (loc (i + 1) ) end for put 1, " ", loc (1), " ", name (loc (1) ) end good var friend : array 1 .. 7 of string (20) := init ( "Al", "Bob", "Cathy", "Doug", "Earl", "Fred", "Gail") var where : array 1 .. 7 of int (20) := init (1, 2, 3, 4, 5, 6, 7) good (where, friend) put "======" for i : 1 .. 7 put i, " ", where(i), " ", friend (where(i) ) end for ____________________ Give the program's output here: 5. [10 marks] The marks for the students in a class are kept in a file, with each line of the file contaiing an integer mark followed by the student's name. Each student has only one mark, and every name is in quotation marks. Write a Turing program to read the file from standard input and print on the standard output: * the average mark for the whole class; * the name of the student with the highest mark; * the number of marks below 50. There is no sentinel name, so your program must explicitly check for end- of-file. 6. [10 marks] Complete the following Turing procedure: procedure RowSun (A : array 1 .. 5, 1 .. 3 of real, var T : array 1 .. 5 of real) Each entry in T is to be given the sum of the entries in the corresponding row of A. 7. [10 marks] Write a Turing program to read tokens ("words") from the standard input and count the number of tokens of each length up to 10. For example, consider this sequence of tokens: Hi there, Jim! I'll be off now. Here we see 7 tokens: 2 of length 2, 1 of length 3, 3 of length 4 and 1 of length 6. (Punctuation is not to be distinguished from letters.) Your program should output this information, arranged in any format you like. It is acceptable to print messages like "There are 0 words of length 5." Tokens of length greater than 10 should all be counted together. 8. [20 marks] The year is 1993. You rlocal computer science department hopes to begin keeping track of its graduates so as to ask them for money regularly. You are helping to set up a Turing program that will maintain a simple database of the graduates. The "database" will consist of an array of records, with one record for each graduate. The record for each graduate includes this information: * name * year of graduation * year of last donation * amount of last donation The department expects never to have more than 500 graduates in the database, though the number will fluctuate. a) Write the declarations fro the data structures (the array and asociated variables). b) Write the part of a program that initializes the data structures to the initial state (containing NO information about graduates). c) Write a prodecure to add a new record to the database. Your procedure is to read the name, year of graduation, ect., by prompting the user at the keyboard. New graduates are added when they graduate, when they may not yet have made a donation. Use the data structures declared in part (a), and assume that they already contain the database in the state before the new record is added. d) Write a procedure to print the names of all graduates whose last donation was more than $10. Assume the program is to run in 1993, and that all the data on donations for the previous twenty years has been stored in the data structures declared as in part (a). Your answer here must be compatible with your answers to earlier parts of the question. e) Write a procedure to store the database in a file called "grads."