Unit 4&5 QAB UPDATED

QUESTION BANK
Data Structure & Analysis of Algorithms

KCA205
Unit 4
1. Explain the difference between complete binary tree , Strict Binary tree and extended
binary tree.
2. Define self-balancing binary tree.
3. What are threaded binary trees?
4. What are skewed binary trees?
5. Discuss the properties of B Tree.
6. Discuss the properties of Binary Search Tree.
7. Explain garbage collection with example.
8. Write down the algorithm for pre-order, post-order and inorder tree traversal.
9. Write an algorithm or function to implement BST for searching an element. Create a
binary search tree using the following using the following data elements:
55,37,66,12,44,88,22,10,99,94,67,11
10.Construct a B Tree of order 5 by inserting following keys in the order shown into an
Empty B Tree.
3,24,17,13,81,51,111,173,113,16,213,122,20,6,14,16,18,44,55 and 29
11.Suppose the numbers 7,5,1,8,3,6,0,9,4,2 are inserted in that order into an initially empty
binary search tree. What is the postorder traversal sequence of the resultant tree?
12.The Inorder and preorder traversal of the binary tree is as follows:
Preorder: 1 2 3 4 5 6 7
Inorder: 2 4 3 1 6 7 5
Draw the binary tree from the above given order.
13.Given the symbols A, B, C, D, E, F, G and H with the probabilities 1 / 30, 1 / 30, 1 / 30,
2 / 30, 3 / 30, 5 / 30, 5 / 30, and 12 / 30 respectively. Find the Huffman code for each
letter with proper tree.
14.Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32
respectively. Write the Huffman code for the letter a, b, c, d, e, f.
15.Create an AVL Tree with the following values: 38,14,56,8,23,45,82

Insert the following element in empty AVL tree:
16.{45,55,65,75,80,90,100,110,120,130,40,35,25,20,15,10,5}
17.The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the
same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from
the root to any leaf. What is the height of the binary tree?
18.Define a B tree. Construct a B tree of order 3 by inserting following keys in the order
shown into an empty B tree. ZQABPYXTGDJ.
Unit 5
1. Discuss Stassen’s algorithm for matrix multiplication.
2. Explain the disadvantage of Bellman Ford Algorithm with example.
3. Explain the concept of Divide & Conquer.
4. Perform merge sort on the following data items stored in single dimensional array:
{10, 5, 9, 8, 7,3, 4, 0, 2, 1}. Also discuss its time complexity.
5. Discuss the concept of Greedy programming.
6. Use Quicksort algorithm to sort the following sequence:

5,3,8,1,4,6,2,7.
7. Perform Quick sort on the following data items stored in single dimensional array:
{6, 9, 5, 8, 7, 4,3, 1, 2, 0}. Also discuss its time complexity.
8. Explain Minimum Spanning Tree with example.
9. Discuss the function or algorithm to implement Merge Sort. What is time and Space
complexity of the algorithm?
10. A list of n strings, each of length n, is sorted into lexicographic order using merge sort
algorithm. What is the worst-case running time of this computation? Explain
11. How you will find out the product of following matrix using strassen’s matrix
multiplication algorithm?
12. Explain the basic architecture of Dijkstra’s algorithm along with an example?
13. Write the algorithm of Bellman Ford to find the shortest path. Explain with example.
14. Discuss Longest Common Subsequence(LCS) problem solution by using Dynamic
programming.
15. What will be the longest common subsequence's length of P and Q?
Consider the both sequences given below:

P = < B, C, D, C, A, B, C >, and
Q = < C, A, D, B, C, B >
16. Explain Minimum Spanning Tree? Draw MST of following graph by applying
Kruskal’s algorithm & prim’s Algorithm. What is number of distinct minimum
spanning trees for the weighted graph below? Explain.
17. For the given graph(weighted, directed) apply Floyd-Warshall algorithm for
constructing shortest path.
18. Describe the Dijkstra algorithm to find the shortest path.
19. Describe the Prim’s algorithm to find the cost of Minimum Spanning Tree using
Prim’s Algorithm.
20. What is spanning tree. Find the minimum cost of the following tree and draw its
spanning tree.

Unit 4&5 QAB UPDATED

Uploaded by

Copyright:

Available Formats

Unit 4&5 QAB UPDATED

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 4&5 QAB UPDATED

Uploaded by

Copyright:

Available Formats

QUESTION BANK

Data Structure & Analysis of Algorithms

15.Create an AVL Tree with the following values: 38,14,56,8,23,45,82

6. Use Quicksort algorithm to sort the following sequence:

Consider the both sequences given below:

18. Describe the Dijkstra algorithm to find the shortest path.

You might also like