Unit 7 Data Structures Flashcards

1
Q

What are the properties of a Tuple? (3)

A
  • It is an ordered set of values
  • It may have elements of mixed types
  • It is immutable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does Immutable mean?

A

Elements cannot change

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

What is a Dynamic Data Structure?

A

It can change size when required

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

What is a Static Data Structure?

A

It cannot change size

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

What are Integer, Real, Boolean and Char all examples of?

A

Elementary data types

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

What are String and Array both examples of?

A

Composite data types

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

What are List, Stack and Queue all examples of?

A

Abstract data types

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

What is an ADT?

A

Abstract Data Type
A logical description of how we view the data and possible operations

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

What does the Queue Function enQueue(item) do?

A

Adds an item to the rear

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

What does the Queue Function deQueue do?

A

Removes and returns an item from the front

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

What does the Queue Function isEmpty do?

A

Indicates if a queue is empty

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

What does the Queue Function isFull do?

A

Indicates if a queue is full

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

What happens in a Priority Queue?

A

Some items are allowed to ‘jump’ the queue

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

What is Overflow?

A

Attempting to push onto a stack that is full

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

What is Underflow?

A

Attempting to pop from a stack that is empty

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

How does a Stack operate?

A

First On Last Off

17
Q

What is a Hash Function?

A

Large data sets can be organised so each record is assigned a unique address. This unique address is calculated using a hashing algorithm or hash function. The algorithm uses some part of the record to map the record to a unique destination address

18
Q

When does a Collision happen?

A

When an algorithm generates the same address for different primary keys
A collision is sometimes referred to as a synonym

19
Q

What is a Graph?

A

A set of vertices or nodes connected by edges or arcs. Edges may be weighted, indicating a cost of traversal

20
Q

What distinguishes an Undirected Graph?

A

All edges are bidirectional

21
Q

What is an advantage of a Matrix?

A

Convenient to work with, and adding an edge is simple

22
Q

What is a disadvantage of a Matrix?

A

A sparse graph with not many connections (edges) will leave most of the cells empty, wasting a lot of memory space

23
Q

What are advantages of an Adjacency List? (2)

A
  • It only uses storage for the connections that exist, so it is more space-efficient
  • It is a good way of representing a large, sparsely connected graph
24
Q

What are some applications of Graphs? (3)

A
  • Computer networks, with nodes representing computers and weighted edges representing bandwidth between them
  • Web pages and links
  • Project management, with nodes as tasks, edges representing sequence and weights, time or cost
25
Q

What is a Tree?

A

A connected, undirected graph with no cycles

26
Q

What is an Edge?

A

A line joining 2 nodes of a tree

27
Q

What is a Root?

A

The start node of a tree that all others are connected off of

28
Q

What is a Subtree?

A

A smaller segment of a tree

29
Q

What is a Leaf?

A

A node on a tree with no children

30
Q

What is a Binary Tree?

A

A rooted tree in which each node has a maximum of two children

31
Q

On a Binary Tree, what does each Node consist of? (3)

A
  • The data (which may be a primitive or more complex object)
  • A left pointer to a child
  • A right pointer to a child
32
Q

What is Pre-order Traversal?

A

Visiting the root, then traversing the left sub-tree, then the right sub-tree. (Left dot)

33
Q

What is In-order Traversal?

A

Traversing the left sub-tree, then visiting the root, then traversing the right sub-tree. (Bottom dot)

34
Q

What is Post-order Traversal?

A

Traversing the left sub-tree, then traversing the right sub-tree, then visiting the root. (Right dot)

35
Q

What is a Balanced Binary Tree?

A

One where the nodes are distributed in such a way that the height is kept to a minimum