CIT 595 – Spring 2016
Practice Questions for Exam #2
This document contains questions that you can use to practice for the second exam.
This is not a “sample exam”!! Nothing should be inferred about the length of the exam, the difficulty
level of the exam, or the type of questions on the exam that you will take. This is simply a collection of
questions that have been used in the past or that are indicative of the types of questions you can expect.
C++ Operator Overloading, STL, and Templates
Questions #1 - 3 refer to the following class, which represents an int array and its size:
class MyArray {
private:
int* p;
int size;
public:
MyArray(int s) {
p = new int[s];
size = s;
}
MyArray(int A[], int s) {
p = new int[s];
// note that you can't just do p = A!!
for (int i = 0; i < s; i++) p[i] = A[i];
size = s;
}
~MyArray() {
delete p;
}
};
The code below is attempting to use operator overloading when using the MyArray class:
1
2
3
4
5
6
7
8
9
10
11
12
int main() {
int array1[] = { 6, 3, 1, 0 };
MyArray m(array1, 4);
m[3] = 8;
int y = 9;
m << 4 << y;
int array2[] = { 2, 4, 8 };
MyArray n(array2, 3);
m += n;
}
Implement the overloaded operators on the following pages.
You can assume that you are implementing each method inside the MyArray class definition.
Question #1
Implement the method needed for overloading the [] operator so that line 4 sets the element with the
specified index to the specified value.
If the specified index is negative or outside the range of the array size, throw an exception using -1 as
the value.
Question #2
Implement the method needed for overloading the << operator so that line 7 adds the specified value to
each element of the array. Note that you should be able to chain together multiple uses of this operator
as shown on line 7.
Question #3
Implement the method needed for overloading the += operator so that line 11 appends the elements of
the array in n to the array in m.
In this case, after executing line 11, the array in m should have 7 elements: the 4 that were already
there, followed by the 3 elements from n.
Be sure to update any other variables, clean up memory, etc. as needed.
Question #4
On the next page, implement a C++ class called Polynomial that represents a polynomial such as
f(x) = 5x^10 + 9x^7 – x – 10
Store the polynomial as a collection of "terms". A "term" contains the coefficient and the power of x.
For example, the terms for the function above would be stored as:
(5, 10), (9, 7), (-1, 1), (-10, 0)
The constructor should take two integers, representing the coefficient and the power of x for one of the
terms in the polynomial.
You should also implement these methods in the class:
• add(int coefficient, int power): adds another term to the polynomial; if there is already a term in
the polynomial with this power, simply add the coefficients
• evaluate(long x): evaluates the polynomial for the value of x and returns it as a long
For simplicity, you do not need to worry about importing classes or anything like that. You may use
STL classes (hint, hint!) in your implementation.
Question #5
While working on a C++ project, you come across the following class definitions and usage:
class IntPair {
private: int x, y;
public:
IntPair() { }
IntPair(int x, int y) {
this->x = x;
this->y = y;
}
int& getX() { return x; }
int& getY() { return y; }
};
class StringPair {
private: string a, b;
public:
StringPair() { }
StringPair(string a, string b) {
this->a = a;
this->b = b;
}
string& getA() { return a; }
string& getB() { return b; }
};
class PairOfPairs {
private:
StringPair sp;
IntPair ip;
public:
PairOfPairs() { }
PairOfPairs(StringPair sp, IntPair ip) {
this->sp = sp;
this->ip = ip;
}
StringPair& getStringPair() { return sp; }
IntPair& getIntPair() { return ip; }
};
IntPair ip(3, 2);
cout << ip.getX() << endl;
StringPair sp("cat", "dog");
PairOfPairs* pop = new PairOfPairs(sp, ip);
doSomething(pop);
Using C++ templates, define a new template class called “Pair” that could be used in place of these
three classes, and then rewrite the code that uses the old classes so that it uses your new template class.
Note that you may need to change some of the method names.
// create the template class here
// rewrite the code so that it uses the template
Scheduling
Question 1
Consider the list of processes from the table below. Assume each process is completely CPU-bound.
Process Arrival
Time
Processing
Time
Priority
P1 0 4 1 – least important
P2 6 3 2
P3 4 6 3
P4 2 2 4 – most important
Determine the average turnaround time using a Preemptive Priority scheme, in which a newly-
arriving process with a higher priority than the executing one is handled immediately (discounting any
time for context switching), and all other processes are handled according to their priority.
What would the average turnaround time be if a non-preemptive First Come First Serve scheduling
scheme (ignoring priority) were used instead?
Question 2
Assume five processes arrive at time zero in the following order: P1, P2, P3, P4, P5
Process Execution Time Priority
P1 4 2
P2 1 4
P3 2 2
P4 1 1
P5 5 3
Determine the average wait time for non-preemptive priority scheduling scheme where a higher
priority number implies a higher priority (more important). Ignore the context switching overhead.
Caching
Question 1
You are working for a company that produces a microprocessor that has a 16kB cache with an access
time of 4ns (a nanosecond is 10-9 seconds) and an average hit rate of 80%. It is used in a system that
has a main memory of 32MB and an access time of 50ns.
Your boss knows that you took CIT 595 and asks you how to improve the effective access time, giving
you three options:
a. Implement a new cache replacement algorithm that will improve the cache hit rate to 90%.
b. Use faster hardware to reduce the cache access time to 3ns.
c. Increase the size of main memory to 64MB.
Disregarding cost and power consumption, which one of the three choices would provide the greatest
improvement to the effective memory access time? Why?
Question #2
Consider a two-level caching scheme in which the system first looks in one cache (the first level cache)
for data; if the data is not there it looks in another cache (the second level cache); and then if it is not
there either it goes to main memory.
Suppose the following:
• the first level cache has a size of 1KB, a hit rate of 70%, and an access time of 4ns
• the second level cache has a size of 16KB, a hit rate of 80%, and an access time of 8ns
• main memory has a size of 2GB, and an access time of 20ns
What is the average memory access time (or, “effective access time”) for this system?
Question #3
Consider a system with the following specifications:
• 12-bit address space
• 8-bit word
• 32-word block
• 4-block fully associative cache
• LRU cache replacement algorithm
Assume that the cache is initially empty, and the following sequence of memory accesses occurs:
x7AE
x7A0
x7AE
x4BC
x4AC
x7B3
x620
x61F
x640
x4AC
What is the hit rate?
Which tags are in each cache line when the sequence is finished?
Line number Tag
0
1
2
3
Virtual Memory
Question #1
Consider a system that uses virtual memory as follows:
• 32-bit address space
• byte addressable
• 1GB of physical memory
• 218 entries in the page table
What is the size (in bytes) of each page?
How many frames are there in physical memory?
Consider the virtual address xABCDEF01. Which (if any) of the following addresses are in the same
page? There may be more than one! And there may be none!
xABCDEFFF
xABCDEC05
xABCCEF01
xABCDEEEE
Question #2
Consider a system that uses virtual memory and that uses hardware with the following latency (time
delay):
• handling a TLB hit: 2ns
• handling a TLB miss: 20ns
Assuming the TLB is initially empty and uses an LRU replacement scheme, what is the minimum size
TLB such that the average time to translate a page number to a frame number is 12ns for the following
sequence of page numbers?
Page #0
Page #1
Page #0
Page #0
Page #2
Page #1
Page #0
Page #4
Page #1
Page #1