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.

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.

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.

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.