II B.Tech I Semester Supplimentary Examinations, November 2008
ADVANCED DATA STRUCTURE
( Common to Computer Science & Engineering and Electronics &
1. (a) What do you mean by Stack unwinding?
(b) What is the difference between const char my*Pointer and char *const my pointer?
(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?
2. What is template? Explain about function templates and class templates with suitable examples.
3. Create a program that opens a file (the first argument on the command line) and searches it for any one of a set of words (the remaining arguments on the command line). Read the input a line at a time, and print out the lines (with line numbers) that match.
4. (a) Write the program which gives the Destructor for list/chain.
(b) Write a method to return the index of the first occurrence of an element in a list/chain.
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.
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?
7. (a) Write pseudo code procedure for insert operations in a red-black tree.
(b) Write an algorithm for visualization of a key insertion algorithm in a B-tree.
8. (a) Write an algorithm for deleting a string from a compressed trie and also analyze its complexity.
(b) Describe the characteristics of Boyer-Moore algorithm.