Sr No.

Questions
Sequence of Characters: EAS*Y*QUE***ST***IO*N***
Consider the stack data structure, supporting two operations push and pop, as discussed in class.
1 Suppose that for the above sequence, each letter (such as E) corresponds to a push of that letter onto
the stack and each asterisk (*) corresponds a pop operation on the stack. Show the sequence of
values returned by the pop operations.
An array of 10 elements, a[0:9], having values [4, 2, 6, 7, 1, 0, 9, 8, 5, 3] is to be sorted using
2 insertion sort, as enacted in class. Draw a figure to show the progress of the sorting, for the above
sequence of input values.
Determine and explain the functionality of the following code fragment:
int function1 (int a[], int n, int x)
{
int i;
3 for (i = 0; i < n && a[i] != x; i++);
if (i == n) return -1;
else return i;
}

4 Define Stack and Queue. Give its real-life application.

5 Design a pseudo code to illustrate the array implementation for the multiplication of 2D matrix.
6 Define Data Structure and It's Types.
Determine and explain the functionality of the following code fragment:
int function2 (int a[], int n, int x)
{
int i, j, k;
i = 0; j = n -1;
while (i <= j) {
7 k = (i + j)/2;
if (x == a[k]), return k;
if (x > a[k]), i = k + 1;
else j = k - 1;
}
return -1;
}
Write a function for removing the minimum element from the given array. Show the array status
after performing one removeMin() operation.
8
Array index (0 to 12) and Key
5 10 6 13 17 8 11 15 16 21 18 9 23
9 Compare abstract data types and concrete data types.
10 What are the various types of set? What all operations can be carried out on the sets?
11 What are the properties of an associative arrays?
12 Compare Linear and Non-linear Data Structure.
13 What are the various operations one can carry on data structure?
14 Explain dynamic arrays with example.
15
Suppose that you are part of a team developing a financial application. One of the functions used in
the application is a calculator, for infix arithmetic expressions. For example, given the expression 5 ∗
16
(((9 + 8) ∗ (4 ∗ 6)) + 7), the function outputs the result 2075. You are supposed to design the data
structures and implementation for this calculator function. Use Postfix to design the application.
17 What are hash tables and where do we use them? Explain.
Declare and define an array to store the temperature measured at each hour of each day for a week.
18
How to access the record of temperature at noon on Tuesday?
19 Draw a picture of push() and pop () function showing some example and illustrate its use.
20 List 2 real-life applications in which it might be appropriate to use a push and pop.
21 Write a small client program to test the implementation for enqeue and deqeue operation.
22 Write the code for the deque interface. That is, show the struct and function definitions.
Draw a picture to illustrate the Stack and Queue pointers for performing insertion and deletion
23
operations.
24 What is the postfix expression for b * b - 4 * a * c?

Which is the correct algorithmic sequence for the conversion of an expression from Infix to Prefix?
A. Change of every '(' (opening bracket) by ')' (closing bracket) and vice-versa.
25 B. Reversal of an infix expression.
C. Conversion of the modified expression into postfix form.
D. Reversal of postfix expression.

26 Write the pseudo-code for your function which reads the expression 5 ∗ (((9 + 8) ∗ (4 ∗ 6)) + 7)
27 Evaluate the postfix expression 6 3 2 4 + - * using stack. Show stack status at each step.
28 List various applications of stack. Explain any-one with an example.
29 Write a function for enqueue operation in circular queue.
30 Write a function to display the contents of the stack data structure.
31 Compare Stack and Queue.
32 Explain Stack as an abstract data type (ADT).
Convert the following infix expression to postfix expression using a stack. Show stack status after
every push/pop operation.
33
A+ (B*C-(D/E^F)*G)*H

Show how to implement a queue using two stacks.

(Note that when you use the stack for implementing a queue, you are only allowed to use the stack
commands, namely makenew(S), top(S), pop(S), push(x; S) and isempty(S). Please keep in mind to
34
explain how you would implement all the queue commands like makenew(Q), enqueue(x;Q),
dequeue(Q) and isempty(Q).)

Write a program for stack implementation using an array. (Perform PUSH, POP, PEEK and
35
DISPLAY function)
Write a program to implement Queue using an array. (Perform INSERT, DELETE and DISPLAY
36
function)
Write a program to implement Circular Queue using an array. (Perform INSERT, DELETE and
37
DISPLAY function)
38 Write a program for converting an infix expression to its equivalent postfix expression using stack.
39 Write a Program to implement a stack using linked list.
40 Define a linked list. How is it different from sequential allocation in arrays?
41 What is a node in a linked list? Describe its components with a neat sketch.
42 State two real-world applications where linked lists are more efficient than arrays.
43 Explain the role of the 'head pointer' and 'NULL pointer' in linked lists.
44 Differentiate between singly linked list and circular singly linked list.
45 List the advantages and disadvantages of a doubly linked list.
46 Describe the use of a circular linked list in memory management.
47 Explain how linked lists can be used to represent polynomials.
48 Why is dynamic memory allocation preferred in linked list representation?
49 Write a function for insertion at the beginning of a linked list.
50 Write a function for insertion at the end of a linked list.
51 Write a function to delete first node of a single linked list.
52 Write a function to insert an element between two nodes of a doubly linked list.
53 Write a fuction to delete an element at the begining from a doubly linked list.
54 Draw a memory representation of a queue implemented using a linked list.
55 Write a function to push the element on to the stack using linked list.
56 Differentiate between static memory allocation in arrays and dynamic allocation in linked lists.
57 What are the limitations of singly linked list? How does doubly linked list overcome them?
58 Explain the concept of 'free list' in memory management using linked lists.
59 What are the special cases that must be handled during deletion in a circular linked list?
60 Implement a queue using a linked list. Show insertion and deletion operations.
61 Compare singly linked list and doubly linked list in terms of efficiency and applications.
62 Write short note on polynomial representation using linked lists with a suitable example.
Show how to implement a queue using two stacks.
(Note that when you use the stack for implementing a queue, you are only allowed to use the stack
63 commands, namely makenew(S), top(S), pop(S), push(x; S) and isempty(S). Please keep in mind to
explain how you would implement all the queue commands like makenew(Q), enqueue(x;Q),
dequeue(Q) and isempty(Q).)
Develop a program for Doubly Linked List with operations like insertion at beginning and middle,
64
deletion from any position, and list traversal in both directions.
Write a program to implement a priority queue using a singly linked list, where insertion maintains
65
the priority order.
Describe the structure of a linked list, including the definition of a node, pointer usage, and how
66
memory is dynamically allocated for each node.
67 Implement a function to reverse a singly linked list and display the list before and after reversal.
Write a program to implement a Singly Linked List that allows insertion at the end, deletion from the
68
beginning, deletion from a specific position, and display it.
Write a program to remove all duplicate elements from a sorted singly linked list, ensuring only
69
unique elements remain.
Create a program to add two polynomials represented by linked lists and display the final
70
polynomial in standard form.
71 Define a tree. Explain the significance of hierarchical representation.
72 Distinguish between strictly binary tree and complete binary tree.
73 What are the properties of a binary search tree?
74 Explain the importance of balance factor in AVL trees.
75 State the applications of binary trees in computer science.
76 What are the differences between B-Trees and B+ Trees?
77 Draw a binary tree for the sequence of values: 40, 20, 50, 10, 30.
Construct a binary search tree (BST) using the following elements: 25, 15, 50, 10, 22, 35, 70, 4, 12,
78
18, 24. Show in-order, pre-order, and post-order traversals.
79 Explain the process of deletion in a binary search tree with suitable examples.
80 Discuss different applications of trees in computer science (like parsing, indexing, searching).
Show inorder, preorder, and postorder traversals for the given binary tree.

81

82 Construct a binary search tree for the values: 15, 10, 20, 8, 12.
83 Illustrate the insertion of nodes in an AVL tree with diagram.
84 Draw a threaded binary tree with 5 nodes.
85 Represent a B-Tree of order 3 for the values: 5, 10, 15, 20, 25.
86 Construct a B+ Tree for the sequence: 12, 18, 6, 24, 30.
87 Draw a binary tree of height 4 and explain its properties.
88 Illustrate deletion of a leaf node in a binary search tree.
89 Show how database indexing is implemented using B+ Trees.
90 Differentiate between internal nodes and external nodes of a tree.
91 Explain the importance of traversal techniques in trees.
92 Compare preorder traversal and postorder traversal with examples.
93 Explain the significance of height-balanced trees.
94 Why are AVL trees considered efficient for searching?
95 Discuss the importance of threaded binary trees in saving storage space.
96 Compare binary search trees with B-Trees in terms of efficiency.
97 What are the challenges faced during deletion operation in AVL trees?
98 Why are B+ Trees widely used in databases instead of B-Trees?
Given a tree, find its in-pre and post order traversal.

99

Draw a BST using preorder and postorder given below. Preorder: 5,2,1,4,3,9,7,8,11,10,13
100
Postorder: 1,3,4,2,8,7,10,13,11,9,5
101 Write a program for AVL tree insertion.
102 Write a program to search for a particular node in a BST.
Construct an AVL tree for the following elements. Show the necessary rotations along with
103 explanation.
M,N,O,P,Q,R,S,T,U,V,W
104 Construct an AVL tree for the keys: 30, 40, 20, 10, 25, 50. Show all the necessary rotations.
Insert the following keys to a 5-way B-tree:
105
2, 8, 10 ,1 ,24 , 45, 59 ,9 ,21 ,33 ,25 ,56
Explain the properties and applications of B-trees. Construct a B-tree of order 3 for the following
106
keys: 10, 20, 5, 6, 12, 30, 7, 17.
107 Write a program to implement binary search tree (BST). All cases for delete should be included.
108 Define graph data structure.
109 How many edges a Complete undirected graph has?
110 Which graph representation allows the most efficient determination of the existence of a particular edge in a graph?
111 How would you describe a cycle in a graph?
112 Draw adjacency list representation of a graph.
113 Draw adjacency matrix representation of a graph.
114 Can we assume a topological sort is possible for all directed graphs? Justify
115 How does an adjacency list save memory compared to an adjacency matrix?
116 Write an algorithm for Depth First Search.
117 Write an algorithm for BFS.
118 Write an algorithm for DFS.

119
What are the various applications of Graph data structure? How graphs are useful in real life?
120 Can you explain why topological sort works only for directed acyclic graphs (DAGs)?
121 Why queue data structure is used in BFS and Stack data structures is used in DFS?
Apply DFS for the following graph: Show the stepwise respective stack contents for the same.

122

Apply DFS for the following graph: Show the stepwise respective queue contents for the same.

123

124 Explain Topological sort in details with an example.

Write step by step BFS order for the following graph.

125

Write step by step DFS order for the following graph.

126

127 Write a program for BFS.

128 How do graph algorithms differ when applied to social networks versus transportation systems?
129 What is hashing?
130 What is binomial heap?
131 Draw a binomial tree of order 3.
132 How is a binomial tree different from a binary tree?
133 Describe the difference between a binomial heap and a binary heap.
134 Draw any binomial tree of order B3.
Delete element 3 from following max heap and show the resultant heap.

135

136 What is collision? What are different collision techniques?

137 Write properties of Binomial tree.
138 What is Red-Black Trees? Explain its properties?
139 Explain Union of two Binomial Heap in details with an example.
140
How does hashing improve the search time in large datasets?
141 Analyze the performance differences between chaining and open addressing in hash tables.
142 Explain separate chaining with an example.
Construct a Binomial heap for the following elements. Show all the steps of construction.
143
12,19,52,10,29,70,1,107,33,45
Consider inserting Keys: 50,38,77,59,24,77 into a hash table of size M=11 using double hashing. Consider the auxiliary hash function
144
Hash function: h(k,i)=[h1(k)+ih2(k)] mod m
145 Explain Insertion operation on Red-Black Trees, with an example. Explain all the cases.
146 Explain deletion operation on Red-Black Trees, with an example. Explain all the cases.
147 Consider a hash table of size 10. Using linear probing, insert keys 72,27,36,24,63,81,92 and 101 into a table. How many collisions oc
Construct a red black tree for following elements.
148
15, 16, 24, 14, 10,20,55,7,19,60
Construct a Binomial heap for the following elements. Show all the steps of construction. Delete the minimum element of the heap
149
12,19,29, 6,9,13, 70,1,107,33,45, 50
150

151

152
153
154
155
156
157
158
159
160
161
162
163
164
Consider the auxiliary hash functions are h1(k)=k mod 11 and h2(k)=k mod 9.

nto a table. How many collisions occurred (if any).

the minimum element of the heap and show the resultant heap.