Unit 7 - Data Structures Flashcards Preview

A level Computer Science > Unit 7 - Data Structures > Flashcards

Flashcards in Unit 7 - Data Structures Deck (21)
Loading flashcards...
1
Q

What is an Abstract Data Type?

A

An ADT (Abstract Data Type) is a logical description of how we view the data type and possible operations.

2
Q

What is encapsulation?

A

Encapsulation is a form of information hiding, a form of abstraction which ADTs use.

3
Q

Give the process of a queue.

A

Add an item to the rear
Remove an item from the front
Check if the queue is full
Check if the queue is empty

4
Q

What is a hash function?

A

A hash function is a function used to obtain the unique address of a record of a large data set.

5
Q

What is a collision?

A

A collision is where the algorithm generates the same address for different keys.

6
Q

Give one problem with hash tables.

A

One notable issue with hash tables is the increase in collisions as the table fills up.

7
Q

Give the names of hashing algorithms.

A
  • Mid square method

- Folding method

8
Q

What is the mid-square method?

A

Mid square method is where a number is squared, then a few digits are extracted and the mod function is performed to get an address.

9
Q

What is the folding method?

A

The folding method is where the a number is divided into pieces of equal sizes, and these segments of the number are added together. The result will be mod by the table size, and the remainder obtained is the address.

10
Q

What is a graph?

A

A graph is an abstract data structure which represents complex relationships.

11
Q

Describe an undirected graph.

A

An undirected graph is a graph consisting of nodes being joined together by edges (links), each with a weight (number). But there are no arrows on the edges, hence there is no direction.

12
Q

Describe a directed graph.

A

A directed graph does show the direction of edges, so links between nodes can be identified. There are no weights on the edges, however.

13
Q

Define a graph.

A

A graph is a set of vertices and nodes connected by edges. The edges may sometimes have a weight value on them, representing the magnitude of a value.

14
Q

What are the two ways to represent a graph?

A
  • Adjacency matrix

- Adjacency list

15
Q

Define an adjacency matrix.

A

The adjacency matrix is a square matrix grid representing the nodes and their connections to other nodes, in both weighted and unweighted graphs.

16
Q

What important property does an adjacency matrix have in an undirected graph?

A

In an undirected graph, the nodes in the adjacenvy matrix are symmetrical.

17
Q

Give an advantage of adjacency matrix.

A

It is a very convenient method to use when representing a graph, as it is very simple to understand.

18
Q

State a disadvantage of the adjacency matrix.

A

All the spaces on the matrix won’t be filled up and if there are many empty spaces then this can waste a lot of memory.

19
Q

What is an adjacency list?

A

An adjacency list is another method to represent a graph, involving a dictionary style structure.

20
Q

Describe the structure of the adjacency list.

A

In an adjacency list, each node will point to its adjacent nodes.

21
Q

Give some applications of graphs.

A
  • Finite State Machines
  • Computer Networks
  • Search engine (most notably, Google)