Data Structures

Question 1

What is an array?

Answer 1

An array is a data structure of fixed-size, which can hold items of the same data type.

Question 2

Why do arrays in JavaScript not have a fixed-size?

Answer 2

This is because arrays in JS are actually objects, whose keys are strings that look like non-negative numbers.

Question 3

What is a linked list?

Answer 3

A linked list is a data structure that consists of a sequence of items in linear other that are linked to each other.

Question 4

What are data structures?

Answer 4

Data structures are data organisation, management and storage formats that allow for efficient data access and management.

Question 5

Describe the different parts that make up a linked list.

Answer 5

All the elements in a linked list are known as nodes. Each node contains a key and a pointer to its successor node, known as next. The beginning of the linked list is stored in a head pointer, which points to the first node. The end of the list of the list is stored in a tail pointer, which points to the last node.

Question 6

What are three types of linked lists?

Answer 6

Singly linked list, doubly linked list, and circular linked list.

Question 7

What is a singly linked list?

Answer 7

It is a linked list that can be done in the forward direction only.

Question 8

What is a doubly linked list?

Answer 8

It is a linked list that can be done in both forward and backward directions. The nodes in this list will contain an additional pointer known as ‘prev’.

Question 9

What is a circular linked list?

Answer 9

It is a linked list where the prev pointer of the head points to the tail, and the next pointer of the tail points to the head.

Question 10

What three operations can be performed on a linked list?

Answer 10

Search, Insert, and Delete.

Question 11

What does the Search operation on a linked list do?

Answer 11

The search operation will find the first element with the matching given key by doing a linear search and will return a pointer to this element.

Question 12

What does the Insert operation on a linked list do and what are the three ways this can be done?

Answer 12

The insert operation will insert a given key into to the linked list. A key can be inserted at the beginning of the list, the end of the list and the middle of the list.

Question 13

What does the Delete operation on a linked list do and what are the three ways this can be done?

Answer 13

The delete operation removes an element with the matching given key from a linked list. A key can be inserted at the beginning of the list, the end of the list and the middle of the list.

Question 14

What is a Hash Map/Table?

Answer 14

A hash map is a data structure that stores values that have keys associated with them.

Question 15

What is a hash function and how does it work?

Answer 15

A hash function is a function used to map data of arbitrary size to one of a fixed size. The function works by calculating a hash value for a given key, which indicates the index of a map/table to which the value will be mapped.

Question 16

What is the hash function equation and what does each part represent?

Answer 16

h(k) = k % m; h = the hash value; k = the key to calculate the hash value for; m = the size of the hash map/table.

Question 17

What is collision in a hash map?

Answer 17

Collision occurs when the hash function calculates the same index/hash value for more than one key.

Question 18

How can collision in a hash map be solved?

Answer 18

Collision in a hash map can be solved by the process of chaining. This is where instead of the table/map storing the values itself, each index/slow will instead store a pointer to a linked list that will instead hold the values for all the keys that hash to that index.

Question 19

What is a binary tree?

Answer 19

A binary tree is a tree-like data structure whose nodes at most can have two children. Every node in a binary tree will hold a value, and can have either a left of right reference, or both.

Question 20

What are the components of a binary tree structure? Explain what each one is.

Answer 20

A binary tree is composed of the following:

• Node - the tree’s termination point.
• Root node - the topmost node in the tree.
• Parent node - a node, excluding the root, that has at least one sub-node.
• Child node - a node that is connected to a parent node.
• Leaf node - an external node that has no child/sub-node.
• Internal node - an internal node that has at least one child/sub-node connected to it.

Question 21

What are the components of a binary node?

Answer 21

A binary node can be composed of the following:

• A data value.
• Pointer to the left subtree.
• Pointer to the right subtree.

Question 22

List the different types of binary trees and explain their characteristics.

Answer 22

Four examples of types of binary trees include:

• Full binary trees - every node except the leaf/external node has two children.
• Complete binary tree - all the tree levels are filled entirely with nodes.
• Perfect binary tree - all the internal nodes have strictly two children, and every external/leaf node is at the same level of depth.
• Degenerate binary tree - where every internal node has only a single child.

Question 23

What are the ways a tree data structure can be traversed? Explain each traversal method.

Answer 23

There are three ways a tree data structure can be traversed:

• In-order Traversal - in this method the left child node is visited first, then the root node, and then the right node. The sub-trees at lower depths are also traversed in-order too.
• Pre-order Traversal - in this method the root is visited first, then the left subtree and then finally the right subtree. The sub-trees at lower depths are also traversed in pre-order too.
• Post-order Traversal - in this method, the root node is visited last. The left subtree is traversed first, then the right subtree, and then the root node. The sub-trees are lower depths are also traversed in post-order too.

Question 24

What type of tree traversal method is illustrated here?

Answer 24

In-order Traversal.

Question 25

What type of tree traversal method is illustrated here?

Answer 25

Pre-order Traversal

Question 26

What type of tree traversal is illustrated here?

Answer 26

Post-order Traversal.