Section 16 Revision Questions

Diagram 1 shows a graph.

Diagram 1

State the output of a breadth-first traversal of Diagram 1 from E, visiting neighbours in alphabetical order. E, B, F, H, A, D, G, C

Diagram 2 shows an expression tree.

Diagram 2

State the output of a post-order traversal of this tree, and explain what it represents. 3 7 + 6 4 - / The expression in Reverse Polish Notation

Convert the infix expression


                            (7 * 2 + 1)
                            * (100 / 4 + 3)

into Reverse Polish Notation.


                        7 2 * 1 +
                        100 4 / 3 +  *

State two advantages of Reverse Polish Notation over infix. No need for parentheses to show the correct order of operations. It is simpler for a computer to evaluate RPN. There is no need to backtrack when evaluating RPN.

A Binary Search is performed on the list


                            ["Apples", "Bananas",
                            "Cherries", "Grapes",
                            "Kiwis", "Lemons",
                            "Mangoes", "Oranges",
                            "Pears", "Pineapples",
                            "Plums", "Strawberries"]

,
looking for the item "Blueberries" (which is not in the list).
How many comparisons are required? 4 comparisons ("Lemons", "Cherries", "Apples", "Bananas")

State the problem that Dijkstra's Algorithm is designed to solve. Finding the shortest path between two nodes in a graph

Score: 0/0

Question 1 of ∞