Data Structures and Algorithms - Unit Wise Questions
1. What is stack? What are the different applications of stack? Explain stack operations with example.(1 + 3 + 7)
2. Differentiate between singly linked list and doubly linked list. How do you insert and delete a node from doubly linked list? Explain.(3+7)
3. What is shortest path? Explain Dijkstra algorithm for finding shortest path using suitable example.(2+8)
4. How do you find complexity of algorithms? Explain.
4. Differentiate between structure and union.
4. What do you mean by complexity of algorithms? How do you find time complexity?
4. Discuss array as an ADT.
4. What are the difference between two dimension array and multidimension array?
4. What is dynamic memory allocation? Compare data structure with abstract data type.(2+3)
5. “To write an efficient program, we should know about data structures.” Explain the above statement.
5. Explain algorithm for evaluation of postfix expression using stack.(5)
5. What are the major characteristics of algorithms?
5. What is an algorithm? What is to analyze in algorithm? Define Big Oh notation for time complexity measurement of algorithm.
5. Differentiate between array and pointer with example.
5. Describe the Big 'O' notation.
6. What is an algorithm? Write down the features of an algorithm.
6. Explain queue as an ADT.(5)
7. Write a recursive program to find GCD of two numbers.(5)
8. What is linked list? How is it different from array?(2+3)
9. Hand test bubble sort with array of numbers 53, 42, 78, 3, 5, 2, 15 in ascending order.(4+1)
10. What is hashing? Explain concept of hash table and hash function with example.(1 + 4)
11. Explain the use of Big O notation in analyzing algorithms. Compare sorting time efficiencies of Quick-Sort and Merge-Sort.
11. Justify the statement: “To write an efficient program, we should know about data structures and algorithms”.
11. What is Big ‘O’ notation? Analyze any one sorting algorithm.
11. What is dynamic memory allocation? How it is achieved for declaring two dimensional array? Explain.
11. How to find complexity of algorithms? Explain.
11. What is minimum spanning tree? Explain.(5)
12. Write short notes on: (2 x 2.5 = 5)
a. Tail recursion b. Collision resolution techniques
1. What is stack? How is it different from queue? Write a program to implement all stack operations.
1. How can you use stack to convert an infix expression to postfix? Convert infix expression (A + B)*(C - D) to postfix using stack.
1. Write a menu program to demonstrate the simulation of stack operations in array implementation.
1. Define stack as ADT. Describe its primitive operations on Array implementation and linked list implementation.
1. Trace out Infix to Postfix conversion algorithm with given Infix expression.
A + (((B-C) * (D-E) + F)/G) $ (H-I)
Evaluate the postfix expression acquired from above for the given values:
A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1.
2. What is Postfix expression? Write an algorithm to evaluate value of postfix expression. Trace the following expression into postfix expression.
(A+B*C)+(D-E/ F)
3. Explain the implementation of stack and queue with example.
3. Explain In-fix to Postfix Conversion Algorithm. Illustrate it with an example. What changes should be made for converting postfix to prefix.
3. Explain the algorithms for infix to postfix conversion and evaluation of postfix expression. Trace the algorithms with suitable example.
5. Evaluate the expression ABCD-x+ using stack where A=5, B=4, C=3 and D=7.
5. Construct an expression tree from the following postfix:
AB + C*DC – -FG + $
5. Transform the postfix expression AB − C + DEF − + $ to infix.
6. How can you convert from infix to post fix notation?
6. What is ADT? Discuss stack as an ADT.
6. Explain the infix to post fix conversion algorithm.
7. How stack as ADT? Explain with example.
1. Define queue. What are different applications of queue? Explain queue operations with example. (1+2+7)
1. Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.
1. Define Queue as ADT. Describe its primitive operation on array implementation and linked list implementation.
3. What is circular queue? Write an algorithm and C function to implement Circular queue.
6. What is priority queue? Why do we need this type of queue?
4. Write C function to insert an item circular queue in array implementation. Write assumptions, you need.
5. Compare stack with queue. How is linear queue different from circular queue?
6. Write C function to display all the items in a circular queue in array implementation. Write assumptions, you need.
7. How can you use Queue as ADT?
7. Describe circular Queue operations in array implementation.
13. What is priority queue? How it is best implemented?
2. Why recursion is required? Explain with Tower-of-Hanoi example. How recursive algorithm makes program effective? Write the merits and demerits of recursion in Programming.
2. What do you mean by recursion? Explain the implementation of factorial and Fibonacci sequences with example.
4. State TOH problem. Write recursion tree when no. of disks are four.
4. Consider the function:
Void transfer (int n, char from, char to, char temp)
{
if (n > 0)
{
transfer ( n – 1, from, temp, to);
Printf ( “Move Disk % d from % C to % C” N, from, to);
transfer ( n – 1, temp, to, from);
}
}
Trace the output with the function Call:
transfer ( 3, "R‟, "L‟, „"C‟);
4. Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursion tree.
4. What is Recursion? Write a recursive algorithm to implement binary search.
7. Write recursive program to find nth fibonacci number.
6. What is recursion? Write a recursive program to find factorial of a number.
6. State TOH problem. Explain a recursive algorithm to solve the problem.
7. Explain the Tower of Hanoi (TOH) with practical example.
7. Define recursive algorithm? How do you implement recursive algorithms while writing computer programs?
11. Write merits and demerits of recursive function over non-recursive function.
12. Write an algorithm to implement tower of Hanoi.
12. Explain the tower of Hanoi algorithm.
2. Explain circular linked list with example. How do you implement linked list operation in singly linked list? Explain. (4+6)
2. State relative merits and demerits of contiguous list and Linked list. Explain the steps involved in inserting and deleting a node in singly linked list.
2. Explain the structure of Doubly Linked List (DLL). Differentiate the difference between DLL and Doubly Circular Linked List (DCLL). Explain the procedures to insert a node in DLL at the beginning and at the last.
2. What is linked list? Explain the process of inserting and removing nodes from a linked list.
2. What do you mean by circular list? Differentiate between stack as a circular list and Queue as a circular list.
8. Explain array implementation of lists.
6. Differentiate between contiguous list and linked list with examples.
6. Differentiate between Singly linked list, DLL, CLL and DCLL.
8. Write an algorithm and C function to delete node in singly link list.
8. How do you insert a nodes at last in doubly linked list? Explain.
8. What do you mean by double linked list? Explain with example.
8. What are the benefits of using linked list over array? How can you insert a node in a singly linked list?
9. Explain why linked list is called dynamic list? Write the algorithm for deleting a new node before a node.
12. Discuss the merits and demerits of contiguous list and linked list.
12. Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).
13. State relative merits & demerits of contiguous list and linked list.
13. Write short notes on (any two):
a) Queue in circular linked list
b) ADT
c) MST (Minimum Cost Spanning Tree) of a graph.
2. Explain concept of divide and conquer algorithm. Hand test quick algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19). What is time complexity of quick sort algorithm?
3. What are external and internal sorting? Explain partition strategies of Merge sort and Quick sort. Trace these sort algorithms for following data:
11 45 61 33 55 9 83 25
5. Write a program in C for bubble sorting.
6. Compare partition strategies of Merge sort and Quick sort.
7. Trace selection – sort algorithm for the following data:
42, 23, 74, 11, 65, 58, 94, 86
7. Explain Divide and Conquer algorithm taking reference to Merge Sort.
7. Explain Bubble sort algorithm. Illustrate it with an example.
9. Hand test selection sort with array of numbers 4, 71, 32, 19, 61, 2, -5 in descending order.
8. Write a program to sort an array using selection sort.
9. Write an algorithm and C function for merge sort.
9. What is sorting? Describe the Insertion sort.
12. Write short notes on: (2 x 2.5 = 5)
a) Divide and conquer sorting
b) AVL tree
11. Differentiate between selection sort and bubble sort.
11. What do you mean by sorting? Explain the Bubble sort with example.
12. Hand test the insertion sort algorithm with following array of numbers.
16 7 31 2 9 41 -10
13. Discuss merge sort. How you rate this sorting from selection sort?
7. Explain binary search. Illustrate it with example.
8. Trace Binary Search algorithm for the data:
21, 36, 56, 79, 101, 123, 142, 203
And Search for the values 123 and 153.
10. Write a program to implement sequential search algorithm.
8. Explain hashing with example.
8. What is Hashing? What collision means? State collision resolution techniques. Explain one of them in brief.
8. Compare and Contrast between Binary searching and Binary tree searching.
9. How do you implement binary search algorithm? What is time complexity of this algorithm?
9. Discuss binary search technique along with its efficiency.
9. Describe recursive procedure of Binary searching technique? Discuss about efficiency of Binary searching.
9. State collision resolution techniques in hashing. Explain double hashing and quadratic probing techniques.
10. Explain the binary searching.
10. What are Hashing and collision? Write about any three hashing algorithms.
10. Why do we need Hashing? Discuss linear probing in detail.
10. What is hashing? Discuss rehashing with example.
12. Explain efficiency of
a) Binary Searching
b) Quick sort
12. Differentiate between sequential searching and binary searching.
13. Write Short notes on (any two):
a) Hash function
b) External Sorting
c) ADT.
13. Write short notes on
a) Hashing
b) Doubly Linked list
1. What is binary search tree? Explain with an example. Write an algorithm to search, insert and delete node in binary search tree.
1. Illustrate the algorithm for Binary search tree with example.
1. What do you mean by binary tree? Explain the binary search tree with example.
2. Describe properties of Binary Search Tree. Write recursive algorithms for constructing BST and its traversals. Illustrate them with an example.
2. Describe the significance of Huffman tree. Describe procedure for construction of a Huffman tree. Illustrate it with example. Describe different types of applications of Binary trees.
3. What is binary search tree? Write a program to implement insertion and deletion algorithm in binary search tree? (2+8)
3. A binary tree T has 12 nodes. The in-order and pre-order traversals of T yield the following sequence of nodes:
In-order : VPNAQRSOKBTM
Pre-order : SPVQNARTOKBM
Construct the Binary tree T showing each step. Explain, how you can arrive at solution in brief?
3. Define Binary Search Tree (BST). Write an algorithm to insert a node in non-empty BST. Construct BST from the data:
10, 20, 30, 25, 27, 7, 4, 23, 26, 21.
3. Discuss depth first and breadth first traversal of a graph with suitable example.
3. Explain the procedure for construction of Huffman algorithm with example.
3. What is graph traversal? Discuss depth-first traversal technique with suitable example.
4. Explain Kruskal’s algorithm with example.
5. Write about applications of Binary trees.
7. Explain almost complete binary tree with example.
8. What is Post-order traversal?
11. What is graph traversal? Explain.
9. Differentiate between tree and graph. What are spanning forest and spanning tree. Explain MST (Minimum cost Spanning Tree) problem.
9. What is weighted graph? Explain Depth-first traversal of a graph.
9. What are the types of binary tree? Compare between them.
10. Explain the characteristics of Huffman’s algorithm and its application.
10. A file contains 100 symbols in which following character with their probability of occurrence. Build a Huff man tree according to Greedy Strategy.
10. Create a Huffman tree for the following set of data:
10. What do you mean by graph traversal? Explain prim's algorithm with example.
10. Differentiate between pre-order traversal and in order traversal.
10. State MST (Minimum Cost Spanning Tree) problem and shortest path (single source and all other destination) problem. Name the algorithms for solving these problems.
11. Differentiate between Pre-order and In order traversal.
11. How do you transverse a binary tree? Discuss.
12. Write the steps involved in deleting a node in a Binary search tree.
12. Write short notes on:
(a) Dynamic memory allocation
(b) Game tree
12. Describe strong and weekly connected graphs with examples. What is weighted graph?
13. Explain the Kruskal‟s algorithm.
13. Discuss the Kruskal's algorithm with example.
13. Write short notes on:
a. Tree traversal
b. Circular queue