M180: Data Structure and Algorithms in Java

M180: Data Structure and Algorithms in Java
Tutor-Marked Assignment (Fall 2016/2017)
Cut-Off Date:
Total Marks: 40
Contents
Warnings and Declaration………………………………………………………………………………..1
Question 1……………..……………………….………………………………………………………….2
Question 2 ………………..…………………………………………………………………………….….2
Question 3 ………….………..………………………………………………………………………….….3
Question 4 ………….…………..……………………………………………………………………….….3
Question 5………….…………..……………………………………………………………………….….4
Plagiarism Warning:
As per AOU rules and regulations, all students are required to submit their own TMA work and avoid plagiarism.
The AOU has implemented sophisticated techniques for plagiarism detection. You must provide all references
in case you use and quote another person's work in your TMA. You will be penalized for any act of plagiarism
as per the AOU's rules and regulations.
Declaration of No Plagiarism by Student (to be signed and submitted by student with TMA
work):
I hereby declare that this submitted TMA work is a result of my own efforts and I have not plagiarized
any other person's work. I have provided all references of information that I have used and quoted in
my TMA work.
Name of Student:………………………………..
Signature:…………………………………………...
Date:……………………………………………………
Arab Open University
2
Question 1: (7 marks)
As a conclusion of what you have learnt, and based on some research, you are asked to
compare between Stacks and Queues in terms of the following:
a- What is the principle used to insert/ remove an object in each data structure?
b- State the two major operations used to access data in each data structure.
c- Name one application using each type.
d- Provide a valid reference.
Question 2:(10 marks)
You are given a Node class and a List class:
public class Node
{
int data;
Node next;
Node(int d, Node n){
data = d;
next = n;
}
}
public class List {
Node header;
}
Write a Java function max2List that takes two lists list1 and list2 of the same size and
returns a list, list3, that will contain the maximum of the data between the corresponding
nodes of lists list1 and list2.
For example:
Then list3 should be:
3 7 5
header
3 7 5
list3
1 2 5
List2
List1
header
header
3
Question 3:(8 marks)
Write a recursive method that takes a stack and prints its contents recursively without using
any temporary stack. At the end of the method, the stack would become empty.
Question 4:(10 marks)
Find the total running time of the following methods (justify your answers, showing the
intermediate calculations after each line).
A.
public int SearchList(List l, int d) {
int counter = 0;
for (ListNode p = l.header.next; p != null; p = p.next) {
if(p.data==d)
counter++;
}
return counter;
}
B.
public static int SumRows(int[][] myArray) {
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray [i].length; j++) {
rowSum[i]+=a[i][j];
}
}
return rowSum;
}
4
Question 5: (5 marks)
Given the following program:
1. class recursion {
2. int func (int n) {
3. int result;
4. result = func (n - 1);
5. return result;
6. }
7. }
8. class Output {
9. public static void main(String args[]) {
10. recursion obj = new recursion() ;
11. System.out.print(obj.func(10));
12. }
13. }
a- What is the output of this program? Explain the result.
b- Include a screenshot that shows the output.
End of Assessment