4.2 - Funamentals of data structures

Question 1

What is a static data structure?

Answer 1

A data structure which reserves memory for a set amount of data. Meaning that it has limited capacity for data

Question 2

What is the advantage of a static array?

Answer 2

They are efficient in terms of being able to access elements directly by index

Question 3

What are the disadvantages of a static array?

Answer 3

• Memory is wasted if its full capacity isn’t used
• if insufficient space has been allocated, the program may crash or not work properly

Question 4

What is a dynamic data structure?

Answer 4

A data structure which has a non-fixed memory capacity with the number of data items it can hold only being limited by the overall memory allocation to the program.

Question 5

What are the advantages of dynamic data structures?

Answer 5

• They are memory efficient
• its size is not predetermined

Question 6

What is the disadvantage of dynamic data structures?

Answer 6

The elements cannot be readily accessed directly by index but rather sequentially by memory location

Question 7

What is a queue?

Answer 7

An abstract data type that holds an ordered linear sequence of items in the form FIFO

Question 8

How is the order of a queue kept?

Answer 8

A pointer is maintained at the front to indicate the element in the front of the queue and a pointer is maintained at the rear to identify the last item in the queue

Question 9

What is an abstract data type?

Answer 9

An abstract data type is the building blocks of a data type/data structure, defining the behaviour and properties of it, without specifying its implementation.

Question 10

What is a concrete data type?

Answer 10

A concrete data type provides a specific implementation of the abstract data type that determines how the data is stored and accessed in memory.

Question 11

What is a data type?

Answer 11

A data type specifies the format of the data and the range of values that can be assigned to it. It defines the set of operations that can be performed on the data and the rules for performing these operations.

Question 12

What is a data structure?

Answer 12

A data structure defines the way data is organized and stored in memory. It specifies how the individual data items are related to each other and how they can be accessed and manipulated efficiently.

Question 13

What is a priority queue?

Answer 13

A queue where each item inserted into the queue is given a certain level of priority. That item is put in from of all items of a lower priority but ahead of those of higher priority.

Question 14

What are the main operations on a queue?

Answer 14

enqueue(data) - adds an element to the queue
dequeue() - returns an element from the front of the queue
is_empty() - check whether the queue is empty
is_full() - check whether the (static only) queue is at maximum capacity

Question 15

Difference between abstract data type and concrete data type?

Answer 15

An abstract data type is the framework of the data type, for example a stack is a first in last out data structure and has functions such as pop and append related to it. Whereas a concrete data type is the implementation of the abstraction, for example the stack can be implemented using an array.

Question 16

Examples of data types?

Answer 16

Integer: used to represent whole numbers
Float: used to represent decimal numbers
Boolean: used to represent true/false values
Character: used to represent single letters or symbols
String: used to represent a sequence of characters

Question 17

Examples of data structures?

Answer 17

Array: a collection of data items of the same type, stored in contiguous memory locations
Linked List: a collection of nodes, each containing data and a reference to the next node in the sequence
Queue: a data structure that allows access to only the oldest added item, using the First-In-First-Out (FIFO) principle
Tree: a hierarchical data structure consisting of nodes, with a single root node and zero or more child nodes at each level

Question 18

What is a linear queue?

Answer 18

A queue stored in an array where, as more items are enqueued and dequeued, the pointers move up the array.
It is limited by the length of the array in which it is stored, so the end of the array will eventually be reached if elements are not constantly moved up to the start of the array which can be time consuming.

Question 19

What is a circular queue?

Answer 19

A queue which reuses the empty slots at the front of the array when elements are removed from the queue. When the rear pointer reaches the last position of the array, it wraps back round to the start of the array. The front pointer moves similarly as items are dequeued.

Question 20

What is a graph?

Answer 20

An abstract data type that can be used to represent complex, non-linear relationships between objects.

Question 21

What are records?

Answer 21

Records are a type of data structure containing several fields used to store data. Each field within a record is usually identified by a name, and the data in each field can be of different types, such as numbers, strings, or dates.

Question 22

What does a graph consist of?

Answer 22

Nodes (or vertices) which are connected by edges (or arcs)

Question 23

What makes 2 nodes neighbours?

Answer 23

When they are connected by an edge.

Question 24

What is the degree of a node?

Answer 24

The number of nodes that is connected to it (i.e. the number of neighbours that it has)

Question 25

What is a loop in a graph?

Answer 25

An edge that connects a node to itself

Question 26

How are records implemented?

Answer 26

Records are in built data structures in certain languages, however in python you can use a class where each attribute represents a field.

Question 27

What is persistent data (file handling)?

Answer 27

Persistent data is data that is stored in secondary storage and will be available whenever the application is used. All persistent data is stored in files.

Question 28

What is a path in a graph?

Answer 28

A sequence of nodes that are connected by edges

Question 29

What is a cycle in a graph?

Answer 29

A closed path, meaning that it starts and ends at the same node with no nodes being visited more thatn once

Question 30

What is an undirected graph?

Answer 30

A graph which allows you to move in either direction between nodes.

Question 31

What is a directed graph?

Answer 31

A graph where the edges have direction, meaning that you can only move between nodes in specific directions

Question 32

How can data/persistent data be stored?

Answer 32

Persistent data can be stored as a single file, or for larger systems it can be stored a collection of related files. Some applications use databases. Databases are large complex file systems where all of the low level file organisation and access is managed for you. However for smaller applications, a more simple file structure is needed.

Question 33

What is a weighted graph?

Answer 33

A graph where its edges have a cost to follow that direction. An example being that the distances between towns.

Question 34

What is a tree?

Answer 34

A connected, undirected graph with no cycles and 0 or more child nodes

Question 35

What is a stack?

Answer 35

A stack is an abstract data type/structure, that holds an ordered, linear sequence of items. A stack is a first in, last out data structure, meaning items can only be retrieved from the top of the stack.

Question 36

What does it mean that a graph is connected?

Answer 36

That there is a path from any node to any other node and no node is disconnected from the others

Question 37

What are the main operations of a stack?

Answer 37

push(data): adds an element to the top of the stack
pop(): removes an element from the top of the stack
peek(): returns a copy of the element on the top of the stack without removing it
is_empty(): checks whether a stack is empty
is_full(): checks whether a stack is at maximum capacity when stored in a static (fixed-size) structure

Question 38

What is the difference between a tree and a rooted tree?

Answer 38

While a tree can start its traversals from any node on the tree, a rooted tree has a single node (or root) with no parent nodes which all traversals start from

Question 39

What is a hash table?

Answer 39

A hash table is a data structure that implements an associative array (a dictionary). In an associative array, data is stored as a collection of key-value pairs. The position of the data within the array is determined by applying a hashing algorithm to the key - a process called hashing. The hashing algorithm is called a hash function.

Question 40

What is the root of tree?

Answer 40

The start node for tree traversals in rooted trees

Question 41

What are the advantages of a hash table?

Answer 41

A hash table allows for very efficient lookup, insertion, and deletion of values based on their keys. They have an average time complexity of O(1) for lookup, insertion, and deletion operations. Worst-case time complexity for these operations can be O(n), where n is the number of keys in the table, if there are many collisions.

Question 42

What is the leaf of a tree?

Answer 42

The end point of a tree graph with no child nodes.

Question 43

What is a branch of a tree?

Answer 43

A path from the root (starting node) of the tree to a leaf (end point)

Question 44

What is the height of a tree?

Answer 44

The number of edges that connects the root node to the leaf node that is furthest away from it, i.e. the longest branch

Question 45

How many edges does a tree have?

Answer 45

The number of nodes minus 1

Question 46

What is a binary tree?

Answer 46

A rooted tree where each node has at most 2 child nodes

Question 47

What is a binary search tree?

Answer 47

A binary tree which is ordered to optimise searching. For every parent node, the nodes on the left-hand side have a smaller value than the parent node and the nodes on the right-hand side have a large value than the parent node.

Question 48

What is a dictionary?

Answer 48

A concrete data structure that defines an unordered collection of data as a set of key-value pairs.
Each key must be unique and has an associated value. The key must be a simple type like integers or strings but the value can be any type

Question 49

What is a hash function?

Answer 49

A hash function in a hash table is the algorithm which allocates an index in an array, for each key in the hash table. This means that each key corresponds to an index in the array of values.

Question 50

What are the standard dictionary operations?

Answer 50

• retrieve a value associated with a particular key
• insert a new key-value pair into the collection
• remove a key-value pair into the collection
• update a value associated with a key

Question 51

What is the benefit of using a key to directly access items stored within a dictionary

Answer 51

It provides much quicker access to unordered data than searching through the data set using linear search or binary search

Question 52

What is rehashing?

Answer 52

Rehashing is the process of creating a new hash table with a larger capacity and moving the key-value pairs from the old table to the new table to reduce collisions and maintain performance.

Question 53

What are the steps of adding an item into a static stack data structure?

Answer 53

Check stack is not full, increase rear pointer by one, place item.

Question 54

When is it beneficial to use an adjacency matrix over an adjacency list?

Answer 54

When there are more adjacencies between nodes on a graph.