Code No: R05211201 R05 Set No.

2
II B.Tech I Semester Examinations,December 2011
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
?????

1. (a) Explain about parameter passing mechanism in C++?

(b) Explain about the various storage classes in C++? [8+8]
2. (a) Write a program to count the no of blank spaces, characters, words in a given
text file.
(b) write a program to copy the contents of one file to other. [8+8]
3. (a) What is a heap? Differentiate between heap and binary search tree.
(b) Show that log 3 n is O(n1/3 ).
(c) Briefly explain about Hashing. [5+5+6]
4. (a) What is an ABC?
(b) What is a “pure virtual” member function ?
(c) How do you define a copy constructor or assignment operator for a class that
contains a pointer to a (abstract) base class? [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) What is Spanning tree? Explain the Prim’s algorithm with an example.
(b) Find the shortest path between all pairs of nodes in the following graph as
shown in figure.8b by using TSP. [8+8]

Figure 8b

1
Code No: R05211201 R05 Set No. 2
7. (a) State the conditions under which insertion of a vertex in a Red-Black tree will
result in a sequence of recolouring steps that terminate with the root changing
colour.
(b) Will the root of a Red-Black tree always be black after performing a deletion
operation? Justify with an example? [8+8]

8. Write and explain the algorithm for evaluating a game tree using alpha-beta prun-
ing. [16]

?????

2
Code No: R05211201 R05 Set No. 4
II B.Tech I Semester Examinations,December 2011
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
?????

1. (a) Write a program to count the no of blank spaces, characters, words in a given
text file.
(b) write a program to copy the contents of one file to other. [8+8]

2. (a) What is a heap? Differentiate between heap and binary search tree.
(b) Show that log 3 n is O(n1/3 ).
(c) Briefly explain about Hashing. [5+5+6]

3. Write and explain the algorithm for evaluating a game tree using alpha-beta prun-
ing. [16]

4. (a) State the conditions under which insertion of a vertex in a Red-Black tree will
result in a sequence of recolouring steps that terminate with the root changing
colour.
(b) Will the root of a Red-Black tree always be black after performing a deletion
operation? Justify with an example? [8+8]

5. (a) Explain about parameter passing mechanism in C++?

(b) Explain about the various storage classes in C++? [8+8]

6. (a) What is an ABC?

(b) What is a “pure virtual” member function ?
(c) How do you define a copy constructor or assignment operator for a class that
contains a pointer to a (abstract) base class? [5+5+6]

7. (a) What is Spanning tree? Explain the Prim’s algorithm with an example.
(b) Find the shortest path between all pairs of nodes in the following graph as
shown in figure.8b by using TSP. [8+8]

3
Code No: R05211201 R05 Set No. 4

Figure 8b
8. 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]

?????

4
Code No: R05211201 R05 Set No. 1
II B.Tech I Semester Examinations,December 2011
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
?????

1. (a) State the conditions under which insertion of a vertex in a Red-Black tree will
result in a sequence of recolouring steps that terminate with the root changing
colour.
(b) Will the root of a Red-Black tree always be black after performing a deletion
operation? Justify with an example? [8+8]

2. (a) What is an ABC?

(b) What is a “pure virtual” member function ?
(c) How do you define a copy constructor or assignment operator for a class that
contains a pointer to a (abstract) base class? [5+5+6]

3. Write and explain the algorithm for evaluating a game tree using alpha-beta prun-
ing. [16]

4. 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]

5. (a) What is a heap? Differentiate between heap and binary search tree.
(b) Show that log 3 n is O(n1/3 ).
(c) Briefly explain about Hashing. [5+5+6]

6. (a) What is Spanning tree? Explain the Prim’s algorithm with an example.
(b) Find the shortest path between all pairs of nodes in the following graph as
shown in figure.8b by using TSP. [8+8]

5
Code No: R05211201 R05 Set No. 1

Figure 8b
7. (a) Write a program to count the no of blank spaces, characters, words in a given
text file.
(b) write a program to copy the contents of one file to other. [8+8]

8. (a) Explain about parameter passing mechanism in C++?

(b) Explain about the various storage classes in C++? [8+8]

?????

6
Code No: R05211201 R05 Set No. 3
II B.Tech I Semester Examinations,December 2011
ADVANCED DATA STRUCTURES AND ALGORITHMS
Common to Information Technology, Computer Science And Systems
Engineering
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
?????

1. (a) What is an ABC?

(b) What is a “pure virtual” member function ?
(c) How do you define a copy constructor or assignment operator for a class that
contains a pointer to a (abstract) base class? [5+5+6]

2. (a) Explain about parameter passing mechanism in C++?

(b) Explain about the various storage classes in C++? [8+8]

3. (a) What is a heap? Differentiate between heap and binary search tree.
(b) Show that log 3 n is O(n1/3 ).
(c) Briefly explain about Hashing. [5+5+6]

4. 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]

5. Write and explain the algorithm for evaluating a game tree using alpha-beta prun-
ing. [16]

6. (a) State the conditions under which insertion of a vertex in a Red-Black tree will
result in a sequence of recolouring steps that terminate with the root changing
colour.
(b) Will the root of a Red-Black tree always be black after performing a deletion
operation? Justify with an example? [8+8]

7. (a) Write a program to count the no of blank spaces, characters, words in a given
text file.
(b) write a program to copy the contents of one file to other. [8+8]

8. (a) What is Spanning tree? Explain the Prim’s algorithm with an example.
(b) Find the shortest path between all pairs of nodes in the following graph as
shown in figure.8b by using TSP. [8+8]

7
Code No: R05211201 R05 Set No. 3

Figure 8b

?????