1. The application of graphs in computer science are huge! Describe what is meant by a graph structure and list its characteristics/features (3 marks)
2. Explain why the following structure is not a binary tree and then state what structure it is. (2 marks)
3. Samuel is considering using a depth-first (post-order) traversal, or a breadth-first traversal to find the path between node B and node Y. Explain the difference between a depth-first (post-order) and breadth-first traversal (4 marks)
4. Show how a depth-first (post-order) traversal would find the path between node B and node Y (1 mark)
Write your answer in the following format and don't forget the square brackets around the letters. Do not include spaces between the letters -just a single comma:
[A,B,C,D,E]
(In this case you would start with E a
and end with Y)
Correct format and correct order would recieve 1 mark
Note: This question would usually be worth 4-6 marks
in an exam due to the neccesity for calculation.
5. Explain how you used backtracking in your answer for the previous question? (3 marks)
6. State the FULL name of the data structure shown below (2 marks)
7. Assume the structure above shows flight paths for the United Kingdom's various airports. State what the values in yellow are likely to be (1 mark)
8. In reference to the data structure in question 6, state what the values (in yellow) could potentially represent. (1 mark)
9. Explain, in simple terms, what the purpose of these values (in yellow) could be in the A* algorithm (1 mark)
10. Show the process of how you would perform an A* algorithm on the data structure in question 6. Read the excerpt and fill in the blanks for ?1 and ?2 (2 marks)
The objective is to find the shortest distance between
Hanoi and Enema.
Here we show each step of the process, and the calculations
performed for each node visited. (This is how you might
present the information requested for an A* algorithm in
an exam)
Fill in the blanks for ?1 = (name of city or BLANK for -)
Fill in the blanks for ?2 = (give just one number)
Node Distance Travelled Heuristic D+H Previous Node
===========================================================
Hanoi 0 800 800 -
Genia 250 700 950 Hanoi
Noland 2100 900 3000 ?1
Lopes ?2 500 1260 Genia
Mara
Enema
11. Following on from the previous question, fill in the blanks for ?3 and ?4 (2 marks)
Following on from the last question:
The calculation can be shown but is not required:
Fill in the blanks for ?3 = (give the total number)
Fill in the blanks for ?4 = (give the total number)
Node Distance Travelled Heuristic D+H Previous Node
===========================================================
Hanoi 0 800 800 -
Genia 250 700 950 Hanoi
Noland 2100 900 3000 ?1
Lopes ?2 500 1260 Genia
Mara ?3 200 2210 Genia
Enema 3830 0 3830 ?4
12. Circular queue avoids the ________________ in a regular queue implementation using arrays. (1 mark)
13. Hans is creating a quiz on the 'fundamentals of the Bible' for his church. He is considering various data structures. Explain why a queue data structure may be suitable for creating a quiz (4 marks)
To achieve the full marks, mention two features of a
queue (its main characteristics) but also talk about
why it would be suitable in terms of storing and
displaying quiz questions.
14. Analyse the pseudocode in the image below. What is the code doing?(2 marks)
15. Hans consults software guru Elliot to suggest an algorithm to insert one data item into a queue data structure. Can you describe this algorithm? (4 marks)
