ANNAMACHARYA INSTITUTE OF TECHNOLOGY AND SCIENCES
BATASINGARAM, PIGLIPUR(V), HAYATNAGR, R R DIST
II [Link] I Semester – R22 Regulations
Data Structures Question Bank
Short Answer Questions:
1) What is the difference between stack and queue?
2) Define top pointer in a stack?
3) What is collision in hashing?
4) Define rehashing.
5) Why does AVL tree require balancing?
6) Describe splaying?
7) What is adjacency matrix representation?
8) Define degree of a vertex.
9) Define brute force pattern matching.
10) Explain briefly suffix trie?
11) Give one example of a data structure.
12) Which data structure helps in reversing a string.
13) What is primary clustering.
14) Which dictionary operation removes an element.
15) What property must be satisfied in a BST.
16) What is the height of an AVL Tree.
17) Which representation uses a 2D array.
18) What is the time complexity of merge sort.
19) What is Boyer–Moore algorithm used for.
20) What is a suffix trie.
Unit 1
1. Discuss in brief about single linked list.
2. Write a C program to convert infix to postfix expression.
3. Write an algorithm of Insert and Delete operation in Singly Linked List.
4. Convert the following infix expression into postfix expression A + B – C * D * E $ F $ G
5. Write a program to implement stack using linked list.
6. Explain the operations of Queue with an example.
7. Define a single linked list. Write the structure of the linked list with a neat sketch.
8. Explain the operations of queue.
9. Write a program to implement stack operations.
10. What are the applications of the queue? Explain.
11. Write an algorithm of Push and Pop operations on a stack.
12. Differentiate between stack and queue.
13. Write an algorithm for insertion of node at last position in Linear Linked List.
14. Evaluate the following postfix expression using stack. Show each step 5 3 + 6 2 / * 3 5 * +
15 Write a program to implement Queue using linked list.
16. Write an algorithm of Push and Pop operations on a stack.
17. What are the applications of the queue? Explain.
18 Write an algorithm to implement queue using stack.
19) [Link] and explain algorithms for Push and pop operations of stack using linked list
20) [Link] following numbers 10, 20, 50, 30, 90, 60 (Top) are present in a stack of size 10.
Perform the following operations in sequence. Pop (), push (30), push (40), pop (), push
(60), pop(), pop(), pop() what is the peek element at last? Draw and explain it.
21) Explain in detail the concept of Data Structures. Discuss their classification and
importance in algorithm design and program efficiency. Provide examples
22) Describe the concept of dynamic memory allocation and its role in linked list-based
implementations of stacks and queues.
Unit 2
1. What are different methods of collision resolution in hashing? Explain in brief.
2. Explain in detail about skip lists in data structures.
3. Explain about the various hash collision resolution techniques with an example.
4. Explain about: a) Rehashing b) Extendible hashing.
5. Explain the operations of the skip list representation.
6. Is linear probing and open addressing same? Justify your answer.
7. Discuss the hash functions.
8. List and explain the advantages of extendible hashing.
9. Insert the following list of elements into the hash table by using Quadratic probing (size of
Hash table is 13) 65, 34, 79, 114, 26, 85, 55, 89, 22, 98.
10. Write an algorithm of skip list operations insertion and deletion.
11. [Link] the following list of elements into the hash table by using Quadratic
probing (size of Hash table is 13) 65, 34, 79, 114, 26, 85, 55, 89, 22, 98.
12. [Link] the operations of the skip list representation.
13. Explain in detail the Dictionary ADT. Describe linear list representation of dictionaries
along with insertion, deletion, and searching operations.
14. Explain dictionary implementation using a hash table. Describe operations insertion,
deletion, and searching
Unit 3
1. Discuss in detail about red-black trees.
2. Explain briefly about binary search trees.
3. Write an algorithm to delete an element from the binary search tree.
4. Construct a Red-Black tree with the following elements 40, 16, 36, 54, 18, 7, 48, 5. Delete
element 18 and add element 66.
5. Write an algorithm of single rotation and double rotation of an AVL tree.
6. Explain the splaying operations of splay tree with an example.
7. Define Binary search tree.
8. Insert the following list of elements from the Red- Black tree. Delete the elements 18, 2 and
30 from the Red-Black tree 12, 30, 36, 18, 25, 9, 4, 2, 17, 14, 20, 47.
9. Explain the operations of Splay tree with an example.
10. Discuss in detail about AVL tree.
11. Write an algorithm to creation of binary treeusing in order, pre order and post order
traversal.
12. Construct AVL tree using following elements. 38,40,502,5,76,25,14,7.
13. Explain heap sort [Link] heap for following erlements then sort
it.13,102,405,136,15,105,390,432,28,444.
14)6. Insert the following list of elements to the AVL tree 12, 30, 36, 18, 25, 9, 4, 2, 17, 14,
20, 47. Delete the elements 18, 2 and 30 from the AVL tree
15) [Link] a Red-Black tree with the following elements 40, 16, 36, 54, 18, 7, 48, 5.
Delete element 18 and add element 66.
16) Describe the structure of a B-Tree. Explain insertion and deletion operations
17) Describe Red-Black Trees in detail. Explain their properties
Unit 4
1. How a graph is traversed using depth first search? Explain with example.
2. Explain the process of heap sort with example. 6. Explain in brief about tries with
example.
3. Compare and contrast different sorting methods.
4. Differentiate between BFS and DFS.
5. Explain about external sorting with an example.
6. Write an algorithm to implement a depth-first search with an example.
7. Perform heap sort algorithm for (10 15 6 2 25 18 16 2
8. Difference between tree and tries.
9. Sort the following list of elements by using Merge sort 30, 56, 78, 99, 12, 43, 10, 24, 85
10. How a graph is traversed using depth first search? Explain with example.
11. How a graph is traversed using breath first search? Explain with example.
11)8. How a graph is traversed using depth first search? Explain with example. [10M]
12) [Link] the following list of elements by using Merge sort 31, 57, 79, 98, 13, 45, 12, 25,
87
13) Discuss Depth First Search and Breadth First Search algorithms. [10M]
14) Explain the Quick Sort algorithm in detail.
Unit 5
1. Explain in brief about tries with example
2. Compare and contrast different sorting methods.
3. Write an algorithm of compressed Trie.
4. Explain about the Brute force algorithm with an example.
5. Difference between tree and tries.
6. Illustrate the Brute force algorithm.
7. Write an algorithm of Standard Trie.
8. Explain the features that distinguish between Boyer Moore algorithm from the conventional
algorithms.
9. Explain Knuth morris algorithm with example.
[Link] boyer moore algorithm with example.
11)10. Solve the Boyer-Moore algorithm for the following Example:
Text: ABCABCDABABCDABCDABDE
Pattern: ABCDABD [10M]
12) [Link] the Knuth Morris-Pratt algorithm for the following Example:
Text: HEREISASIMPLEEXAMPLE
Pattern: EXAMPLE
13) Describe the Boyer–Moore algorithm in detail.
14) Explain the importance of prefix-based and suffix-based structures in text processing.
Discuss how tries and suffix tries enable fast searching.
== ALL THE BEST ==