Data Structures and Algorithms Model Question

NATIONAL ENGINEERING COLLEGE, K.R.NAGAR, KOVILPATTI – 628 503. B.E./B.Tech. Degree Examination – Internal assessment Test II –October 2010 Branch & Semester: IT & III Subject: IT33 - Data Structures & Algorithms Time: 3 hours Maximum Marks: 100 Part – A Answer all questions (10x2=20) What are dummy headers? Mention its use. Draw the diagram and give statements for deletion of a node in SLL. Convert the infix expression to prefix and postfix:( a + b ^ c ^ d ) * ( e + f / d) List few applications of queue. Construct an expression tree for the expression:( a + b * c ) + ( ( d * e + f ) * g ) A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a non – empty binary tree. Write preorder and post order of following tree:  Define hash function. What do you mean by path compression? What is collision? Give example. Part – A Answer all questions (5x16=80) a) Write algorithm / Pseudo code for : i) Counting the no. of nodes in single linked list.  ii) Reverse a single linked list.  iii) Concatenating 2 single linked list.  iv) Copy one SLL into another. (4 x 4 =16) (or)b) i) Explain the push and pop operations for linked list implementation of stack. (8) ii) Explain with example the stack operation conversion for conversion of infix to postfix. (8) a) i) Explain the insertion operation in BST. (8) ii) Draw the binary search trees that will be constructed for the insertion of  8 names as: Tim, Dot, Era, Roy, Tom, Kim, Guy, Any. (8) (or)b) i) Explain ADT Insertion operation of AVL tree. (8) ii) Show that for the perfect binary tree of height h containing nodes, the sum of heights of the nodes is . (8) a) Given the input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h (x) = x mod 10, show the resulting.  i) Separate chaining table  ii) Open addressing with linear probing  iii) Open addressing with quadratic probing  iv) Open addressing with second hash function  h2 (x) = 7 – (x mod 7) (4x4=16) (or)b) i) Explain with suitable examples about disjoint set ADT. (8) ii) Discuss in detail about set applications. (8) a) i) Write an algorithm to insert and delete an item in double linked list. (8) ii) Give two lists L1 and L2 write a procedure to compute L1 ∩ L2 using only the basic operations. (8) (or)b) Write an algorithm to count the no. of occurrences of a given data in a circular linked list and also to delete all duplicates present. (16) a) i) Write an algorithm to convert a general tree to binary tree. (8) ii)Given an UNIX file system as an input, formulate a routine to list the directory structure in an alphabetical order. (8) (or) b) Construct the heap and perform the delete - min operation for the following inputs: 142, 543, 123, 65, 453, 879, 572. Draw neat diagrams. (16) H F E I G C B A D