# 14- Past Paper Simulation - DS 2 (A)

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)