Coding skills
Question 1
Marks: 1
The subject of these questions is an unusually simple kind of binary tree, defined by these properties:
Terminal nodes contain a string.
Internal nodes have one or two children, called "left" and "right".
Either child of an internal node may be null, but not both.
Internal nodes contain no other information.
By "tree" we simply mean a node and all of its descendants.
A tree rooted at a node having left child A and right child B is a different tree than one rooted at a node having left child B and right child A.
Here's an example, with plus signs (+) used to indicate internal nodes:
+
/ \
/ \
/ \
+ +
/ / \
/ / \
/ / \
"A" + "D"
/ \
/ \
/ \
"B" "C"
class InternalNode extends Node {
Node left, right;
}
What constructors could InternalNode have according to the specifications for the tree structure (potentially in addition to others)?
InternalNode()
InternalNode(String)
InternalNode(Node)
Choose one answer.
Question 2
Marks: 1
Given the following code snippet answer the following question.
struct AVLTree
{
AVLTree * left;
AVLTree * right;
int element;
int height;
};
int MAX(int a, int b){
if(a>=b)
return a;
if(a<b)
return b;
}
int height(AVLTree *node)
{
if (node == NULL)
{
return -1;
}
else
{
return node->height;
}
}
AVLTree * single_rotation_with_left(AVLTree *k2)
{
AVLTree *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->left), height(k2->right)) + 1;
return k1;
}
AVLTree * single_rotation_with_right(AVLTree *k2)
{
AVLTree *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k2->height = MAX(height(k2->left), height(k2->right)) + 1;
k1->height = MAX(height(k1->right), height(k2->left)) + 1;
return k1;
}
AVLTree *double_rotation_with_left(AVLTree *k3)
{
k3->left = single_rotation_with_right(k3->left);
return single_rotation_with_left(k3);
}
AVLTree *double_rotation_with_right(AVLTree *k3)
{
k3->right = single_rotation_with_left(k3->right);
return single_rotation_with_right(k3);
}
void insert(int value, AVLTree **node)
{
if (*node == NULL)
{
*node = new AVLTree;
if (*node == NULL)
{
return;
}
(*node)->element = value;
(*node)->height = 0;
(*node)->left = (*node)->right = NULL;
return;
}
else if (value < (*node)->element)
{
insert(value, &((*node)->left));
if (height((*node)->left) - height((*node)->right) == 2)
{
if (value < (*node)->left->element)
{
*node = single_rotation_with_left(*node);
}
else
{
*node = double_rotation_with_left(*node);
}
}
}
else if (value > (*node)->element)
{
insert(value, &((*node)->right));
if (height((*node)->right) - height((*node)->left) == 2)
{
if (value > (*node)->right->element)
{
*node = single_rotation_with_right(*node);
}
else
{
*node = double_rotation_with_right(*node);
}
}
}
(*node)->height = MAX(height((*node)->left), height((*node)->right)) + 1;
}
Consider an input sequence that is provided as an input to the insert method
20,5,15,9,13,2,6,12,14,15,16,17,18,19
In the process of inserting the above nodes how many times double_rotation_with_left is being called?
Choose one answer.
Question 3
Marks: 1
Following is the array representation of a Binary search tree:
Consider that the binary tree specified above id given as input to the following function.
int numofleaves(tNode *p)
{
if (p==0)
return 0;
if (p->left==0 && p->right ==0)
return 1;
else
return numofleaves(p->right)+numofleaves(p->left);
}
Choose one answer.
Question 4
Marks: 1
Following is the array representation of a Binary search tree:
Consider that the binary tree specified above id given as input to the following function.
int func1(tNode *p)
{
if (p!=0)
return func1 (p->left) + func1 (p->right) + 1;
else
return 0;
}
Choose one answer.
Question 5
Marks: 1
Following is the array representation of a Binary search tree:
What would be the output of the following code snippet for the above mentioned binary search tree?
void func() {
std::queue q;
q.push(root);
while( q.size() != NULL ) {
Node *cur = q.front();
std::cout << cur->data << std::endl;
q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
Choose one answer.
