Chapter 10 - Data Types & Structures

Question 1

record

Answer 1

• a composite data structure used to store of data of different types under one identifier
• contains a fixed number of fields, each with its own name and type
• creates a more structured and readable approach to storing and managing data

Question 2

array

Answer 2

• ordered, static set of elements
• can only store 1 data type

Question 3

array index

Answer 3

identifies the position of each element in the array

Question 4

array lower bound

Answer 4

array first element

Question 5

array upper bound

Answer 5

array last element

Question 6

what is a linear search

Answer 6

• type of searching method that starts with the first value in a dataset and checks every value one at a time until all values have been checked
• can be performed even if the values are not in order

Question 7

describe the steps of a linear search

Answer 7

1. check the 1st value
2. IF it is the value required, stop
3. ELSE, move to the next value and check
4. REPEAT UNTIL you have checked all values and have not found the value you are looking for

Question 8

how does a linear search go through an array?

Answer 8

in order, from the lower bound (first) to the upper bound (last)

Question 9

what is a bubble sort?

Answer 9

• it is a simple sorting algorithm that starts at the beginning of a dataset and checks pairs of values and swaps them if they are not in the correct order
• one complete comparison of the dataset from beginning to end is called a ‘pass’, sometimes multiple passes are needed to fully sort the dataset
• the bubble sort stops when there are no more swaps to make

Question 10

describe the steps of a bubble sort

Answer 10

1. compare the first 2 values in the dataset
2. IF they are in the wrong order, swap them
3. check the next 2 values in the dataset
4. repeat steps 2 and 3 until the end of the dataset
5. IF any swaps were made during a pass, REPEAT from the start
6. ELSE no swaps were made, algorithm stops - the dataset is ordered

Question 11

what is file handling?

Answer 11

the use of programming techniques to work with data stored in files

Question 12

file handling techniques

Answer 12

• opening
• reading
• writing
• closing

Question 13

pseudocode for opening a text file for reading

Answer 13

OPENFILE file.txt FOR READ

Question 14

pseudocode for opening a text file for writing/creating a new file

Answer 14

OPENFILE file.txt FOR WRITE

Question 15

pseudocode for closing a text file

Answer 15

CLOSEFILE file.txt

Question 16

pseudocode for reading a line in a text file

Answer 16

READFILE file.txt, line

Question 17

pseudocode for writing a line in a text file

Answer 17

WRITE file.txt, “string”

Question 18

pseudocode for checking the end of a file

Answer 18

IF NOT EOF(file.txt) THEN

Question 19

pseudocode for appending to a file

Answer 19

OPENFILE file.txt FOR APPEND

Question 20

what is an abstract data type?

Answer 20

a collection of data and a set of operations on that data

Question 21

what are 3 common ADTs

Answer 21

• stacks
• queues
• linked lists

Question 22

what is a stack?

Answer 22

• ADT that stores data using the Last In, First Out principle
• first item pushed onto the stack (added) will be the last one to be popped of (removed)
• uses a base pointer which points to the first item in the stack and a top pointer which points to the last item in the stack

Question 23

what is the operation for checking if a stack is empty by checking the value of the top pointer?

Answer 23

isEmpty()

Question 24

push(value)

Answer 24

• adds a new value to the end of a list
• needs to check that the stack isn’t full before pushing

Question 25

peek() [for stacks]

Answer 25

- returns the top value of the stack without removing the value - it first checks that the stack is not empty by looking at the value of the top pointer

Question 26

pop()

Answer 26

- removes and returns the top value of the stack - it first checks that the stack is not empty by looking at the value of the top pointer

Question 27

size()

Answer 27

returns the size of the stack

Question 28

isFull()

Answer 28

- compares the stack size to the top pointer to check if the stack is full - returns a boolean value

Question 29

how is data pushed to a stack

Answer 29

1. the stack needs to be checked first if it is full; if an item is pushed onto a full stack a stack overflow error occurs 2. data is pushed to the position of the pointer 3. once pushed, the pointer will increment by 1, signifying the top of the stack

Question 30

how is data popped from a stack

Answer 30

1. the stack needs to be checked first if it is empty; if an item is popped from an empty stack a stack underflow error occurs 2. data is popped from the position of the pointer 3. once popped, the pointer will decrement by 1, signifying the new top of the stack

Question 31

what is a queue?

Answer 31

- an ADT that stores data in the order they arrive, using the First In First Out principle - first item added is the first one removed

Question 32

how do you remove an item from a queue?

Answer 32

deQueue(value) removes item from the front and returns it

Question 33

how do you add an item to a queue?

Answer 33

enQueue(value) adds an item to the back of the queue

Question 34

peek [for queues]

Answer 34

returns the value of the item at the front of the queue without removing it

Question 35

isEmpty()

Answer 35

checks whether the queue is empty

Question 36

isFull() [queues]

Answer 36

checks whether the queue is full (if it has a size constraint)

Question 37

what are linear queues?

Answer 37

data structure that consists of an array

Question 38

how are items added to a linear queue?

Answer 38

1. check that queue is not full 2. if the queue is not full, the item is added to the next available space in the queue starting from the front and the rear index pointer is incremented by 1 3. if the queue was originally empty, both the front and rear pointer must be changed from null to the first index of the queue

Question 39

how are items removed from a linear queue?

Answer 39

1. make sure that queue is not empty 2. if queue is not empty the item at the front of the queue is returned and the front index pointer is incremented by 1

Question 40

what are circular queues?

Answer 40

- static array with a fixed capacity - reuses empty slots at the front of the array left when items are dequeued - as items are enqueued and the rear index pointer reaches the end of the array, it wraps around the array to point to the start of the array as long as the array isn't full - when items are dequeued the front index pointer would wrap around until it passes the rear index pointer, indicating that the queue is empty

Question 41

how are items added to a circular queue?

Answer 41

1. first must check that the queue is not full 2. it is full if the next position to be used is already occupied by the item at the front of the queue 3. if the queue is not full, the rear index pointer moves to reference the next free position so the item can be added

Question 42

how are items removed from a circular queue?

Answer 42

1. first make sure that the queue is not empty 2. if the queue isn't empty the item at the front is returned 3. if this was the only item in the queue the rear and front pointers are reset; if not the front pointer moves to reference the next item

Question 43

what is a linked list?

Answer 43

- an ADT that stores a chain of items called nodes, where each node contains a data field and a pointer (an address) to the next node in the list - new nodes are usually added to the start of the chain, and each node links to the next

Question 44

how to traverse a linked list?

Answer 44

1. check if the linked list is empty 2. start at the node the pointer is pointing to 3. output the item at the current node 4. follow the pointer to the next node repeating through each node until the end of the linked list is reached which is indicated when the pointer field is null/empty

Question 45

what is the advantage of using a linked list?

Answer 45

it is easy to add and remove nodes

Question 46

what are the disadvantages of using a linked list?

Answer 46

- memory is wasted when nodes are "removed" as they are only ignored and not actually deleted - more memory is needed than an array as storing pointers take up space - nodes in a linked list are stored in a sequence and must be traversed in order and cannot be directly accessed as possible in an array

Question 47

how do you add nodes in a linked list?

Answer 47

1. check that there is free memory to insert the new value 2. add the new value to the end of the list and update the NextFree pointer 3. update the pointer field

Question 48

how do you remove nodes from a linked list?

Answer 48

update the pointer field to ignore the node to be removed - this doesn't remove the node, but ignores it, so it is not traversed

Question 49

pseudocode for declaring a 2d array

Answer 49

DECLARE _arrayname_: ARRAY[x, y] OF _datatype_