Ads Question Papers

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 1

1. (a) What do you mean by Data abstraction? (b) Difference between “C structure” and “C++ structure”. (c) Diffrence between a “assignment operator” and a “copy constructor”. (d) What is the difference between overloading and “overridding”? [4+4+4+4] 2. (a) What is multilevel inheritance? Write a program to illustrate the concept of Multilevel Inheritance. (b) What is Hybrid inheritance? Write a program to illustrate the concept of Hybrid Inheritance. [8+8] 3. What is an Error and Exception? Explain the exception handling mechanism in C++ ? [16] 4. (a) What are the applications of stack explain with an example. (b) Explain the list representation of a tree by means of an example. (c) Mention some common computing times for algorithms in order of increasing difficulty? [5+5+6] 5. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly configured hash table in which neverUsed is true for every empty bucket. [16] 6. (a) Write a method to delete the pair with the largest key from a Binary Search Tree. (b) Write a method to find the height of a Binary Search Tree? [8+8] 7. Write and explain an algorithm to determine if the AND/OR tree T is solvable. [16] 8. (a) Write a linear time algorithm that generates the OBST from the root table. (b) Prove that the greedy method always obtains an optimal solution to the job- sequencing problem. [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 2

1. (a) Explain about the friend function with a suitable example. (b) Why is it best to use inline functions instead of plain old # define macros? (c) How to tell the compiler to make a nonmember function inline? (d) How to tell the compiler to make a member function inline? [4+4+4+4] 2. What do you mean by run time polymorphism and how to implement run time polymorphism using virtual functions in C++? [16] 3. (a) How do I use exceptions? (b) Can I throw an exception from a constructor? From a destructor? (c) Why doesn’t C++ provide a “finally” construct? (d) What is an auto ptr and why isn’t there an auto array? (e) Why can’t I resume after catching an exception? [3+3+3+3+4] 4. (a) What are the applications of stack explain with an example. (b) Explain the list representation of a tree by means of an example. (c) Mention some common computing times for algorithms in order of increasing difficulty? [5+5+6] 5. (a) Explain the linear probing method in Hashing? Explain its performance analy- sis? (b) What is hashing with Chains? Explain? Compare this with Linear Probing? [8+8] 6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in è (logn) time in the worst case. (b) Derive the amortized complexity of a find, insert or delete operation performed on a splay tree with n elements. [8+8] 7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space. (b) Explain divide and conquer strategy by means of its control abstraction. (c) What is the difference between Greedy method and Divide and conquer. [6+6+4] 8. (a) What are the general characteristics of greedy algorithms and the problems solved by these algorithms. (b) What is 0/1 Knapsack problem? Explain how principle of optimality applies to it. Also derive its dynamic recurrence relation. [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 3

1. (a) Explain about Object Oriented Programming principles? (b) Comapare C++ with C. [8+8] 2. Define Inheritance? How many types of inheritances are there? Explain each with suitable examples. [16] 3. (a) How does that funky while (std :: cin >> foo) syntax work? (b) Why does input seem to process past the end of file? (c) Should we end output lines with std::endl or ‘\n'? [5+5+6] 4. (a) What are the applications of stack explain with an example. (b) Explain the list representation of a tree by means of an example. (c) Mention some common computing times for algorithms in order of increasing difficulty? [5+5+6] 5. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly configured hash table in which neverUsed is true for every empty bucket. [16] 6. (a) Write a method to delete the pair with the largest key from a Binary Search Tree. (b) Write a method to find the height of a Binary Search Tree? [8+8] 7. Write and explain an algorithm to determine if the AND/OR tree T is solvable. [16] 8. (a) Write a linear time algorithm that generates the OBST from the root table. (b) Prove that the greedy method always obtains an optimal solution to the job- sequencing problem. [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 4

1. (a) What is diff between malloc()/free() and new/delete? (b) What are the access privileges in C++? What is the default access level? (c) What is destructor? (d) What is passing by reference? [4+4+4+4] 2. (a) What’s the deal with operator overloading? (b) What are the benefits of operator overloading? (c) What are some examples of operator overloading? (d) What operators can/cannot be overloaded? [4+4+4+4] 3. (a) How can we provide printing for an entire hierarchy of classes? (b) How can we open a stream in binary mode? (c) How can we “reopen” std::cin and std::cout in binary mode? [5+5+6] 4. (a) What are the applications of stack explain with an example. (b) Explain the list representation of a tree by means of an example. (c) Mention some common computing times for algorithms in order of increasing difficulty? [5+5+6] 5. (a) What is a dictionary? Define the abstract data type for it? Write the abstract class for the dictionary? (b) Give the applications of dictionary or dictionary with duplicates in which sequential access is desired. [8+8] 6. What is a Binary search tree? Provide a specification for the abstract data type BSTree(binary search tree with duplicates). Define a C++ abstract class that corresponds to this ADT. Write a program to insert a pair into a binary search tree. [16] 7. Write and explain a non recursive algorithm for post order traversal of a Binary tree with an example. [16] 8. (a) Explain the Job sequencing with deadlines with an example using the greedy approach. (b) Describe the dynamic programming approach for the construction of OBST for a set of n keys, if all keys are equally likely to be searched for. [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 5

1. (a) Compare various forms of type cast operations (in C and C++ styles). Tell about overloading of these operations. (b) How to set default values of function arguments? What are pros and contras of use of this C++ opportunity? What’s its alternative? (c) When writing catch operator we can write directly type of exception as a type of its argument, pointer to a type of exception or reference to a type of exception. Compare these approaches. [6+5+5] 2. (a) What is Hybrid inheritance? Write a program to illustrate the concept of Hybrid Inheritance. (b) What is single inheritance? Write a program to illustrate the concept of single Inheritance. [8+8] 3. (a) Why should we use iostream instead of the traditional cstdio? (b) Why does a program go into an infinite loop when someone enters an invalid input character? (c) How can we get std::cin to skip invalid input characters? [5+6+5] 4. Write a C ++ program using stack ADT that reads an infix expression, converts the expression to postfix form and evaluates the postfix expression. [16] 5. (a) What is the structure to represent node in a skip list. Write the constructor for skipList. (b) Write a method in C++ to find a pair with key theKey in a dictionary using skip list representation? What is its complexity? [8+8] 6. (a) Explain about the LLr, LRr, LLb, LRb imbalances in a Red-Black tree with example? (b) Draw the sequence of rotations required to perform a single right rotation and a double LR rotation in an AVL tree? [8+8] 7. (a) What is the maximum number of disk accesses needed to delete an element that is in a non leaf node of a B-tree of order m? (b) Does deleting a leaf node from a red-black tree then reinserting the same key always result in the original tree? Prove it does or given a counter example where it does not. [6+10] 8. (a) Describe about search engine and inverted files. (b) Explain the main features of BoyerMoore algorithm. [10+6]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 6

1. (a) What do you mean by Stack unwinding? (b) What is the difference between const char *myPointer and char *const (c) Define precondition and post-condition to a member function. (d) What are the conditions that have to be met for a condition to be an invariant of the class? [4+4+4+4] 2. (a) If a class CStudent inherits from two classes CPerson and CQueenMary (“mul- tiple inheritance”), when you instantiate CStudent what constructors would be called? What is the syntax? How can you pass arguments to the other constructors? (b) What is the difference between private and protected? Which is more ap- proapriate in a library class hierarchy? or an application class hierarchy? (c) What is the difference between // and /* */ comment types? What are the strengths and weaknesses of each? [5+7+4] 3. (a) Explain about try, catch, throw keywords in C++? (b) Write a program to illustrate the exception handling mechanism in C++. [8+8] 4. What are the different mathematical notations used for algorithm analysis. 16] 5. What is Hashing? Explain the different Hash table representations in detail? [16] 6. Define a class called binarySearchTree to represent a Binary search tree. Extend this class by adding a public method outputInRange (Low,High) that outputs, in ascending order of key, all elements in a binary search tree whose key lies between Low and High. Use recursion and avoid entering sub trees that cannot possibly contain any elements with keys in desired range. [16] 7. (a) Show that the inorder and post order sequences of a binary tree uniquely define the binary tree. (b) Explain the AND/OR graph with an example. [8+8] 8. (a) What is dynamic programming technique? How does it differ from divide and conquer technique. (b) Solve the Greedy Knapsack problem where m=25, n=3, P = (25,24,17) and W = (16,14,9). [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 7

1. (a) What are C++ storage classes? (b) What is encapsulation? (c) What does extern “C”int func(int , Foo) accomplish? [5+5+6] 2. What is template? Explain about function templates and class templates with suitable examples. [16] 3. (a) How should we handle resources if constructors may throw exceptions? (b) How do we change the string-length of an array of char to prevent memory leaks even if/when someone throws an exception? (c) What should we throw? What should we catch? [5+5+6] 4. Write a C++ program to implement operations of doubly linked list. [16] 5. (a) What is a dictionary? Define the abstract data type for it? Write the abstract class for the dictionary? (b) Give the applications of dictionary or dictionary with duplicates in which sequential access is desired. [8+8] 6. Define a Binary Search Tree? Write the procedures to perform insertion, deletion and searching in a binary search tree? [16] 7. Write and explain a non recursive algorithm for post order traversal of a Binary tree with an example. [16] 8. (a) What is dynamic programming technique? How does it differ from divide and conquer technique. (b) Solve the Greedy Knapsack problem where m=25, n=3, P = (25,24,17) and W = (16,14,9). [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 8

1. (a) Each class has some special member-functions, which calls can be inserted by the compiler into a code without explicit instruction of the programmer. Enumerate such functions, members and cases, when implicit calls can arise. (b) If when creating a variable the programmer explicitly did not initialize it, in some cases, the compiler itself would give it a certain, predefined initial value, and in some cases the initial value would be unpredictable. What does it depend on? [8+8] 2. (a) What’s the difference between public, private, and protected? (b) Why can’t the derived class access private things from my base class? (c) How can we protect derived classes from breaking when we change the internal parts of the base class? [5+5+6] 3. (a) Explain about try, catch, throw keywords in C++? (b) Write a program to illustrate the exception handling mechanism in C++. [8+8] 4. (a) What is meat by Profiling ? Explain it with an example. (b) Trace the heap sort algorithm to sort the following list of numbers 8, 20, 9, 4, 15, 10, 7, 22, 3, 12. [8+8]

5. (a) What is the structure to represent node in a skip list. Write the constructor for skipList. (b) Write a method in C++ to erase a pair in the dictionary with key theKey in a skip list representation. What is the complexity of this method? [8+8] 6. Define a class called binarySearchTree to represent a Binary search tree. Extend this class by adding a public method outputInRange (Low,High) that outputs, in ascending order of key, all elements in a binary search tree whose key lies between Low and High. Use recursion and avoid entering sub trees that cannot possibly contain any elements with keys in desired range. [16] 7. (a) Determine the running time of Quick sort for i. Reverse order input ii. Random input iii. Sorted input (b) Show that DFS visits all vertices in G reachable from V. [10+6] 8. (a) Solve the following 0/1 Knapsack Problem using dynamic programming n=4, m=30, (w1,w2,w3,w4) = (10,15,6,9) and (p1, p2, p3, p4) = (2,5,8,1). (b) Differentiate between Greedy method and Dynamic Programming [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 9

1. (a) What is a friend function? Explain the advantages and disadvantages of it? (b) What is static member function? Explain it’s limitations. [8+8] 2. (a) Explain the concept of virtual functions in C++ with suitable examples. (b) Explain the concept of operator overloading in C++. [8+8] 3. (a) Write a program to replace all the occurrences of a word with some other word in a given file. (b) Write a program to check whether the given string is palindrome or not. [8+8] 4. Write an algorithm for transposing a given matrix of n × m size and determine the time complexity of the algorithm by using Asymptotic notation method. [16] 5. (a) What is the structure to represent node in a skip list. Write the constructor for skipList. (b) Write a method in C++ to find a pair with key theKey in a dictionary using skip list representation? What is its complexity? [8+8] 6. What is an AVL Tree? Explain about the different rotation patterns in AVL trees for balancing with appropriate examples? [16] 7. (a) Find a necessary and sufficient condition for the root of a depth first search for a connected graph to be an articulation point. (b) Solve the following recurrence relation using substitution method [8+8] T(n) = 1 where n 4 = 2T( n)+logn where n 4 8. (a) If objects are selected in order of decreasing Vi/Wi then prove that the algo- rithm Knapsack finds an optimal solution. (b) Explain the Optimal binary search tree. [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 10

1. (a) What do you mean by Data abstraction? (b) Difference between “C structure” and “C++ structure”. (c) Diffrence between a “assignment operator” and a “copy constructor”. (d) What is the difference between ?overloading? and “overridding”? [4+4+4+4] 2. (a) Explain the need for “Virtual Destructor”. (b) Can we have “Virtual Constructors”? [8+8] 3. (a) What does throw; (without an exception object after the throw keyword) mean? Where would we use it? (b) How do we throw polymorphically? (c) When we throw this object, how many times will it be copied? [5+5+6] 4. (a) Discuss briefly the asymptotic notations used for finding the complexity of Algorithms. (b) Write a C++ program to implement the sparse matrix. [8+8] 5. Define the abstract class for dictionary? Write the methods find, insert, erase used in dictionary? Explain the time complexities to perform above three operations? [16] 6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in ? (logn) time in the worst case. (b) Derive the amortized complexity of a find, insert or delete operation performed on a splay tree with n elements. [8+8] 7. (a) Find a necessary and sufficient condition for the root of a depth first search for a connected graph to be an articulation point. (b) Solve the following recurrence relation using substitution method [8+8] T(n) = 1 where n 4 = 2T( n)+logn where n 4 8. (a) Show how Prim’s algorithm can be implemented using heap. What would be the time complexity of the algorithm. (b) What is the time complexity of traveling sales person problem using dynamic programming. [10+6]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 11

1. (a) Explain about the dynamic memory allocation and de-allocation in C++. (b) Explain about static inner classes with a program. [8+8] 2. Explain the difference between virtual function and virtual inheritance. [16] 3. (a) Why should we use iostream instead of the traditional cstdio? (b) Why does a program go into an infinite loop when someone enters an invalid input character? (c) How can we get std::cin to skip invalid input characters? [5+6+5] 4. (a) What is meat by Profiling ? Explain it with an example. (b) Trace the heap sort algorithm to sort the following list of numbers 8, 20, 9, 4, 15, 10, 7, 22, 3, 12. [8+8] 5. Develop a class for hash table using linear probing and neverUsed concept to handle an erase operation. Write complete C++ code for all the methods. Include a method to reorganize the table when (say) 60% of the empty buckets have never used equal to false. The reorganization should move pairs around as necessary and leave a properly configured hash table in which neverUsed is true for every empty bucket. [16] 6. Define a Binary Search Tree? Write the procedures to perform insertion, deletion and searching in a binary search tree? [16] 7. (a) Show that depth first search can be used to find the connected components of an undirected graph. (b) Write the Quick sort algorithm Also analyze its time complexity in Best case. [6+10] 8. (a) Solve the following 0/1 Knapsack Problem using dynamic programming n=4, m=30, (w1,w2,w3,w4) = (10,15,6,9) and (p1, p2, p3, p4) = (2,5,8,1). (b) Differentiate between Greedy method and Dynamic Programming [8+8]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Advanced Data Structures Previous Question papers

Question Paper 12

1. (a) Explain about the static variable? (b) Explain about the static functions and static classes in detail with a program. [8+8] 2. (a) What special considerations do we need to know about when I use Virtual Inheritance? (b) What special considerations do we need to know about when I inherit from a class that uses virtual inheritance? (c) What special considerations do I need to know about when I use a class that uses virtual inheritance? [5+5+6] 3. (a) What does throw; (without an exception object after the throw keyword) mean? Where would we use it? (b) How do we throw polymorphically? (c) When we throw this object, how many times will it be copied? [5+5+6] 4. (a) What is a heap ? Differentiate between heap and binary search tree. (b) Show that log3n is O(n1/3). (c) Briefly explain about Hashing. [5+5+6] 5. (a) Explain the linear probing method in Hashing? Explain its performance analy- sis? (b) What is hashing with Chains? Explain? Compare this with Linear Probing? [8+8] 6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in è (logn) time in the worst case. (b) Derive the amortized complexity of a find, insert or delete operation performed on a splay tree with n elements. [8+8] 7. Prove the equation T( N ) + a T ( N /b ) + è(NklogpN) [16] Where a 1, b 1 and P 0 is T(N) = O(Nlogb a)ifa bk O(Nklogp+1N) if a = bk O(NklogpN) if a bk. 8. (a) Show how Prim’s algorithm can be implemented using heap. What would be the time complexity of the algorithm. (b) What is the time complexity of traveling sales person problem using dynamic programming. [10+6]

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.

Free Materials E-books Online Bits Previous Question Papers Important Questions Syllabus book List of books to refer …n many more

For all JNTU related Stuff

www.jntu123.blogspot.com

AcroPDF - A Quality PDF Writer and PDF Converter to create PDF files. To remove the line, buy a license.