Topic 1.1 - Data Structures

Question 1

What is a data structure?

Answer 1

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

Question 2

What is an array?

Answer 2

It is a data store where:

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

Question 3

What is a record?

Answer 3

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

Question 4

What is a stack?

Answer 4

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

Question 5

Give an example of where a stack is used

Answer 5

• Stacks are used to store subprogram return addresses

- Good when using reverse polish notation

Question 6

What is a queue?

Answer 6

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

Question 7

What is a binary tree?

Answer 7

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

Question 8

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

Answer 8

• 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

Question 9

What is a linked list?

Answer 9

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

Question 10

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

Answer 10

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

Question 11

Give an example of where a queue would be used

Answer 11

• Download buffer

- Keyboard buffer

Question 12

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

Answer 12

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

Question 13

What is hashing?

Answer 13

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

Question 14

Give an advantage and disadvantage of hashing

Answer 14

• 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

Question 15

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

Answer 15

The root node

Question 16

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

Answer 16

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

Question 17

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

Answer 17

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

Question 18

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

Answer 18

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

Question 19

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

Answer 19

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

Question 20

What are the benefits and drawbacks of a binary tree?

Answer 20

• Fast access to data
• Data can be retrieved in different useful orders
• More complex to program
• Poorly balanced trees would mean as increase in access times