Instructions: This exam is open-book. You may use your personal notes and problem set submissions, copies of any of the course Web pages, copies of the problem set solutions, and Computer Science: An Overview by Brookshear. No other materials are allowed.
You have 50 minutes for this exam. There are 5 problems. Show your work.
Use an exam booklet. Be sure that your name is on the front of the booklet and printed legibly. Write and sign the honor code pledge.
Honor Code Pledge: I pledge my honor that I have not violated the honor code during this examination.
Problem 1:(20 points)
Can an operating system allow several programs to have started
and be in the process of execution at the same time without using time slices?
That is, can an operating system provide some sort of multitasking without using time slices? If your answer is yes, how? If your answer is no,
why not?
Problem 2:(25 points)
Given an array A with n items (or elements)
A[1], A[2], ... A[n], write pseudocode
that copies array A into another array B, but in reverse order.
That is, after your pseudocode is executed, B should contain the same
items as A, but reading B from B[1] through B[n] will give the items
in the same order as reading A from A[n] through A[1].
You should try to make your pseudocode statements as much like statements in
a real programming language
as possible, but you need not use perfect Java
(or perfect any other programming
language).
Problem 3:(25 points)
Given array A as shown below, what is printed
by applying PrintsWhat to the array A with length containing the
value 7 and start containing the value 1. That is, execute
PrintsWhat(A,7,1) and show the results.
Also, show how the computation progresses by indicating when
each recursive application of PrintsWhat is begun
and when each value is printed.
PrintsWhat is a procedure specified in Java-like pseudocode.
(It is not correct Java.) Note that * denotes multiplication.
Warning: giving what is printed correctly without showing how
the execution produces that printing will not receive full credit.
PrintsWhat(int A[], int length, int start) { if ( 2*start <= length ) { temp = 2*start PrintsWhat(A, length, temp) } if ( (2*start)+1 <= length ) { temptoo = (2*start)+1 PrintsWhat(A, length, temptoo) } print A[start] }
Array A: A[1]= 22 A[2]= 13 A[3]= 9 A[4]= 8 A[5]= 5 A[6]= 3 A[7]= 6
Problem 4:(20 points)
Below are two functions (in pseudocode)
that return x^k (x raised to the power k) for arguments x and k ( k >= 0 ).
Which function is more efficient? Justify your answer. You may
do an example as part of your justification.
int PowerA(int x, int k) { result = 1 i=1 while (i <= k) { result = result * x i = i+1 } return result } int PowerB (int x, int k) { if (k <= 0) { return 1 } else { half = integer part of k/2 i.e. round k/2 down temp = PowerB(x, half) if (remainder of k/2 is 1) {result = temp * temp * x} else {result = temp * temp} return result } }Problem 5:(10 points)
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 doc.
The translation was initiated by Andrea LaPaugh on Thu Jan 7 13:13:25 EST 1999