Constructs/Algorithms

Question 1

Code an insertion sort

Answer 1

For i = 1 to length(list)

Value = list(i)     

Index = i 

Do while Index > 0             

    If Value < list(Index - 1) Then             

        list(Index) = list(Index - 1)             

        Index = Index - 1         

    Else            

        Exit do         

    End if  

Loop    

list(Index) = value 

Next i

For i = 0 to length(list)

lstdisplay.additem list(i) 

Next i

Question 2

Describe an insertion sort

Answer 2

This is when the first value is labelled the sorted side and the second the unsorted and the unsorted is either switched or remains once this is determined the value is now sorted and then next unsorted goes through the same process till the whole list is sorted. Much more efficient on longer lists than bubble

Question 3

Description of 2-D arrays

Answer 3

They are made from a grid/table of data, made from rows and columns, of the same data type and can be accessed uniquely using the array name and two indexes. They are traversed using nested if statements.

Question 4

How to initialise a 2-D array

Answer 4

For row = 0 to 5

For column = 0 to 5        

    data(row, column) = Inputbox(”Please input data”)     

Next column 

Next row

Question 5

How to display a 2-D array

Answer 5

For row = 0 to 5

For column = 0 to 5         

    PicDisplay.Print Tab(column * 10); data(row,column);     

Next column 

Next row

Question 6

Describe a single/double linked list

Answer 6

Linked list contain nodes that hold data, their own address and a pointer to the next node address. The first one is the head and the last node points to null. Double linked lists have the address of the previous node stored too making it easier to insert/delete nodes.

Question 7

Describe binary search

Answer 7

A binary search algorithm searches by halving the list till the target is found therefore the list must be sorted first. When working with parallel arrays they all must be kept together.

The code begins with a start and end point this helps calculate the middle of the list.

Question 8

Code a binary search

Answer 8

low = 0

high = length(list) - 1

found = false

Do

mid = (low + high)   

If target = list(mid) Then         

    fposition = mid         

    found = true     

End if    

If mid > target Then         

    low = mid + 1     

End if  

If mid < target Then         

    high = mid - 1     

End if 

Loop until found = true Or low>=high

Question 9

Describe a bubble sort

Answer 9

This is when the first two values are compared and switched if necessary and this is then repeated all the way down the list till the one value is sorted this is then continued with all the other values.

Question 10

Code a bubble sort

Answer 10

n = length(list)

swapped = true

While swapped = true and n>=0 Then

swapped = false 

For i = 0 to n-2                 

    If list(i) > list(i+1) Then             

        temp = list(i)             

        list(i) = list(i+1)             

        list(i+1) = temp             

        swapped = true         

    End if     

Next i 

n = n-1 

End while

Question 11

How to add/delete a node from a single/double linked list

Answer 11

To insert a node in a linked list first the new node must be made to contain the data and must be given a random unique address this will become the pointer for the previous node and the new nodes pointer will be the next nodes address.

This is the same for a double linked list however the new node will need to know the previous nodes address too.