Fundamentals of Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is a data structure

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an abstract data type

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

Array (List)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a Record

A

Is one line of a text file or array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Field

A

an item of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a Queue? (use XIXO)

A

FIFO - can be static or dynamic data strucutre

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a Stack? (use XIXO)

A

LIFO - can be static or dynamic data strucutre

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Linear Queue? (use XIXO)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Circular Queue? (use XIXO)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a Priority Queue? (use XIXO)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a Graph?

A

A way of describing relationships between pairs of objects

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Define vertex/vertices

A

Object in a graph (known as a node)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is an Arc?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Graphs can be undirected, directed and…

A

weighted and unweighted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is an Adjacency List?

A

Data structure to store a list of nodes and adjacent nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is an Adjaceny Matrix?

A

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

17
Q

What is a Tree?

A

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

18
Q

Define a Hash Table

A

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

19
Q

Name some uses of hashing algorithms

A
  • 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.
20
Q

What is a dictionary?

A

A data structure that maps keys to data

21
Q

What is an Associative Array?

A

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

22
Q

Define the technique chaining.

A

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.

23
Q

Define the technique rehashing.

A

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

24
Q

What is a component of a vector?

A

The values within the vector

25
Q

What is a scalar?

A

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

26
Q

What is a dot product multiplication?

A

Multiplying two vectors together to produce a number

27
Q

What is convex combination?

A

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

28
Q

Define the term convex hull

A

A spatial representation of the vector space between two vectors.

29
Q

Define the term vector space

A

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

30
Q

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

A

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