Suggestive questions Module wise

DSA
Module-I

1. What are the advantages and disadvantages of the array data structure?

2. Discuss time-space trade-off for algorithms.

3.

int a[n];

for(int i = 0;i < n;i++)

cin >> a[i]for(int i = 0;i < n;i++)

for(int j = 0;j < n;j++)

if(i!=j && a[i]+a[j] == z)

return true

else

return false

Calculate time and space complexity for the above pseudo code.

4. List the various operations that can be performed on data structure. Explain Big Oh
Notation. With example.

5. Give the general recurrence for divide and conquer algorithms.

6. What is ADT? What is an algorithm? Discuss the different steps in the development of
an algorithm?

7. Explain Linear Data structure with examples What are the various performance
measurement for an array list?
8. Write a program to create dynamic list of n elements. Write the algorithm for searching an
element in a given list using linear search

9. Write a program to define a function to search an element using Binary search technique.
Define different functions available in for dynamic memory allocation

10. Distinguish between linear and non-linear data structures State the advantages of ADT.

11. A 20x6 matrix array, named "MATRIX", is stored in memory using 'row-major order'. The
base address is 300 and each memory cell can hold 5 words. Calculate the address of the
element located at MATRIX[8, 4].

12. Define "asymptotic notation" in the context of algorithm analysis and provide examples of
common asymptotic notations.

13. Compare and contrast linear search and binary search techniques and analyse their time
complexity
14. What do you mean by Array? Describe the storage structure of array. What is static
memory allocation?

15. What do you mean by Asymptotic Notation? Explain Big Oh Notation. With example.

16. List out the areas in which data structures are applied extensively. What is ADT?

17. What do you mean by Asymptotic Notation? Explain Big Oh Notation. With example.

18. Consider the following recursive algorithm for computing the sum of the first n cubes.
S(n)=13+23+33+…..+n3 If n=1 return 1 Else return S(n-1)+n*n*n Identify the basic operation
in the algorithm. Set up the recurrence relation for the number of times the algorithm’s basic
operation is executed and solve it using back substitution.

19. Write the algorithm of the Binary searching technique and analyse the algorithm to
determine Time complexity.

MCQs

1. Consider the following statements:

i. First-in-first out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an
array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing
QUEUES on a linear array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES

2. Match the following.

a) Completeness i) How long does it take to find a solution

b) Time Complexity ii) How much memory need to perform the search.

c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.

3. A program P reads in 500 integers in the range [0..100] representing the scores of 500
students. It then prints the frequency of each score above 50. What would be the best way
for P to store the frequencies?

4. Which data structure is mainly used for implementing the recursive algorithm?

5. What is the time complexity of the following code snippet?

void solve() {

int a[] = {1, 2, 3, 4, 5};

int sum = 0;

for(int i = 0; i < 5; i++) {

if(i % 2 == 0) { sum += a[i];

} }

printf(“%d”,sum); }
6. In general, the binary search method needs no more than ________ comparisons.

7. The minimum number of stacks needed to implement a queue

8. Who is responsible for coining the term Sparse Matrix?

9. What is the time complexity of the binary search algorithm?

Module-II

1. Circular queue is very much advantageous than normal queue, Why? Explain with
example. List the applications of queue.
2. Convert the infix expression A+B-(C*D/E+F)-G*H into postfix expression using stack
Write an algorithm for converting Parenthesized Infix expression into Postfix
expression.
3. Write algorithm of PUSH and POP operation on stack. Explain tail Recursion for find
a factorial of number in detail.
4. What are the limitations of queue? Write an algorithm to insert an element in circular
queue. Give brief introduction of priority queue.
5. How an “empty queue” is distinguished from a “full queue”? Evaluate the postfix
expression "3 4 + 5 * 2 /" and show the step-by-step process of each operation,
including Push and Pop on a stack
6. Explain the implementation of circular queue using array.
7. Discuss the use of stack in implementing recursive procedures? Explain stack as
static data structure.
8. Develop an algorithm of inserting element into the stack.
9. Write an algorithm to insert and delete an element from a simple queue.
10. What is queue? Why it is known as FIFO?
11. Compare working of stack and queue data structure.
12. What is the base case for the following code? void my_recursive_function(int n) {
if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() {
my_recursive_function(10); return 0; }
13. Consider the following operation performed on a stack of size 5.
Push(1);Pop();Push(2);Push(3);Pop();Push(4);Pop();Pop();Push(5);After the
completion of all operation, the number of elements present in stack is?
14. In the worst case, the number of comparisons needed to search a singly linked list of
length n for a given element is
15. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
16. Postfix form of following expression. D + (E * F)
17. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
18. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a
time, in what order will they be removed?
19. Insertion and Deletion operation in Queue is known as
20. Which one of the following is an application of Stack Data Structure?
21. Which of the following data structures is required to convert arithmetic expression in
infix to its equivalent postfix notation?

Module- III
 1. Write algorithm for implementing operations of queue using linked list.
2. Write the algorithm to implement circular queue using linked list
3. Explain algorithm to delete element from circular linked list What is the need of two
way linked lists?
4. Write down the steps to invert a singly-linked list to circular linked list?
5. Compare singly linked lists and doubly linked lists.
6. Write the algorithm to insert element in specific location in single linked list. Explain
how to represent singly linked list in memory with help of diagram and example.
7. Write and explain algorithm to insert element at the beginning of circular linked list.
8. Discuss the advantages and disadvantages of linked list over array? How
advantageous is double linked list tham single linked list?
9. Explain algorithm to delete element from singly linked list.
10. Write the function to insert a new node before the given node in the single linked list.
11. Describe advantages of linked list over arrays.
12. Compare double ended queue and circular queue.

Module-IV

1. Define Prim’s algorithm for minimum cost spanning tree with an example. What are
the differences between BFS and DFS?
2. Using the Breadth-First Search (BFS) algorithm, provide a step-by-step explanation
for traversing a given graph.
3. The post-order and in-order traversal sequences of nodes in a binary tree are given
below: Post order: D G E B H I F C A In order: D B G E A C H F I 1. The post
order and in-order traversal sequences of nodes in a binary tree are given below:
Post order: D G E B H I F C A In order: D B G E A C H F IWat is AVL tree?
4. Construct a binary tree for the expression (a+b)*(c-d) Define key
terms related to graphs such as vertices, edges, and directed and undirected graphs.
How graphs are typically represented in programming?
5. What is an AVL tree? Explain how it maintains balance after insertions and deletions.
6. Describe the differences between binary trees and binary search trees (BST). What
are the advantages of using a BST over a regular binary tree?
7. State the properties of the binary search tree. Construct the binary search tree of the
following numbers: 40,33,11,55,60,50,15,22
8. How many bits would a succinct binary tree occupy?
9. Five node splitting operations occur when an entry is inserted into a B-tree. Then
how many nodes are written?
10. Which type of data structure does rope represent?
11. What is the traversal strategy used in the binary tree?
12. What is the space complexity of the post-order traversal in the recursive fashion? (d
is the tree depth and n is the number of nodes)
13. Which of the following ways can be used to represent a graph?
14. What is the number of edges present in a complete graph having n vertices?
15. Construct a binary tree using the following data. The preorder traversal of a binary
tree is 1, 2, 5, 3, 4. The in-order traversal of the same binary tree is 2, 5, 1, 4, 3.
16. How many common operations are performed in a binary tree?
17. Describe all types of rotations with examples in the above AVL tree.
18. Compare B tree and B+ tree.
 19. Using the Breadth-First Search (BFS) algorithm, provide a step-by-step explanation
for traversing a given graph.
20.

Module-V

1. Given the input { 4371, 1323, 6173, 4199, 4344, 9679, 1989 } and a hash function of
h(X)=X (mod 10) show the resulting: a. Separate Chaining hash table b. Open
addressing hash table using linear probing
2. Write the C function of merge sort with a a suitable example? Evaluate the time
complexity of merge sort algorithm.
3. Explain the basic principles of the Bubble Sort algorithm. Provide an example of its
operation on a small list, and discuss its time complexity.
4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the
hash function x mod 10, which of hash has same value?
5. What is a heap? Outline the properties of heap.
6. Discuss different kind of collision resolution technique in hashing.
7. What is the hash function used in the division method?
8. What is the advantage of selection sort over other sorting techniques?
9. Using division method, in a given hash table of size 157, the key of value 172 be
placed at position ____
10. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements.
How much iteration will be done to sort the array?
11. Which of the following sorting algorithm uses the method of insertion?
12. What is a collision in the context of hashing?
13. In Quick Sort, what is the pivot element used for?
14. What is a hash function?

How many steps are involved in creating a hash function using a multiplication method?

15. Quick sort uses which of the following method to implement sorting?
16. What is a collision in the context of hashing?

What is a hash function?

In Quick Sort, what is the pivot element used for?

17. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements.
How much iteration will be done to sort the array?

How many steps are involved in creating a hash function using a multiplication
method?

18. Which of the following sorting algorithm uses the method of insertion?

Quick sort uses which of the following method to implement sorting?

19. State and explain the algorithm of quick sort. Explain with the example.
20. Explain the working method of merge sort with the following data-
10,15,14,17,20,30,70,6
21. Explain the time complexity of merge sort.
22. Show the result of inserting the keys 2,3,5,7,11,13,15,6,4 into an initially empty
extendible hashing data structure with M=3
23. What is hashing, and how does it work? Difference between internal and external
hashing.