**"QUESTION BANK"**

Important Questions in Data Structures & Algorithms 142301

subject for NOV/DEC 2011 AUT ANNA UNIVERSITY OF TECHNOLOGY EXAMINATIONS FOR SECOND YEAR THIRD SEMESTER IT Students

Data Structures & Algorithms

UNIT I

**1.**

**What is Stack? Give the implementations of stack and explain clearly the data structure and**

routines used.

**2.**

**What is singly linked list? Explain the algorithm in detail about various operations performed on a node from a Singly Linked list**

**3.**

**Illustrate with a neat example the implementation of a circular queue**

UNIT II

1. With an example explain the algorithms of inorder and postorder traversals

2. Explain the binary heap in detail.

3. Explain the rotations operations which are done in AVL-Tree. Construct the AVL Tree for the

following 18,26,9,47,54,32,12,58,30,60,44,74,33,55

4. Explain the tree traversals in detail

UNIT III

1. Discuss in detail open addressing and rehashing

2. Explain in detail the collision resolution methods.

3. What is meant by collision in hashing? Explain the separate chaining collision resolution strategy.

4. Explain in detail about Extensible hashing

UNIT IV

1. Explain in detail about DIjkstra’s Algorithm with an example

2. Explain in detail about DFS and BFS Techniques with an example

3. Explain the prim’s and Kruskal’s Algorithm with an example

UNIT V

1. Explain in detail about Divide and conquer Algorithm with an example.

2. Explain in detail about Dynamic Programming with an example

3. Explain in detail about Greedy Algorithm with an example

4. Explain in detail about Backtracking Algorithm with an example

UNIT I : DATA STRUCTURES

1. Define ADT.

2. What is a data structure? What are the types of data structures?

3. Define a linear and non linear data structure.

4. Define in brief an array. What are the types of array operations?

5. What is a recursive algorithm?

6. What is the difference between a stack and a Queue?

7. Can a stack be described as a pointer? Explain

8. Is it possible to insert different type of elements in a stack? How?

9. How would you sort a linked list?

10. Explain the types of linked lists.

11. Explain in brief a linked list.

12. Implement an algorithm to reverse a doubly linked list.

13. Implement an algorithm to insert in a sorted list.

14. Implement an algorithm to reverse a doubly linked list.

15. Implement an algorithm to insert in a sorted list.

16. What is an Algorithm?

17. List out and define the performance measures of an algorithm.

18. What is Complexity analysis?

19. Explain Space complexity?

20. Explain Time complexity?

21. List out the components that are used for space complexity?

22. What do asymptotic notation means?

23. Define linear data structure?

24. Define Non Linear data structure?

25. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.

26. What are different types of Linked List?

27. What are different types of Circular Linked List?

28. List certain applications of lists

29. List the basic operations carried out in a linked list?

30. Define a stack?

31. Define a queue?

32. Difference between Arrays and Linked List?

33. What is single linked list?

34. Define HEAD pointer and NULL pointer?

35. Define double linked list?

36. Write operations that can be done on stack?

37. Mention applications of stack?

38. Define Infix, prefix and postfix notations?

39. What are the conditions that followed in the array implementation of queue?

40. What are the conditions that could be followed in a linked list implementations of queue?

UNIT II : TREES

UNIT I : DATA STRUCTURES

1. Define ADT.

2. What is a data structure? What are the types of data structures?

3. Define a linear and non linear data structure.

4. Define in brief an array. What are the types of array operations?

5. What is a recursive algorithm?

6. What is the difference between a stack and a Queue?

7. Can a stack be described as a pointer? Explain

8. Is it possible to insert different type of elements in a stack? How?

9. How would you sort a linked list?

10. Explain the types of linked lists.

11. Explain in brief a linked list.

12. Implement an algorithm to reverse a doubly linked list.

13. Implement an algorithm to insert in a sorted list.

14. Implement an algorithm to reverse a doubly linked list.

15. Implement an algorithm to insert in a sorted list.

16. What is an Algorithm?

17. List out and define the performance measures of an algorithm.

18. What is Complexity analysis?

19. Explain Space complexity?

20. Explain Time complexity?

21. List out the components that are used for space complexity?

22. What do asymptotic notation means?

23. Define linear data structure?

24. Define Non Linear data structure?

25. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.

26. What are different types of Linked List?

27. What are different types of Circular Linked List?

28. List certain applications of lists

29. List the basic operations carried out in a linked list?

30. Define a stack?

31. Define a queue?

32. Difference between Arrays and Linked List?

33. What is single linked list?

34. Define HEAD pointer and NULL pointer?

35. Define double linked list?

36. Write operations that can be done on stack?

37. Mention applications of stack?

38. Define Infix, prefix and postfix notations?

39. What are the conditions that followed in the array implementation of queue?

40. What are the conditions that could be followed in a linked list implementations of queue?

UNIT II : TREES

**41. List out few of the Application of tree data-structure?**

42. Draw a binary Tree for the expression :

A * B - (C + D) * (P / Q)

Write a program in ‘C' language which accepts inorder and preorder traversal outputs of a Binary Tree as input and prints the corresponding Binary tree.

43. Define tree?

44. Write a function and the node data structure to visit all of the nodes in a binary tree.

45. Write a function to find the depth of a binary tree.

46. Define Depth of tree?

47. Define Degree of a node?

48. define Degree of a tree?

49. Define Terminal node or leaf?

50. Define Non-terminal node?

51. Define sibling?

52. Define binary tree?

53. Define expression tree?

54. Construction of expression trees?

55. Define tree traversal and mention the type of traversals?

UNIT III SORTING AND SEARCHING

56. What is insertion sort? How many passes are required for the elements to be sorted ?

57. What is the need of external sorting? Differentiate between merge sort and quick sort ?

58. What is replacement selection ?

59. What is sorting?

60. What is sequential search? What is the average number of comparisons in a sequential search?

61. What is binary searching and Fibonacci search?

62. The element being searched for is not found in an array of 100 elements. What is the average number of comparisons needed in a sequential

63. Which sort show the best average behavior?

64. What is the average number of comparisons in a sequential search?

65. Write Binary Search program

66. Write programs for Bubble Sort, Quick sort

UNIT IV GRAPHS AND THEIR APPLICATIONS

67. What is a graph?

68. What are Directed graphs?

69. What is the Huffman algorithm?

70. Define Path.

71. Define Cycle.

72. Define Connected graph.

73. What are the conditions for a graph to become a tree?

74. . Define a Weighted Graph.

75. Give the types of representation of graphs

76. What is a minimum spanning tree

77. Explain about Adjacency Matrix

78. What are the methods to solve minimum spanning tree?

79. Explain briefly about Prim’s algorithm

80. Define a depth first spanning tree.

81. What is a tree edge?

UNIT V STORAGE MANAGEMENT

82. What is the reference count method?

83. What is Garbage Collection?

84. What are the algorithms associated with Garbage Collection

85. What is Collection and Compaction ?

86. What are the variations in Garbage Collection?

42. Draw a binary Tree for the expression :

A * B - (C + D) * (P / Q)

Write a program in ‘C' language which accepts inorder and preorder traversal outputs of a Binary Tree as input and prints the corresponding Binary tree.

43. Define tree?

44. Write a function and the node data structure to visit all of the nodes in a binary tree.

45. Write a function to find the depth of a binary tree.

46. Define Depth of tree?

47. Define Degree of a node?

48. define Degree of a tree?

49. Define Terminal node or leaf?

50. Define Non-terminal node?

51. Define sibling?

52. Define binary tree?

53. Define expression tree?

54. Construction of expression trees?

55. Define tree traversal and mention the type of traversals?

UNIT III SORTING AND SEARCHING

56. What is insertion sort? How many passes are required for the elements to be sorted ?

57. What is the need of external sorting? Differentiate between merge sort and quick sort ?

58. What is replacement selection ?

59. What is sorting?

60. What is sequential search? What is the average number of comparisons in a sequential search?

61. What is binary searching and Fibonacci search?

62. The element being searched for is not found in an array of 100 elements. What is the average number of comparisons needed in a sequential

63. Which sort show the best average behavior?

64. What is the average number of comparisons in a sequential search?

65. Write Binary Search program

66. Write programs for Bubble Sort, Quick sort

UNIT IV GRAPHS AND THEIR APPLICATIONS

67. What is a graph?

68. What are Directed graphs?

69. What is the Huffman algorithm?

70. Define Path.

71. Define Cycle.

72. Define Connected graph.

73. What are the conditions for a graph to become a tree?

74. . Define a Weighted Graph.

75. Give the types of representation of graphs

76. What is a minimum spanning tree

77. Explain about Adjacency Matrix

78. What are the methods to solve minimum spanning tree?

79. Explain briefly about Prim’s algorithm

80. Define a depth first spanning tree.

81. What is a tree edge?

UNIT V STORAGE MANAGEMENT

82. What is the reference count method?

83. What is Garbage Collection?

84. What are the algorithms associated with Garbage Collection

85. What is Collection and Compaction ?

86. What are the variations in Garbage Collection?

**PART -A**

**What is meant by sorting?**

**What are the two main classifications of sorting based on the source of data?**

**What is meant by external sorting?**

**What is meant by internal sorting?**

;

**What are the various factors to be considered in deciding a sorting algorithm?****What is the main idea in Bubble sort?**

;

**What is the main idea behind insertion sort?****What is the main idea behind selection sort?**

**What is the basic idea of shell sort?**

**What is the other name for shell sort?**

**What is the purpose of quick sort?**

**What i the advantage of quick sort?**

**What is the average efficiency of heap sort?**

**Name some of the external sorting methods?**

**When is a sorting method said to be stable?**

**Name some simple algorithms used in external sorting?**

**When can we use insertion sort?**

**How many passes are required for k-way merging?**

**Define max heap?**

**Define min heap?**

**PART - B**

**Explain Heap sort?**

**Explain Insertion sort with example?**

**Explain merge sort with example?**

**Explain shell sort with example?**

;

**Explain quick sort with example?****Explain Exchange sorts with example?**

**Explain Selection and tree sorting with example?**

**Explain merge and radix sort with example?**

**Explain shortest path algorithm with example?**

**Explain Depth first and breadth first traversal?**

**Explain spanning and minimum spanning tree?**

**Explain Kruskal’s and prim’s algorithm?**

**Explain topological sorting?**

**PART -A**

**Define non-linear data structure?**

**Define tree?**

**Define leaf?**

**What is meant by directed tree?**

**What is a ordered tree?**

**What is a Binary tree?**

**What are the applications of binary tree?**

**What is meant by traversing?**

**What are the different types of traversing?**

**What are the two methods of binary tree implementation?**

**Define pre-order traversal?**

**Define post-order traversal?**

**Define in -order traversal?**

**What is the length of the path in a tree?**

**Define expression trees?**

**Define Strictly binary tree?**

**Define complete binary tree?**

**What is an almost complete binary tree?**

**Define AVL Tree**

**Define Graph?****Define adjacent nodes?****What is a directed graph?****What is a undirected graph?****What is a loop?****What is a simple graph?****What is a weighted graph?****Define out degree of a graph?****Define indegree of a graph?****Define path in a graph?****What is a simple path?****What is a cycle or a circuit?****What is an acyclic graph?****What is meant by strongly connected in a graph?****When is a graph said to be weakly connected?****Name the different ways of representing a graph?****What is an undirected acyclic graph?****What are the two traversal strategies used in traversing a graph?****What is a forest ?****What is a minimum spanning tree?**

**Name two algorithms two find minimum spanning tree**

**What is NP?**

**PART- B**

**What is a Binary tree?**

**Explain the different tree traversals with an application?**

**Explain Representing lists as Binary tree? Write algorithm for finding Kth element and**

**deleting an element?**

**Write a program to find duplicate numbers in an input list which includes the routines**

**maketree and setleft?**

**Define binary search tree? Explain the various operations with an example?**

**Define AVL trees? Explain the LL, RR, RL, LR case with an example?**

**Explain shortest path algorithm with example?**

**Explain Depth first and breadth first traversal?**

**Explain spanning and minimum spanning tree?**

**Explain Kruskal’s and prim’s algorithm?**

**Explain the various representation of graph with example in detail?****Define topological sort? Explain with an example?**

**PART -A**

**Write down the definition of data structures?**

**Give few examples for data structures?**

**Define Algorithm?**

**What are the features of an efficient algorithm?**

**List down any four applications of data structures?**

**What is meant by problem solving?**

**What is problem definition phase?**

**Mention some of the problem solving strategies?**

**Mention the types of bugs that may arise in a program?**

**What is divide and conquer?**

**State the importance of dynamic programming**

**Define storage structure?**

**Define file structure?**

**What are the four major parts in an iterative process?**

**Write down the algorithm for solving Towers of Hanoi problem?**

**What are the different types of data structur es?**

**What do you mean by primitive data structure?**

**What are the three stages of problem solving aspect.**

**Define depth of recursion?**

**What is searching?**

**PART -A**

**Write down the definition of data structures?**

**Give few examples for data structures?**

**Define Algorithm?**

**What are the features of an efficient algorithm?**

**List down any four applications of data structures?**

**What is meant by problem solving?**

**What is problem definition phase?**

**Mention some of the problem solving strategies?**

**Mention the types of bugs that may arise in a program?**

**What is divide and conquer?**

**State the importance of dynamic programming**

**Define storage structure?**

**Define file structure?**

**What are the four major parts in an iterative process?**

**Write down the algorithm for solving Towers of Hanoi problem?**

**What are the different types of data structur es?**

**What do you mean by primitive data structure?**

**What are the three stages of problem solving aspect.**

**Define depth of recursion?**

**What is searching?**

**What is Linear search?****Define Space Complexity****Define Time Complexity****What are asymptotic notations?****What is information?****Define Recursion?****What is a Fibonacci sequence?****What is an Abstract Data type(ADT)? Explain?****What are the operations of ADT?****What is meant by list ADT?****What are the various operations done under list ADT?****What are the two parts of ADT?****What is a Stack ?****What are the two operations of Stack?****Write postfix from of the expression –A+B-C+D?****What is a Queue ?****What is a Priority Qu eue?****What are the different ways to implement list?****What are the adv advantages in the array implementation of list?****What is a linked list?****Name the two fields of Link ed list?****What is a doubly linked list?****Name the three fields of Doubly Link ed list?****Define double circularly linked list?****What is the need for the header?****List three examples that uses linked list?****Give some examples for linear data structures?**

**Write postfix from of the expression –A+B-C+D?**

**How do you test for an empty queue?**

**What are the postfix and prefix forms of the expression?**

**A+B*(C-D)/(P-R)**

**Explain the usage of stack in recursive algorithm implementation?**

**Write down the operations that can be done with queue data structure?**

**What is a circular queue?**

**What is a Priority Queue? What are its types?**

**Define Hash function.**

**List out the different types of hashing functions?**

**What are the problems in hashing?**

**Define collision resolution**

**PART - B**

**Explain the types of analysis that can performed on an algorithm?**

**Design an algorithm to reverse the linked list. Trace it with an example?**

**Define an efficient representation of two stacks in a given area of memory**

**with n words and explain.**

**Explain the process of problem solving?**

**Explain program verification in detail?**

**Explain top down design?**

**What are the steps taken to improve the efficiency of an algorithm?**

**What is an Abstract Data type(ADT)? Explain?**

**What is a Stack? Explain with example?**

**Explain the linked list implementation of stack ADT in detail?**

**Write the algorithm for converting infix expression to postfix expression?**

**What is a Queue? Explain its operation with example?**

**Explain the array implementation of queue ADT in detail?**

**Explain the applications of stack?**

**Explain the linked list implementation of list ADT in Detail?**

**Explain the various applications of Linked List.**

**Explain the cursor implementation of linked list?**

**Write an algorithm for inserting and deleting an element from Doubly linked list?**

**Explain linear linked implementation of Stack and Queue?**

**Define priority queue? Explain the basic heap operation with an example?**

**Explain any two techniques to overcome hash collision?**

we need materials related to first semester syllabus... we are finding it difficult to face the assessment test since we don't have any idea abt it...

ReplyDelete