DATA STR. USING C++

DATA STR. USING C++
SEM-VI, 2012
B.TECH EXAMINATION
UTTARAKHAND TECHNICAL UNIVERSITY
(UTU)

Time: 3 hours

Total Marks: 100

Attempt any four of the following:

1. Explain the meaning of following expression f(n) is n⁰⁽¹⁾
2. Prove the following statement
   2^n+a is 0(2ⁿ)
3. Find the computational complexity for the following loop
   for (cnt 4 = 0, i=1; i<=n, i*=2)
   for (j=1; j<=i, j++)
   cnt 4++;
4. Write a member function to check whether two singly lists have the same contents.
5. Write a member function to reverse a singly linked list using only one pass through the list.
6. Write a function to insert a node in the middle of a doubly linked list.

Attempt any two of the following:

1. Define a queue in terms of a stack. Write a program using stack that determines whether an
2. Suggest an implementation of a stack to hold elements of two types such as structures and float numbers.
3. Write a functions to add and delete elements from either end of the double-ended queue and also to return an element from either end.

Attempt any two of the following:

1. Show that the hash function h(k) = k% 17 does not satisfy the one-way property, weak collision resistance, or strong collision resistance.
2. Write search and insert functions for a hash table using random probing and the mid square hash function.
3. Outline an algorithm to delete key from a table when the linear hashing method is used for inserting keys.

Attempt any two of the following:

1. Write a function that checks whether a binary tree is perfectly balanced.
2. Write a function to construct a winner tree for k records. Assume that K is a power of 2. Each node at which a tournament is played should store only a pointer to the winner.
3. Heap sort is unstable. Give an example of an input list in which the order of records with equal keys is not preserved.

Attempt any two of the following:

1. Show that the sum of the vertices of an undirected graph is twice the number of edges.
2. Let G be an undirected graph with at least one vertex of odd degree. Show that G contains no Eulerian walk.
3. Let G be a connected graph and let T be any of its depth-first spanning trees. Show that G has no cross edges relative to T.

____________________________