Data Types and Structures

Question 1

Describe a 1D array

Answer 1

Data structure which contains as set of variables of the same data type
Position is stored using an integer index

Question 2

What is a 2D array?

Answer 2

An array of arrays

Question 3

What is the difference between an array and a linked list?

Answer 3

Array - items organised sequentially

Linked List - items organised sequentially, but each item contains a link to next item

Question 4

Give two advantages of linked lists

Answer 4

Dynamic Data structure, can grow and shrink
Very flexible, order of items can be changed without moving data
More memory efficent

Question 5

Give a disadvantage of a linked list

Answer 5

Not possible to identify a specific item directly using its index

Question 6

Give an example of a dynamic data structure which linked lists are used to implement

Answer 6

Queues

Stacks

Question 7

Why is it inefficient to to resize an array in the middle of execution?

Answer 7

Array has to be copied into new memory to accommodate the extra added items
Double array in memory

Question 8

What is a stack?

Answer 8

A stack is a data structure which behaves like a vertical list
Elements can be added or deleted from the top of the stack
‘Last in, First out’

Question 9

In what situation would a stack be useful?

Answer 9

Situation which calls for the most recent items to be accessed
Store code produced during compilation of high level languages
Intermediate results of calculations

Question 10

If you have a stack overflow error on a computer what does this mean?

Answer 10

Program has attempted to place too many items on the stack

Question 11

Describe a queue

Answer 11

1D array or list, items are inserted and retrieved at different ends
‘First in, First Out’

Question 12

Identify three variables required for implementation of a stack

Answer 12

Stack Pointer
Maximum stack size
An array

Question 13

How can a 2D array be accessed?

Answer 13

Nested loops

Two fixed loops

Question 14

Describe a linked last

Answer 14

Dynamic data structure where data items have a link to the next item in the list

Question 15

Describe a record

Answer 15

Data structure consisting of several variables of different types

Question 16

Describe situations where queues are useful to implement

Answer 16

• multiple printing jobs have to be processed
• scheduling of tasks in a multitasking environment.
• event-driven languages where events are placed in a queuing system to wait being processed

Question 17

What is a circular queue?

Answer 17

A queue which uses a system where only the start and end pointers move, allowing the array to behave as if its spaces were arranged in a circle.

Question 18

Where will a link to the last data item point to?

Answer 18

NULL

Question 19

How many pointers does a queue usually need?

Answer 19

2

Question 20

What is a dynamic data structure?

Answer 20

Data structure that can grow or shrink during execution

Question 21

What are two advantages of a 1D array over a 2D array?

Answer 21

• Allows different data types

- More memory efficient if stored in suitable data type

Question 22

A call stack is a stack data structure used to keep track of the active subprograms.
Explain the role of a stack data structure in the execution of this search procedure

Answer 22

Whenever the search procedure is
called, it is added to the call stack
When the base case is reached, the
last procedure call added to the
stack is removed and value is
passed to the previous procedure
call. This repeats until the first
procedure call is reached and a
value is returned