Galgotias College of Engineering & Technology

Department of Information Technology

Question Bank

Program Name: B. Tech (IT)

Semester: III

Session: 2023-24(ODD)

Subject Name: Data Structure

Subject Code: BCS 301

Faculty Name: Ms. Archana Das,

Dr. Meenakshi Yadav

 B.TECH
SEM III
DATA STRUTURES
QUESTION BANK
Unit 1
S.No. Questions Marks CO
1. What is primitive data types 2 CO1
2. Define the sparse matrix 2 CO1
3. What is Data Structures 2 CO1
4. What does abstract data type means? 2 CO1
5. Explain about the types of linked lists 4 CO1
6 Write an algorithm to merge two sorted arrays into a third 4 CO1
array. Do not sort the third array.
7 Write the programs for Linked List (Insertion and Deletion) 4 CO1
operations.
8 What data structure would you mostly likely see in a 4 CO1
non-recursive implementation of a recursive
algorithm?
9 List out the areas in which data structures are applied 4 CO1
extensively?
10. If you are using C language to implement the heterogeneous 4 CO1
linked list, what pointer type will you use?
11. What are the data structures used to perform recursion? 4 CO1
12. What are the disadvantages array implementations of linked 4 CO1
list?
13 Whether Linked List is linear or Non-linear data structure? 4 CO1
14. Explain what the effect will be if both continuous linked 4 CO1
versions of sequential search have only one item in the list
and when the list is empty.
15. A two-dimensional array TABLE [6] [8] is stored in row 4 CO1
major order with base address 351. What is the address of
TABLE [3] [4].
16. What is the difference between a grounded header link list 4 CO1
and a circular header link list?
17. What is the following code segment doing? 4 CO1
void fn( ){
char c;
cin.get(c);
if (c!= ‘\n’)
{
fn( );
cout.put(c);
}}
18. What values are automatically assigned to those array 4 CO1
elements which are not explicitly initialized?
19. Explain the method to calculate the address of an element in 4 CO1
an array. A 25*4 matrix array DATA is stored in memory in
‘row-major order’. If base address is 200 and 4 words per
memory cell. Calculate the address of DATA [12, 3].
20. How do you find the complexity of an algorithm? What is 4 CO1
the relation between the time and space complexities of an
algorithm? Justify your answer with an example.
21. Compare two functions n2 and 2 4 n for various values of n. 4 CO1
Determine when second becomes larger than first.
22. Explain an efficient way of storing a sparse matrix in 4 CO1
memory. Write a module to find the transpose of a sparse
matrix stored in this way.
23. Explain an efficient way of storing two symmetric matrices 4 CO1
of the same order in memory.
24. What is the difference between a Stack and an Array? 4 CO1
25. Two linked lists contain information of the same type in 4 CO1
ascending order. Write a module to merge them to a single
linked list that is sorted.
26. Define the term array. How are two-dimensional arrays 4 CO1
represented in memory?
27. Explain how address of an element is calculated in a 4 CO1
two-dimensional array. An array, A contains n unique
integers from the range x to y (x and y inclusive where
n=y-x). That is, there is one member that is not in A. Design
an O(n) time algorithm for finding that number.
28. Explain asymptotic notations. Define Big-Oh notation and 10 CO1
find the complexity of the following recursive function
T(n) = 4T(n/2)+nlogn
29. How do you find the complexity of an algorithm? What is 10 CO1
the relation between the time and space complexities of an
algorithm? Justify your answer with an example
30. What is recursion? Write a C code to solve tower of Hanoi 10 CO1
problem.
31. Rank the following typical bounds in increasing order of 10 CO1
growth rate:
O(log n), O(n4), O(1), O(n2 log n)
32. Suppose a three dimensional array A is declared using 10 CO1
A[1:10, -5:5, -10:5)
(i) Find the length of each dimension and the number of
elements in A
(ii) Explain Row major order and Column Major Order in
detail with explanation
formula expression
33. Consider a multi-dimensional Array A[90] [30] [40] with 10 CO1
base address starts at 1000. Calculate the address of A[10]
[20] [30] in row major order and column major order.
 Assume the first element is stored at A[2][2][2] and each
element take 2 byte.
34. Write advantages and disadvantages of linked list over 10 CO1
arrays. Write a 'C' function
creating new linear linked list by selecting alternate
elements of a linear linked list.
35. Consider a multi-dimensional Array A[90] [30] [40] with CO1
base address starts at 1000. Calculate the address of A[10]
[20] [30] in row major order and column major order.
Assume the first element is stored at A[2][2][2] and each
element take 2 byte.

Unit 2
S.No. Questions Marks CO
1. Evaluate the following prefix expression " ++ 26 + - 1324" 4 CO2
2. Convert the following infix expression to post fix notation 4 CO2
((a+2)*(b+4))-1 (Similar types can be asked).
3. How is it possible to insert different type of elements in 2 CO2
stack?
4. Stack can be described as a pointer. Explain. 2 CO2
5. Which data structure is needed to convert infix notations to 10 CO2
post fix notations?
6 Parenthesis are never needed in prefix or postfix 10 CO2
expressions. Why?
7 Minimum number of queues needed to implement the 10 CO2
priority queue?
8 Write an algorithm to evaluate a postfix expression. Execute 10 CO2
your algorithm using the following postfix expression as
your input: a b + c d+*f.
9 What are circular queues? Write down routines for inserting 10 CO2
and deleting elements from a circular queue implemented
using arrays.
10. In which data structure, elements can be added or removed 10 CO2
at either end, but not in the middle?
11. What are the methods available in storing sequential files? 10 CO2
12. A stack is to be implemented using an array. The associated 10 CO2
declarations are:
int stack [100];
int top = 0;

13 Give the statement to perform push operation. 10 CO2

14. Implement a Queue using a singly linked list L. The 10 CO2
operations INSERT and DELETE should still take O (1)
time.
15. Explain how to implement two stacks in one array A[1..n] in 10 CO2
such a way that neither stack overflows unless the total
number of elements in both stacks together is n. The PUSH
and POP operations should run in O(1) time.
16. What do you mean by Base case, Recursive case, Binding 10 CO2
Time, Run Time Stack and Tail Recursion?
17. Assume that a queue is available for pushing and popping 10 CO2
elements. Given an input sequence a,b, c, (c be the first
element), give the output sequence of elements if the
rightmost element given above is the first to be popped from
the queue.

18. Write an algorithm for finding solution to the Tower’s of 10 CO2

Hanoi problem. Explain the working of your algorithm (with
4 disks) with diagrams.

19. Reverse the order of elements on a stack S 10 CO2

(i) Using two additional stacks.
(ii) Using one additional queue.

20. Write an algorithm INSERT that takes a pointer to a sorted 10 CO2

list and a pointer to a node and inserts the node into its
correct position in the list.
21. Let P be a pointer to a singly linked list. Show how this list 10 CO2
may be used as a stack. That is, write algorithms to push and
pop elements. Specify the value of P when the stack is
empty.
22. Devise a representation for a list where insertions and 10 CO2
deletions can be made at either end. Such a structure is
called Deque (Double ended queue).
23. Write functions for inserting and deleting at either end. 10 CO2
24. Execute your algorithm to convert an infix expression to a 10 CO2
post fix expression with the following infix expression as
input A+BC/D*E*F*G/H.
25. Write an algorithm for PUSH and POP operation of Stack 10 CO2

Unit 3
S.No. Questions Marks CO
1. Write an algorithm to sort a given list using Quick sort 6 CO3
method. Describe the behaviour of Quick sort when input is
already sorted.
2. Sort the following list using Heap Sort 66, 33, 40, 20, 50, 6 CO3
88, 60, 11, 77, 30, 45, 65
3. Define graph, adjacency matrix, adjacency list, hash 6 CO3
function, sparse matrix, reachability matrix.
4. What is quick sort? Sort the following array using quick sort 6 CO3
method. 24 56 47 35 10 90 82 31.
5. How many key comparisons and assignments an insertion 10 CO3
sort makes in its worst case?
6 Create a heap with following list of keys: 8, 20, 9, 4, 15, 10, 10 CO3
7, 22, 3, 12
7 The following values are to be stored in a hash table: 25, 42, 10 CO3
 96, 101, 102, 162, 197
8 Describe how the values are hashed by using division 10 CO3
method of hashing with a table size of 7. Use chaining as the
method of collision resolution.
9 Describe insertion sort with a proper algorithm. What is the 10 CO3
complexity of insertion sort in the worst case?
10. How will you represent a max-heap sequentially? Explain 10 CO3
with an example.
11. Write an algorithm to insert an element to a max-heap that is 10 CO3
represented sequentially.
12. What do you mean by hashing? Explain any five popular 10 CO3
hash functions.
13 What is the best-case complexity of quick sort and outline 10 CO3
why it is so? How could its worst-case behaviour arise?
14. Apply the merge sort algorithm to sort the following 10 CO3
elements in ascending order. 13, 16, 10, 11, 4, 12, 6, 7.
Discuss the time and space complexity of merge sort?
15. Apply the quick sort algorithm to sort 15, 22, 30, 10, 15, 64, 10 CO3
1, 3, 9, 2. Is it a stable sorting? Justify.
16. Write heap sort algorithm. Analyze the running time of your 10 CO3
algorithm.
17. The keys 12, 17, 13, 2, 5, 43, 5 and 15 are inserted into an 10 CO3
initially empty hash table of length 15 using open
addressing with hash function h(k)=k mod 10 and linear
probing. Show the resultant hash table?
18. Differentiate between linear and quadratic probing 10 CO3
techniques, with example.
19. Using the bubble sort algorithm, find the number of swaps 10 CO3
(interchange) required to sort: 5, 10, 15, 55, 45, 35, 60, 75,
70
20. Write algorithm of insertion sort. Implement the same on the 10 CO3
following numbers; also calculate its time complexity. 13,
16, 10, 11, 4, 12, 6, 7
21. Explain the following as a short note: 10 CO3
a) Internal Sorting vs External Sorting with example
b) Stable Sorting vs Unstable Sorting with example
c) In-Place Sorting vs Out-Place Sorting with
example

22. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} 10 CO3
and a hash function h(X) = X (mod 10) Calculate the
memory location of each key and set them at the memory
from 1 to 10.
i. Hash table with using linear probing and
ii. Hash table with quadratic probing.
iii. Hash table with second hash function
h2 (x) = 7 − (x mod 7).
23. Discuss the worst case and best case time complexity of 10 CO3
Binary search.
24. Bubble sort algorithm is inefficient because it continues 10 CO3
execution even after an array is sorted by performing
unnecessary comparisons. Therefore, the number of
comparisons in the best and worst cases are the same.
Modify the algorithm in such a fashion that it will not make
the next pass when the array is already sorted.
25. Write an algorithm for merge sort with suitable example 10 CO3

Unit 4
S.No. Questions Marks CO
1. Given a set of input representing the nodes of a binary tree, 6 CO4
write a non recursive algorithm that must be able to output
the three traversal orders.
2. Write an algorithm for checking validity of the input, i.e., 6 CO4
the program must know if the input is disjoint, duplicated
and has a loop.
3. What is a Binary Search Tree (BST)? Make a BST for the 6 CO4
following sequence of numbers 45, 36, 76, 23, 89, 115, 98,
39, 41, 56, 69, 48 Traverse the tree in Preorder, Inorder and
postorder.
4. Two Binary Trees are similar if they are both empty or if 6 CO4
they are both nonempty and left and right sub trees are
similar. Write an algorithm to determine if two Binary Trees
are similar.
5. The degree of a node is the number of children it has. Show 10 CO4
that in any binary tree, the number of leaves is one more
than the number of nodes of degree 2.
6 Taking a suitable example explains how a general tree can 10 CO4
be represented as a Binary Tree.
7 What is the maximum total number of nodes in a tree that 10 CO4
has N levels? Note that the root is level (zero).
8 Write the non-recursive algorithm to traverse a tree in 10 CO4
preorder.
9 What are expression trees? Represent the following 10 CO4
expression using a tree. Comment on the result that you get
when this tree is traversed in Preorder, Inorder and
postorder. (a-b) / ((c*d)+e).
10. Taking a suitable example explains how a general tree can 10 CO4
be represented as a Binary Tree.
11. How many different binary trees and binary search trees can 10 CO4
be made from three nodes that contain the key values 1, 2 &
3?
12. How will inorder, preorder and postorder traversals print the 10 CO4
elements of a tree?
13 Which one is faster? A binary search of an orderd set of 10 CO4
elements in an array or a sequential search of the elements.
14. Write a non-recursive algorithm to traverse a binary tree in 10 CO4
inorder.
15. Construct a binary tree whose nodes in inorder and preorder 10 CO4
are given as follows:
Inorder : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50
Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50.

16. Given the following inorder and preorder traversal 10 CO4

reconstruct a binary tree
Inorder sequence D, G, B, H, E, A, F, I, C
Preorder sequence A, B, D, G, E, H, C, F, I

17. Make a BST for the following sequence of numbers. 10 CO4

45,32,90,34,68,72,15,24,30,66,11,50,10
Traverse the BST created in Preorder, Inorder and Postorder.

18. What is a Binary Tree? What is the maximum number of 10 CO4

nodes possible in a Binary Tree of depth d. Explain the
following terms with respect to Binary trees (i) Strictly
Binary Tree (ii) Complete Binary Tree (iii) Almost
Complete Binary Tree?

19. Construct a complete binary tree with depth 3 for this tree 10 CO4
which is maintained in memory using linked representation.
Make the adjacency list and adjacency matrix for this tree.

20. Construct the binary tree for the following sequence of 10 CO4
nodes in preorder and inorder respectively.
Preorder: G, B, Q, A, C, K, F, P, D, E, R, H
Inorder: Q, B, K, C, F, A, G, P, E, D, H, R

21. What is a height balanced tree? Explain how the height is 10 CO4
balanced after addition/deletion of nodes in it?
22. Let a binary tree ‘T’ be in memory. Write a procedure to 10 CO4
delete all terminal nodes of the tree.
23. Consider the following eight numbers 50, 33, 44, 22, 77, 35, 10 CO4
60 and 40. Display the construction of the binary by
inserting the above numbers in the given order.
24. If the Inorder of a binary tree is B,I,D,A,C,G,E,H,F and its post 10 CO4
order is I,D,B,G,C H,F,E,A then draw a corresponding binary tree
with neat and clear steps from above assumption.
25. Insert the following sequence of elements into an AVL tree, 10 CO4
starting with empty tree 71,41,91,56,60,30,40,80,50,55 also find
the minimum array size to represent this tree.
26. Write Short notes of following: 10 CO4
(a) Extended Binary Trees
 (b) Complete Binary Tree
(c) Threaded Binary Tree.

27. What is the difference between a binary search tree (BST) and 10 CO4
heap? For a given sequence of numbers, construct a heap and a
BST. 34, 23, 67, 45, 12, 54, 87, 43, 98, 75, 84, 93, 31
28. What is a B-Tree? Generate a B-Tree of order 4 with the 10 CO4
alphabets (letters) arrive in the sequence as follows:
AGFBKDHMJESIRXCLNTUP
29. Can you find a unique tree when any two traversals are given? 10 CO4
Using the following traversals construct the corresponding binary
tree:
INORDER: H K D B I L E A F C M J G
PREORDER: A B D H K E I L C F G J M.
Also find the Post Order traversal of obtained tree.

30. Consider the following AVL Tree and insert 2, 12, 7 and 10 as 10 CO4
new node. Show proper rotation to maintain the tree as AVL.

31. What maximum difference in heights between the leafs of a AVL 10 CO4
tree is possible?
a) log(n) where n is the number of nodes
b) n where n is the number of nodes
c) 0 or 1
d) at most 1

32. Define AVL Trees. Explain its rotation operations with examples. 10 CO4
Construct an AVL Trees with the values 10 to 1 numbers into an
initially empty binary tree.

33 Differentiate between fixed length and variable length encoding. 10 CO4

Draw a Huffman tree for the following symbols whose frequency
of occurrence in a message is stated along with the symbol below
A : 15, B : 6, C : 7, D : 12, E : 25, F : 4, G : 6, H : 1, I : 15 Decode
the message 1110100010111011

Unit 1
S.No. Questions Marks CO
1. Write an algorithm for BFS. 4 CO5
2. What are the different ways of representing a graph? Represent 4 CO5
the following graph using those ways.
3. Write an algorithm which does depth first search through an 6 CO5
un-weighted connected graph. In an un-weighted graph, would
breadth first search or depth first search or neither find a shortest
path tree from some node? Why?
4. Which are the two standard ways of traversing a graph? Explain 4 CO5
them with an example of each.
5. Explain Dijkstra’s algorithm for finding the shortest path in a 6 CO5
given graph.

6 Explain Depth First Search (DFS) algorithm. Find all possible 6 CO5
DFS and BFS of below given graph started at node “a”.
a)Find the adjacency Matrix A of G.
b)Find the Path Matrix of G. Is G Strongly connected.

7 How to find maximum edges in directed and undirected graph. 4 CO5

Explain with suitable example.
8 Define and draw a connected and disconnected graph. 4 CO5
9 Write an algorithm to test whether a graph is connected or not. 4 CO5
10. Consider the graph G in given below figure. Suppose the nodes 4 CO5
are stored in memory in an array DATA as follows: Data :
X, Y, Z, W

11. Describe Dijkstra’s algorithm for finding shortest path. Describe 8 CO5
its working for the graph given below.
12. Apply Prim’s and Kruskal’s algorithm to find the minimum 8 CO5
spanning tree on given graph.

13. Compute the Transitive closure of following graph using 6 CO5

Warshall’s Algorithm.

14. Discuss Connected Components. Write down algorithm to print 4 CO5

and count connected components.
15. Write Floyd-Warshal algorithm for all pair shortest path and find 8 CO5
the all pair shortest paths for the graph given below.