1.1 data structures

Question 1

pre order

Answer 1

dots to the left

Question 2

in order

Answer 2

dots on the bottom

Question 3

post order

Answer 3

dots on the right

Question 4

linked list characteristics

Answer 4

• dynamic data structure it can grow and stinks in size after declaration
• each element is called a node - first element is head node
• each node consists of the data and the reference to the next node
• consists of starter pointer which points at the first item in the list and so on
• items can be added into a linked list without having to shift the other items to fill the gap left (adv over 1D array)

Question 5

how to create binary trees

Answer 5

from first element - bigger (right) smaller (left)

Question 6

remove from a binary tree with 2 children

Answer 6

go the right pointer and find the lowest value child from that element then replace the value being deleted with that child

Question 7

what is a data structure

Answer 7

a set of related data items

Question 8

why are the data structures are useful

Answer 8

• efficient way of organising data relating to a real problem
• may be efficient to deal with various elements as one item

Question 9

an example of data that could be stored in a 2D array

Answer 9

sales of each product number by month

Question 10

what are the key features of an array

Answer 10

• a data structure which is a set of data elements of the same type
• can be directly accessed via indexes, subscripts, row/column names
• has a fixed number of elements (static)

Question 11

give an example of data that could be stored in 3D arrays

Question 12

what is a record data and structure and when would they be used

Answer 12

• a record is a set of data items all related to a single individual/ entity
• a record can contain data of different types
• a record would be used if there is data of more than one type

Question 13

drawbacks of using 3D arrays

Answer 13

• more complex to program/process

Question 14

what data is suitable for a 1D array

Answer 14

when the data set comprises of single values of the same data type

Question 15

what is a stack

Answer 15

• a container of objects that are inserted and removed according to LIFO
• It has a limited access data structure - elements can be added and removed from the stack only at the top
• push adds an item to the top of the stack
• pop removes the item from the top
• a stack can be used as a recursive data structure
• a stack is either empty or is consists of a top and the rest which is a stack
• underflow occurs when an attempt is made to pop an empty stack or when an attempt is made to push a full stack

Question 16

Examples of when a stack could be used

Answer 16

• undo and back button
• a subprogram to return addresses (winding back nesting of subprograms)
• recursion values
• reversing a queue / list (LIFO)

Question 17

what is a queue

Answer 17

operates on the FIFO principle and data items are added at the end of the queue and removed from the front

Question 18

what happens when there is an attempt is made to add an item to a full queue

Answer 18

returns an appropriate message or condition
(produces an error message)

Question 19

examples of where a queue could be used in computing and why

Answer 19

• a printer queue
• keyboard buffer
• a download buffer
• a processor scheduling queue
• because the natural/desirable processing order is FIFO so the job waiting the longest should be printed next

Question 20

what is a linked list (simple)

Answer 20

a set of data elements, where each element contains the data itself and a pointer to the next element

Question 21

advantages and drawbacks of a linked list compared to an array

Answer 21

advantages:
- new items can be inserted into a linked list without rearranging all the other elements
- if programmed dynamically uses memory more efficiently

disadvantages:
- a linked list is more complex to program/ manipulate than an array
- extra programming is required to access the data in the opposite direction
- can only be accessed in a linear manner

Question 22

what is an unbalanced binary tree

Answer 22

not the same amount on each branch

Question 23

example of in order traversal

Answer 23

-searching for a file in the file system
-listing files in alphabetical order

Question 24

example of post order traversal

Answer 24

delete all the files in the file system (each folder could only be deleted once all the files beneath have been deleted)

Question 24

example of pre order traversal

Answer 24

create copy files in the file system (each file above has to be copied before the files below)

Question 25

what is the first node called in a binary tree

Answer 25

root

Question 26

advantages and disadvantages of using a binary tree

Answer 26

advantages:
- faster to add a value
- faster to search for a value

disadvantages:
-more complex to program/process
-may be slow processing/ traversal if unbalanced

Question 27

what is a hash table

Answer 27

• a structure that can map keys to values

Question 28

how are hash tables used

Answer 28

a hash function is used to compute an index ( a hash code) into an array of buckets or slots from which the desired value can be found

Question 29

examples of where hash tables are used

Answer 29

• to deal with collisions
• many kinds of computer software, particularly for associative arrays, database indexing, caches and sets