# Topic 1.1 - Data Structures Flashcards

1
Q

What is a data structure?

A

A data structure is a store of a group of related items

2
Q

What is an array?

A

It is a data store where:

• All the data is of the same type
• Elements accessed via an index
• Has a predetermined size
3
Q

What is a record?

A

A record is a set of data items which are all related to one entity

4
Q

What is a stack?

A

It is a data store in the form of a linear list where the list items added are the first items to be removed
- Uses a stack pointer is a small register that stores the address of the last program request in a stack

5
Q

Give an example of where a stack is used

A
• Stacks are used to store subprogram return addresses

- Good when using reverse polish notation

6
Q

What is a queue?

A

A queue is a data structure where data can only be added to the end of it and is then retrieved from the front of the queue
- A queue has two queue pointers, one for the front and one for the rear

7
Q

What is a binary tree?

A

Trees are a large store of data and are quick to search through but needs to be balanced to be efficient

• Each node has a left and a right pointer which points to items either greater or less than it
• The first node is known as the root node
8
Q

What is pre-order, in-order and post-order

A
• Pre-order is when you first meet a node
• In-order is when you travel under a node (this is the correct order of the data)
• Post-order is when you’ve visited both of that nodes children
9
Q

What is a linked list?

A

Has a logical order which is different to its physical order (data items can be anywhere in memory)
- Each item in the list is composed of two parts, data and a pointer to the next item to the list

10
Q

What’s a benefit and dis-advantage of using a linked list?

A
• New items can be added anywhere in the list
• Saves on memory if programmed dynamically
• Complex to program
• Only accessed in a linear fashion
11
Q

Give an example of where a queue would be used

A

- Keyboard buffer

12
Q

Why’s it bad for a binary tree to be unbalanced?

A

An unbalanced binary tree can significantly increases the number of comparisons to be made when searching through the tree.

13
Q

What is hashing?

A

Hashing uses is the mod function to store different items of data in a table according to its remainder. If a data collision occurs, it goes into the overflow area.

• Random access file where physical location is calculated using the hashing algorithm.
• Known as Direct Acess
14
Q

Give an advantage and disadvantage of hashing

A
• Equally fast access to any record in the file
• Addresses may not be unique leading to collisions which reduces the efficiency of the solution.
• SOLUTION, create a new, larger hashing table
15
Q

What is the top/first item in a binary tree known as?

A

The root node

16
Q

Describe the pseudo code for adding an item to a circular queue:

A
```If NumOfItems = MaxIndex Then
Output error message
Else
If rearPointer = MaxIndex Then
rearPointer = 1
Else
Increment rearPointer by 1
End if
Increment NumOfItems by 1
Queue(rearPointer) = new item
End if```
17
Q

Describe the pseudo code for retrieving an item from a circular queue:

A
```If NumOfItems = 0 Then
Output error message
Else
Use for Data = Queue(frontPointer)
NumOfItems -= 1
If frontPointer = MaxIndex Then
frontPointer = 1
Else
Increment frontPointer by 1
End if
End if```
18
Q

Describe the pseudo code for pushing an item onto a stack:

A
```If Top = MaxIndex Then
Output error message
Else
Increment Top by 1
Stack(Top) = New data
End if```
19
Q

Describe the pseudo code for popping an item off a stack:

A
```If Top = 0 Then
Output error message
Else
UseForData = Stack(Top)
Top -= 1
End if```
20
Q

What are the benefits and drawbacks of a binary tree?

A