Data Structures

Question 1

Data Structures

Answer 1

Containers within which information is stored

Question 2

Arrays

Answer 2

• An indexed, finite set of elements with the same data type
• Can be created in many dimensions

Question 3

Files

Answer 3

A collection of data stored permenantly on secondary storage

Question 4

Abstract Data Types

Answer 4

• Don’t exist as data structures in their own right
• Uses other data structures to form a new way of storing data

Question 5

Queues

Answer 5

• A FIFO abstract data type that is based on an array
• Used in keyboard buffers

Question 6

Linear Queues

Answer 6

• A fixed length queue with a front and rear pointer
• Once a space has been used it cannot be reused until the queue is reset

Question 7

Circular Queues

Answer 7

A queues where the front and rear pointers can move over the 2 ends of the queue

Question 8

Queue Operators

Answer 8

Enqueue, Dequeue, IsEmpty, IsFull

Question 9

Priority Queues

Answer 9

• Items are assigned a priority that determines when they are dequeued
• Uses a FIFO system for items with equal priority

Question 10

Stacks

Answer 10

• A FILO abstract data type that is based off an array
• Has a single pointer (the top pointer)

Question 11

Stack Operations

Answer 11

Push, Pop, Peek, IsFull, IsEmpty

Question 12

Stack Overflow

Answer 12

Error that occurs when a push command is executed on a full stack

Question 13

Stack Underflow

Answer 13

Error that occurs when a pop command is executed onto an empty stack

Question 14

Graph

Answer 14

An abstract data type comprising of nodes (entities) connected by edges (relationships)

Question 15

Weighted Graph

Answer 15

• A graph where each edge has an assigned value
• Represented by adjacency matrices or adjacency lists

Question 16

Adjacency Matrices

Answer 16

• A tabular representation of a graph
• Each node is assigned a row and column

Question 17

Adjacency List

Answer 17

• Represents a graph using a list
• Each node has a list of adjacent nodes

Question 18

Adjacency List vs Matrix

Answer 18

• Adjacency matrices store every possible edge, even those that do not exist
• Adjacency lists are slow to query as each item in a list must be searched sequentially
• Adjacency matrices are suited to dense graphs with high amounts of edges

Question 19

Tree

Answer 19

A connected, undirected graph with no cycles

Question 20

Rooted Tree

Answer 20

A tree with a root node

Question 21

Root Node

Answer 21

The node from which all other nodes stem

Question 22

Parent Node

Answer 22

A node from which other nodes stem

Question 23

Child Node

Answer 23

A node with a parent node

Question 24

Leaf Node

Answer 24

A child node with no children

Question 25

Binary Tree

Answer 25

A rooted tree where each parent node has no more than 2 child nodes

Question 26

Hash Tables

Answer 26

- A way of storing data with constant time complexity - Uses a hashing algorithm to return a hash - The hash is the index of the key-value pair

Question 27

Hashing Algorithm

Answer 27

An algorithm that takes an input and returns a hash

Question 28

Hash

Answer 28

- Each hash is unique to its input - They cannot be reversed to retrieve the input value

Question 29

Collision

Answer 29

- Where different inputs produce the same hash - Can be avoided by using rehashing

Question 30

Dictionaries

Answer 30

- Collections of key-value pairs - Values are accessed by their associated key

Question 31

Static Data Structures

Answer 31

- Fixed in size - Declared in memory as a series of sequential, contiguous memory locations

Question 32

Dynamic Data Structures

Answer 32

- Change in size to store their content - Store each piece of data alongside a reference to where the next item is stored in memory