Data Structures

Question 1

Describe:

Array

Data Structure

Answer 1

• A linear collection of data values that are accessible at numbered indices, starting at 0.
• Contiguous area of memory consisting of equal-size elements indexed by contiguous integers.

Question 2

Stack

Interface

Answer 2

The stack is a data structure that operates on the last-in-first-out (LIFO) principle.
* Push(T) - pushes a valule to the top of the stack
* Pop() T - removes and element from the top of the stack and returns its value
* Top() T - returns that value of the element on top of the stack
* Size() int - returns the number of elements in the stack

All of the above operations are implemented in O(1) time complexity.

Question 3

Application of stacks

Answer 3

• Implementation of recursive calls
• Postfix evaluation of an expression
• Backtracking
• Depth-first search of trees and graphs
• Converting a decimal to a binary number, and so on

Question 4

Queue

Interface

Answer 4

The queue is a data structure that works under the first-in-first-out (FIFO) principle.
* Enqueue(T) - adds an element T at the end of the queue
* Dequeue() T - removes the first element from the queue and returns its value
* Front() - returns the first element of the queue
* Len() int - returns the number of elements in the queue.

All of the above operations are implemented in O(1) time complexity.

Question 5

Application of queue

Answer 5

• Scheduling of the shared resources in the operating system
• Multiprogramming tasks
• Message queue of a messaging service
• Breadth-first search (BFS) of trees and graphs

Question 6

Binary Search Tree

Interface

Answer 6

• Insert(T) - insert an element at the appropriate position in the tree
• Delete(T) - deletes an element from the tree
• Search(T) - determines whether an element is present in the tree or not
• Max() T - finds the maximum value stored in the tree
• Min() T- finds the minimum value stored in the tree

When the tree is a balanced binary search tree, the time complexity of these operations is O(log(n)). When the tree is not balanced, the worst-case time complexity is O(n).

Question 7

Describe:

Binary Search Tree

Data Structure

Answer 7

A binary search tree (BST) is a binary tree in which the following two conditions must be fulfilled:
* The left subtree’s key is less than or equal to the parent node’s key
* The right subtree’s key is greater than the parent node’s key