Fundamentals of Data Structures

Question 1

What is an array

Answer 1

An array is an indexed set of elements. An array must be finite, indexed and must only contain elements with the same data types.

Question 2

What is a queue

Answer 2

A queue is an abstract data structure based on an array. Queues are FIFO abstract data structures (First in First out)

Question 3

What is a Linear Queue

Answer 3

A linear queue has two pointers, a front pointer and a rear pointer. The queue is full if there are no available positions on or after the rear pointer.

Question 4

What is a Circular Queue

Answer 4

A circular queue is a queue in which the front and rear pointers can move over the two ends of the queue, making for a more memory efficient data structure.

Question 5

What is a Priority Queue

Answer 5

In a priority queue, items are assigned a priority. Items with the highest priority are dequeued before low priority items. If two items have the same priority, FIFO is used.

Question 6

Name 3 operations that can be performed on a queue

Answer 6

Enqueue

Dequeue

IsEmpty

IsFull

Question 7

What is a stack

Answer 7

A stack is a FILO (first in last out) abstract data structure. Stacks have just one pointer, a top pointer.

Question 8

Name 3 operations that can be performed on a stack

Answer 8

Push
Pop
PeekIsFull
IsEmpty

Question 9

What is a stack overflow error

Answer 9

When you attempt to add an item to a stack with no available spaces

Question 10

What is a stack underflow error

Answer 10

When you attempt to pop an item from an empty stack

Question 11

What is a graph

Answer 11

A graph is an abstract data structure used to represent complex relationships between items within datasets. A graph consists of nodes (vertices) which are joined by edges (arcs).

Question 12

What is the difference between a graph and a weighted graph.

Answer 12

A weighted graph is one in which edges are assigned a value, representing a value such as time, distance, cost, etc.

Question 13

What is an Adjacency Matrix

Answer 13

An adjacency matric is a tabular representation of a graph, each of the nodes in the graph is assigned both a row and a column in the table, a 1 is used to show an edge exists between 2 nodes and a 0 indicates that there is no connection. (if the graph is weighted, use the weight instead of 1, and infinity instead of 0)

Question 14

What is an Adjacency List

Answer 14

Rather than using a table to represent a graph, a list can be used. For each node in the graph, a list of adjacent nodes is created, this means that only existing connections are stored, which is more memory efficient.

Question 15

What is a tree

Answer 15

A tree is a connected, undirected graph with no cycles.

Question 16

What is a rooted tree

Answer 16

a rooted tree has a root node from which all the other nodes stem. When displayed as a diagram, the root node is usually at the top of the tree. Nodes with children are called parent nodes, nodes with a parent are called child nodes, and nodes with no children are called leaf nodes.

Question 17

What is a binary tree

Answer 17

A binary tree is a rooted tree in which each parent node has no more than two child nodes.

Question 18

What is a Hash Table

Answer 18

hash tables are a way of storing data that allows data to be retrieved with a constant time complexity of O(1). A hashing algorithm takes an input and returns a unique irreversible hash. The has is used as an index in the hash table which stores key-value pairs.

Question 19

How do you deal with collisions in a hash table

Answer 19

There are many techniques to deal with collisions, one is to keep on moving to the next position until an available one is found.

Question 20

What is a dictionary

Answer 20

A dictionary is a collection of key-value pairs in which the value is accessed by its associated key.

Question 21

What is Convex combination of two vectors.

Answer 21

If you have two vectors, a and b, then a convex combination of the two would be ax + by where x and y are both non-zero numbers less than 1 that add to 1

Question 22

What is the dot product of two vectors

Answer 22

The dot product is a single number derived from the components of two vectors that can be used to determine the angle between them.

Question 23

What is the difference between a static and dynamic data structure.

Answer 23

Static data structures have a fixed size (stores items as a series of sequential memory locations) whereas dynamic data structures can be any size, instead of being stored sequentially, each item is stored alongside a reference to where the next item is stored. The advantage to dynamic structures is the dynamic size, however a downside is that they require more work on the part of the computer to set up and use.

Question 24

Define “Abstract data structure”

Answer 24

Data structures that dont exist as data structures in their own right, by make use of other data structures to form a new way of storing data.

Question 25

Which are best suited to dense graphs, adjacency matrices or adjacency lists

Answer 25

adjacency matrices are better for dense graphs, adjacency lists are better for sparse graphs.