DATA STRUCTURES AND
ALGORITHMS EXAM QUESTIONS AND
ANSWERS
Why do we need a high level language? - Correct Answers -High-level languages
encourage you to think more about the problem domain and less about the execution
platform. There is less ceremony, so you can spend more time on stuff that actually
brings you value. Money. Cheaper developers, faster development speeds, and less
bugs equal more money.
A high level language is easier to code in and therefore less error prone.
Program - Correct Answers -A set of instructions for the computer to perform a task.
It can be stored in memory or downloaded from the internet.
when do you use float instead of double? - Correct Answers -Though both Java float
and Double can represent floating-point numbers, we can consider a couple of things to
choose between Java float and double.
Though both Java float vs Double is approximate types, use double if you need more
precise and accurate results. Use float if you have memory constraint because it takes
almost half as much space as double. If your numbers cannot fit in the range offered by
float, then use double. Though be careful with floating-point calculation and
representation, don't use double or float for monetary calculation, instead use Big
Decimal.
What is selection? - Correct Answers -Making the program behave differently each time
it runs.
the switch statement - Correct Answers -In computer programming languages, a switch
statement is a type of selection control mechanism used to allow the value of a variable
or expression to change the control flow of program execution via search and map.
Designing algorithms - Correct Answers -A strategy to solve a problem in terms of
1. the actions to be executed
2. the order in which the actions are to be executed
,when do we use a for loop? - Correct Answers -generally used when the number of
repetitions or iterations is known in advance.
For example, you know there are 10 students in a class and you want to calculate the
average mark for them all.
What to do when the number of loops is not fixed? - Correct Answers -Use a while loop
What is the difference between a while loop and a for loop? - Correct Answers -A while
loop causes the code inside it to be repeated until some condition is satisfied.
A for loop is repeated for a fixed number of iterations.
Asymptotic Notation - Correct Answers -Asymptotic notations are the mathematical
notations used to describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by
the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time
(quadratic) to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time.
These durations are denoted using asymptotic notations.
There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
What types of trees do you know? - Correct Answers -Free trees
Binary
Positional trees
Rooted trees
Ordered trees
Define a free tree - Correct Answers -In a free tree there's no designated root vertex.
You can make a free tree into a rooted one by choosing any of its vertices to be the
root.
Define rooted tree - Correct Answers -In graph theory, the basic definition of a tree is
that it is a connected graph without cycles. This definition does not use any specific
node as a root for the tree. A rooted tree introduces a parent — child relationship
between the nodes and the notion of depth in the tree.
Roughly and visually, adding a root to a tree just corresponds to grabbing one of the
nodes of the tree and hanging the tree with this node. Once the tree is hanged, each
node has a depth related to its height, a parent to which it is suspended and several
children which hang from this node.
, what is a binary and positional tree - Correct Answers -a binary tree is a tree data
structure in which each node has at most two children, which are referred to as the left
child and the right child.
A tree is either empty or consists of a node containing a label value and an indexed
sequence of zero or more children, each a positional tree. If every node has two
positions, we have a binary tree and the children are its left and right subtrees. Again,
nodes are the parents of their non-empty children.
How can you distinguish between binary trees and ordered trees - Correct Answers -An
ordered tree is an oriented tree in which the children of a node are somehow "ordered."
What sorting algorithms do you know? - Correct Answers -Quicksort
Heapsort
merge sort
insertion sort
Insertion Sort - Correct Answers -Each item is take in turn, compared to the items in a
sorted list and placed in the correct position.
A simple sorting algorithm that builds the final sorted array (or list) one item at time. It is
much less efficient on large lists than more advanced algorithms such as quicksort,
heapsort, or merge sort.
Insertion sort sorts in place and therefore uses less memory space. Though its
asymptotic running time is O(n^2), its code is very tight so the constant factor in the
running time is very small. Insertion sort is, therefore, an efficient algorithm for a small
input size.
Merge Sort Algorithm - Correct Answers -Sorts an array by cutting the array in half,
recursively sorting each half, and then merging the sorted halves
Insertion Sort Algorithm - Correct Answers -
Insertion Sort Worst Case - Correct Answers -O(n^2)
Heapsort algorithm - Correct Answers -a sorting algorithm that inserts the values to be
sorted into a heap
Heapsort Worst Case - Correct Answers -n log n
Quick Sort Worst Case - Correct Answers -O(n^2)
Quick Sort - Correct Answers -Unstable, O(n log n) for a good pivot,O(n^2) for a bad
pivot Ω(n log n) : Uses partitioning O(n), Pick a median of 1st, middle, and last element
ALGORITHMS EXAM QUESTIONS AND
ANSWERS
Why do we need a high level language? - Correct Answers -High-level languages
encourage you to think more about the problem domain and less about the execution
platform. There is less ceremony, so you can spend more time on stuff that actually
brings you value. Money. Cheaper developers, faster development speeds, and less
bugs equal more money.
A high level language is easier to code in and therefore less error prone.
Program - Correct Answers -A set of instructions for the computer to perform a task.
It can be stored in memory or downloaded from the internet.
when do you use float instead of double? - Correct Answers -Though both Java float
and Double can represent floating-point numbers, we can consider a couple of things to
choose between Java float and double.
Though both Java float vs Double is approximate types, use double if you need more
precise and accurate results. Use float if you have memory constraint because it takes
almost half as much space as double. If your numbers cannot fit in the range offered by
float, then use double. Though be careful with floating-point calculation and
representation, don't use double or float for monetary calculation, instead use Big
Decimal.
What is selection? - Correct Answers -Making the program behave differently each time
it runs.
the switch statement - Correct Answers -In computer programming languages, a switch
statement is a type of selection control mechanism used to allow the value of a variable
or expression to change the control flow of program execution via search and map.
Designing algorithms - Correct Answers -A strategy to solve a problem in terms of
1. the actions to be executed
2. the order in which the actions are to be executed
,when do we use a for loop? - Correct Answers -generally used when the number of
repetitions or iterations is known in advance.
For example, you know there are 10 students in a class and you want to calculate the
average mark for them all.
What to do when the number of loops is not fixed? - Correct Answers -Use a while loop
What is the difference between a while loop and a for loop? - Correct Answers -A while
loop causes the code inside it to be repeated until some condition is satisfied.
A for loop is repeated for a fixed number of iterations.
Asymptotic Notation - Correct Answers -Asymptotic notations are the mathematical
notations used to describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by
the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time
(quadratic) to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time.
These durations are denoted using asymptotic notations.
There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
What types of trees do you know? - Correct Answers -Free trees
Binary
Positional trees
Rooted trees
Ordered trees
Define a free tree - Correct Answers -In a free tree there's no designated root vertex.
You can make a free tree into a rooted one by choosing any of its vertices to be the
root.
Define rooted tree - Correct Answers -In graph theory, the basic definition of a tree is
that it is a connected graph without cycles. This definition does not use any specific
node as a root for the tree. A rooted tree introduces a parent — child relationship
between the nodes and the notion of depth in the tree.
Roughly and visually, adding a root to a tree just corresponds to grabbing one of the
nodes of the tree and hanging the tree with this node. Once the tree is hanged, each
node has a depth related to its height, a parent to which it is suspended and several
children which hang from this node.
, what is a binary and positional tree - Correct Answers -a binary tree is a tree data
structure in which each node has at most two children, which are referred to as the left
child and the right child.
A tree is either empty or consists of a node containing a label value and an indexed
sequence of zero or more children, each a positional tree. If every node has two
positions, we have a binary tree and the children are its left and right subtrees. Again,
nodes are the parents of their non-empty children.
How can you distinguish between binary trees and ordered trees - Correct Answers -An
ordered tree is an oriented tree in which the children of a node are somehow "ordered."
What sorting algorithms do you know? - Correct Answers -Quicksort
Heapsort
merge sort
insertion sort
Insertion Sort - Correct Answers -Each item is take in turn, compared to the items in a
sorted list and placed in the correct position.
A simple sorting algorithm that builds the final sorted array (or list) one item at time. It is
much less efficient on large lists than more advanced algorithms such as quicksort,
heapsort, or merge sort.
Insertion sort sorts in place and therefore uses less memory space. Though its
asymptotic running time is O(n^2), its code is very tight so the constant factor in the
running time is very small. Insertion sort is, therefore, an efficient algorithm for a small
input size.
Merge Sort Algorithm - Correct Answers -Sorts an array by cutting the array in half,
recursively sorting each half, and then merging the sorted halves
Insertion Sort Algorithm - Correct Answers -
Insertion Sort Worst Case - Correct Answers -O(n^2)
Heapsort algorithm - Correct Answers -a sorting algorithm that inserts the values to be
sorted into a heap
Heapsort Worst Case - Correct Answers -n log n
Quick Sort Worst Case - Correct Answers -O(n^2)
Quick Sort - Correct Answers -Unstable, O(n log n) for a good pivot,O(n^2) for a bad
pivot Ω(n log n) : Uses partitioning O(n), Pick a median of 1st, middle, and last element
