Information Technology Engineering (Semester 4)
TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.
Answer any one question from Q1 and Q2
1 (a) Explain the concept of implicit and explicit stack.(2 marks)
1 (b) Write an algorithm to convert infix to postfix expression.(4 marks)
1 (c) Consider following circular queue of characters and size 5.
Front point to A and Rear Points to C Show the queue contents as per the following operations at every step.
i) F is added to the queue.
ii) Two letters are deleted.
Iii) K, L, M are added to the queue.
iv) Two letters are deleted.
v) R is added to the queue.
vi) Two letters are deleted.
vii) R is added to the queue.
viii) Two letters are deleted(6 marks)
2 (a) Implement Queue as an ADT using array representation.(6 marks)
2 (b) Clearly indicate the contents of stack during conversion of given infix expression to prefix expression. Consider ^ as exponent operator.
(((A+B)*C-(D-E))^(F+G))(6 marks)
Answer any one question from Q3 and Q4
3 (a) For Given graph draw the adjacency list / matrix and perform BFS or DFS.
(6 marks)
3 (b) With Example define following terms:
i) Complete Binary tree
ii) Strictly Binary tree
iii) Predecessor and successor(6 marks)
4 (a) Write a pseudo code for Prim's algorithm and find the MST for the graph given and show all the steps.
(8 marks)
4 (b) For the binary tree representation as an array, perform in-order threading for the tree.
A B C D E G H -- -- F -- -- -- J K -- -- -- -- -- -- -- -- -- -- -- -- L -- --(4 marks)
Answer any one question from Q5 and Q6
5 (a) Construct an AVL search tree by inserting the following elements in the order of their occurrence. Show the balance factor and type of rotation at each stage:
MAR MAY NOV AUG APR JAN DEC JUL FEB JUN(10 marks)
5 (b) Explain Huffman algorithm with an example.(4 marks)
6 (a) Sort the following numbers in ascending order using heap sort:
55 33 11 77 44 22 66 88 99(10 marks)
6 (b) Write a note on OBST.(4 marks)
Answer any one question from Q7 and Q8
7 (a) With the prototype and example, explain following functions:
i) seekg()
ii)tellp()(4 marks)
7 (b) Write C++ implementation of all primitive operations on Sequential file.(8 marks)
8 (a) What is a File? List different file opening modes? List the different types of external storage devices?(6 marks)
8 (b) Compare Sequential, Index sequential and direct access files.(6 marks)
and 5 others joined a min ago.
teamques10
★ 68k
sagarkolekar
★ 11k