NEW
Font size
WorksheetsFinal Quiz
Total questions: 20
Worksheet time: 20mins
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
(a) log2n
(b) n-1
(c) n
(d) 2n
In the balanced binary tree in the figure given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
1
3
7
8
A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is
(a) (4, 7)
(b) (7, 4)
(c) (8, 3)
(d) (3, 8)
Which of the following statements is false?
A tree with n nodes has (n – 1) edges
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
A complete binary tree with n internal nodes has (n + 1) leaves.
The maximum number of nodes in a binary tree of height h is (2h+1-1)
A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by
(a) x(n – 1) +1
(b) xn - 1
(c) xn + 1
(d) x(n+1)
Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
(a) (1 2 (4 5 6 7))
(b) (1 ((2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))
The most appropriate matching for the following pairs
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack
is:
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y—3 Z-1
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) Both are True
(d) None of the above
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
a) 7 5 1 0 3 2 4 6 8 9
b) 0 2 4 3 1 6 5 9 8 7
c) 0 1 2 3 4 5 6 7 8 9
d) 9 8 6 4 2 3 0 1 5 7
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
(a) 2h -1
(b) 2h-1 – 1
(c) 2h+1 -1
(d) 2h+1
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1
4
3
5
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
(A) d e b f g c a
(B) e d b g f c a
(C) e d b f g c a
(D) d e f g b c a
Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
(a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?
i) Preorder and Postorder
ii) Inorder and Postorder
iii) Preorder and Inorder
iv) Level order and Postorder
(a) (i) only
(b) (ii), (iii) only
(c) (iii) only
(d) (iv) only
Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?
(a) Database relations have a large number of records
(b) Database relations are sorted on the primary key
(c) B-trees require less memory than binary search trees
(d) Data transfer form disks is in blocks.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
(a) 2
(b) 3
(c) 4
(d) 5
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.
The appropriate expression for the two boxes B1 and B2 are
(a) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(b) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(c) B1 : height(n->right), B2 : max(h1,h2)
(d) B1 : (1 + height(n->right)), B2 : max(h1,h2)
Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to
(A) only vertex a
(B) only vertices a, e, f, g, h
(C) only vertices a, b, c, d
(D) all the vertices
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(a) 1, 3, 5, 6, 8, 9
(b) 9, 6, 3, 1, 8, 5
(c) 9, 3, 6, 8, 5, 1
(d) 9, 5, 6, 8, 3, 1
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements '1' and '7' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
a) 10, 8, 7, 5, 3, 2, 1
(b) 10, 8, 7, 2, 3, 1, 5
(c) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5
