Faculty of Computer Studies
M180
Data Structures and Algorithms in Java
Mid-Term Assessment (MTA)
Fall – 2013
Saturday 17, November 2012
Number of MTA Pages:
(including this cover sheet)
( 3 ) Time Allowed:
( 2 ) Hour
Instructions:
1- Write all your answers on the same exam paper.
2- Electronic devices (especially calculators) are not allowed.
Question Type
Max.
Mark
Part 1: Multiple Choice Questions
10
Part 2: Short questions
20
Part 3: Coding questions
30
Total
60
Student Mark
M180
Midterm-Ex am
Fall 2012-2013
PART 1: ALL QUESTIONS ARE REQUIRED [10 Marks]
Question 1: Choose the correct answer: (10 marks, one mark each)
1)
a)
b)
c)
d)
One of the following methods return the top of the stack without applying any modifications: pop( ) push( ) peek( ) isEmpty( )
2)
a)
b)
c)
d)
Two main measures for the efficiency of an algorithm are:
Processor and memory
Time and space
Complexity and capacity
Data and space
3)
a)
b)
c)
d)
A doubly nested “for loop” typically takes time in:
Θ(n2)
Θ(n)
Θ(log n)
Θ(log n2)
4)
a)
b)
c)
d)
Arrays are best data structures:
For relatively permanent collections of data
For the size of the structure and the data in the structure are constantly changing
For both of above situation
For none of above situation
5) The elements of an array are stored successively in memory cells because:
a) The architecture of computer memory does not allow arrays to store other than serially
b) By this way computer can keep track only the address of the first element and the addresses of other elements can be calculated
c) Both of above
d) None of above
6) A program P reads in 500 integers in the range [0..100] presenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies? a) An array of 100 numbers
b) An array of 500 numbers
c) An array of 50 numbers
d) A dynamically allocated array of 550 numbers
7)
a)
b)
c)
d)
The complexity of the average case of an algorithm is:
Much more complicated to analyze than that of worst case
Much more simpler to analyze than that of worst case
Sometimes more complicated and some other times simpler than that of worst case
None of above
8)
a)
b)
c)
d)
Linked lists are best suited
For relatively permanent collections of data
For the size of the structure and the data in the structure are constantly changing
For both of above situation
For none of above situation
Form A
2/5
M180
9)
a)
b)
c)
d)
Midterm-Ex am
Fall 2012-2013
Which of the following name does not relate to stacks?
LIFO
Piles
Push-down Lists
FIFO
10) The method add(E target) of the Queue interface
a) Add target to the front of the queue
b) Add target to the back of the queue
c) This method is not a member of the Queue interface
d) None of the above
PART 2: ALL QUESTIONS ARE REQUIRED [20 Marks]
Question 1: What is the output of the following operations if S is a stack and Q is a queue and both S and Q are initially empty? (6 marks)
S.push(“X”)
S.push(”F”)
Q.add(“A”)
S.push(“H”)
Q.add(S.pop( )) print (Q.remove( ))
Q.add(“G”)
S.push(Q.remove( )) print(S.pop( )) print(S.pop( ))
Answer: AHF (//2 marks for each successful letter)
Question 2: Order the following expressions from 1 to 4, where 1 represents the asymptotically smallest and 4 represents the asymptotically largest: (8 marks)
Expression
Order
n2/500
4 (//2 marks)
log n
2 (//2 marks)
500
1 (//2 marks)
nlog n
3 (//2 marks)
Question 3: What is the output of the following program? (6 marks)
ListNode list1 = new ListNode(); for (i=0; i 0){
System.out.print(list1.getFirst()+" , "); list1.removeFirst(); }
Answer: 4,3,2,1,0, (//1 mark for each successful number and 1 mark for the last comma)
Form A
3/5
M180
Midterm-Ex am
Fall 2012-2013
PART 3: ALL QUESTIONS ARE REQUIRED [30 marks ]
Question 1:
Write the Java code of a LinkedList method swap( ) that takes two integers as arguments and swaps the elements at those two positions. Your method should not traverse the list twice to find the two elements, and it should not create or destroy any nodes. (13 marks)
Answer:
public void swap(int index1, int index2) { (//1 marks) if(index1 == index2) { (//0.5 marks) return; } if(index2 < index1) { (//0.5 marks) int temp = index1; (//0.5 marks) index1 = index2; (//0.5 marks) index2 = temp; (//0.5 marks)
}
Predecessor node = this; (//0.5 marks) for (int i = 0; i < index1; i++) { (//0.5 marks) node = node.getNext();(//0.5 marks)
}
Predecessor firstPrev = node; (//0.5 marks)
ListNode first = node.getNext();(//0.5 marks) for (int i = 0; i < index2 - index1; i++) { (//0.5 marks) node = node.getNext();(//0.5 marks)
}
Predecessor secondPrev = node; (//0.5 marks)
ListNode second = node.getNext();(//0.5 marks)
ListNode temp = second.getNext();(//0.5 marks) firstPrev.setNext(second); (//0.5 marks) if(secondPrev != first) { (//1 marks) second.setNext(first.getNext());(//0.5 marks) secondPrev.setNext(first); (//0.5 marks) first.setNext(temp); (//1 marks)
} else { second.setNext(first); (//0.5 marks) secondPrev.setNext(temp); (//0.5 marks)
}
}
Question 2:
Find the total running time of the following methods (justify your answers): (10 marks)
A.
1 public int size() {
2
int tally = 0;
3
for (ListNode node = front;
4
node != null;
5
node = node.getNext()) {
6
tally++;
7
}
8
return tally;
9 }
//
//
//
//
//
//
1
1
1
1
1
1
step, step, step, step, step, step, once once (//0.5 marks) once n + 1 times (//0.5 marks) n times (//0.5 marks) n times (//0.5 marks)
// 1 step, once
Answer: O(n+1) = O(n) (//3 marks)
Form A
4/5
M180
Midterm-Ex am
Fall 2012-2013
B.
1 /** Return the sum of the elements of matrix. */
2 public static double sum(double[][] matrix) {
3
double result = 0;
4
for (int i = 0; i < matrix.length; i++) {
5
for (int j = 0; j < matrix[i].length; j++) {
6
result += matrix[i][j];
7
}
8
}
9
return result;
10 }
//
//
//
//
//
once once (//0.5 marks) n + 1 times (//0.5 marks) n(n + 1) times (//0.5 marks) n * n times (//0.5 marks)
// once
Answer:
O(n*n) = O(n2) (//3 marks)
Question 3:
You are given a Stack class and a Queue class. The following functions are available for use: (7 marks) public public public public
}
class Stack { boolean isEmpty(){}; void push(int n){}; int pop(){};
public public public public }
class Queue { boolean isEmpty(){}; void add(int n){}; int remove(){};
Write a method reverseQueue that takes a (Queue myQueue), as an input and reverses the order of elements in myQueue. You are only allowed to use Stack and Queue objects in your method.
Answer:
public void reverseQueue(Queue myQueue) { (//2 marks)
Stack tmpStack = new Stack();(//1 marks) while (!myQueue.isEmpty())(//1 marks)
{
tmpStack.push(myQueue.remove());(//1 marks)
}
while (!tmpStack.isEmpty())(//1 marks)
{
myQueue.add(tmpStack.pop());(//1 marks)
}
}
Form A
5/5 