|
|
Q.Write a recursive algorithm to implement Quick Sort.
Ans. The Quick Sort can be implemeted efficiently using recursion. The Base case may be when low is greater than or equal to high.
The function/algo is as follows:
quick(a, low, high)
int a[], low, high
{
if (low>=high)
return;
partition (a, low, high, pos);
quick(a.low, pos-1);
quick(a.pos_1, high);
}
3 (c) What is an AVL tree? How does it differ from a Binary Tree?
Answer
A Tree is called AVL tree (Balanced Binary tree) if each node possesses one of the following properties:
(i) A node is called left heavy, if the longest path in its left subtree is one longer then the longest past of its right subtree.
(ii) A node is called right heavy, if the longest part in the right subtree is one longer than the longest path in its left subtree.
(iii) a node is called balanced if the longest paths in both the right and the left subtrees are equal.
Binary tree: A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then its is called binary tree. In a binary tree left and right subtrees distinguish subtrees of a node.
An AVL tree is a balanced tree, but binary tree can be unbalanced also.
3(a) Write the postfix form of the following expresstion:
(i) (C X D) ÷ (a-b)
(ii) C X D ÷ a – b
Answer (i) :
cd* ÷ (ab-)
cd*ab-÷
Answer (ii) :
c*da÷- b
cda÷*- b
cda÷*b-
3(a) Write the postfix form of the following expresstion:
(i) (C X D) ÷ (a-b)
(ii) C X D ÷ a – b
Answer (i) :
cd* ÷ (ab-)
cd*ab-÷
Answer (ii) :
c*da÷- b
cda÷*- b
cda÷*b-
Question 2.(c) List atleast 4 differences between Arrays and Pointers in 'C' Language.
Answer: (i) Array elemets are always stored in contiguous memory location irrespective of array size.
(ii) There is necessary to assign the size in array, ut not in Pointers.
(iii)Pointers are randomly location.
(iv) The size of the data type which pointer variable refers to is dependent on the data type pointed to by the pointer.
(v) A pointer whenever increameted, points to a location after skipping number of bytes required by the data type.
Q.2. (b) Consider the tree in the following figure:
Give the Postfix, Prefix and Infix expressions corresponding to the above tree.
Answer:
Infix expression = (a * b) x (c + d ) - e
Prefix expression= *ab* + cd - e = *ab* -+ cde
Postfix expression= (ab *) * (cd + ) -e =ab*cd + * .e -
QuestionDraw the internal memory representation of the following Binary Tree using Sequential Representation. Assume that nodes appear in the following physical sequence:
A, B, C, D, E, G, F, H
Answer
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Value | A | B | C | D | E | G | F | H |
Question: Write a function that takes only a pointer to the root of a binary tree T and computes the number of nodes in T.
Answer: When we traverse a binary tree then all the nodes of tree should traversed. Now if we put a pointer as a counter than it will print the total no of nodes. Any of the traversal schemes can be used to determine the number of elements in abinery tree. But we can use this mechanism also to count the total no. of neds of left subtree and right subtree.
The function is as follows:
int TotalNodes(bnodes*tree)
{
if(tree==(bnode*true)NULL)
return 0;
else
return (TotalNodes(tree->left)+TotalNodes(tree->right)+1);
}
Question:
Write a function to multiply two polynomials, using a linked list implementation. You must make sure that the output polynomial is sorted by exponent and has almost one term corresponding to any power. Assume appropriate representation for input polynomials.
Answer:
Void Multiply Polynimal (node*ptr, node*ptr2, node*ptr3)
{
int powe coef;
node*temp, *loc, *tt;
while (ptr1!=(node*)NULL)
{
temp=ptr2;
while(temp!=(node*)NULL)
{
coef=ptr1->coeff*temp->coeff;
powe=ptr1->power+temp->powe;
tt=*ptr3;
loc=search(tt.powe);
if(loc==(node*)NULL)
inser node(sptr3,coef,powe);
else
loc->coef+=coef;
temp=temp->next;
}
ptr1=ptr1->next;}
}
}
