Implementation of a priority queue by using heap

Question

Question 1:

a) What do you mean by the term priority queue? How do you implement a priority queue by using Heap?
b) List out a few application of priority queue?

Question 2:

a) Sort the given lists in ascending order by using heap sort D, A, T, A, S, T, R, U, C, T, U, R, E
b) What are the various applications of priority queue?

Question 3:

a) Define the term max tree, max heap, min heap with appropriate examples?
b) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3 and 9, one at a time into an initially empty min heap?

Question 4: What is an AVL Tree? Write down the algorithm to search for an element of an AVL Search Tree? Also write its time complexity?

Question 5:

a) Define the term Binary Search Tree? Write the procedures to perform insertion, deletion and searching in a binary search tree?
b) What are the various applications of binary search trees?

Question 6: Start with empty binary search tree:

a) Insert the keys 15, 5, 20, 14, 30, 22, 2, 4, 5, 7, 9, 18 in this order. Draw the tree following each insert by using binary search insert method.
b) Delete the keys 2, 4, 5 in the order and draw the tree following each deletion.

Question 7: Write an algorithm to search an element from the B-tree and analyze its complexity by frequency count method.

Question 8:

a) Draw the order-7 B-tree resulting from inserting the given keys into an initially empty tree

T: 4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12

b) What are search trees? Describe the different kinds of search trees and its applications.

Question 9: Describe the working of DFS and BFS algorithms with an illustration.

Question 10:

a) Write Brute force pattern matching algorithm and as well analyze its complexity.
b) What are the applications of tries?

Question 11:

a) Explain about the suffix trie with an example.

b) Follow the brute force algorithm and count the total number of comparisons done for the following:

Text: babcbabbbcabcabcbbabcabcaacabc
Pattern: abcabca.

Question 12:

a) Draw the flowchart for Brute - force pattern matching.
b) Consider a Text T = raman likes mango to match against the pattern P = mango by using the Knuth - Morries - Pratt pattern algorithm.