# Set 6 Flashcards

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

What is a static data structure?

A

A data structure that reserves a fixed amount of memory, specified by the programmer in advance of its use

2
Q

What is a dynamic data structure?

A

Data structures that have no fixed size. The memory used grows and shrinks as items are added/removed

3
Q

Give two advantages of static data structures over dynamic data structures:

A
• Data is quicker to access directly, with minimal overhead
• No additional memory is needed to store all of the pointers
4
Q

Give two advantages of dynamic data structures:

A
• There is no wasted memory
• There is no theoretical limit on the number of items that can be added
5
Q

Is a queue FIFO or LIFO?

A

FIFO (First in first out)

6
Q

Give the four key operations of a queue:

A
• Enqueue - adds item to rear of the queue
• Dequeue - removes item and returns item from the front of the queue
• IsEmpty - checks if the queue is empty
• IsFull - checks is the queue is full
7
Q

Describe briefly the data structures and pointers used by a linear queue:

A
• Linear queues are implemented with arrays (or lists)
• They use a front and rear pointers to point to:
• front → the next item to dequeue
• rear → last item enqueued
8
Q

Disadvantages of linear queues if you
1. Don’t shuffle down the items
2. If you do

A
1. There is a limit on the number of items that can be added and removed (maxSize)
2. Implementing a linear queue where you “shuffle” the items down each time an item is dequeued is very processing intensive
9
Q

What is the key difference between a circular queue and a linear queue?

A
• Circular queues virtually connect the end to the start of the array
• This overcomes the problem of reusing spaces in the array
10
Q

What happens to the `rear` pointer when enqueuing an item to a circular queue?

A

`rear ← (rear + 1) % maxSize`

11
Q

What is a priority queue? How does enqueuing work?

A
• A queue where each element in the queue has a priority
• When new elements are enqueued, they are inserted ahead of those of lower priority and behind elements of equal or greater priority
12
Q

Name an algorithm that can be implemented with a priority queue

A

Dijkstra’s Algorithm

13
Q

Is a graph static or dynamic?

A

Dynamic, they can grow and shrink in size

14
Q

What is a graph?

A

Graphs are sets of vertices (nodes) and the edges (arcs) that connect them

15
Q

What is a graph with a high ratio of edges to vertices called?

A

Dense

16
Q

What is a graph with a low ratio of edges to vertices called?

A

Sparse

17
Q

What is a weighted graph?

A

A graph that has weights (number values) on each edge

18
Q

What is a connected graph?

A

A graph where there is a path between each pair of vertices

19
Q

Suggest three things that graphs could be used to model

A
• Social networking: the nodes could be individual people. An edge could represent that two people are acquaintances.
• Transport networks: the nodes could be towns. An edge could represent that a train line connects two towns.
• The internet: the nodes could be routers. An edge could represent that two routers are connected.
20
Q

Give two ways to represent graphs:

A

21
Q

How do you represent no edge for a weighted graph?

A

“-” or “∞” (can’t use zero)

22
Q

How could an adjacency list be implemented if graph is 1. weighted 2. unweighted?

A
1. List of dictionaries if weighted
2. List of lists if unweighted
23
Q

A
• Adjacency lists are very space efficient, as no memory is needed to store the empty spaces
• It is easy to add / delete nodes
24
Q

What is the disadvantage of an adjacency list:

A

Slow to query (e.g. to check the presence of an edge), as each item in the list must be searched sequentially until the desired edge is found

25
Q

A
• If the graph is sparse, then there are lots of empty spaces, which is wasted memory
• It can be hard to add / delete nodes if a 2D static array is used
26
Q

What is a tree?

A

A connected, undirected graph with no cycles

27
Q

What is a rooted tree?

A
• A tree in which one vertex has been designated as the root
• Rooted trees have parent-child relationships between adjacent nodes
• The root is the only node with no parent. All other nodes are descendants of the root
28
Q

What is an internal node?

A

A node in a rooted tree which has a parent and at least one child

29
Q

What is a leaf node?

A

A node in a rooted tree that has a parent but is not the parent of other nodes (no child nodes)

30
Q

Suggest a use for rooted trees

A

A game tree, where edges represent moves, and nodes represent all possible positions in the game

31
Q

What is a binary tree?

A

A rooted tree in which each node has at most two child nodes

32
Q

Name a common application of binary trees

A

Binary search trees

33
Q

What is an ordered binary tree?

A
• A type of binary tree where the data items are in a particular order
• Items left of a node have a value less than the node
• Items right of a node have a value greater than the node
34
Q

What is a hash table?

A

A data structure that creates a mapping between keys and values

35
Q

What is the purpose of a hash table?

A
• To provide a way of storing a list of values in which a key is used to locate values in the list without searching through all other values
• They are used so that records can be retrieved quickly
36
Q

What does a hash function/algorithm do in a hash table?

A

Computes the array index for the value to be stored or retrieved

37
Q

What is hashing?

A

Hashing is the irreversible process of converting data of arbitrary length into data of a fixed length.

38
Q

When does a collision occur (hashing)?

A

When two or more keys hash to the same index

39
Q

When are collisions unavoidable (hashing)?

A

When the number of possible keys is larger than the number of available spaces

40
Q

What is a dictionary?

A
• A collection of key-value pairs in which the value is accessed via the associated key
• There can be no duplicate keys
41
Q

Name an application of dictionaries

A

Dictionary based compression

42
Q

What is the meaning of the symbol ↦ ?

A

Maps to

43
Q

Describe the steps involved in rehashing

A
• A larger hash table is created
• Each value in the existing table is inserted into the new table in a position determined by a new hashing algorithm
44
Q

Describe the steps involved in rehashing

A
• A larger hash table is created
• Each value in the existing table is inserted into the new table in a position determined by a new hashing algorithm
45
Q

Describe the steps involved in adding a record to a hash table

A
• Hash algorithm applied to key, which returns the location (often an array index) in table where the record should be stored
• If location is not empty, a collision has occurred
Open addressing is used (the next free location is used, wrapping round at the end of the array)
– Or rehashing occurs (starting from scratch with a larger array)
– Or chaining is used (a pointer to a list is stored at each location a collision has occurred)
46
Q

Name three methods of collision handling (for a hash table)

A
• Rehashing
• Chaining
47
Q

How are collisions resolved with chaining?

A

A pointer to a list is stored at each location that points to a list of items that have collided at that location

48
Q

How are collisions resolved with open addressing?

A

The item is stored in the next available location in the hash table (wrapping around at the end)

49
Q

Example of where parity bits are typically used

A

In the transmission of 7-bit standard ASCII codes

50
Q

What is a downside of majority voting?

A

If you choose a large odd number of repetitions, there is lots of redundant information that needs to be transmitted across the channel

51
Q

What is a checksum?

A
• A checksum is a piece of data that is added to a block of data to enable error detection.
• It is produced by applying a checksum algorithm (often MOD to limit magnitude of checksum).
• The receiver recalculates the checksum and if it doesn’t match the data’s checksum then there is an error in the data
52
Q

What is a check digit?

A
• An extra digit that is placed at the beginning or end of a number and is used to identify a product or verify a user
• It allows for error detection
• They are produced by algorithms that often use modulo arithmetic
53
Q

Name an application of breadth-first search

A

Finding the shortest path for an unweighted graph

54
Q

Name an application of depth-first search

A

Navigating a maze

55
Q

Give two differences between depth-first traversal and breadth-first traversal:

A

DF: Chooses to explore the most recent node to be discovered
BF: Chooses to explore the least recent node to be discovered

DF: Implemented using a stack (when implemented iteratively)
BF: Implemented using a queue (when implemented iteratively)

56
Q

What is tree traversal?

A

Visiting the nodes of a tree in a specific order

57
Q

Use of pre-order traversal

A

Copying a tree

58
Q

Give two uses of in-order traversal:

A
• Outputting the contents of a binary search tree in ascending order
• Producing infix expression from an expression tree
59
Q

Give two uses of post-order traversal:

A
• Infix to RPN conversions
• Producing a postfix (RPN) expression from an expression tree
60
Q

Describe pre-order traversal operation

A
1. Visit the node
2. Traverse the left hand sub tree
3. Traverse the right hand sub tree
61
Q

Describe in-order traversal operation

A
1. Traverse the left hand sub tree
2. Visit the node
3. Traverse the right hand sub tree
62
Q

Describe post-order traversal operation

A
1. Traverse the left hand sub tree
2. Traverse the right hand sub tree
3. Visit the node