4.3.2.1 Pre-order, post-order and in-order traversal Quiz: AQA Computer Science, Unit 3

The 20 questions

1. Which traversal visits the root first, then the left subtree, then the right subtree?

   • Post-order
   • Level-order
   • In-order
   • Pre-order

2. Which traversal of a binary search tree outputs values in ascending order?

   • Pre-order
   • Breadth-first
   • Post-order
   • In-order

3. Which traversal produces a postfix expression from an expression tree?

   • In-order
   • Depth-first with no fixed order
   • Pre-order
   • Post-order

4. In post-order traversal, when is the root visited?

   • Before the left subtree but after the right
   • Last
   • After the left subtree and before the right subtree
   • First

5. Which traversal is used when copying a tree?

   • Inverse-order
   • Post-order
   • In-order
   • Pre-order

6. In-order traversal visits nodes in which sequence?

   • Left, root, right
   • Left, right, root
   • Right, root, left
   • Root, left, right

7. Post-order traversal visits nodes in which sequence?

   • Root, left, right
   • Right, left, root
   • Left, right, root
   • Left, root, right

8. An expression tree has root '+', left child '*' with children 'a' and 'b', and right child 'c'. What is the pre-order output?

   • +c*ab
   • +*abc
   • abc*+
   • a*b+c

9. Using the same expression tree (root '+', left '*' with children 'a' and 'b', right 'c'), what is the in-order output?

   • ab*c+
   • c+ab*
   • a*b+c
   • +*abc

10. Using the same expression tree, what is the post-order output?

    • a*b+c
    • +*abc
    • cab*+
    • ab*c+

11. A binary search tree is built by inserting 5, 3, 8, 1 and 4 in that order. What is its in-order output?

    • 8, 5, 4, 3, 1
    • 1, 3, 4, 5, 8
    • 1, 4, 3, 8, 5
    • 5, 3, 1, 4, 8

12. For the same binary search tree (root 5, left 3 with children 1 and 4, right 8), what is the pre-order output?

    • 1, 3, 4, 5, 8
    • 5, 3, 1, 4, 8
    • 5, 8, 3, 4, 1
    • 1, 4, 3, 8, 5

13. For the same binary search tree, what is the post-order output?

    • 1, 4, 3, 8, 5
    • 1, 3, 4, 8, 5
    • 8, 4, 1, 3, 5
    • 5, 3, 1, 4, 8

14. Why does in-order traversal of a binary search tree give sorted output?

    • Binary search trees are stored in an array
    • It sorts the values as it visits them
    • Every left-subtree value is smaller than its node and every right-subtree value is larger, so left-root-right gives ascending order
    • It visits the root before its subtrees

15. Infix to postfix conversion of an expression tree uses which traversal?

    • In-order
    • Pre-order
    • Post-order
    • Level-order only

16. Which traversal is used to empty a tree, as listed in the specification?

    • Breadth-first
    • Pre-order
    • Post-order
    • In-order

17. A tree has root 4, left child 2 (children 1 and 3), and right child 6 (children 5 and 7). What is the in-order output?

    • 4, 2, 1, 3, 6, 5, 7
    • 1, 3, 2, 5, 7, 6, 4
    • 1, 2, 3, 4, 5, 6, 7
    • 7, 6, 5, 4, 3, 2, 1

18. For the same tree (root 4, left 2 with children 1 and 3, right 6 with children 5 and 7), what is the pre-order output?

    • 4, 6, 2, 5, 7, 1, 3
    • 4, 2, 1, 3, 6, 5, 7
    • 1, 2, 3, 4, 5, 6, 7
    • 1, 3, 2, 5, 7, 6, 4

19. For the same tree, what is the post-order output?

    • 1, 2, 3, 4, 5, 6, 7
    • 4, 2, 1, 3, 6, 5, 7
    • 7, 5, 6, 3, 1, 2, 4
    • 1, 3, 2, 5, 7, 6, 4

20. Which statement about tree traversals is correct?

    • In-order alone uniquely determines a binary tree
    • The first item of a post-order traversal is always the root
    • Pre-order alone uniquely identifies a binary tree's shape
    • Pre-order together with in-order, for distinct values, uniquely determines the binary tree

Related quizzes

• Breadth-first and depth-first search Quiz · 4.3.1.1 · 20 questions
• Infix to Reverse Polish notation Quiz · 4.3.3.1 · 20 questions
• Linear and binary search Quiz · 4.3.4.1 · 20 questions
• Binary tree search Quiz · 4.3.4.3 · 20 questions
• Bubble sort Quiz · 4.3.5.1 · 20 questions
• Merge sort Quiz · 4.3.5.2 · 20 questions
• Dijkstra's shortest path algorithm Quiz · 4.3.6.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions
• Entity relationship modelling Quiz · 4.10.1.1 · 20 questions
• Big Data Quiz · 4.11.1.1 · 20 questions