Data Structures

Question 1

What are the common data structures?

Answer 1

Queues
Lists
Stack,
Arrays
Hash Tables
Graphs
Trees
Binary Search Trees

Question 2

What is an abstract data type?

Answer 2

Logical representation of the data and enforced behaviour where the user does not know how the data structure is actually implemented.

Question 3

Operations of a queue

Answer 3

Enqueue
Dequeue
IsFull
IsEmpty
Peek

Question 4

Operations of a stack

Answer 4

Push
Pop
IsFull
IsEmpty
Peek

Question 5

What is the difference between static and dynamic data structures?

Answer 5

Static data structure - fixed size
Dynamic data structure - grows and shrinks to match its contents

Question 6

Definition of a queue

Answer 6

-Abstract data structure
-First thing to be added to queue is first out (FIFO)
-Front and rear pointer

Question 7

Types of queue

Answer 7

Linear
Circular
Priority

Question 8

Describe a linear queue

Answer 8

-Has front and rear pointer
-Queue can run out of space as front pointer reaches end of available addresses
-Follows First In First Out (FIFO) approach

Question 9

Describe a circular queue

Answer 9

Front and rear pointer can point at index zero when it reaches end of available address
More memory efficient because it can reuse a previously used space

Question 10

Describe a priority queue

Answer 10

Item given priority
Item with highest priority dequeued before the items with lower priority
2 items with same priority follow First In First Out (FIFO)

Question 11

Definition of a stack

Answer 11

-Abstract data structure
-First item to be pushed is last to be popped (First In Last Out)
-Top Pointer (Bottom is always index 0, so no need for bottom pointer)

Question 12

Definition of a hash table

Answer 12

Used to change data with a one way transformation with a mathematical process (different to encryption as it cannot be reversed)
If two inputs hash to the same index, collision occurs and skip value is added on to destination index to get a new index (repeat process again)
Modulus operator is used if you reach the last index to go to the starting index
Skip value is set as part of table
Hash table ideally 2/3 full because reduces odds of collisions without being too memory inefficient

Question 13

Explain the process of resizing a hash table

Answer 13

Take the number of items in hash table and multiply by 1.5
Create new hash table of that size and traverse old hash table, rehashing each item

Question 14

Definition of a tree

Answer 14

A connected, undirected graph with no cycles

Question 15

Definition of a binary tree

Answer 15

A rooted tree in which each node has at most 2 children

Question 16

Definition of rooted tree

Answer 16

A tree in which one node has been designated as the root

Question 17

Definition of directed graph

Answer 17

A graph where the order of the vertices paired in an edge matter (one way)

Question 18

Definition of undirected graph

Answer 18

A graph where the order of the vertices paired in an edge does not matter. (bidirectional)

Question 19

What is an Adjacency Matrix

Answer 19

A matrix representation of a graph that stores the edges connecting all possible nodes.

Question 20

Definition of a weighted graph

Answer 20

A graph where each edge has an associated value