2: Fundamentals of Data Structures

Question 1

n-Dimensional Array

Answer 1

A set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements

Question 2

Abstract Data Structures (7)

Answer 2

• Queue
• Stack
• Graph
• Tree
• Hash table
• Dictionary
• Vector

Question 3

Static Data Structures

Answer 3

They reserve memory for a set amount of data and cannot be resized

Question 4

Dynamic Data Structures

Answer 4

They have no limit to the amount of data they can hold so can be resized

Question 5

Static vs Dynamic Data Structures (6)

Answer 5

• Static data structures have storage size determined at compile-time
• Dynamic data structures can grow during execution
• Static data structures can waste memory if the number of data items stored is small relative to the size of the structure
• Dynamic data structures only take up the amount of storage space required for the
  actual data
• Dynamic data structures require pointers to the next item whereas static data structures do not
• Static data structures store data in consecutive memory locations whereas dynamic data structures do not

Question 6

Queue (4)

Answer 6

• Items are added to the back of the queue
• Items are removed from the front of the queue
• Front and rear pointers are used

Question 7

Linear Queue

Answer 7

Once the maximum number of items has been added to the queue, no more items can be added even if some are removed

Question 8

Circular Queue

Answer 8

Once the maximum number of items has been added, if some are removed, items are added to the front of the queue

Question 9

Priority Queue (5)

Answer 9

• Each item has a priority associated with it
• The queue has different points at which items can join the queue according to priority
• They join at the back of the section according to their priority
• If there are no items queued in the correct priority section then they join the queue at the front of the next
  lower priority
• Items are still taken one at a time from the front of the entire queue

Question 10

Stack (3)

Answer 10

• Items are pushed to the back of the stack
• Items are popped from the back of the stack
• A top pointer is used for the item at the back

Question 11

Graph

Answer 11

A data structure used to represent more complex relationships

Question 12

Weighted Graph

Answer 12

A graph with a value associated with each edge

Question 13

Vertex / Node

Answer 13

A point on a graph

Question 14

Edge / Arc

Answer 14

A connection between two vertices

Question 15

Undirected Graph

Answer 15

A graph where you can traverse an edge either way

Question 16

Directed Graph

Answer 16

A graph where edged may have associated directions

Question 17

Adjacency Matrices + (3)

Answer 17

• Appropriate when there are many edges between vertices or when graph is not sparse
• Appropriate when edges frequently changed
• Appropriate when presence of specific edges needs to be tested frequently

Question 18

Tree

Answer 18

A connected, undirected graph with no cycles

Question 19

Rooted Tree (3)

Answer 19

• A tree in which one vertex has been designated as the root
• A rooted tree has parent-child relationships between nodes
• The root is the only node with no parent and all other nodes are descendants of the root

Question 20

Binary Tree

Answer 20

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

Question 21

Rooted Tree Uses (4)

Answer 21

• Binary trees are used in compilers to build syntax trees
• Binary trees are used within routers to store routing tables
• Binary search trees can be built to speed up searching
• Expression trees can be used to represent algebraic and Boolean expressions in a way that simplifies the processing of the expression

Question 22

Hash Table

Answer 22

A data structure that creates a mapping between keys and values

Question 23

Collision

Answer 23

When two key values compute the same hash

Question 24

Rehashing (4)

Answer 24

• When a collision occurs, the value is placed in the next free position in the hash table
• A pointer to the position of the value is stored in its hashed position
• When retrieving values, the key is checked against the key in the hashed position
• If they are different, the pointer position is checked

Question 25

Dictionary

Answer 25

A collection of key-value pairs in which the value is accessed via the associated key

Question 26

Dictionary Applications

Answer 26

Information retrieval

Question 27

Vector

Answer 27

A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space

Question 28

Vector Notations (5)

Answer 28

• [2.0, 3.14159, -1.0, 2.718281828]
• 4-vector over ℝ written as ℝ⁴
• Function interpretation
  0 ↦ 2.0
  1 ↦ 3.14159
  2 ↦ -1.0
  3 ↦ 2.718281828
• ↦ means maps to
• All the entries must be drawn from the same field, e.g., ℝ

Question 29

Vector Addition

Answer 29

Achieves translation

Question 30

Scalar-Vector Multiplication

Answer 30

Achieves scaling

Question 31

Convex Combination of Two Vectors

Answer 31

An expression of the form αu + βv where α, β ≥ 0 and α + β = 1

Question 32

Dot / Scalar Product of Two Vectors

Answer 32

The dot product of u = [u₁, …., uₙ ] and v = [v₁, ….., vₙ ] is:
u ∙ v = u₁v₁ + u₂v₂ + …… + uₙvₙ

Question 33

Dot Product Applications

Answer 33

Finding the angle between two vectors