Picture of Alan TuringAlan Turing
Started onWednesday, 23 July 2014, 12:20 PM
StateFinished
Completed onWednesday, 23 July 2014, 1:31 PM
Time taken1 hour 10 mins
GradeNot yet graded

Information

Not flagged

Information text

This is the exam for the first "Prüfungszeitraum" for Informatik 2 in the SS 2014.

It covers a wide spectrum of the various topics we covered this term, with 23 questions alltogether and 60 points to achieve - remember that there is enough slack in the grading that you can get a 1.0 without getting all the points here!

As announced, you can use one DIN A4 Sheet of handwritten "Cheat Sheet" along with plain paper and a pen to take notes. Please remove everything except that, maybe some water and your ID card from the desk.

Viel Erfolg!

 

Response history

Step Time Action State
1 23/07/14, 12:20 Started
2 23/07/14, 12:21 Seen
3 23/07/14, 13:31 Attempt finished

Question 1

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

Match the following growth rates to their Big-Oh Notation! xxx
A Correct
B Correct
C
D Correct
E Correct
F Correct
G Correct
H Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:22 Saved: A -> O (N^5); B -> O (N^3); C -> O (N^2); D -> O(2^N); E -> O (N log N); F -> O (N); G -> O (N/2); H -> O (log N) Answer saved
3 23/07/14, 13:31 Attempt finished Correct 3.00

Question 2

Correct
Mark 2.00 out of 2.00
Not flagged

Question text

What is the Big-Oh complexity for the following code!

for ( int i = 0; i < 2n; i ++)
for ( int j = i; j < n; j ++)
sum++;


NMC! Cross out all incorrect answers; leave the correct answer unchecked.

 

Select one or more:
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:23 Saved: O(log N); O(2^N); O(N log N); O(N^3); O(N^4); O(N^5); O(N); O(N!) Answer saved
3 23/07/14, 13:31 Attempt finished Correct 2.00

Question 3

Correct
Mark 2.00 out of 2.00
Not flagged

Question text

What is the Big-Oh complexity for the following code!

for ( int i = 0; i < n; i ++)
for ( int j = i; j < n*n; j ++)
sum++;

 


NMC! Cross out all incorrect answers; leave the correct answer unchecked.

Select one or more:
Correct
Correct
Correct
Correct
Correct
Correct
Correct
Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:24 Saved: O(log N); O(N); O(N log N); O(N^2); O(N^4); O(N^5); O(N!); O(2^N) Answer saved
3 23/07/14, 13:31 Attempt finished Correct 2.00

Question 4

Partially correct
Mark 2.80 out of 4.00
Not flagged

Question text

What is the complexity of a good implementation for the following tasks?

Looking up something in a HashMap

Correct

Sorting an array using SelectionSort

Correct

Accessing a specific element in a linked list

Incorrect

Searching an Item in a sorted ArrayList using Binary Search

Correct

Sorting an array using QuickSort

Correct

Searching for an element in a HashMap that is contained in it

Correct

Searching for an element in a balanced binary tree that is contained in the tree

Incorrect

Accessing a specific element in an array

Correct

Searching for an element in an unsorted linked list that is not contained in the list

Correct

Searching for an element in a balanced binary tree that is not contained in the tree

Incorrect

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:26 Saved: Sorting an array using SelectionSort -> O (N^2); Searching an Item in a sorted ArrayList using Binary Search -> O (N^2); Sorting an array using QuickSort -> O (N log N); Accessing a specific element in an array -> O (N) Incomplete answer
3 23/07/14, 12:28 Saved: Sorting an array using SelectionSort -> O (N^2); Searching an Item in a sorted ArrayList using Binary Search -> O (log N); Sorting an array using QuickSort -> O (N log N); Searching for an element in a HashMap that is contained in it -> O (1); Accessing a specific element in an array -> O (1); Searching for an element in an unsorted linked list that is not contained in the list -> O (N) Incomplete answer
4 23/07/14, 12:32 Saved: Looking up something in a HashMap -> O (1); Sorting an array using SelectionSort -> O (N^2); Searching an Item in a sorted ArrayList using Binary Search -> O (log N); Sorting an array using QuickSort -> O (N log N); Searching for an element in a HashMap that is contained in it -> O (1); Searching for an element in a balanced binary tree that is contained in the tree -> O (N log N); Accessing a specific element in an array -> O (1); Searching for an element in an unsorted linked list that is not contained in the list -> O (N); Searching for an element in a balanced binary tree that is not contained in the tree -> O (N) Incomplete answer
5 23/07/14, 12:39 Saved: Looking up something in a HashMap -> O (1); Sorting an array using SelectionSort -> O (N^2); Accessing a specific element in a linked list -> O (1); Searching an Item in a sorted ArrayList using Binary Search -> O (log N); Sorting an array using QuickSort -> O (N log N); Searching for an element in a HashMap that is contained in it -> O (1); Searching for an element in a balanced binary tree that is contained in the tree -> O (N log N); Accessing a specific element in an array -> O (1); Searching for an element in an unsorted linked list that is not contained in the list -> O (N); Searching for an element in a balanced binary tree that is not contained in the tree -> O (N) Answer saved
6 23/07/14, 13:31 Attempt finished Partially correct 2.80

Question 5

Partially correct
Mark 1.60 out of 2.00
Not flagged

Question text

What is the difference between a stack and a queue? Check all answers which are correct. Not correct! (corrected during exam)

NMC! Cross out all incorrect answers; leave the correct answer unchecked.

Select one or more:
Correct
Correct
You've been watching too much television!
Correct
The have the same signatures, but there is still a difference!
Correct
Nonsense, a queue is an algorithm, too!

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:29 Saved: Both a stack and a queue are FIFA.; Only a stack can be implemented by using a linked list.; There is no difference between a stack and a queue because they have the same signatures.; A stack is a data structure, but a queue is an algorithm.; A stack is LIFO, a queue is FIFO. Answer saved
3 23/07/14, 12:33 Saved: A stack is FIFO, a queue is LIFO.; Both a stack and a queue are FIFA.; There is no difference between a stack and a queue because they have the same signatures.; A stack is a data structure, but a queue is an algorithm.; A stack is LIFO, a queue is FIFO. Answer saved
4 23/07/14, 12:33 Saved: A stack is FIFO, a queue is LIFO.; Both a stack and a queue are FIFA.; There is no difference between a stack and a queue because they have the same signatures.; A stack is a data structure, but a queue is an algorithm. Answer saved
5 23/07/14, 13:31 Attempt finished Partially correct 1.60

Question 6

Complete
Marked out of 2.00
Not flagged

Question text

What is the difference between the abstract data types Set and Map?

Ein Set ist eine mathematische Menge. Sie kann ein Element nur einmal enthalten.

Eine Map hat immer einen Key und einen Value. Kann also auch Elemente mehrmals enthalten (Mappen).

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:40 Saved: Ein Set ist eine mathematische Menge. Sie kann ein Element nur einmal enthalten. Eine Map hat immer einen Key und einen Value. Kann also auch Elemente mehrmals enthalten (Mappen). Answer saved
3 23/07/14, 13:31 Attempt finished Complete

Question 7

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

What type of collection would you use to implement a ...
dictionary? Correct
determining which nodes of a graph have been visited? Correct
the change a drinks machine gives back to you? Correct
gradebook? Correct
the Lotto numbers? Correct
index of terms found in a text? Correct
prime factorization? Correct
telephone book? Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:31 Saved: dictionary? -> map; determining which nodes of a graph have been visited? -> set; the change a drinks machine gives back to you? -> bag; gradebook? -> map; the Lotto numbers? -> set; index of terms found in a text? -> set; prime factorization? -> bag; telephone book? -> map Answer saved
3 23/07/14, 13:31 Attempt finished Correct 3.00

Question 8

Correct
Mark 1.00 out of 1.00
Not flagged

Question text

What is the correct Java syntax for declaring a map for mapping a String to a Double?

Select one or more:
Correct
Correct!
Correct
Correct!

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:34 Saved: Map<String,Double>; TreeMap<String><Double> foo;; HashMap(String, Double) foo;; HashMap<String,Double>; HashMap<String><Double> foo; Answer saved
3 23/07/14, 12:41 Saved: HashMap<String,Double> foo;; Map<String,Double> foo; Answer saved
4 23/07/14, 13:31 Attempt finished Correct 1.00

Question 9

Complete
Marked out of 2.00
Not flagged

Question text

Given the following definition for a node:
public class Node {
   private Object data;
   private Node next;
   public Node (Object data, Node next) { this.data = data; this next = next;}
   public Node (Object data) {this.data=data;}
  } 

and a list anchor as a class variable in the class which contains the method insert:

Node first;

Give syntactically correct Java code to complete this method for deleting an Object from the list!

public void delete (Object obj){
 // What goes here?
}




if (first == null){

break;

}

If (first == obj){

remove first;

} else if(first.next() == obj) {

remove first.next();

} else {

        first = first.next();

public void delete (obj);

}

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:15 Saved: if (first == null){ break; } If (first == obj){ remove first; } else if(first.next() == obj) { remove first.next(); } else {         first = first.next(); public void delete (obj); } Answer saved
3 23/07/14, 13:31 Attempt finished Complete

Question 10

Complete
Marked out of 3.00
Not flagged

Question text

What does method xxx return? What is the condition that must be met that it works properly?

 public class Node { int data; Node x; Node y; }
 public Node xxx(int i, Node n) {

   if (n == null) return n;
   if (n.data > i) {return xxx(i, n.x);};
   if (n.data < i) {return xxx(i, n.y);};
   return n;
  }
  

XXX sucht nach einer Node mit einem bestimmten int data .

Die gesuchte int data wird als int i Parameter in XXX übergeben um dort mit der Data von Node n verglichen zu werden. Ist keine Data vorhanden wird die momentane Node zurückgegeben, ansonsten wird geschaut ob n.data kleiner oder größer des gesuchten i Wertes ist und dann rekursiv wieder mit der nächsten verlinkten x oder y Node aufgerufen.

XXX returned die Node die unsere gesuchte data gespeichert hat.

Um zu garantieren dass die Methode richtig funktioniert muss die node n eine verwiesene Node x und Node y besitzen.

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:01 Saved: XXX sucht nach einer Node mit einem bestimmten _int data ._ Die gesuchte int data wird als int i Parameter in XXX übergeben um dort mit der Data von Node n verglichen zu werden. Ist keine Data vorhanden wird die momentane Node zurückgegeben, ansonsten wird geschaut ob n.data kleiner oder größer des gesuchten i Wertes ist und dann rekursiv wieder mit der nächsten verlinkten x oder y Node aufgerufen. XXX returned die Node die unsere gesuchte data gespeichert hat. Um zu garantieren dass die Methode richtig funktioniert muss die node n eine verwiesene Node x und Node y besitzen. Answer saved
3 23/07/14, 13:31 Attempt finished Complete

Question 11

Complete
Marked out of 3.00
Not flagged

Question text

Define the following terms as they pertain to a graph:

1. vertex
2. edge
3. path

A Vertex is a point within a path. It can be source and destination of an edge. It can also contain an ID.

An Edge connects 2 vertices. It can also have a weight parameter attached to it.

A path is the list of edges and vertices.

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:39 Saved: A Vertex is a point within a path. It can be source and destination of an edge. It can also contain an ID. An Edge connects 2 vertices. It can also have a weight parameter attached to it. A path is the list of edges and vertices. Answer saved
3 23/07/14, 13:31 Attempt finished Complete

Question 12

Complete
Marked out of 3.00
Not flagged

Question text

What is recursion? Give a definition in natural language and then write a syntactically correct and terminating method in Java! xxx

Wenn man von einer rekursiven Methode spricht meint man, dass diese sich selber wieder aufruft. Eine Rekursion braucht immer eine Abbruchbedingung.

public void komischerCounter(int j){

for (int i = 0; i > j; i++){

j--;

komischerCounter(j);

}

}

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:42 Saved: Wenn man von einer rekursiven Methode spricht meint man, dass diese sich selber wieder mit anderen Parametern aufruft. Eine Rekursion braucht immer eine Abbruchbedingung.  Answer saved
3 23/07/14, 13:19 Saved: Wenn man von einer rekursiven Methode spricht meint man, dass diese sich selber wieder aufruft. Eine Rekursion braucht immer eine Abbruchbedingung. public void komischerCounter(int j){ for (int i = 0; i > j; i++){ j--; komischerCounter(j); } } Answer saved
4 23/07/14, 13:31 Attempt finished Complete

Question 13

Incorrect
Mark 0.00 out of 2.00
Not flagged

Question text

Which of the following rules are part of an inductive definition of a regular expression? Check all that apply! There will be points taken off for checking wrong answers.
Select one or more:
Correct
Yes, this is the Kleene star.
Incorrect
No idea what this is supposed to be :)
Incorrect
Sorry, no idea what this is supposed to be.

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:31 Saved: if R is a RE, then R* is a RE.; if R and S are RE, then {R} # {S} is a RE; if R is a RE, then R^ is a RE. Answer saved
3 23/07/14, 13:31 Attempt finished Incorrect 0.00

Question 14

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

Given the following tree. In what order will the nodes be printed out if the tree traversal is in ...

xxx

inorder

Correct

pre-order

Correct

level order

Correct

post-order

Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:45 Saved: inorder -> A-B-C-D-E-F-G-H-I-J-K-L; pre-order -> G-C-B-A-E-D-F-I-H-K-J-L; level order -> G-C-I-B-E-H-K-A-D-F-J-L; post-order -> A-B-D-F-E-C-H-J-L-K-I-G Answer saved
3 23/07/14, 13:31 Attempt finished Correct 3.00

Question 15

Complete
Marked out of 2.00
Not flagged

Question text

What is the complexity of a brute force string searching algorithm that matches a pattern in a text by iterating through the text, checking for each possible match position if the pattern matches in this position?

Knuth Morris Pratt and Boyer-Moore are algorithms that improve string searching to O(n) on average. What is the basic idea behind these algorithms?

  Worst Worst Case Worst Case Avg.
Brute Force O(N) O(N) O(N)

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:04 Saved:   Worst Worst Case Worst Case Avg. Brute Force O(N) O(N) O(N) Answer saved
3 23/07/14, 13:31 Attempt finished Complete

Question 16

Partially correct
Mark 1.50 out of 3.00
Not flagged

Question text

Consider the Finite State Automaton below. Which are words of its language? (half are, other half are not.)  (three are, other five are not.)

 

xxx

Select one or more:
Correct
Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:47 Saved: steve@apple.com; jeff@amazon.wherever Answer saved
3 23/07/14, 13:31 Attempt finished Partially correct 1.50

Question 17

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

Given two objects in Java referenced by a and b. If you have the following code in your program, is there a possibility that it can be in a dead lock?

 
synchronized(a){
  synchronized(b){
    // .... something is done here ....
  }
}


synchronized(b){
  synchronized(a){
    // .... something is done here ....
  }
}
Select one:
Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:47 Saved: True Answer saved
3 23/07/14, 13:31 Attempt finished Correct 3.00

Question 18

Partially correct
Mark 0.60 out of 3.00
Not flagged

Question text

What properties must a pseudorandom number generator in the interval [i,j] have to be considered sufficiently random? Check all that apply.
Select one or more:
Correct
Correct.
Correct
Yes, they must be uniformly distributed.
Incorrect
No - this would be a pattern we could depend on, as even numbers have a 0 in the least significant bit, odd ones have a 1.

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:08 Saved: The average of all the numbers generated is (j-i+1)/2 .; Each number in the intervall [i,j] is equally likely.; The numbers must alternate even/odd. Answer saved
3 23/07/14, 13:31 Attempt finished Partially correct 0.60

Question 19

Not answered
Marked out of 2.00
Not flagged

Question text

How can Random Numbers be used to obtain an approximation of PI?

Describe an algorithm with your own words or give it in pseudo or java code.

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:31 Attempt finished Not answered

Question 20

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

What is the complexity of the following sorting algorithms?
Shell sort Correct
Insertion Sort Correct
Selection sort Correct
Heapsort Correct
Quicksort Correct
Bogosort Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:50 Saved: Insertion Sort -> O(N^2); Selection sort -> O(N^2); Heapsort -> O(N log N); Quicksort -> O(N log N); Bogosort -> O(N!) Incomplete answer
3 23/07/14, 13:09 Saved: Shell sort -> O(N^2); Insertion Sort -> O(N^2); Selection sort -> O(N^2); Heapsort -> O(N log N); Quicksort -> O(N log N); Bogosort -> O(N!) Answer saved
4 23/07/14, 13:31 Attempt finished Correct 3.00

Question 21

Complete
Marked out of 3.00
Not flagged

Question text

Explain in complete sentences how the quicksort algorithm works.

The quicksort algorithm wants to sort values. By taking the divide and conquer method it determines which of the given numbers should be sorted on the decreasing or increasing side of the Mittelwert

 

 

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 13:24 Saved: The quicksort algorithm wants to sort values. By taking the divide and conquer method it determines which of the given numbers should be sorted on the decreasing or increasing side of the _Mittelwert_   Answer saved
3 23/07/14, 13:27 Saved: The quicksort algorithm wants to sort values. By taking the divide and conquer method it determines which of the given numbers should be sorted on the decreasing or increasing side of the _Mittelwert_     Answer saved
4 23/07/14, 13:31 Attempt finished Complete

Question 22

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

Which of the following are properties of a binary search algorithm? Check all that apply.
Select one or more:
Correct
Correct!
Correct
Correct! Binary search has a complexity of O(log N).

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:51 Saved: It only works on sorted arrays.; It is faster than linear search. Answer saved
3 23/07/14, 13:31 Attempt finished Correct 3.00

Question 23

Correct
Mark 3.00 out of 3.00
Not flagged

Question text

Given a hash table of size 13, that is, m=13.
With the hash function h(k) = k mod m and linear probing collision resolution h(k,i) = (h(k) + i) mod m using the step size of 1 for the linear probing, what values are in the following cells after this sequence has been hashed:

16, 13, 12, 30, 19, 43, 24, 50, 39
0 Correct
1 Correct
2 Correct
3 Correct
4 Correct
5 Correct
6 Correct
7 Correct
8 Correct
9 Correct
10 Correct
11 Correct
12 Correct
13 Correct

Feedback

Response history

Step Time Action State Marks
1 23/07/14, 12:20 Started Not yet answered
2 23/07/14, 12:51 Saved: 0 -> 13; 1 -> 50; 2 -> 39; 3 -> 16; 4 -> 30; 5 -> 43; 6 -> 19; 7 -> empty; 8 -> empty; 9 -> empty Incomplete answer
3 23/07/14, 12:52 Saved: 0 -> 13; 1 -> 50; 2 -> 39; 3 -> 16; 4 -> 30; 5 -> 43; 6 -> 19; 7 -> empty; 8 -> empty; 9 -> empty; 10 -> empty; 11 -> 24; 12 -> 12; 13 -> no such index Answer saved
4 23/07/14, 13:31 Attempt finished Correct 3.00