F453 - data structures and manipulation

Question 1

Showing the steps of serial search
e.g. Find York
Aberdeen, Belfast, Cardiff, Oxford, York

Answer 1

1. start at ‘Aberdeen’…
2. look at each word in turn/then ‘Belfast’, ‘Cardiff’ etc…
3. …until ‘York’ is found

Question 2

Showing the steps of binary search e.g. Find York

Aberdeen,Belfast, Cardiff, Oxford, York

Answer 2

look at middle/‘Cardiff’/‘Glasgow’
‘York’ is in second half of list
repeated halving…
…until ‘York’ is found

Question 3

What are the advantages of binary search over seial search?

Answer 3

(usually) faster because…

…alf of data is discarded at each step/fewer item

Question 4

How do you add a data item into a stack?

Answer 4

if stack is full…
…report error and stop
increment pointer
add data item at position ‘pointer

Question 5

How can quicksort be used to put a set of numbers in ascending order?
e.g. 30 9 46 14 22

Answer 5

highlight first number in the list (the ‘search number’)
pointer at each end of list
repeat:
compare numbers being pointed to…
…f in wrong order, swap
move pointer of non-search number
until pointers coincide so search number in correct position
split list into 2 sublists
quick sort each sublist
repeat until all sublists have a single number
put sublists back together

Question 6

Name another method or sorting

Answer 6

insertion sort or bubble sort

Question 7

What is a static data structure?

Answer 7

size is fixed when structure is created/size cannot change

during processing

Question 8

What would be an advantage of static data structures over dynamic structures?

Answer 8

amount of storage is known/easier to program

Question 9

How would you merge two files?
e.g. File A: Anna, Cleo,Helen, Pretti
FiLe B: Billy, Ian, Omar, Rob, Tom

Answer 9

(Anna, Billy, Cleo, Helen, Ian, Omar, Pritti, Rob, Tom)

You must: get correct order, use all names used once

Question 10

State the algorithm for merging two sorted files

Answer 10

open existing files
create new file
check existing files are not empty
use pointers/counters to identify records for
comparison
repeat
compare records indicated by pointers
copy earlier value record to new file
move correct pointer
until end of one file
copy remaining records from other file
close files
assume common key
assume if 2 records are the same…
…only 1 is written to new file

Question 11

What is a dynamic data structure?

Answer 11

size changes as data is added & removed/size is not fixed

Question 12

What would be a disadvantage to the programer of using dynamic data structures
over static ones?

Answer 12

more complex program to write

Question 13

State a data structure which must be static

Answer 13

array/fixed length record

Question 14

What steps need to be taken to add a new item to a binary tree

Answer 14

start at root
repeat
compare new data with current data
if new data < current data, follow left pointer
else follow right pointer
until pointer is null
write new data
create (null) pointers for new data

Question 15

How can insertion sort be used to arrange numbers in order?

e.g. 17 2 3 26 5

Answer 15

list of sorted numbers is built up…

…with one number at a time being inserted into correct position

Question 16

a list of positive numbers up to and including 1000 is

2,4,6,…500,502,…998,1000

an attempt is made to find 607

show the first 3 steps for a binary search

Answer 16

go to middle value 500
compare 607 with 500
607 > 500 therefore discard everything before 500 (including 500)
repeat process in remaining set of numbers (go to middle value etc)

Question 17

a list of positive numbers up to and including 1000 is

2,4,6,…500,502,…998,1000

an attempt is made to find 607

show the first 3 steps for a serial search

Answer 17

start at 2
compare 607 with 2 (no match)
compare 607 with 4 (no match)
& repeat comparison until match is found

Question 18

explain different between binary and serial search

Answer 18

binary search discards half of data at each step

serial search discards one data at each step

Question 19

one advantage of binary search
one disadvantage of binary search
compared with serial

Answer 19

binary usually faster in a large set of data because there are less comparisons to do
However disadvantage is that values must first be sorted in order but with serial it doesn’t need to be in order