22317 Computer Science Past Paper PDF

23242 22317 3 Hours / 70 Marks Seat No. Instructions : (1) All Questions are compulsory. (2) Answer each next main Question on a new page. (3) Ill...

23242 22317 3 Hours / 70 Marks Seat No. Instructions : (1) All Questions are compulsory. (2) Answer each next main Question on a new page. (3) Illustrate your answers with neat sketches wherever necessary. (4) Figures to the right indicate full marks. (5) Assume suitable data, if necessary. (6) Mobile Phone, Pager and any other Electronic Communication devices are not permissible in Examination Hall. Marks 1. Attempt any FIVE of the following : 10 (a) Define Abstract Data Type (ADT). (b) Explain the term : Time Complexity. (c) List the operations that can be performed on data structure. (d) Define Searching. State two methods of Searching. (e) Define Stack with suitable example. (f) Define linked list with example. (g) Define the following terms with respect to tree : (i) In-degree (ii) Out-degree [1 of 4] P.T.O. 22317 [2 of 4] 2. Attempt any THREE of the following : 12 (a) Describe working of Bubble sort with example. (b) Explain PUSH and POP operation on stack with suitable example. (c) Explain the concept of information, next, null pointer and empty list with respect to linked list. (d) Write an algorithm to insert a new node at the beginning in linear list. 3. Attempt any THREE of the following : 12 (a) Write a program to implement linear search for 10 elements in an array. (b) Write a program to print a string in reverse order. (c) Explain the operations on a singly linked list. (d) Draw a binary search tree for the given numbers : 50, 33, 44, 22, 77, 35, 60, 40 4. Attempt any THREE of the following : 12 (a) Explain linear data structure with any three types. (b) Write a ‘C’ program to implement selection sort. (c) Convert the following infix expression to postfix expression using stack and show the details of stack in each step : ((A + B)  C) ^ (D – E) (d) Implement a ‘C’ program to insert element into the queue and delete the element from the queue. (e) Compare linear list with circular list. (Any four points). 22317 [3 of 4] 5. Attempt any TWO of the following : 12 (a) Evaluate the given infix expression to the postfix expression using stack : ((a / (b – c + d))  (e – a)  c) (b) Create a singly linked list using data fields 15, 20, 22, 58, 60. Search a node 22 from the singly linked list and show procedure step-by-step with the help of diagram from start to end. (c) From the given tree, complete six answers : (i) Degree of tree (ii) Degree of node 3 (iii) Level of node 5 (iv) In-degree of node 3 (v) Out-degree of node 3 (vi) Height of tree 6. Attempt any TWO of the following : 12 (a) With a neat sketch explain working of priority queue. (b) Draw the tree for given expression : (a – 2b + 5c)2  (4d – 6e)5 P.T.O. 22317 [4 of 4] (c) Consider the graph G given below : (i) Write adjacency matrix representation (ii) Write adjacency list _______________