3.1 Data Structures

Question 1

Data structure

Answer 1

An organised means of storing related data.

Question 2

7 examples of data structures

Answer 2

1. Arrays
2. Records
3. Stacks
4. Queues
5. Trees
6. Linked Lists
7. Hash tables.

Question 3

Array

Answer 3

A data structure that stores multiple data items of the same data type.

Question 4

Element of an array (2)

Answer 4

1. The index of each data value in the array.
2. Accessed by its index - 0,1,2,3 etc.

Question 5

3 advantages of an array.

Answer 5

1. Allows direct accessing of elements.
2. Can be used to implement other data structures e.g. stacks/queues.
3. No need to declare large number of variables individually.

Question 6

Disadvantage of an array.

Answer 6

Cannot be dynamically resized in most languages.

Question 7

Record

Answer 7

A data structure to store multiple pieces of data with may have different data types.

Question 8

Field

Answer 8

A single item of data within a record.

Question 9

Stack

Answer 9

A FILO or LIFO data structure where data items can be pushed or popped.

Question 10

FILO

Answer 10

First In Last Out

Question 11

LIFO

Answer 11

Last In First Out

Question 12

Pushed

Answer 12

When an item is added to the top of the stack.

Question 13

Popped

Answer 13

When an item is taken from the top of the stack.

Question 14

What is significant about the top of the stack?

Answer 14

It is the only position where a record can be added or removed.

Question 15

How can a stack be implemented? (2)

Answer 15

1. Can be implemented using an array and one integer variable.
2. A variable, called “Top” can be used as the stack pointer.

Question 16

Stack pointer

Answer 16

To contain the index of the most recent data item added.

Question 17

How do you push records using arrays and variables? (2)

Answer 17

1. Add new data in “Top” + 1
2. Add 1 to “Top” variable

Question 18

How do you pop records using arrays and variables? (3)

Answer 18

1. Subtract 1 from the “Top” variable
2. Data that has been popped can also been deleted, but does not need to be.
3. The next time data is pushed the old data will be overwritten.

Question 19

*Practical uses for stacks (3)

Answer 19

1. ‘Undo’ function in a word processing package.
2. ‘Back’ button on a browser to take user to the most recently visited page.
3. Sub-program return address

Question 20

*Practical uses for stacks (3)

Answer 20

1. Recursion values
2. Reverse polish calculations
3. As part of a compiler, check that bracket are closed )}]> in the reverse order to that in which they were opened <[{(