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.
a. B only
|
||
b. A or C but not B
|
||
c. none of them are legitimate
possibilities
|
||
d. C only
|
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?
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.
a. 0
|
||
b. 5
|
||
c. 3
|
||
d. 2
|
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.
a. 10
|
||
b. 9
|
||
c. 4
|
||
d. 8
|
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.
a. 10
|
||
b. 9
|
||
c. 4
|
||
d. None of these
|
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.
a. 5 10 15 20 78 98 99 100 105 110
|
||
b. 99 20 100 10 78 105 5 15 98 110
|
||
c. 99 20 10 5 15 78 98 100 105 110
|
||
d. 5 15 10 98 78 20 110 105 100 99
|
Great. Thanks for sharing the complete question paper. I am really scared of the coding part as I find difficulty in this portion. This post will prove to be of great use for me as I can now prepare this portion in a much better way.
ReplyDeletesap test
give the answers for problem and we can rectify it for next time.
ReplyDelete