I85PREP
⌘ K
Saarland Abitur Informatics - independent foundations study materials
Saarland Abitur Informatics - independent foundations study resources

Saarland Abitur Informatics - independent foundations practice questions

One question at a time. Build your Saarland Abitur Informatics - independent foundations understanding.

First 50 of 190 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Programming, object modelling and software development

In UML class diagrams, what does the '+' symbol before an attribute or method name indicate?

  1. public visibility Correct answer.
  2. private visibility
  3. protected visibility
  4. package (default) visibility

Explanation

In UML notation, '+' indicates public visibility, meaning the attribute or method is accessible from any other class.

Question 2Programming, object modelling and software development

What is 'Kapselung' (encapsulation) in object-oriented programming?

  1. Bundling data and methods within a class while restricting direct external access to internal data Correct answer.
  2. Making all attributes of a class publicly accessible with no restrictions
  3. A term unrelated to object-oriented programming
  4. A technique that only applies to database design, not programming

Explanation

Encapsulation bundles data (attributes) and the methods that operate on that data within a class, while restricting direct external access to internal data (typically via private attributes accessed through public getter/setter methods).

Question 3Programming, object modelling and software development

What is 'Vererbung' (inheritance) in object-oriented programming?

  1. A mechanism where a subclass acquires attributes and methods from a superclass Correct answer.
  2. A mechanism where two unrelated classes share no attributes or methods
  3. A term unrelated to object-oriented programming
  4. A mechanism that only works with private attributes

Explanation

Inheritance is a mechanism where a subclass (Unterklasse) acquires attributes and methods from a superclass (Oberklasse), enabling code reuse and establishing an 'is-a' relationship, represented in UML with a hollow triangle arrow.

Question 4Programming, object modelling and software development

What is 'Polymorphie' (polymorphism) in object-oriented programming?

  1. The ability of different classes to be treated through a common interface, with each class providing its own implementation of a shared method Correct answer.
  2. A term describing a class that can never be extended by subclasses
  3. A concept unrelated to method behavior across classes
  4. A restriction that forces all subclasses to use identical method implementations

Explanation

Polymorphism is the ability of objects from different classes (typically related through inheritance) to be treated through a common interface (e.g., a shared superclass method signature), while each subclass provides its own specific implementation of that method.

Question 5Programming, object modelling and software development

In UML class diagrams, what distinguishes 'Aggregation' from 'Komposition' (composition)?

  1. In composition, the part cannot exist independently of the whole; in aggregation, the part can exist independently Correct answer.
  2. In aggregation, the part cannot exist independently of the whole; in composition, the part can exist independently
  3. There is no meaningful distinction between aggregation and composition
  4. Aggregation and composition both refer exclusively to inheritance relationships

Explanation

In composition (filled/solid diamond in UML), the part cannot exist independently of the whole - if the whole is destroyed, so are its parts (e.g., a House and its Rooms). In aggregation (hollow diamond), the part CAN exist independently of the whole (e.g., a University and its Students).

Question 6Programming, object modelling and software development

In Java, which keyword is used to create a new instance (object) of a class?

  1. new Correct answer.
  2. class
  3. this
  4. static

Explanation

The 'new' keyword is used in Java to instantiate a new object of a class, e.g., 'Auto meinAuto = new Auto();' allocates memory and calls the class's constructor.

Question 7Programming, object modelling and software development

What is a 'Konstruktor' (constructor) in a Java class?

  1. A special method automatically called when an object is instantiated, typically used to initialize attributes Correct answer.
  2. A method that deletes an object from memory
  3. A term unrelated to object-oriented programming
  4. A method that must always return a value of type int

Explanation

A constructor is a special method automatically called when an object is instantiated (via 'new'), typically used to initialize the object's attributes; it shares the same name as the class and has no return type.

Question 8Programming, object modelling and software development

What is the correct term for a class that cannot be instantiated directly but serves as a base for other classes, often containing at least one method without an implementation?

  1. Abstrakte Klasse (abstract class) Correct answer.
  2. Finale Klasse (final class)
  3. Statische Klasse (static class)
  4. Private Klasse (private class)

Explanation

An abstract class (abstrakte Klasse) cannot be instantiated directly and often contains at least one abstract method (declared without an implementation), serving as a base class that concrete subclasses must extend and implement.

Question 9Programming, object modelling and software development

What is an 'Interface' (interface) in Java, relevant to object-oriented design?

  1. A contract specifying method signatures that implementing classes must provide, without specifying implementation details itself Correct answer.
  2. A concrete class containing only private attributes
  3. A term unrelated to object-oriented programming
  4. A structure that can only contain exactly one method

Explanation

An interface in Java is a contract specifying method signatures (and constants) that any implementing class must provide concrete implementations for, enabling a form of multiple inheritance of behavior without inheriting implementation.

Question 10Programming, object modelling and software development

In UML class diagrams, what does a multiplicity of '1..*' on an association end indicate?

  1. At least one, and potentially many, related objects on that end Correct answer.
  2. Exactly zero related objects on that end
  3. Exactly one and only one related object on that end
  4. An unrelated notation with no numeric meaning

Explanation

A multiplicity of '1..*' indicates at least one (minimum 1) and potentially many (unbounded maximum) related objects on that association end, e.g., one Teacher teaches 1..* Students.

Question 11Programming, object modelling and software development

What is method 'Überladung' (method overloading) in Java, as distinct from overriding?

  1. Defining multiple methods with the same name but different parameter lists within the same class Correct answer.
  2. Redefining a superclass method in a subclass with the identical signature
  3. A term unrelated to Java methods
  4. A restriction preventing a class from having more than one method

Explanation

Method overloading defines multiple methods with the SAME NAME but DIFFERENT parameter lists (number or types of parameters) within the same class, allowing the compiler to select the appropriate version based on the arguments provided.

Question 12Programming, object modelling and software development

What is a 'statisches Attribut' (static attribute) in a Java class?

  1. An attribute that belongs to the class itself, shared across all instances, rather than to individual objects Correct answer.
  2. An attribute that can never be changed once initialized
  3. A term unrelated to Java classes
  4. An attribute that only exists within a single method's scope

Explanation

A static attribute belongs to the class itself (not to individual object instances) and is shared across all instances of that class - changing it via one object affects the value seen by all other instances.

Question 13Programming, object modelling and software development

What does the exam Operator 'implementieren' (implement) require when applied to a described algorithm or class in a Java code-writing task?

  1. To write correct, syntactically valid Java code that realizes the described algorithm or class structure Correct answer.
  2. To simply describe the algorithm in prose with no actual code written
  3. To draw only a UML diagram with no Java code
  4. To translate the described algorithm into a natural spoken language

Explanation

'Implementieren' (implement) requires writing correct, syntactically valid Java code that concretely realizes the described algorithm or class structure, demonstrating both conceptual understanding and correct programming-language syntax.

Question 14Programming, object modelling and software development

In UML class diagrams, what distinguishes an 'Assoziation' (association) from an 'Abhängigkeit' (dependency)?

  1. Association represents a structural, usually long-term relationship (often via an attribute reference); dependency represents a weaker, typically temporary relationship (e.g., a method parameter) Correct answer.
  2. There is no meaningful difference between association and dependency
  3. Dependency is always drawn with a solid line, and association with a dashed line
  4. Association can only exist between a class and itself

Explanation

Association represents a structural, typically long-term relationship (often implemented via an attribute reference to another class, drawn as a solid line), while dependency represents a weaker, typically temporary relationship - such as one class using another only as a method parameter or local variable - drawn as a dashed arrow.

Question 15Programming, object modelling and software development

In Java, what does the 'this' keyword refer to within an instance method?

  1. The current object instance on which the method was called Correct answer.
  2. The superclass of the current object
  3. A static class-level variable shared by all instances
  4. A term unrelated to object-oriented programming

Explanation

The 'this' keyword refers to the current object instance on which the method was called, commonly used to distinguish an instance attribute from a same-named parameter (e.g., 'this.name = name;').

Question 16Programming, object modelling and software development

In Java, what is the purpose of the 'super' keyword within a subclass?

  1. To call a constructor or method of the immediate superclass from within the subclass Correct answer.
  2. To create a completely new, unrelated class with no inheritance connection
  3. A term unrelated to Java inheritance
  4. To permanently delete the superclass from the program

Explanation

The 'super' keyword is used within a subclass to call a constructor (super(...)) or method (super.methodName()) of its immediate superclass, often used to reuse or extend inherited behavior.

Question 17Programming, object modelling and software development

What is a 'Getter'-Methode (getter method) in Java, commonly paired with encapsulated private attributes?

  1. A method that returns the current value of a private attribute, providing controlled read access Correct answer.
  2. A method that permanently deletes a private attribute
  3. A term unrelated to encapsulation
  4. A method that can only be called by exactly one specific object in the entire program

Explanation

A getter method returns the current value of a private attribute, providing controlled read access to otherwise inaccessible encapsulated data, typically named 'getAttributName()' by Java convention.

Question 18Programming, object modelling and software development

What is the purpose of a 'Setter'-Methode (setter method) paired with a private attribute?

  1. To allow controlled modification of a private attribute's value, optionally including validation logic Correct answer.
  2. To permanently prevent any modification of the attribute under all circumstances
  3. A term unrelated to encapsulation
  4. To return the attribute's value without allowing any modification

Explanation

A setter method allows controlled MODIFICATION of a private attribute's value from outside the class, and can optionally include validation logic (e.g., rejecting a negative age value) before actually updating the attribute.

Question 19Programming, object modelling and software development

What is an 'abstrakte Methode' (abstract method) within an abstract class?

  1. A method declared without an implementation (method body), which concrete subclasses must override and implement Correct answer.
  2. A method that always has a complete, ready-to-run implementation body
  3. A term unrelated to abstract classes
  4. A method that can never be called by any object under any circumstances

Explanation

An abstract method is declared WITHOUT an implementation (no method body, just a signature ending in a semicolon), and any CONCRETE (non-abstract) subclass extending the abstract class must provide (override) a full implementation of that method.

Question 20Programming, object modelling and software development

In Java, what does declaring an attribute with the 'final' keyword indicate?

  1. The attribute's value, once initialized, cannot be reassigned or changed afterward Correct answer.
  2. The attribute belongs to the class rather than to individual instances
  3. The attribute is automatically publicly accessible from any other class
  4. A term unrelated to Java attribute declarations

Explanation

Declaring an attribute 'final' indicates that its value, once initialized, CANNOT be reassigned or changed afterward - commonly used for constants (e.g., 'final double PI = 3.14159;').

Question 21Programming, object modelling and software development

What is the essential difference between a 'Klasse' (class) and an 'Objekt' (object) in object-oriented programming?

  1. A class is a blueprint/template defining structure and behavior; an object is a concrete instance created from that blueprint Correct answer.
  2. A class and an object refer to exactly the same programming concept with no distinction
  3. An object always exists before its corresponding class is defined
  4. A class can only ever produce exactly one object

Explanation

A class is a blueprint or template defining the structure (attributes) and behavior (methods) that its instances will have; an object is a concrete INSTANCE created from that class blueprint (via 'new'), with its own specific attribute values.

Question 22Programming, object modelling and software development

What is the 'toString()' method's typical purpose in a Java class, when overridden?

  1. To return a human-readable String representation of an object's state, often used for display or debugging output Correct answer.
  2. To convert an integer value into a corresponding boolean value
  3. A term unrelated to Java object representation
  4. To permanently delete the object's toString representation from memory

Explanation

The 'toString()' method, when overridden in a class, returns a human-readable String representation of an object's current state (typically summarizing its attribute values), commonly used for display or debugging output (e.g., when printing an object with System.out.println).

Question 23Programming, object modelling and software development

What is an 'Assoziationsklasse' (association class) in UML modeling, relevant to n:m relationships with additional attributes?

  1. A class attached to an association that itself carries additional attributes specific to that particular relationship Correct answer.
  2. A class that can never be associated with any other class
  3. A term unrelated to UML relationship modeling
  4. A class that is identical in every respect to a regular attribute

Explanation

An association class is attached to an association (typically an n:m relationship) and carries additional attributes specific to that particular relationship instance - for example, an 'Enrollment' association class between Student and Course, carrying an attribute like 'Grade' that belongs to the specific student-course pairing, not to either class alone.

Question 24Programming, object modelling and software development

In Java, what does it mean for a method to have a 'void' return type?

  1. The method does not return any value to its caller Correct answer.
  2. The method must always return the integer value zero
  3. The method can only be called from within the same class
  4. A term unrelated to Java method declarations

Explanation

A method declared with a 'void' return type does not return any value to its caller - it performs an action (like printing output or modifying an attribute) without producing a result to be used elsewhere.

Question 25Programming, object modelling and software development

What does it mean for a Java class to 'implement' an interface using the 'implements' keyword?

  1. The class commits to providing concrete implementations for all method signatures declared in that interface Correct answer.
  2. The class becomes permanently unable to have any methods of its own
  3. A term unrelated to Java interfaces
  4. The class automatically becomes abstract and cannot be instantiated

Explanation

When a class 'implements' an interface, it commits to providing concrete implementations for ALL method signatures declared in that interface (unless the implementing class is itself declared abstract), fulfilling the interface's contract.

Question 26Programming, object modelling and software development

What is the correct meaning of the AFB II-level Operator 'modellieren' (model), applied to a described real-world scenario in an Informatik exam?

  1. To translate the described real-world scenario into an appropriate UML class diagram, capturing relevant classes, attributes, methods, and relationships Correct answer.
  2. To simply repeat the scenario description in the exact same words with no diagram produced
  3. To write only executable Java code with no diagrammatic representation at all
  4. To evaluate whether the scenario is ethically acceptable, with no diagram involved

Explanation

'Modellieren' (model) requires translating a described real-world scenario into an appropriate UML class diagram (or similar model), capturing the relevant classes, attributes, methods, and relationships that represent the scenario's essential structure.

Question 27Programming, object modelling and software development

What is a 'Paket' (package) in Java, used to organize classes?

  1. A namespace mechanism grouping related classes together, helping avoid naming conflicts and organize larger programs Correct answer.
  2. A term describing a single method within a class
  3. A concept unrelated to Java program organization
  4. A structure that can only ever contain exactly one class

Explanation

A package is a namespace mechanism in Java that groups related classes together, helping avoid naming conflicts (two classes with the same name can coexist in different packages) and organizing larger programs into logical, manageable groups.

Question 28Programming, object modelling and software development

In a UML class diagram, how is a 'Komposition' (composition) relationship typically drawn between two classes?

  1. A solid line with a filled (solid black) diamond at the end nearest the 'whole' class Correct answer.
  2. A solid line with a hollow (unfilled) diamond at the end nearest the 'whole' class
  3. A dashed line with an open arrowhead
  4. A solid line with a hollow triangle arrowhead

Explanation

Composition is drawn as a solid line with a FILLED (solid black) diamond positioned at the end nearest the 'whole' class, indicating the strong, life-cycle-dependent 'part-of' relationship.

Question 29Algorithms, recursion and complexity

In computer science, abstraction is best described as which of the following?

  1. Hiding unnecessary details so a problem or system can be understood and managed at a higher level Correct answer.
  2. Writing out every single low-level instruction a processor executes
  3. Translating source code into machine language
  4. Measuring the time complexity of an algorithm

Explanation

Abstraction means focusing on the essential features of a problem while ignoring or hiding unnecessary details, which lets people reason about complex systems at a manageable level. The GACE objective treats abstraction as a foundational concept of computer science.

Question 30Algorithms, recursion and complexity

What is the decimal (base-10) value of the binary number 1011?

  1. 11 Correct answer.
  2. 13
  3. 9
  4. 23

Explanation

Each binary digit represents a power of two from right to left: 1x8 + 0x4 + 1x2 + 1x1 = 8 + 0 + 2 + 1 = 11. Converting between number bases is an explicit GACE Algorithms and Computational Thinking objective.

Question 31Algorithms, recursion and complexity

What is the hexadecimal representation of the decimal number 255?

  1. FF Correct answer.
  2. 100
  3. 0F
  4. F0

Explanation

Hexadecimal is base 16, where F equals 15. The value 255 equals 15x16 + 15 = FF, the largest two-digit hexadecimal number. Analyzing and converting representations of numbers in different bases is a GACE objective.

Question 32Algorithms, recursion and complexity

A student breaks the task of building a school website into smaller subtasks: design the layout, write the content, code the navigation, and test the pages. This approach best demonstrates which computational thinking practice?

  1. Problem decomposition Correct answer.
  2. Number base conversion
  3. Data encryption
  4. Operator precedence

Explanation

Problem decomposition is the practice of breaking a large, complex problem into smaller, more manageable subproblems that can be solved individually. Dividing the website project into layout, content, navigation, and testing tasks is a clear example.

Question 33Algorithms, recursion and complexity

An algorithm performs a single pass through a list of n items, doing constant work for each item. Which describes its time complexity?

  1. Linear, O(n) Correct answer.
  2. Quadratic, O(n^2)
  3. Logarithmic, O(log n)
  4. Constant, O(1)

Explanation

When the number of operations grows in direct proportion to the input size n, the running time is linear, written O(n). A single pass doing constant work per element is the canonical example of linear time.

Question 34Algorithms, recursion and complexity

A binary search is performed on a sorted list of 16 elements. What is the maximum number of comparisons needed to determine whether a target value is present?

  1. 5 Correct answer.
  2. 16
  3. 8
  4. 4

Explanation

Binary search halves the search space with each comparison, so the maximum number of comparisons is floor(log2 n) + 1. For 16 elements, log2(16) = 4, giving a maximum of 5 comparisons. Calculating comparisons for binary search is a stated GACE objective.

Question 35Algorithms, recursion and complexity

Which essential component must every recursive algorithm include to avoid running forever?

  1. A base case (stopping condition) Correct answer.
  2. A nested loop
  3. A global variable
  4. A sorting step

Explanation

A recursive algorithm calls itself on smaller inputs and must include a base case, a condition under which it stops recursing and returns a direct result. Without a base case, the recursion never terminates. Identifying the base case is an explicit GACE objective.

Question 36Algorithms, recursion and complexity

Which problem is best characterized as one that cannot be solved exactly within a practical time, making a heuristic solution appropriate?

  1. Finding the absolute shortest route that visits hundreds of cities exactly once (the traveling salesman problem) Correct answer.
  2. Adding two integers together
  3. Finding the largest value in a list of ten numbers
  4. Reversing a short string of characters

Explanation

The traveling salesman problem grows so quickly with the number of cities that finding the guaranteed optimal route becomes computationally impractical for large inputs, so heuristics that find good-enough solutions are used. Recognizing when heuristic solutions are useful is a GACE objective.

Question 37Algorithms, recursion and complexity

A teacher explains the difference between random and pseudorandom numbers. Which statement is correct?

  1. Pseudorandom numbers are generated by a deterministic algorithm from a seed and will repeat if the same seed is used Correct answer.
  2. Pseudorandom numbers can never be reproduced under any circumstances
  3. Truly random numbers are always produced by software loops
  4. Pseudorandom and truly random numbers are identical in every way

Explanation

Pseudorandom number generators use a deterministic algorithm starting from a seed value, so the same seed always produces the same sequence, which makes them reproducible. This distinguishes them from truly random sources, which derive from physical, unpredictable phenomena.

Question 38Algorithms, recursion and complexity

Consider the recursive definition: factorial(0) = 1, and factorial(n) = n * factorial(n - 1) for n > 0. What value does factorial(4) produce?

  1. 24 Correct answer.
  2. 12
  3. 16
  4. 10

Explanation

Tracing the recursion: factorial(4) = 4 * 3 * 2 * 1 * factorial(0) = 4 * 3 * 2 * 1 * 1 = 24. Tracing simple recursive algorithms such as n factorial is an explicit GACE objective.

Question 39Algorithms, recursion and complexity

A flowchart uses a diamond shape at a decision point. What does the diamond most commonly represent in standard flowchart notation?

  1. A condition or decision that branches the flow based on yes/no or true/false Correct answer.
  2. The start or end of the algorithm
  3. A simple process or calculation step
  4. Input or output of data

Explanation

In standard flowchart notation, the diamond represents a decision: a condition is evaluated and the flow branches based on the result, typically yes/no or true/false. Interpreting flowchart symbols and tracing algorithms in different formats is a GACE objective.

Question 40Algorithms, recursion and complexity

A student is given a table showing input values 1, 2, 3, 4 paired with outputs 1, 4, 9, 16. Which rule best describes the pattern that produces the outputs?

  1. Each output is the input squared Correct answer.
  2. Each output is the input plus three
  3. Each output is the input multiplied by four
  4. Each output is double the input

Explanation

Checking the pairs: 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 16. The output equals the square of the input. Identifying patterns in a table of values and the algorithm that produces them is a GACE pattern-recognition objective.

Question 41Algorithms, recursion and complexity

An algorithm using nested loops compares every element of a list to every other element. As the list size n grows large, which growth rate best describes the number of comparisons?

  1. Quadratic, proportional to n^2 Correct answer.
  2. Linear, proportional to n
  3. Logarithmic, proportional to log n
  4. Constant, independent of n

Explanation

When an inner loop runs n times for each of the n iterations of an outer loop, the total number of comparisons is proportional to n times n, which is n^2, or quadratic growth. The GACE objective asks teachers to identify and compare linear, quadratic, exponential, and logarithmic algorithms.

Question 42Algorithms, recursion and complexity

Which list of items represents an abstraction hierarchy correctly ordered from the lowest (most detailed) level to the highest (most abstract) level?

  1. Transistors, logic gates, integrated circuits, computer Correct answer.
  2. Computer, integrated circuits, logic gates, transistors
  3. Logic gates, transistors, computer, integrated circuits
  4. Integrated circuits, computer, transistors, logic gates

Explanation

Abstraction hierarchies build from the most detailed physical components upward. Transistors combine into logic gates, gates form integrated circuits, and circuits make up the complete computer, moving from low (detailed) to high (abstract). Ordering an abstraction hierarchy is a GACE objective.

Question 43Algorithms, recursion and complexity

An algorithm's running time doubles every time one additional input element is added. Which growth rate does this describe?

  1. Exponential Correct answer.
  2. Linear
  3. Logarithmic
  4. Constant

Explanation

If adding one element doubles the work, the running time grows as a power of two with respect to input size, which is exponential growth. Exponential algorithms quickly become infeasible for large inputs, a key idea in the GACE limitations objective.

Question 44Algorithms, recursion and complexity

A selection sort repeatedly finds the smallest remaining element and places it at the front of the unsorted portion. After the first full pass over an unsorted list, which statement is guaranteed to be true?

  1. The smallest element is now in the first position Correct answer.
  2. The entire list is fully sorted
  3. The largest element is now in the first position
  4. No elements have changed position

Explanation

Selection sort scans the unsorted portion to find the minimum and swaps it into the next sorted position. After the first pass, the smallest element is correctly placed at the front. Tracing sorting algorithms and predicting intermediate results is a GACE objective.

Question 45Digital representation and data structures

What is a 'Stack' (stack) data structure, and its access principle?

  1. A LIFO (last-in, first-out) structure, where the most recently added element is the first to be removed Correct answer.
  2. A FIFO (first-in, first-out) structure, where the first added element is the first removed
  3. A term unrelated to data structures
  4. A structure that allows access to any element at any position with no ordering restriction

Explanation

A stack is a LIFO (last-in, first-out) data structure, where elements are added ('push') and removed ('pop') only from the top, meaning the most recently added element is the first to be removed.

Question 46Digital representation and data structures

What is a 'Queue' (queue) data structure, and its access principle?

  1. A FIFO (first-in, first-out) structure, where the first element added is the first to be removed Correct answer.
  2. A LIFO (last-in, first-out) structure, where the last element added is the first to be removed
  3. A term unrelated to data structures
  4. A structure that only ever holds exactly one element at a time

Explanation

A queue is a FIFO (first-in, first-out) data structure, where elements are added at one end (enqueue) and removed from the other end (dequeue), meaning the first element added is the first to be removed.

Question 47Digital representation and data structures

In a 'binärer Suchbaum' (binary search tree), what property must hold for every node?

  1. All values in the left subtree are smaller, and all values in the right subtree are larger, than the node's own value Correct answer.
  2. All values in the left subtree must be larger than the node's own value
  3. Every node must have exactly two children with no exceptions
  4. There is no defined ordering property for a binary search tree

Explanation

In a binary search tree, for every node: all values in its LEFT subtree are SMALLER, and all values in its RIGHT subtree are LARGER, than the node's own value - this ordering property enables efficient searching.

Question 48Digital representation and data structures

For a binary search tree, what is the correct order of values visited during an 'Inorder'-Traversierung (in-order traversal)?

  1. Left subtree, then the node itself, then right subtree - producing values in ascending sorted order Correct answer.
  2. Node itself, then left subtree, then right subtree
  3. Left subtree, then right subtree, then the node itself
  4. Right subtree, then the node itself, then left subtree

Explanation

In-order traversal visits the left subtree, then the node itself, then the right subtree (Left-Node-Right); for a valid binary search tree, this produces the values in ascending sorted order.

Question 49Digital representation and data structures

What is the average-case time complexity of searching for an element in a balanced binary search tree with n elements?

  1. O(log n) Correct answer.
  2. O(n)
  3. O(n²)
  4. O(1)

Explanation

In a BALANCED binary search tree, searching has an average-case time complexity of O(log n), since each comparison eliminates roughly half of the remaining elements from consideration, similar to binary search.

Question 50Digital representation and data structures

What sorting algorithm repeatedly finds the minimum (or maximum) element from the unsorted portion and swaps it into its correct position?

  1. Selectionsort (selection sort) Correct answer.
  2. Bubblesort, which instead repeatedly compares and swaps adjacent elements
  3. Quicksort, which instead uses a pivot-based partitioning approach
  4. Mergesort, which instead uses a divide-and-conquer merging approach

Explanation

Selection sort repeatedly scans the unsorted portion of a list to find the minimum (or maximum) element, then swaps it into its correct sorted position at the boundary of the sorted portion.