Preview

07-Alevel-Prog&Algo(C2)Part#1

1. A games company is developing a flight simulation program. State three pieces of information that would need to be researched in order to design this simulator. (3 marks)

2. Explain what is meant by "concurrent processing" and describe one example of how the simulator could make use of it. (2 marks)

3. The following tube map of London is an abstraction made up of component parts. Using this example, explain the term abstraction (2 marks)

4. A simulation games company is re-creating the London tube for a game. Program development requires the use of re-usable components. State three examples of how reusable components are used in the above example (3 marks)

5. Another term for the use of re-usable components is modular programming. Why is this necessary for large programs? (3 marks)

6. State two advantages to using re-usable parts while developing programs (2 marks)

7. Explain why good programming practice generally avoids the use of global variables.(2 marks)

8. The following algorithm shows the outworking of a binary search. Fill in the blanks on line 5.

function S(A[0..N-1], value, low, high) 
          if (high < low)then                
		return error_message   
	  endif 
          ____________________________??????
	  if (A[mid] > value)then             
		return S(A, value, low, mid-1)               
	  elseif (A[mid] < value)then              
                return S(A, value, mid+1, high)           
          else             
                return mid      
          endif 
endfunction

mid = (low + high) / 2

low = (mid + high) / 2

high = (low + mid) / 2

mid = (high / 2)

9. Part of the data held by the programmers for the search is shown below. State two reasons that suggest it would be best NOT to use a binary search on this data. (2 marks)

(42, 83, 27, 18, 52)

10. Fill in the blanks on line 1 for the linear search that could be carried out on the data set above (to find the value 27 in the list)

____________________________________????
Compare 83 (second value) and discard
Compare 27 (third value)
Display result / search stops

Compare 83 (second value) with the first value and discard

Compare 42 (first item) to be searched with 83 (second value)

Compare 27 to 83 (second value) and discard if smaller

Compare 42 (first item) to be searched with 27

11. The following diagram shows the steps needed for a _______ on these values: (42, 83, 27, 18, 52).

bubble

quick

insertion

merge

12. When comparing linear and binary search it is possible to look at the best, worst and average number of items in the array that need to be checked to find the item being searched for. The assumption here is that:

only the first half of the list in the array is likely to be searched.

not every item in the array is equally likely to be searched for.

every item in the array is equally likely to be searched for.

every item in the array is equal to or less than 526 (or the equivalent size of RAM).

13. As the size of an array increases the average number of checks grows logarithmically. State what is meant by logarithmic growth.

As x (or the size of the array) increases, the rate at which y (or the number of checks needed) increases more slowly.

The rate of increase is a logarithmic function of the size of the array.

All the listed answers are valid answers.

It can be thought of as the inverse of exponential growth.

14. A binary search tree is one example of a type of tree. State the main features of a tree. (3 marks)

15. The following function is recursive. State the line in which recursion is occuring.

01 function generateObstacle(diceNumber) 
02 if diceNumber == 0 then 
03 return true 
04 else 
05 x = randomNumber(0, 7) 
06 y = randomNumber(0, 7) 
07 board(x, y) = new obstacle() 
08 generateObstacle(diceNumber-1) 
09 endif 
10 endfunction

16. State two things that are occuring on line 01 of the algorithm above (2 marks)

17. State three advantages of recursion (3 marks)

18. State four drawbacks of recursion (4 marks)

19. The following code re-writes the code above (recursive function) in an iterative manner. Which of the following would correctly fit in with this algorithm on line 02?

function generateobstacle(diceNumber)
    ________________________________????
	x = randomNumber(0,7)
	y = randonNumber(0,7)
	board(x,y) = new obstacle()
    next count
    return true
End Function

Context of the game given below
=================================
This game involves a board.
The board is to be stored as a 2-dimensional array.

Game play: The game is played by rolling two 6-sided dice 
and moving that number of spaces. 

Both players start on the START space. 

If a player lands on a space occupied by the other player, 
they move to the next available space.

Each time a player moves, a series of obstacles are to be added
to the board.

On their turn, each player rolls two dice. The smaller number from
the two dice is taken, and that many obstacles will appear on the
board in random locations.

For example, if a 3 and 6 are rolled, then 3 obstacles will appear.

for count = 1 to 6

while count > 0 and diceNumber <7

for count = 0 to diceNumber

while diceNumber <7 and count > 0

20. Lisa wants to create an app and does some market research first. State four items of data that she could obtain in order to make a sensible choice of an app development project. (4 marks)

21. A cafe manager is reorganising the layout of the cafeteria in order to speed up the service to customers. Explain how computational methods could be used in order to improve the layout of this cafeteria. (3 marks)

22. Describe what is meant by a heuristic approach to problem-solving? (2 marks)

23. In which of the following are heuristic methods likely to be used?

A human crossing a busy road

Insertion of a RAM chip into a desktop PC

Insertion of a leaf node into a binary tree data structure

The powering on of a robot

24. Connect 4 is a popular game in which players must place four 'coins' in a row to win. Explain how a programmer could make use of a tree structure, using a heuristic approach in the development of the computer player for Connect 4? (4 marks)

25. Virus checkers work by looking for _________________________. They also use ___________ approaches.

viruses in the RAM / advantageous

patterns in the program code / heuristic

computational failure / computational method

instances of machine failure or illegal file deltion / file fragmentation

26. The following answer explains how _________________ principles can be used to ensure that a house is built as quickly as possible.

Look for processes that can be processed at the same time (1) 
processes that must be sequential (1). Example of possible parallel 
processes, e.g. windows installed at same time as electrics / plumbing 
(1). Example of an obligatory sequence e.g. rafters installed before 
tiles put on / walls before roof (1).

multi-tasking

modular programming

pathfinding

pipelining

27. How is the above used in any computer system? (3 marks)

28. Read the context below and fill in the blanks for the following algorithm.

Context
=======
It is possible to use XOR together with a key to encrypt a plain text message.

For example, to encrypt the bit pattern 111100001111 using the number 5 as a key, 
the key is repeated as often as necessary to match the length of the message. 
An XOR operation is performed to generate the encoded message.

111100001111 <- Message to be encrypted

101101101101 <- Key: repeated as necessary

010001100010 <- Encrypted message

Fill in the blanks for the following algorithm to accept a text message
and a key that would  use the method above to generate an encoded message.

asc_msg=encryptmsg+complete_key(1,i) XOR

encryptmsg=encryptmsg - complete_key(i) XOR

encryptmsg=asc_msg+complete_key(0,i) XOR

encryptmsg=encryptmsg+complete_key(1,i) XOR

29. In reference to the table below, assume every item in the array is equally likely to be searched for. Fill in the blanks for A.

30. Refer to the table above. Fill in the blanks for B.

31. Refer to the table above. Fill in the blanks for C.

32. Refer to the table above. Fill in the blanks for D.

33. State the purpose of Big O notation.(2 marks)

34. Explain the difference between a depth-first (post-order) and breadth-first traversal. (3 marks)

35. Read the context below and describe why a queue is a suitable structure for this program. (3 marks)

A program stores a queue of mathematical questions to be asked to a user. 
The questions are asked in the order they are added. 

Once a question has been asked it cannot be asked again. 
New questions are continually added to the end of the queue.

The program will use a non-circular queue, questions, (implemented using an array)
to store the questions.

The pointer, head, stores the index of the first element in the queue.
The pointer, tail, stores the index of the last element in the queue.

Report an error