1.4.2 - Data Structures Flashcards

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

What is an array?

A

An ordered, finite set of elements of a single data type.

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

What does zero-index mean?

A

The first element in the array is considered to be at position zero.

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

What is a list?

A

A data structure consisting of a number of ordered items where the items can occur more than once.

They can store values of different data types and they are stored non-contiguously.

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

What is a tuple?

A

An ordered set of values of any type. A tuple is immutable which means it cannot be changed.

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

What is a linked list?

A

A dynamic data structure used to hold an ordered sequence.

Each item contains an index, a data field and a pointer to the next index.

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

What is a graph?

A

A graph is a set of vertices or nodes connected by edges.

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

What are the three types of graphs?

A

Directed, undirected and weighted.

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

What is a directed graph?

A

The edges can only be traversed in a single direction.

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

What is an undirected graph?

A

The edges can be traversed in both directions.

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

What is a weighted graph?

A

A ‘weight’ is attached to each edge.

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

What are the two ways computers are able to process graphs?

A

Using an adjacency matrix or an adjacency list.

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

What is an adjacency matrix?

A

A table that contains all of the possible connections between a graph.

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

What is an adjacency list?

A

A list that contains all of the links for a node of the array.

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

What are the advantages of an adjacency matrix?

A

Convenient to work with due to quicker access times.

Easy to add nodes.

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

What are the advantages of an adjacency list?

A

More space efficient for large, sparse graphs.

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

What is a stack?

A

A stack is a last in, first out data structure.

17
Q

What can stacks be used for?

A

The ‘undo’ operations in applications.

18
Q

What is a queue?

A

A queue is a first-in, first-out data structure.

19
Q

What can queues be used for?

A

Printers, keyboards and simulators.

20
Q

What is a tree?

A

A connected form of graph.

21
Q

What is a binary tree?

A

A tree where each node has a maximum of two children.

22
Q

What is a binary tree used to do?

A

Represent information for binary searches.

23
Q

What are the three ways of traversing through a binary tree?

A

Pre-order, in-order, post-order.

24
Q

What is a hash table?

A

An array which is used with a hash function. The index of the array to use is determined from the hash function.

25
Q

What features should a good hashing function have?

A

A low probability of collisions.