For the given set of values. 11, 33, 20, 88, 79, 98, 44, 68, 66, 22 Create a hash table with size 10 and resolve collision using chaining with replacement. Use the modulus Hash function. (key % size.)

Insert the keys 9, 19, 29, 39, 49, 59, 71 into the Hash Table of size 10. Resolve all collisions using Quadratic probing where hash-function is h(k). h(k) = k mod 10

Write difference between separate chaining and open addressing.

Solve the following example using extendible hashing. Elements: 28,4,19,1,22,16,12,0,5,7 & Bucket Size: 3

Construct hash table of size 10 using linear probing without replacement strategy for collision resolution. The hash function is h(x)=x%10. Consider slot per bucket is 1. 31, 3, 4, 21, 61, 6, 71, 8, 9, 25.

What is Skip List? What are advantages and disadvantages of skiplist?

Write an algorithm for recursive and non-recursive postorder traversal of binary tree and give suitable example.

Construct Huffman’s Tree and the prefix free code for all characters: Value A, B, C, D, E, F Frequency 5, 25, 7, 15, 4, 12

From the given traversals construct the binary tree. Pre-order: G, B, Q, A, C, K, F, P, D, E, R, H In-order: Q, B, K, C, F, A, G, P, E, D, H, R

Write an algorithm to delete node from BST with example.

Explain the storage representation of a binary tree with the following example.

Explain Binary Search Tree. Construct Binary Search Tree(BST) for the following : J, R, D, G, T, E, M, H, P, A, F, Q.

Construct a hash table to insert following data in hash table. Use quadratic probing for collision resolution. Hash function key% 10.Consider one slot per bucket. Elements: 13, 48, 25, 33, 55, 72, 147, 43 Calculate the average number of comparisons.

Explain the folding method of hashing with examples.

Explain the terms Key density and load density Calculate the load density for the hash table with 20 slots, that stores 1000 elements

Consider the hash table with 9 buckets. The hash function is h(K)=k mod table size. The collision is resolved by chaining using replacement. The following keys are inserted in the order: 5, 37, 19, 24, 29, 23, 48, and 17. Calculate the maximum chain length.

Explain the concept of skip list with example. State its application.

Compare static hashing and extendible hashing.

Generate Huffman tree and find the codes for following alphabets having specified frequency: A-4, B-5, C-2, D-7, E-3, F-1

Write an algorithm for non recursive post order traversal of binary tree.

Explain how to convert general tree to binary tree with example.

Construct a binary tree from its given preorder traversal PQSXYTRUV and postorder traversal XYSTQUVRP and apply inorder traversal to it.

Write an algorithm to delete a node from binary search tree.

Explain threaded binary tree with example and state its advantages.

For the given set of values: 76,40,48,5,55 Construct a hash table with size 7 and resolve collision using quadratic probing.

Explain about skip list in Hashing. Give applications of skip list.

What is hash function? What are characteristics of good hash function?

Prepare hash table by Inserting following Elements into hash table using extendible hashing: 16, 4, 6, 22, 24, 10, 31, 7, 9, 20, 26. Bucket Size: 3 (Assume)

Explain applications of Hash Table.

What is hashing? Explain different methods of hash function calculation.

Explain how to convert general tree to binary tree with example.

Write non recursive pseudocode for inorder traversal of Binary tree.

Describe binary search tree deletion with example.

Write pseudocode for BFS traversal of binary search tree.

Construct Huffman’s tree and determine code for following characters whose frequencies are as given : Character A B C D E Frequency 20 10 10 30 30

What is the necessity of Threaded binary three? Explain advantages and disadvantages of TBT.

We have a hash table of size 10 to store integer keys, with hash function h(x) = x mod 10. Construct a hash table step by step using linear probing without replacement strategy and insert elements in the order 31,3,4,21,61,6,71,8,9,25. Calculate average number of comparisons required to search given data from hash table using linear probing without replacement.

Explain the concept of quadratic probing using example. What are the advantages and disadvantages of quadratic probing over linear probing?

What is hashing? Explain the properties of good hash function with examples.

Insert the following data in the hash table of size 10 using linear probing with chaining by applying with replacement : 11, 33, 20, 88, 79, 98, 68, 44, 66, 24. Calculate average number of comparisons required to search given data from hash table.

Add following keys in hash table by applying extendible hashing mechanism. Assume capacity of each directory to store buckets is 3. Keys are 10, 20, 15, 12, 25, 30, 7, 11, 08.

Write short note on skip list.

Write an algorithm to delete a node from Threaded binary Search Tree.

The following numbers are inserted into an empty binary search tree in the given order : G, C, B, A , D, E, F, I, H. Construct tree step by step. Represent the constructed tree using static memory allocation.

Let characters a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 respectively. Find an optimal Huffman code and draw Huffman tree.

Construct threaded binary tree step by step if the preorder traversal is G, B, D, C, A, K, Q, P, R & in-order traversal is B, A, C, D, G, K, P, Q, R. Delete G and redraw a tree.

Write a non-recursive function to display data in Binary Search Tree in descending order.

Explain how to convert general tree to binary tree with example.

Represent the following graphs using adjacency matrix.

Explain Floyd Warshall algorithm to calculate shortest paths.

Construct the minimal spanning tree for the graph shown below using Kruskal's algorithm.

Find the MST for the following graph using Prims algorithm.

Explain Depth first traversal of a graph with example.

Find Single source shortest path using Dijkstra's Algorithm. Select source as vertex 1.

What is K-D tree? Show creation of 2-D tree with example.

Consider following : Input: keys[] = {10, 12, 20}, freq[] = {34, 8, 50} Draw all possible BSTs. Find minimum cost of the BST.

Do the following operations on the tree : i) Zig Zag Rotation ii) Zag Zig Rotation

Construct a AVL tree for the following data: 5, 12, 10, 9, 8, 14, 23, 29, 28, 17

Define Red- Black tree, state its properties and give suitable example.

i) Illustrate AA tree. ii) Define splay tree. List the operations and rotations that can be performed on splay tree.

Explain the various cases of node deletion in B- tree.

Build B+ tree of order 4 for the following data: 1, 3, 5, 7, 9, 2, 4, 6, 8, 10.

Explain indexing and types of indexing techniques.

Construct a B tree of order 3 for following data: 10, 34, 78, 45, 123, 341, 234, 167, 159, 52.83

Answer the following questions w.r.t. trie tree: i) Which of the following is not true? a) Trie requires less storage space than hashing b) Trie allows listing of all the words with same prefix c) Tries are collision free d) Trie is also known as prefix tree ii) What can be the maximum depth of the trie with n strings and m as the maximum sting the length? a) log2n b) log2m c) n d) m iii) Which of the following is true about the trie? a) root is letter a b) path from root to the leaf yields the string c) children of nodes are randomly ordered d) each node stores the associated keys iv) Auto complete and spell checkers can be implemented efficiently using the trie. a) True b) False v) What traversal over trie gives the lexicographical sorting of the set of the strings? a) postorder b) preorders c) inorder d) level order vi) What is/are the key feature(s) of trie tree? a) Fast String Operations b) Efficient Prefix Searches c) Memory Compactness d) All of the above

What are multiway search trees? Explain its need and applications.

Differentiate between sequential & linked organization.

What is indexed sequential access file organization? Write two advantages & disadvantages of it.

What is Direct access file? State its advantages.

Differentiate between dense & sparse indices.

Explain Sequential file organization and discuss their advantages and disadvantages.

Describe inverted files.

Elaborate following terminologies : i) Graph ii) Adjacency List iii) Adjacency Matrix

Differentiate between tree and graph.

Write pseudo code for Floyd-Warshall algorithm.

Find the shortest path using Dijkstra’s algorithm. Write all the sequence of steps used in algorithms.

Write Prim’s algorithm to find minimum spanning tree.

Write the applications of : i) Graph ii) BFS iii) DFS

Explain following terms w.r.t. symbol table : i) Insert & lookup operations ii) Advantages iii) Disadvantages

Construct an AVL tree having the following elements : H, I, J, B, A, E, C, F, D, G

Insert 15, 10, 17, 7 in splay tree.

What is the need of AA tree? List the five invariants that AA tree must satisfy.

Who developed K-D tree? What is the purpose of K-O tree? Insert step by step (7, 8), (12, 3), (14, 1), (4, 12), (9, 1), (2, 7) and (10, 19) into K-D tree.

Show the balanced AVL tree after deletion of mentioned node : i) Delete 30 ii) Delete 55 iii) Delete 60

What is indexing? What are the advantages of indexing? Discuss clustering index with example.

Construct a B-Tree of order 3 for following data : 50, 30, 21, 90, 10, 13, 20, 70, 25, 92, 80.

Why B+ tree? List its properties and advantages.

Explain with example trie tree. Give properties and advantages of trie tree.

Build B+ tree of order 3 for the following : F, S, Q, K, C, L, H, T, V, W, M, R

What is difference between B and B+ tree?

Explain Index Sequential file and discuss their advantages and disadvantages.

List & explain two possible ways of representing records.

Differentiate between indexed sequential file and direct access file.

Explain Sequential file organization and discuss their advantages and disadvantages.

What is coral rings? Describe inverted files w.r.t linked organization.

Explain Direct Access file.

Using Kruskal’s algorithm, construct minimum spanning tree for the following graph.

Write an algorithm for traversing Graphs BFS and DFS.

Write in brief about adjacency multilist. Build adjacency multilist for the following graph.

Find the minimum spanning tree using Prim’s method for the graph given below with A as the root.

What does Floyd Warshall Algorithm compute? Which approach is used by it for computation? Write pseudo C/C++ code for the same.

Define the following terms: i) Complete Graph ii) Connected Graph iii) Subgraph

Construct the AVL tree by inserting numbers from 11 to 18.

Explain following terms with respect to height balance tree: LL, LR, RR.

Elaborate the concept of Splay Tree and K Dimension Tree.

What is OBST? How dynamic programming is used in OBST to reduce time complexity? What are the advantages of OBST?

What is symbol table? Describe static tree table and dynamic tree table with example.

Elaborate the concept of AA tree and Red Black tree.

What is B+ tree? Construct B+ tree of order 3 for the following data: F, S, Q. K, C, L, H, T, V, W, M, R

Elaborate the concept of Trie Tree, Construct a Trie Tree for the following data: Big, Bigger, Bill, Good, Gosh, Goodbye.

Explain primary and secondary indexing techniques.

Construct a B tree of order 4 by inserting the following numbers 10, 34, 78, 45, 123, 341, 234, 167, 159, 52, 83

Write a brief remark about indexing techniques and multiway trees.

Write steps for insertion of a node in B+ Tree. Give example.

Explain Sequential file and random flie organization.

What is a File? Write with an example different file opening modes in C++.

Describe inverted files.

What is cellular partitions? What are its advantages?

Clarify about the following: i) Coral Ring; ii) Benefits and Drawbacks of Linked Organization

Explain any two types of indices.

Write an algorithm for depth first traversal of a graph.

Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm staring from vertex 6.

What is topological sorting? Find topological sorting of given graph.

Write an algorithm for breadth first traversal of a graph.

Using Prim’s Algorithm, find the cost of minimum spanning tree (MST) of the given graph starting from vertex ‘a’ -

Define the following terms : i) Complete Graph ii) Connected Graph iii) Subgraph

Construct an AVL Tree by inserting numbers from 1 to 8.

Define Red Black tree. List its properties. Give example of it.

Write functions for RR and RL rotation with respect to AVL tree.

Construct an AVL Tree for following data : 50, 25, 10, 5, 7, 3, 30, 20, 8, 15

Explain with example K dimensional tree.

Explain static and dynamic tree tables with suitable example.

Construct a B-Tree of order 3 by inserting numbers from 1 to 10.

Explain following primary index, Secondary index, Sparse index and Dense index with example.

Construct a B Tree of order 5 with the following data : D H Z K B P Q E A S W T C L N Y M

What is trie tree? Explain insert and search operation on it.

Explain multilist files & coral rings.

What is Sequential and index sequential file organization? State its advantages and disadvantages.

Explain inverted file & cellular partitions.

Explain direct access file organization. State its advantages and disadvantages.

Write Floyd Warshall Algorithm.

Construct stepwise minimum spanning tree (MST) for the given graph using Prim’s Algorithm. Also calculate sum of all weights. Start from vertex 1.

Apply Dijkstra’s Algorithm for the graph given below, and find the shortest path from node A to node C.

Define indegree & outdegree of a directed graph. Write degree for G1 & G2. Write indegree & outdegree of each vertex for G3 graph.

Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm.

Find the number of different topological orderings possible for the given graph.

Construct AVL tree for insertion of following data: 9, 15, 20, 8, 7, 13, 10.

Draw splay tree after i) Zig rotation ii) Zag rotation for follwoing tree- iii) Zig Zig Rotation iv) Zag Zag Rotations for following tree-

Create 2D tree for following data: (3, 6), (17, 15), (13, 15), (6, 12), (9, 1) (2,7), (10, 19). Also plot all the points in XY plane.

Construct AVL tree for insertion of following data: 63, 9, 19, 27, 18, 108, 99, 81.

Define Red Black tree. List its properties. Give example of it.

Write the functions for split & skew operations in AA tree.

Create a B- Tree of order 5 from the following list of data items: 30, 20, 35, 95, 15, 60, 55, 25, 5, 65, 70, 10, 40, 50, 80, 45

Explain following indexing techniques: i) Primary ii) Secondary iii) Sparse iv) Dense

Create a B+Tree of order 3 from the following list of data items: 1, 3, 5, 7, 9, 2, 4, 6, 8, 10

Define trie tree. Compare trie tree with hash table. Draw trie tree for following data: bear, sell, bell, bid, stock, bull, buy, stop.

Explain sequential & direct access file organization. Also list two advantages & disadvantages of same.

Explain Indexed sequential access file organization. Also list two advantages & disadvantages of same. Compare sequential & indexed sequential file organization.

What is linked organization? Explain inverted file and coral rings with respect to linked organization.

Explain multilist files & cellular partitions.