JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2018 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (June/July - 2018 - R13)
Part A is compulsory which carries 20 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 8 marks and may have a, b, c as sub questions.
Part A
Write a procedure to convert infix expression to postfix expression. Apply the procedure on the following ((A+B)*D) ↑ (E-F)
Answer
To convert infix to postfix, use a stack to hold operators. Scan the expression from left to right: if an operand is encountered, append it to the result; if an operator is encountered, pop operators from the stack with higher or equal precedence to the result before pushing the current operator; use parentheses to control precedence. For ((A+B)*D) ↑ (E-F):
- ( ( A + B ) * D ) ↑ ( E - F )
- Postfix: AB+D*EF-↑
Define Binary tree. Write an algorithm to insert an element in to a binary tree.
Answer
A Binary Tree is a non-linear data structure where each node has at most two children, referred to as the left child and the right child. To insert an element into a binary tree (typically a binary search tree):
- If the tree is empty, create a new node as the root.
- If the value is less than the current node's value, move to the left subtree.
- If the value is greater than the current node's value, move to the right subtree.
- Repeat until an empty spot is found and insert the new node there.
Write the principle of(i) Quick sort (ii) Merge sort and write their complexities.
Answer
Sign in to view the complete answer paper.
Construct an AVL Tree by inserting numbers from 1 to 8.
Answer
Sign in to view the complete answer paper.
Explain Kruskal’s Algorithm for Minimum cost spanning trees.
Answer
Sign in to view the complete answer paper.
Part B
What is meant by stack? Write push and pop functions in C++ using an array.
Answer
Sign in to view the complete answer paper.
Write a short note on Linked List. What the various applications of linked list?
Answer
Sign in to view the complete answer paper.
Write an algorithm for deleting an element from the linked list.
Answer
Sign in to view the complete answer paper.
With a neat sketch explain DFS and BFS traversals with an example.
Answer
Sign in to view the complete answer paper.
Explain Binary tree ADT and its representation in Array and Linked lists.
Answer
Sign in to view the complete answer paper.
Suppose a sequence of numbers is given like: 5, 1, 6, 7, 9, 22, 10, 55, 45, and 34. How this numbers will be sorted using a) Insertion Sort b) Bubble sort.
Answer
Sign in to view the complete answer paper.
Write an algorithm for linear search and Binary Search and compare them in terms of time complexity.
Answer
Sign in to view the complete answer paper.
Explain in detail about Red-Black trees and Splay trees with examples.
Answer
Sign in to view the complete answer paper.
Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree.
Answer
Sign in to view the complete answer paper.
Show the result of deleting the root.
Answer
Sign in to view the complete answer paper.
Discuss about Job Sequencing with deadlines and Single Source Shortest path problem.
Answer
Sign in to view the complete answer paper.
Explain the Pattern matching algorithm with an example.
Answer
Sign in to view the complete answer paper.