Question Bank

CSE-AIML/AI III Sem

UNIT-I

1. Describe algorithms with suitable example. Also discuss the properties of an algorithm.
Define the parameters to analysis the complexity of an algorithm.
2. Elaborate Data Structure and Discriminate linearity and non-linearity of data structure?
3. Write a program to insert an element at certain position into 1D array.
4. Elaborate the pros and cons of array and linked list by giving the example.
5. What is the output of following program?
int main ()

{
int a[][] = {{1,2},{3,4}};
int i, j;
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
printf("%d ", a[i][j]);
return 0;
}

6. Consider a 2D array declared in C++ as: A[20][30]. Element type is integer and each
element occupy 2-byte space in memory. If the base address is 1076, and memory is byte
oriented. Find the address of an element A[17][29] using:
(i) Row major order representation
(ii) Column major order representation
7. A 20×22 matrix is implemented using array A[20][22], if the base address of the array A
is 1215 and the word size (element size) is 2 Byte then compute the address of the element
A[8][12] in:
(i) Row major order representation
(ii) Column major order representation
8. Explain the algorithm to perform each of the following operations on Singly linked list
(SLL):
(i) Inserting an element at first position
(ii) Inserting an element at last position
 (iii) Inserting an element at specified position
(iv) Traversing nodes in a single linked list
9. Explain the algorithm to perform each of the following operations on Singly linked list
(SLL):
(i) Deleting an element at first position
(ii) Deleting an element at last position
(iii) Deleting an element at specified position
10. Explain the algorithm to perform each of the following operations on Circular linked list
(CLL):
(i) Inserting an element at first position
(ii) Inserting an element at last position
11. Explain the algorithm to perform each of the following operations on Doubly linked list
(DLL):
(i) Inserting an element at first position
(ii) Inserting an element at last position

UNIT-II

12. Explain various applications of stack. Convert the following Parenthesized infix
expression into postfix expression:
(P ^ (Q + (R + S + T +U) * (V + W) + X) / Y / Z)
13. Explain stack data structure? Write PUSH() and POP() function of stack when stack is
implemented using an Array data structure.
14. Explain queue data structure with suitable example. What are the limitations of linear
queue and how these are removed in circular queue? Explain with appropriate example.
15. Explain with appropriate example. Explain an algorithm for evaluating a postfix expression
using stack data structure. Consider the following arithmetic expression P, written in
postfix notation-
P: 9 8 + 3 8 2 / * 2 + - Evaluate P using stack.
16. Write an algorithm for converting Infix expression into Postfix expression and convert
following Infix expression into Postfix expression:
a-b/c*d+e*f/g
17. Explain the different types of Queues like Circular queue, Priority Queue, DEQUES.
18. Explain the linked list implementation of Stack and Queue data structures.
 UNIT-III

19. Generate a Binary Search Tree by inserting in order the following integers: 50, 15, 62, 5,
20, 58, 91, 3, 8, 37, 60, 24. Also find the number of nodes in the left subtree and right
subtree of the root in the generated binary search tree.
20. Explain the Tree Traversal technique with example?
(i) In-order (ii) Pre-order (iii) Post-order Traversal

21. Draw the binary tree with node labels a, b, c, d, e, f and g for which the in-order and post-
order traversals result in the following sequences:

In-order: a f b c d g e
Post-order: a f c g e d b
Also find the height of the constructed binary tree.
22. The post-order traversal of a binary tree is: 8, 9, 6, 7, 4, 5, 2, 3, 1. The in-order traversal of
the same tree is: 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path
from the root to any leaf. Construct the binary tree and also find the height of the
constructed binary tree.
23. What is AVL Tree? How do you generate an AVL tree?
24. Create an AVL tree by adding the numbers sequentially to an initially empty binary search
tree for the given data set: {6,15,50,3,33,45,40,80,10}
25. Explain height balanced search trees with suitable example. Mark the balance factor of
each node on the tree given on the below figure and state whether it is height-balanced or
not.

26. Insert the following entries into an initially empty B-Tree of order 5?
a, g, f, b, k, c, h, n, j, d, r, i, s, x, e, l, m, t, u, v

27. Describe max heap? Create the max heap by adding the numbers sequentially to an
initially empty binary Max-heap for the given data set: {6,15,50,3,33,45,40,80,10}.
28. Construct an AVL Tree for following elements:
H, I, J, B, A, E, C, F, D, G, K, L
29. Explain following terms:
a. Binary Tree
b. Strictly Binary Tree
c. Complete Binary Tree
d. Almost Complete Binary Tree
30. What is Heap? Explain max heap and min heap with example.
31. Construct max heap and min heap tree for following sequence of numbers.
4,40,23,50,11,34,62,78,66,22,90,59,25,72,64,77,39 & 12.
32. Explain multiway tree, B Tree, B+ Tree, B* Tree and write their properties.
33. Explain Red-Black Tree. What are different properties of RBT.
34. What are different problems occur every time when you insert new node in RBT.
35. Create a Red Black tree by inserting following sequence of number 8,18, 5, 15, 17, 25, 40
and 80.
UNIT-IV

36. Describe Minimum Spanning Tree (MST). Describe Prim’s and Kruskal’s method for
finding the minimum spanning tree.
37. Find the Minimum spanning tree of the given graph and demonstrate the addition of
sequence of edges to a minimum spanning tree at each stage using:
(i) Prim’s algorithm
(ii) Kruskal’s algorithms.

38. Find the shortest path from ‘s’ to all other vertices using Dijkstra’s algorithms for the
given graph:
39. Find the minimum cost spanning tree using prim’s method for the following weighted
graph? Display tree at each stage.

40. Write DFS and BFS algorithm.

41. Differentiate between Depth first search (DFS) and Breadth first search (BFS) algorithm?
Traverse the following graph using DFS and BFS approach: Source is ‘0’
42. Find the Minimum spanning tree of the given graph using Kruskal’s algorithm? Display
tree at each stage.

43. Explain how does Bellmen ford algorithm work on negative weight edges and how does
it analyse negative weight edge cycle?

UNIT-V

44. Explain selection sort method? Arrange the given array using selection sort and give the
required steps: {96, 31, 27, 42, 34, 76, 61, 10, 4}.
45. Describe binary search method with iterative algorithm. Suppose that the following 13
elements are stored in an array in sorted manner: 11, 22, 30, 33, 40, 44, 50, 60 ,66, 77, 80,
88, 99. Apply the binary search algorithm for searching ITEM value 60.
46. Give an algorithm for Quick Sort and explain its time complexity in best case and worst-
case scenario. Trace the algorithm for the following given data: 65, 70, 75, 80, 85, 60, 55,
50, 45.
47. Describe hashing and state the advantages of hashing over the searching methods. Draw
the hash table resulting from hashing the keys: 12, 48, 22, 80, 23, 64, 21, 32, 20, 15 and 58
using the hash function h(i) = (2i+5) mod 10. Use chaining as the method of collision
resolution.
48. Describe Merge Sort sorting technique? Write the algorithm to sort using merge sort. Also
discuss worst and best cases for merge sort algorithm. Explain your answer using following
given data set: 50, 40 20, 70, 15, 35, 10, 60.
49. Explain Heap sort and write its algorithm. How do you sort through max heap?
50. Explain insertion sort method? Arrange the given array using insertion sort and give the
required steps: {96, 31, 27, 42, 34, 76, 61, 10, 4}.