Fundamentals of Data Structures

Question 1

What is a data structure

Answer 1

A common format for storing large volumes of related data, which is an implementation of an abstract data type!

Question 2

What is an abstract data type

Answer 2

A conceptual model of how data can be stored and the operations that can be carried out on the data

Question 3

Name the data structure that holds a set of related data items stored under a single identifier.
This can also work on one or more dimensions

Answer 3

Array (List)

Question 4

What is a Record

Answer 4

Is one line of a text file or array

Question 5

What is a Field

Answer 5

an item of data

Question 6

What is a Queue? (use XIXO)

Answer 6

FIFO - can be static or dynamic data strucutre

Question 7

What is a Stack? (use XIXO)

Answer 7

LIFO - can be static or dynamic data strucutre

Question 8

What is a Linear Queue? (use XIXO)

Answer 8

FIFO - organised as a line of data (like a list)

Question 9

What is a Circular Queue? (use XIXO)

Answer 9

FIFO - organised as a ring, using front and rear pointers (re-uses lost memory)

Question 10

What is a Priority Queue? (use XIXO)

Answer 10

FIFO - some data may leave out of sequence if it has priority, high priorities go to the top

Question 11

What is a Graph?

Answer 11

A way of describing relationships between pairs of objects

Question 12

Define vertex/vertices

Answer 12

Object in a graph (known as a node)

Question 13

What is an Arc?

Answer 13

A join or relationship between two nodes (known as an edge)

Question 14

Graphs can be undirected, directed and…

Answer 14

weighted and unweighted

Question 15

What is an Adjacency List?

Answer 15

Data structure to store a list of nodes and adjacent nodes

Question 16

What is an Adjaceny Matrix?

Answer 16

Data strucutre as a 2D array that shows if there is a relationship between each pair of nodes (think times table grid)

Question 17

What is a Tree?

Answer 17

Data strucutre very similar to a graph, except with no loops

Question 18

Define a Hash Table

Answer 18

A data structure made of two parts.

1) A table or array of data
2) a key which identifies the location of the data within the table

Question 19

Name some uses of hashing algorithms

Answer 19

• Used to create indicies for databases enabling quick storage and retrival of data
• Used to generate memory addresses where data will be stored. (especially with cache memory where it is stored temporarily)
• Used to encrypt data. In this case the algorithm must be complex so it cannot be reverse engineered.

Question 20

What is a dictionary?

Answer 20

A data structure that maps keys to data

Question 21

What is an Associative Array?

Answer 21

Like a dictonary but two-dimensional. A 2D data strucutre containing key/value pairs of data.

Question 22

Define the technique chaining.

Answer 22

A technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index.

Question 23

Define the technique rehashing.

Answer 23

The process of running the hashing alogrithm again when a collision occurs.

Question 24

What is a component of a vector?

Answer 24

The values within the vector

Question 25

What is a scalar?

Answer 25

A real value used to multiply a vector to scale the vector.

Question 26

What is a dot product multiplication?

Answer 26

Multiplying two vectors together to produce a number

Question 27

What is convex combination?

Answer 27

A method of multiplying vectors that produces a resulting vector within the convex hull

Question 28

Define the term convex hull

Answer 28

A spatial representation of the vector space between two vectors.

Question 29

Define the term vector space

Answer 29

A collection of elements that can be formed by adding or multiplying vectors together.

Question 30

Given two vectors, u = [1, 1, 1, 1] and v = [1, 0, 1, 1] work out the dot product u.v

Answer 30

= 1 AND 1 XOR 1 AND 0 XOR 1 AND 1 XOR 1 AND 1
= 1 XOR 0 XOR 1 XOR 1
= 1