Uttarakhand Technical University B.Tech Computer Science and Engineering UTU exam paper of Data string using c++

UTU B.Tech CCSE Previous Year exam paper of Data string using c++       

   UTTARAKHAND TECHNICAL UNIVERSITY

SEM-VI

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.