Data Structures

Question 1

A data structure used to store homogeneous elements at contiguous locations. Size must be provided before storing data.

Answer 1

Array

Question 2

Search Time: O(n) for Sequential search, O(log n) for Binary Search (if sorted)

Answer 2

Array

Question 3

Accessing Time: O(1), because elements are stored at contiguous locations

Answer 3

Array

Question 4

Insertion Time: O(n), the worst case occurs when insertion happens at the beginning of the structure which then requires shifting all of the other elements

Answer 4

Array

Question 5

Deletion Time: O(n), the worst case occurs when deletion happens at the beginning of the structure which then requires shifting all of the elements

Answer 5

Array

Question 6

A data structure where each element is a separate object. Each element is comprised of two items – the data and a reference to the next node.

Answer 6

Linked list

Question 7

In this type of linked list, every node stores the address / reference of next node. The last node’s reference is NULL.

For example 1->2->3->4->NULL

Answer 7

Singly linked list

Question 8

In this type of Linked list, there are two references associated with each node. One that points to the next node and one that points to the previous node.

For example NULL23->NULL

Answer 8

Doubly Linked List

Question 9

Advantage of this linked list data structure is that we can traverse in both directions and for deletion we don’t need to have explicit access to previous node.

Answer 9

Doubly Linked List

Question 10

A linked list where all nodes are connected in either a singly linked list or doubly linked list.

Answer 10

Circular linked list

Question 11

Advantage of this linked list data structure is that any node can be the starting node.

Answer 11

Circular linked list

Question 12

Accessing time: O(n)
Search time: O(n)
Insertion of an Element : O(1), if we are at the position where we have to insert an element
Deletion of an Element : O(1), if we know the address of the node previous the node to be that is to be deleted.

Answer 12

Linked list

Question 13

Eliminates unused memory when compared to an Array as nodes are only added when a new element is introduced.

Answer 13

Linked list

Question 14

Insertions and deletions are easier when compared to an array because there is not need to shift elements.

Answer 14

Linked list

Question 15

One big drawback of this data structure is that random access is not allowed. Unlike arrays, where we can access the n’th element in O(1) time. In this data structure, it would take O(n) time.

Answer 15

Linked list

Question 16

An abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added. Both operations take place at the top end of the structure and it can be implemented by using both an array or a linked list.

Answer 16

Stack

Question 17

Insertion : O(1)
Deletion : O(1)
Access Time : O(n), worst case
Insertion and Deletion are only allowed on one end.

Answer 17

Stack or LIFO

Question 18

A data structure used for maintaining function calls (the last called function must finish execution first). We can always remove recursion with the help of a __________. They are also used in cases where we have to reverse a word or to implement back functionality in web browsers.

Answer 18

Stack

Question 19

An abstract data structure that serves as a collection of elements, with two principal operations: enqueue, the process of adding an element to the end of collection, and dequeue, the process of removing the first element in the collection. It can be implemented by using an array or a linked list.

Answer 19

Queue or FIFO

Question 20

A data structure that best handles any situation where resources are shared among multiple users and served on first come first server basis. Examples include CPU scheduling, Disk Scheduling.

Answer 20

Queue

Question 21

Arrays, Linked Lists, Stack and queues

Answer 21

Linear data structures

Question 22

Hierarchical data structures

Answer 22

Trees

Question 23

A data structure in which each node has at most two children, which are referred to as the left child and the right child. It is implemented mainly using Links.

Answer 23

Binary Tree

Question 24

A _______ is represented by a pointer to the topmost node. If the _______ is empty, then the value of root is NULL.

A _______ node contains the following parts:

1. Data
2. Pointer to left child
3. Pointer to right child

Answer 24

Binary Tree

Question 25

A __________ can be traversed in two ways:

1) Depth First Traversal: Inorder (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)
2) Breadth First Traversal: Level Order Traversal

Answer 25

Binary Tree

Question 26

These data structures are useful for hierarchal objects or file structures where each file is located in a particular directory and there is a specific hierarchy associated with files and directories.

Answer 26

Binary Tree