NEW
Font size
S
M
L
XL
WorksheetsCPS02-Day3-NWC -Set02
Total questions: 30
Worksheet time: 30mins
Name
Class
Date
1.
What is the traversal strategy used in the binary tree?
a)
depth-first traversal
b)
breadth-first traversal
c)
random traversal
d)
Priority traversal
2.
What are the children for node ‘w’ of a complete-binary tree in an array representation?
a)
2w and 2w+1
b)
2+w and 2-w
c)
w+1/2 and w/2
d)
w-1/2 and w+1/2
3.
Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good?
a)
yes because we are overcoming the need of pointers and so space efficiency
b)
yes because array values are indexable
c)
No it is not efficient in case of sparse trees and remaning cases it is fine
d)
No linked list representation of tree is only fine
4.
What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
a)
floor(w-1/2)
b)
ceil(w-1/2)
c)
w-1/2
d)
w/2
5.
Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?
a)
Yes just traverse through the array and form the tree
b)
No we need one more traversal to form a tree
c)
No in case of sparse trees
d)
Yes by using both inorder and array elements
6.
If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array?
a)
every node stores data saying which of its children exist in the array
b)
no need of any changes continue with 2w and 2w+1, if node is at i
c)
keep a seperate table telling children of a node
d)
use another array parallel to the array with tree
7.
How many children does a binary tree have?
a)
2
b)
any number of children
c)
0 or 1 or 2
d)
0 or 1
8.
What is/are the disadvantages of implementing tree using normal arrays?
a)
difficulty in knowing children nodes of a node
b)
difficult in finding the parent of a node
c)
have to know the maximum number of nodes possible before creation of trees
d)
difficult to implement
9.
What must be the ideal size of array if the height of tree is ‘l’?
a)
2l-1
b)
l-1
c)
l
d)
2l
10.
Level order traversal of a tree is formed with the help of
a)
breadth first search
b)
depth first search
c)
dijkstra’s algorithm
d)
prims algorithm
11.
Identify the reason which doesn’t play a key role to use threaded binary trees?
a)
The storage required by stack and queue is more
b)
The pointers in most of nodes of a binary tree are NULL
c)
It is Difficult to find a successor node
d)
They occupy less size
12.
Advantages of linked list representation of binary trees over arrays?
a)
dynamic size
b)
ease of insertion/deletion
c)
ease in randomly accessing a node
d)
both dynamic size and ease in insertion/deletion
13.
Disadvantages of linked list representation of binary trees over arrays?
a)
Randomly accessing is not possible
b)
Extra memory for a pointer is needed with every element in the list
c)
Difficulty in deletion
d)
Random access is not possible and extra memory with every element
14.
Which of the following traversing algorithm is not used to traverse in a tree?
a)
Post order
b)
Pre order
c)
Post order
d)
Randomized
15.
What may be the psuedo code for finding the size of a tree?
a)
find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)
b)
find_size(root_node–>left_node) + find_size(root_node–>right_node)
c)
find_size(root_node–>right_node) – 1
d)
find_size(root_node–>left_node + 1
16.
Which of the following is not an advantage of trees?
a)
Hierarchical structure
b)
Faster search
c)
Router algorithms
d)
Undo/Redo operations in a notepad
17.
In a full binary tree if number of internal nodes is I, then number of leaves L are?
a)
L = 2*I
b)
L = I + 1
c)
L = I – 1
d)
L = 2*I – 1
18.
In a full binary tree if number of internal nodes is I, then number of nodes N are?
a)
N = 2*I
b)
N = I + 1
c)
N = I – 1
d)
N = 2*I + 1
19.
What is a complete binary tree?
a)
Each node has exactly zero or two children
b)
A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left
c)
A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
d)
A tree In which all nodes have degree 2
20.
The number of edges from the root to the node is called __________ of the tree.
a)
Height
b)
Depth
c)
Length
d)
Width
21.
The number of edges from the node to the deepest leaf is called _________ of the tree.
a)
Height
b)
Depth
c)
Length
d)
Width
22.
What is a full binary tree?
a)
Each node has exactly zero or two children
b)
Each node has exactly two children
c)
All the leaves are at the same level
d)
Each node has exactly one or two children
23.
What is the average case time complexity for finding the height of the binary tree?
a)
h = O(loglogn)
b)
h = O(nlogn)
c)
h = O(n)
d)
h = O(log n)
24.
In a full binary tree if there are L leaves, then total number of nodes N are?
a)
N = 2*L
b)
N = L + 1
c)
N = L – 1
d)
N = 2*L – 1
25.
Which of the following is incorrect with respect to binary trees?
a)
Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
b)
Let T be a binary tree with λ levels. Then T has no more than 2λ – 1 nodes
c)
Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
d)
Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
26.
If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?
a)
2i+1
b)
2i+2
c)
2i
d)
4i
27.
Which of the following properties are obeyed by all three tree – traversals?
a)
Left subtrees are visited before right subtrees
b)
Right subtrees are visited before left subtrees
c)
Root node is visited before left subtree
d)
Root node is visited before right subtree
28.
Several kinds of queries are possible on a k-d called as?
a)
partial queries
b)
range queries
c)
neighbour queries
d)
search queries
29.
In a k-d tree, k originally meant?
a)
number of dimensions
b)
size of tree
c)
length of node
d)
weight of node
30.
An expression tree’s nodes can be deleted by calling?
a)
malloc
b)
calloc
c)
delete
d)
free
Reset
