7. data structures

Question 1

data strucutre

Answer 1

is a format used to store, organise and manage data in a way that allows for efficient access and modification for the needs of the program

Question 2

abstract data type

Answer 2

is a logical description of how the data is viewed and the operations that can be performed on it, but how this is done is not necessarily known by the user

Question 3

ADT

Answer 3

queues
stacks
trees
graphs

Question 4

advantages of ADT

Answer 4

+ can be easily shown in graphical form
+ its not had to understand how to perform operations such as adding, deleting or counting elements in each structure

Question 5

data abstraction

Answer 5

process of simplifying complex data structures by providing a simple interface and hiding the underlying details.

Question 6

example of data abstraction

Answer 6

its up to the programmer who creates the data structure to decide how to implement it, and it may be built in to the programming language

by providing this level of abstraction we are creating an encapsulation around data.

Question 7

encapsulation

Question 8

information hiding

Question 9

queue

Answer 9

FIFO data structure. new elements may only be added to the end of a queue, and elements may only be retrieved from the front of a queue.

the sequence of data items in a queue is determined by the order in which they are inserted.

the size of the queue depends on the number of items in it.

Question 10

queue application (1)

Answer 10

output waiting to be printed is commonly stored in a queue on disk. in a room full of networked computers, several people may send work to be printed at more or less the same time. by putting the output into a queue on disk, the output is printed on a first come, first served basis as soon as the printer is free.

Question 11

queue application (2)

Answer 11

characters typed at a keyboard are held in a queue in a keyboard buffer

Question 12

queue application (3)

Answer 12

stimulation program - attempts to model a real-life situation so as to learn something about it

Question 13

stimulation program example

Answer 13

a program that stimulates customers arriving at random times at check-outs in a supermarket store, and taking random times to pass through the checkout.

with the aid of a stimulation program, the optimum number of check-out counters can be established.

Question 14

enQueue(item)

Answer 14

add a new item to the rear of the queue

Question 15

deQueue()

Answer 15

remove the front item from the queue and return it

Question 16

isEmpty()

Answer 16

tests to see whether the queue is empty

Question 17

isFull()

Answer 17

test to see whether queue is full

Question 18

static data structure

Answer 18

organisation or collection of data in memory that is fixed in size.

e.g. array

• maximum size needs to be known in advance
• memory can’t be reallocated once program is running

Question 19

dynamic data structure

Answer 19

organisation or collection of data in memory that has ability to grow or shrink in size. it does this with the aid of the heap.

e.g. linked lists or queues

• allows the programmer to control exactly how much memory will be used
• unused memory is allocated or de-allocated as needed
• maximum size of data structure is not known in advance
• can be given arbitrary maximum to avoid causing memory overflow

Question 20

dynamic data structure advantage

Answer 20

+ makes efficient use of memory because the data structure only uses as much memory as it needs

Question 21

dynamic data structure disadvantage

Answer 21

• dds run the risk of ‘overflow’ error, this happens when it exceeds its allowed limit. can also cause an ‘underflow’ error if it becomes empty
• harder to program because the code needs to keep track of the data structures size and location of items inside it at all times

Question 22

static data structure advantage

Answer 22

+ memory allocation is fixed which means there will be no issues with adding and removing items from the data structure
+ easier to program as there isn’t a requirement to check on the size of the data structure at any point before accessing it

Question 23

static data structure

Answer 23

• can be very inefficient as memory for the data structure is set aside at the start of the program but might not be utilised

Question 24

implementing a linear queue

Answer 24

• as items leave the queue, all of the other items move up one space so that the front of the queue is always the first element of the structure
• can be implemented with pointers to the front and rear of the queue. an integer holding the size of the array (the maximum size of the queue

however, clearly a problem will arise as many items are added to and deleted from the queue, as space is created at the front of the queue which cannot be filled, and items are added until the rear pointer points to the last element of the data structure