Jump to Year/Set
Instructions:
- The marks are indicated in the right-hand margin.
- There are NINE questions in this paper.
- Attempt FIVE questions in all.
- Question No. 1 is compulsory.
Questions
Answer the following:
Define data structure.
What are average, best and worst case complexities?
Write formula to calculate address of elements in two-dimensional array.
What is deque? Explain with example.
Define tail recursion.
What is the need for linked representation of lists?
Give node structure for the term of polynomial having single variable.
What is the maximum number of nodes in a binary tree of depth ?
What is threaded binary tree?
What is worst case time complexity of quick sort?
Answer the following:
Formulate an algorithm to find the number of total nodes in a binary tree. What is the complexity of your algorithm?
Answer the following:
What is Tower of Hanoi problem? Draw the recursive tree diagram for the solution of Tower of Hanoi problem, where the number of disks is 4 and number of pegs is 3.
Answer the following:
Explain the following operations on a binary search tree with suitable algorithms:
Answer the following:
Explain the following operations with pseudo-code in a doubly circular linked list:
Answer the following:
The odd-even transposition sort proceeds as follows : Pass through the file several times. On the first pass, compare x[i] with x[i+1] for all odd i. On the second pass, compare x[i] with x[i+1] for all even i. Each time that x[i] > x[i+1], interchange the two. Continue altering in this fashion until the file is sorted.
Answer the following:
Construct an inorder threaded binary tree (TBT) for the given tree. Illustrate its node structure. Also show the memory representation of a complete TBT for this :
Answer the following:
Define AVL tree. Construct an AVL tree for the following elements : 3, 5, 11, 8, 4, 1, 12, 7, 2, 6, 10
Answer the following:
Prove the correctness of Kruskal's algorithm for minimum spanning tree. Draw minimum cost spanning tree for the graph given below and also find its cost :