DATA STRUCTURES

UNIT I – ARRAY AND LINKED LIST

  1. What is meant by an Abstract data type (ADT)?
  1. What is the basic idea behind ADT?
  1. What are advantages in the array implementation of list?
  1. What are the disadvantages in array implementation of stacks?
  2. What is doubly liked list?
  3. Define double circularly linked list.
  4. List three examples that use linked list.
  5. What is the cursor implementation of linked list?
  6. What are the applications of stack?
  7. What is the solution for the Towers of Hanoi problem?
  8. What is a pointer?
  9. Why do we convert the infix expression into suffix expression?
  10. What is meant by degree of an operator?
  1. Define Data Structures.
  1. Define Linked Lists.
  1. State the different types of linked lists .
  1. List the basic operations carried out in a linked list .
  2. List out the advantages of using a linked list .
  3. List out the disadvantages of using a linked list .
  1. List out the applications of a linked list .
  2. State the difference between arrays and linked lists .

UNIT II – STACK AND QUEUE

  1. Define a stack
  1. List out the basic operations that can be performed on a stack
  1. State the different ways of representing expressions

The different ways of representing expressions are

• Infix Notation

• Prefix Notation

• Postfix Notation

  1. State the rules to be followed during infix to postfix conversions
  2. State the difference between stacks and linked lists
  1. Mention the advantages of representing stacks using linked lists than arrays
  1. Define a queue .
  1. Define a priority queue .
  2. State the difference between queues and linked lists
  3. Define a Deque.
  4. Define an Abstract Data Type (ADT) .
  5. What are the advantages of modularity?
  1. What are the objectives of studying data structures?
  1. What are the types of queues?
  1. List the applications of stacks .
  1. List the applications of queues .
  1. Why we need cursor implementation of linked lists?
  2. What is the solution for the Towers of Hanoi problem?
  3. What is a pointer?
  4. Why do we convert the infix expression into suffix expression?
  5. What is meant by degree of an operator?

UNIT III – TREE STRUCTURES

  1. Define a tree .

2. Define root .

3. Define degree of the node .

4. Define leaves .

5. Define internal nodes .

6. Define parent node .

7. Define depth and height of a node .

8. Define depth and height of a tree .

9. What do you mean by level of the tree?

10. Define forest .

11. Define a binary tree .

12. Define a path in a tree .

13. Define a full binary tree .

14. Define a complete binary tree.

15. State the properties of a binary tree .

16. What is meant by binary tree traversal?

17. What are the different binary tree traversal techniques?

• Preorder traversal

• Inorder traversal

• Postorder traversal

• Levelorder traversal

18. What are the tasks performed during inorder traversal?

• Traverse the left sub-tree

• Process the root node

• Traverse the right sub-tree

19. What are the tasks performed during postorder traversal?

• Traverse the left sub-tree

• Traverse the right sub-tree

• Process the root node

20. State the merits of linear representation of binary trees.

21. State the demerit of linear representation of binary trees.

22. State the merit of linked representation of binary trees.

23. State the demerits of linked representation of binary trees.

24. Define a binary search tree .

25. What is the use of threaded binary tree?

26.Traverse the given tree using Inorder, Preorder and Postorder traversals.

Inorder : D H B E A F C I G J

Preorder: A B D H E C F G I J

Postorder: H D E B F I J G C A

27. In the given binary tree, using array you can store the node 4 at which location?

At location 6

1 / 2 / 3 / - / - / 4 / - / - / 5

whereLCn means Left Child of node n and RCn means Right Child of node n

  1. Define AVL Tree.
  2. What do you mean by balanced trees?
  3. What are the categories of AVL rotations?
  4. What do you mean by balance factor of a node in AVL tree?
  5. Define Heap.
  6. What is the minimum number of nodes in an AVL tree of height h?
  7. Define B-tree of order M.
  8. What do you mean by 2-3 tree?
  9. What do you mean by 2-3-4 tree?
  10. What are the applications of B-tree?
  1. What are the properties of binary heap?
  2. What do you mean by structure property in a heap?
  3. What do you mean by heap order property?
  4. Define Hashing.
  5. What do you mean by hash table?
  6. What do you mean by hash function?
  7. Write the importance of hashing.
  8. What do you mean by collision in hashing?

UNIT IV –GRAPHS

1. Define Graph.

2. Define adjacent nodes.

3. What is a directed graph?

4. What is a undirected graph?

5. What is a loop?

6. What is a simple graph?

7. What is a weighted graph?

8. Define outdegree of a graph?

9. Define indegree of a graph?

10. Define path in a graph?

11. What is a simple path?

12. What is a cycle or a circuit?

13. What is an acyclic graph?

14. What is meant by strongly connected in a graph?

15. When is a graph said to be weakly connected?

16. Name the different ways of representing a graph?
17. What is an undirected acyclic graph?

18. What are the two traversal strategies used in traversing a graph?
19. What is a minimum spanning tree?

20. Name two algorithms two find minimum spanning tree
21. Define graph traversals.

22. List the two important key points of depth first search.

23. What do you mean by breadth first search (BFS)?

24. Differentiate BFS and DFS.
25. What do you mean by tree edge?

26. What do you mean by back edge?

27. Define biconnectivity.

28. What do you mean by articulation point?

29. What do you mean by shortest path?

30. Define Activity node graph.

31. Define adjacency list.

UNIT IV- SEARCHING AND SORTING

NOTE – ALL THE QUESTIONS FROM THIS UNIT ARE ASKED DIRECTLY BY NAME.

Sequential search,

Binary Search,

Comparison and Analysis Internal Sorting:

Insertion Sort,

Selection,

Bubble Sort,

Quick Sort,

Two Way Merge Sort,

Heap Sort,

Radix Sort,

Practical consideration for Internal Sorting.