Page 1
DAP 1 – 11.8.2021
module
Data structures, algorithms and programming 1
Summer semester 2021
Exam – 11.8.2021
5:00 p.m. – 7:30 p.m.
This is the exam for the module data structures, algorithms and programming 1 (DAP 1) im
Summer semester 2021. You have 120 minutes to complete the exam. Additionally stand
You have another 30 minutes to digitize and upload your submission. Overall must
the exam can be submitted digitally in Moodle by 7:30 p.m. at the latest , i.e. 150 minutes after it was issued
will. Delayed submissions will not be taken into account.
The submission must take place as exactly one file of the type PDF. You can deliver your donations by hand
in writing as well as directly digitally, whereby the use of tools for program or
Diagrams or for digitizing handwriting (e.g. tablets) are allowed. Uploading
of archive formats (such as .zip, .7z, etc.) is explicitly not permitted and is prevented by Moodle. the
Submissions must be legible and may only contain one processing per task.
Your first name, last name and matriculation number must be at the beginning of the first page of your submission
stand. The name of the file with its submission must conform to the following naming scheme:
DAP1_01_
By starting editing, you confirm that you have
• are entitled to take the exam through proper registration,
• will take the exam yourself,
• will carry out the test independently,
• will not communicate with other people during the exam,
• During the exam, the tasks or the associated processing are not for other people
will make accessible
• will generally behave in compliance with the exam and
• are capable of health examinations.
Attempts to cheat will be punished according to the examination regulations that apply to you.
You only have access to this exam after submitting several affidavits
Page 1 of 4 Exam DAP 1 – 11.8.2021
obtain. A violation of these affidavits can result in criminal penalties.
Page 2
Task 1
[4 points] Add the values 14 , 35, 22, 41 and 84 in exactly that order to each of the below
given binary search trees.
exercise 2
[5 points] The syntax diagram describes what a valid expression may look like.
87
19th
12th
53
54
6831
9910
Expression
(
+
Y
)
page 2 of 4 Exam DAP 1 – 11.8.2021
DAP 1 – 11.8.2021
Enter four character strings that make up a valid expression and one of the
meet the following conditions:
a) The expression contains the character Y at least twice .
b) The expression contains at least two + characters .
c) The expression contains at least twice the symbol ( and at least twice the symbol Y .
d) The expression consists of exactly ten characters and contains exactly four times the character ).
e) The expression consists of exactly eight characters .
Task 3
[12 points] Create a method public static int biggerThan (int [] allInts, int p) .
The biggerThan method returns the smallest value from allInts that is greater than p . Is there no
such a value, an exception of the class IllegalStateException is thrown.
Page 3
Task 4
[8 points] Create a method
public static
The size method returns the number of contents contained in structures .
Note: See slide 941 of the lecture slides for the summer semester 2021.
Task 5
[8 points] Create a method
public static
The max method returns the largest content of allObjects . If allObjects has no content,
should return null .
Note: See slide 941 of the lecture slides for the summer semester 2021.
Exercise 6
[16 points] The well-known class DoublyLinkedList
When implementing the required method, the class DoublyLinkedList
which is provided in the program examples from Chapter 12 .
Create the public DoublyLinkedList
The cutInFrontOf method returns a newly created list. The new list contains unchanged
Order of all elements of the executing list that are before the first occurrence of the content obj .
These elements should also be removed from the executing list. The comparison with the content
is done with the equals method . If the content obj is not in the executable list, a
page 3 of 4 Exam DAP 1 – 11.8.2021
DAP 1 – 11.8.2021
returned empty list.
Exercise 7
[16 points] The well-known class DoublyLinkedList
When implementing the required method, the class DoublyLinkedList
which is provided in the program examples from Chapter 12 .
Create the public int countDoubles () method .
The method count doubles are the number of content back to the executive list exactly
occur twice . The contents are compared with the equals method .
Exercise 8
[16 points] The known class BinarySearchTree
Method can be supplemented. When implementing the required method, the class
BinarySearchTree
Chapter 12 is provided.
Create the public int deleteLeavesAbove (int level) method .
The method deleteLeavesAbove deletes all the leaves from the tree, which is above the level level are
– so on a level with a smaller number. The number of sheets deleted is returned.
The root is on level 0 . If a negative argument is passed, an exception is made for the class
IllegalStateException thrown.
Page 4
Exercise 9
[15 points] The interfaces BoolFunction , IntFunction and the class Data are given .
public interface BoolFunction { public interface IntFunction {
boolean apply ( int x, boolean b); int apply ( int x, int y);
} }
public class data
{
private int [] intValues;
public data ( int [] iV) {
intValues = iV;
}
public boolean test (BoolFunction f, boolean init) {
boolean check = init;
for ( int v: intValues) {
check = f.apply (v, check);
}
return check;
}
Page 4 of 4 Exam DAP 1 – 11.8.2021
DAP 1 – 11.8.2021
public int make (IntFunction f, int init) {
int result = init;
for ( int v: intValues) {
result = f.apply (v, result);
}
return result;
}
}
Note: In the following description of tasks, the name intValues is always used as a short form
used when the intValues attribute of the Data object passed as an argument is meant.
Create the following three methods outside of the Data class . If you from the class data , the
When using the test and make methods, the arguments for the parameter f are only lambda
Use expressions .
a) Create a static int sizeIf (Data d, int p) method .
The sizeIf method returns the length of intValues , if intValues at least once
Contains value p . If intValues does not contain the value p , -1 is returned.
b) Create a static boolean containsIf (Data d, int p) method .
The method containsIf are true back if all intValues values contained greater than p are
and at least one of these values is greater than 2 * p . Otherwise false is returned.
c) Create a static int multiplyIf (Data d, int limit) method .
The multiplyIf method returns the product of all values from intValues if the length of
intValues is less than limit . Otherwise 0 is returned.