Algorithms and data structures test questions
How does the Divide and Conquer method work?
:r1 It divides the problem into partial tasks, which must be independent.
:r2 It divides the problem into partial tasks that may be dependent.
:r3 It divides the tasks between multiple computers
:r4 It does not look for a specific solution, but just some appropriate approximation
:r1 ok 2
--
How does a greedy algorithm work?
:r1 It calls itself until it finds a solution
:r2 Makes decisions based on random (pseudo-random) elections
:r3 Seeks local extrema to find extreme global
:r4 It divides the problem into partial tasks that are dependent.
:r3 ok 2
--
What is ADT - Abstract data type?
:r1 Abstract data that cannot be implemented
:r2 Designation for data types that are independent of their own implementation
:r3 General data types like Integer, Real, Boolean ...
:r4 Specific implementation of data type
:r2 ok 2
--
Basic operations with ADT are:
:r1 Constructor, Selector, Modifier
:r2 Constructor, Destructor
:r3 Constructor, Selector, Modifier, Destructor
:r4 Selector, Destructor
:r1 ok 2
--
Experimental analysis of time-consuming algorithms:
:r1 Take place in an environment where the program (algorithm) runs
:r2 It does not depend on the environment where the program is running
:r3 It does not require algorithm implementation
:r4 It focuses on the simplest (least difficult) case
:r1 ok 2
--
Pseudo-code:
:r1 It depends on the programming language
:r2 It reveals the problems of a specific implementation
:r3 Is a higher description level, more structured than a classic description, less detailed than
implementation
:r4 A lower description level, less structured than a classic description, requires knowledge of a
specific programming language
:r3 ok 2
--
Primitive operations
:r1 Depending on the specific programming language, it cannot be identified in the pseudocode
:r2 Another name for a specific implementation of the procedure (methods, algorithm)
:r3 A program block that includes several operations that are made on a single call basis
:r4 Basic operations performed by an algorithm such as evaluating an expression, assigning a value
to a variable, calling a procedure ...
:r4 ok 2
--
If the algorithm is the number of 2n2 -3, the
time-consuming and Big O notation is:
:r1 Exponential O (c^n -3)
:r2 Logarithmic, O (log n)
:r3 Constant, O (1)
:r4 Quadratic O (n^2)
:r4 ok 2
--
ADT Stack
:r1 Inserting and deleting is performed using the FIFO principle
:r2 The basic operations are: push (Object), findMin (), findMax (), deleteAll ()
:r3 It never throws an exception
:r4 It is controled by the LIFO principle and the basic operations are: push (Object), pop ()
:r4 ok 2
--
If the Stack is based on an array,
:r1 Then, time required for each operation is O (n^2 + n), where n number of elements in the stack
:r2 At the beginning, we need to define the stack size
:r3 Any number of elements can be stored, you can simply enlarge the stack
:r4 When adding an element to the full stack, the EmptyStackException exception occurs
:r2 ok 2
--
ADT Queue
:r1 Inserting and deleting is performed using the FIFO principle
:r2 The basic operations are: push (Object), findMin (), findMax (), deleteAll ()
:r3 Insertion and deletion occurs using the LIFO principle
:r4 It never throws an exception
:r1 ok 2
--
Queue
:r1 Stores a collection of items where the item is an ordered pair (priority-value), which
maintains the order in the queue
:r2 We use a circular array for implementation
:r3 The basic operations are: enqueue (object), dequeue (), first (), last (), order()
:r4 The time complexity for any implementation it is best to O (N^2 log N)
:r2 ok 2
--
Vector
:r1 Defines the relationship before / after between positions
:r2 Elements are ordered by size
:r3 Expands the concept of array to store sequence of arbitrary objects
:r4 Allows you to store objects even on negative positions (negative index)
:r3 ok 2
--
List
:r1 Dynamic data structure, size varies based on element addition (deletion)
:r2 Static data structure, size does not change
:r3 The element can be read, inserted and removed by determining its order
:r4 Basic, generally usable data type for storing an ordered set of elements
:r1 ok 2
--
Single linked list
:r1 Contains a link to the previous and next nodes
:r2 It can be used to implement stack and queues with linear memory difficulty and constant time
requirement for each basic operation
:r3 Static data structure
:r4 Defines the relationship before / after between positions
:r2 ok 2
--
Sequence
:r1 Combination of Vector and List ADT, access to elements by order and position
:r2 Elements cannot be accessed by determining their order
:r3 Access to elements based on the FIFO principle
:r4 Access to elements based on the LIFO principle
:r1 ok 2
5 – 8
Tree
:r1 Linear static data structure
:r2 It contains nodes, with the ancestor-child relationship (parent-child)
:r3 The external node is called the root
:r4 The internal node is called a leaf
:r2 ok 2
--
The pre-order traversal of tree shown in the figure gives the sequence:
:r1 A, B, C, D, E, F, G, H, I
:r2 A. C, E, D, F, G, H, I
:r3 F, B, A, D, C, E, G, I, H
:r4 C, E, H, A, D, I, B, G, F
:r3 ok 2
--
The in-order passage through the tree shown in the figure gives the sequence:
:r1 A, B, C, D, E, F, G, H, I
:r2 A, C, E, D, B, H, I, G, F
:r3 F, B, A, D, C, E, G, I, H
:r4 C, E, H, A, D, I, B, G, F
:r1 ok 2
--
Binary tree
:r1 It contains two roots
:r2 It contains just two sheets
:r3 Each internal node has at least two offspring, at least one of which is a leaf
:r4 Each internal node has just two offspring that form an ordered pair (left child, right child)
:r4 ok 2
--
Priority queue
:r1 It introduces the Comparator ADT, which allows you to compare two objects
:r2 Two different elements must always have a different priority (key)
:r3 A set of elements must be defined on a set of elements
:r4 Basic operations with a priority queue are: insertItem (k, o), removeMin (), upheap (),
downheap ()
:r1 ok 2
--
Priority queue
:r1 Stored elements can be accessed based on their queue index
:r2 Keys are any objects that can be defined in order, two different elements may have the same
key
:r3 Linear static data structure
:r4 The element with the smallest priority is always taken first
:r2 ok 2
--
Heap
:r1 It is represented as a binary tree that keeps the keys as internal nodes, for which the child
key is always greater than or equal to the parent keys
:r2 Root contains the largest key
:r3 The last node leaf is the outermost node located at the leftmost
:r4 The downheap () function re-arranges the heap when inserting a new element
:r1 ok 2
--
Heap
:r1 Access to elements based on the FIFO principle
:r2 Access to elements based on the LIFO principle
:r3 After inserting a node, you need to call the upheap () function to restore the stack
:r4 Inserting and removing any element from the heap will not disrupt its arrangement
:r3 ok 2
--
Dictionary
:r1 Size must always be set when creating a dictionary, regardless of implementation
:r2 Requires that in the key-value pair, both the key and the value can be ordered
:r3 Oredered key-value pairs, where the keys are unique, values are not
:r4 We always remove the element with the smallest key
:r3 ok 2
--
Log File
:r1 Cannot be used if the set of values is not defined in the layout
:r2 Used for small dictionaries or applications where search is the most common operation
:r3 It is used where the most frequent operation is insertion, while searching and removal is
rare.
:r4 The elements are always inserted in the middle of the sequence
:r3 ok 2
--
Lookup table
:r1 We always use a disordered dictionary to implement it
:r2 Used for small dictionaries or applications where the most common operation is searching
:r3 It is used where the most frequent operation is insertion, while searching and removal is
rare.
:r4 Access to elements based on the LIFO principle
:r2 ok 2
--
Hash table
:r1 For a given key type, it has a hash function that assigns an integer value to the key, and a
table of size N
:r2 Cannot be used if the hash function returns the same value to different keys (there is a
collision)
:r3 Requires that in the key-value pair, both the key and the value can be ordered
:r4 It organizes the values according to the key, independent of the hash function, which only
serves to control the stored data
:r1 ok 2
--
Sorting algorithms
:r1 We designate them as stable if they retain the order of inserting items with the same key
:r2 Sorts a dataset by value, not by key
:r3 They require a defined order of values
:r4 Cannot be used if the data contains several keys with the same value
:r1 ok 2
--
Bubble sort
:r1 It works by comparing the first and last element of the series
:r2 Requires extra memory for the size of the sorted data file
:r3 Only one pass is sufficient to order any data set
:r4 Versatile, the most value elements bubble at the end of the list
:r4 ok 2
--
Heap sort
:r1 It is a stable sorting algorithm using the ADT List
:r2 From the array, it creates a heap where the smallest element serves as a root that we then
remove
:r3 Demanding the minimum time complexity is O (N^3)
:r4 It cannot sort data on the spot, it requires extra memory for the size of the data file
:r2 ok 2
--
Insertion sort
:r1 Compares two adjacent elements in a sequence
:r2 It fails if the set is partially ordered
:r3 Stable, efficient on partially ordered sets, can sort data online (as they come to input)
:r4 Unstable, it is used for a large amount of data
:r3 ok 2
9 – 12
Mergesort
:r1 Unstable, cannot be paralleled, the extra memory required is O (1)
:r2 Stable, well parallelizable, worst time complexity is O (nlog n)
:r3 Only one pass is sufficient to compare any data set
:r4 It works by comparing the first and last element of the series
:r2 ok 2
--
Quicksort
:r1 Stable, able to order any data set in a single pass
:r2 It fails if the set is partially aligned
:r3 Versatile, the most value elements bubble at the end of the list
:r4 On average, it is the fastest known algorithm, unstable, uses pivot for sorting
:r4 ok 2
--
Selection sort
:r1 Algorithm complicated for implementation, but very fast, for ordering any data set is
sufficient only one pass
:r2 Universal, local, unstable, suitable for small amounts of data
:r3 Requires additional memory of O (n^2)
:r4 The minimum and average time complexity is O (n)
:r2 ok 2
--
Sorting algorithms:
:r1 In the worst-case scenario, the time complexity of Heapsort and Mergesort O (nlog n)
:r2 Heapsort, Quicksort, and Insertion sorts are all unstable
:r3 Heapsort, Quicksort, Merge sort, and Insertion sort sorts data in-place (in-place, extra
memory is O (1))
:r4 Bubble sort and Insertion sort ideally have time complexity constant - O (1)
:r1 ok 2
--
Pattern matching
:r1 It means finding a pattern P in a given sequence T (searching for a substring in a string)
:r2 Compare two objects based on their size
:r3 Finding repeating parts of the text
:r4 Finding the sequence that can encode the whole text
:r1 ok 2
--
Pattern matching - Brute force
:r1 Passes the text from right to left (back), not all positions
:r2 Compares P with T for all possible positions
:r3 It is a simple and time-consuming algorithm, its time complexity with longer text decreases
:r4 Removing characters from the text until the text T remains a string of the same length as P
:r2 ok 2
--
Pattern matching - KMP algorithm
:r1 It searches text from left to right, like Brute-Force algorithm makes all comparisons
:r2 If it encounters a disagreement, it moves the search for more than one letter, does not make
all possible comparisons
:r3 It is a simple and time-consuming algorithm, its time complexity with longer text decreases
:r4 Compare strings from behind, shifts only by one character
:r2 ok 2
--
Trie
:r1 The node order at that level indicates the order of the letter in the word
:r2 If Trie is compressed, each node contains just one letter
:r3 The text-processing structure where each node has one letter or word
:r4 Cannot store the entire text
:r3 ok 2
--
Theory of graphs
:r1 If the graph is oriented, it contains at least one oriented edge (not all edges must be
oriented)
:r2 The path is the sequence of vertices such that there are edges between consecutive vertices,
and the vertices are not repeated
:r3 The edge is determined by more than two vertices, weight and direction
:r4 The graph is an ordered pair V, E, where V is a set of vertices and E is a set of edges
:r4 ok 2
--
DFS – depth-first search of the graph shown in the figure gives sequence:
:r1 A, B, C, D, E, F, G, H, I
:r2 G, H, I, D, E, F, B, C, A
:r3 A, B, D, E, G, H, C, F, I
:r4 D, B, G, E, H, A, I, F, C
:r3 ok 2
--
BFS - Breadth-first search of the graph shown in the figure gives sequence:
:r1 A, B, C, D, E, F, G, H, I
:r2 G, H, I, D, E, F, B, C, A
:r3 A, B, D, E, G, H, C, F, I
:r4 D, B, G, E, H, A, I, F, C
:r1 ok 2
--
Finding the shortest path
:r1 In the worst-case scenario, the time complexity of O (n) is always independent of the
algorithm selected
:r2 Using the Dijkstra’s algorithm, it works on any type of graph with arbitrary edge values
:r3 Using the Floyd-Warshall algorithm requires a oriented graph with positive edges and finds the
shortest path between all vertices
:r4 Cannot be used on a graph that contains negative edges
:r3 ok 2
--
Genetic algorithms
:r1 They mimic the techniques of evolutionary biology, belong to artificial intelligence
:r2 t is an exact deterministic algorithm, it does not use any randomness
:r3 The method of describing (coding) individuals does not affect the success or failure of
solving a specific task
:r4 If they are triggered several times in a row, they always give the same result
:r1 ok 2
--
Parents selection
:r1 It is done so that parents become the individuals with the lowest fitness value
:r2 We use our fitness value when choosing our parents randomly
:r3 It is done to get the best individuals for the next generation
:r4 It does not affect the success or failure of a specific task
:r3 ok 2
--
Crossover
:r1 There is no way to crossover more than two individuals in one generation
:r2 Parents will exchange part of their genetic code, two new individuals are created at the
one-point crossover
:r3 Every individual in each generation must become a parent
:r4 The parent always extinguishes and his / her place is taken by a descendant, this descendant
will have the same fitness value as his / her parent
:r2 ok 2
--
Mutation
:r1 Describes a random change in the genome of an individual and it is done with very small
probability
:r2 It never brings new features that would not exist in the original generation
:r3 Every single individual from every generation mutates at least in one place
:r4 e mutations always take place at one and the same place in the genome in the same generation
:r1 ok 2