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 n0(1)
  2. Prove the following statement
    2n+a is 0(2n)
  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.
at
Labels: ,