Unit 4: Recursion and Trees - Practice Quiz

1 What is recursion in programming?

2 What is the purpose of a base case in a recursive function?

3 What is the maximum number of children that a node in a binary tree can have?

4 Which statement describes a complete binary tree?

5 In an extended binary tree, what replaces each missing child of an original node?

6 Which fields are commonly stored in a linked binary-tree node?

7 A binary tree stored in sequential memory is commonly represented using which structure?

8 In a zero-based array representation of a binary tree, what is the index of the left child of a node at index ?

9 Which property is normally true for every node in a binary search tree with distinct keys?

10 While searching a binary search tree, where should the search continue if the target is smaller than the current node's key?

11 Where is a new key normally placed during binary search tree insertion?

12 What is the simplest case of deleting a node from a binary search tree?

13 When deleting a binary search tree node with two children, which value can replace it?

14 What is the visiting order of recursive in-order traversal?

15 What is the visiting order of recursive pre-order traversal?

16 What is the visiting order of recursive post-order traversal?

17 What is the minimum number of moves required to solve Towers of Hanoi with disks?

18 In Towers of Hanoi, which disk may be placed on top of a larger disk?

19 What does merge sort do after recursively sorting two halves of a list?

20 Which element is selected to divide data into partitions in quick sort?

21 Consider the recursive function:

f(n) = n + f(n - 2) for , with f(0) = 0 and f(1) = 1.

What is the value of f(6)?

22 A recursive algorithm makes one call with input and performs constant work during each call. Which recurrence and time complexity describe it?

23 A binary tree has 18 nodes. If every node except the root has exactly one incoming edge, how many edges does the tree contain?

24 A complete binary tree contains 10 nodes stored in level order. At which zero-based array index will the next inserted node be placed?

25 An extended binary tree is formed by replacing every null child pointer with an external node. If the original binary tree has 12 internal nodes, how many external nodes are added?

26 A node in a linked binary tree has fields data, left, and right. If left is null and right points to another node, what does this indicate?

27 A binary tree is stored in a one-based array. If a node is stored at index 7, where are its left and right children stored, assuming both exist?

28 Which sequence could be the in-order traversal of a binary search tree containing the keys 10, 4, 15, 7, and 12?

29 A binary search tree is formed by inserting 50, 30, 70, 20, 40, 60, and 80 in that order. Which keys are compared when searching for 60?

30 The keys 40, 20, 60, 10, 30, and 50 are inserted into an empty binary search tree in that order. Where will key 55 be inserted?

31 In a binary search tree, a node with two children is deleted by replacing it with its in-order successor. Which node is selected as the successor?

32 A binary search tree is formed by inserting 40, 20, 60, 10, 30, and 50. If node 60 is deleted, which key directly replaces it using the standard one-child deletion rule?

33 A binary tree has root A. Its left child B has children D and E, while its right child C has only a left child F. What is its recursive in-order traversal?

34 A binary tree has root 8. Its left subtree is rooted at 4 with children 2 and 6, and its right subtree is rooted at 12 with left child 10. What is its recursive pre-order traversal?

35 A binary tree has root M. Its left child G has children D and J, and its right child T has only a right child W. What is its recursive post-order traversal?

36 In the recursive Towers of Hanoi solution for 4 disks, how many disk moves are required to transfer all disks from the source peg to the destination peg?

37 To move Towers of Hanoi disks from peg A to peg C using peg B, what is the first major recursive operation?

38 During merge sort, the sorted subarrays [2, 7, 9] and [1, 6, 8] are merged. What is the array after the first four elements have been selected?

39 Merge sort divides an array into two equal halves and spends linear time merging them. Which recurrence represents its running time?

40 Using Lomuto partitioning on [4, 2, 7, 3, 6] with the final element 6 as the pivot, which array results immediately after partitioning?

41 Let , , and for . What are the value of and the maximum number of simultaneously active calls when evaluating using direct recursion?

42 A binary tree contains 20 nodes and exactly 7 leaf nodes. How many nodes in the tree have exactly one child?

43 A complete binary tree has 1000 nodes and uses zero-based array indexing. Which statement correctly identifies its leaves and last internal node?

44 An extended binary tree is formed by replacing every missing child link of an ordinary binary tree with an external node. If the original tree has 23 internal nodes, how many external nodes and total nodes does the extended tree contain?

45 A linked binary tree has ordinary nodes, and every node stores two child pointers. Assuming absent children are represented by null pointers, how many null pointers exist?

46 Using one-based sequential representation, a binary tree has a single node at depth 10, and that node is the rightmost possible node at that depth. What is the minimum array length required to represent it without compression?

47 Consider the BST with root 50, whose left subtree is rooted at 30 with right child 40 and left child 10, and whose right subtree is rooted at 80 with left child 70, where 70 has right child 75. How many key comparisons are required to successfully search for 75?

48 Starting with an empty BST, insert the keys . How many comparisons are made while inserting key 34, counting the comparison at each visited node?

49 A BST has root 50; its right subtree is rooted at 70, with left child 60 and right child 80; node 60 has left child 55 and right child 65. When deleting 50 using its in-order successor, what is the resulting root and the new left child of node 60?

50 For the binary tree with root 8; left subtree rooted at 3 with children 1 and 6, where 6 has children 4 and 7; and right subtree rooted at 10 with right child 14, where 14 has left child 13, what is the recursive in-order traversal?

51 Using the same tree with root 8; left subtree rooted at 3 with children 1 and 6, where 6 has children 4 and 7; and right subtree rooted at 10 with right child 14, where 14 has left child 13, what is the recursive pre-order traversal?

52 Using the same tree with root 8; left subtree rooted at 3 with children 1 and 6, where 6 has children 4 and 7; and right subtree rooted at 10 with right child 14, where 14 has left child 13, what is the recursive post-order traversal?

53 A standard recursive Towers of Hanoi implementation makes one recursive call for each smaller problem, performs one move, and makes another recursive call. Including calls with as invocations, how many total function calls and disk moves occur for ?

54 What is the maximum number of element comparisons performed by standard top-down merge sort when sorting 10 elements, assuming each merge stops as soon as one subarray is exhausted?

55 In a recursive merge sort implementation that splits until every subarray has one element, how many merge operations are performed when sorting 13 elements?

56 Quick sort uses the last element as the pivot and Lomuto partitioning. What is the array immediately after partitioning around pivot 5?

57 Quick sort always chooses the first element as pivot and partitions a sorted array of 1024 distinct elements into subarrays of sizes 0 and 1023. What are the comparison count and maximum recursion depth?

58 A two-way quick sort partition treats values equal to the pivot as belonging to the same side rather than separating them. On an array of identical values, which complexity pair is most accurate for the resulting recursion?

59 In a BST, a node with two children is deleted by replacing it with its in-order predecessor. If the predecessor has a left child but no right child, which structural operation is required after the replacement?

60 Starting with an empty BST, insert . What are the height in edges and the number of leaves in the resulting tree?