Data Structures R23 UNIT-1&2

                                    Data Structures Short questions

Unit-1:

1. Define Data Structure.

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently.

2. What are the different types of data structures?

Two types:

Linear Data Structures

Non-Linear Data Structures

3. What is a linear data structure?

A linear data structure stores elements sequentially where each element is connected to the next element.

4. What is a non-linear data structure?

A non-linear data structure stores elements hierarchically and elements are not arranged sequentially.

5. Give two examples of linear data structures.

Array

Linked List

6. Give two examples of non-linear data structures.

Tree

Graph

7. Define Abstract Data Type (ADT).

An ADT is a logical description of data and operations on the data without specifying the implementation details.

8. What are the components of ADT?

Data objects

Operations on the data

9. Give two examples of ADT.

Stack

Queue

10. What is the difference between ADT and Data Structure?

ADT: Logical model of data and operations.

Data Structure: Physical implementation of ADT.

11. Define Algorithm.

An algorithm is a step-by-step procedure used to solve a problem.

12. What is time complexity?

Time complexity measures the amount of time an algorithm takes to execute.

13. What is space complexity?

Space complexity is the amount of memory required by an algorithm during execution.

14. What is Big-O notation?

Big-O notation represents the upper bound of an algorithm’s time complexity.

15. What is best case complexity?

The best case complexity is the minimum time taken by an algorithm.

16. What is worst case complexity?

The worst case complexity is the maximum time taken by an algorithm.

17. Define Searching.

Searching is the process of finding the location of a specific element in a list.

18. What is Linear Search?

Linear search checks each element sequentially until the required element is found.

19. What is the time complexity of Linear Search?

Time complexity: O(n)

20. What is Binary Search?

Binary search divides a sorted array into two halves repeatedly to find the target element.

21. What is the condition required for Binary Search?

The array must be sorted.

22. What is the time complexity of Binary Search?

Time complexity: O(log n)

23. Define Sorting.

Sorting is the process of arranging data elements in a particular order (ascending or descending).

24. What is Bubble Sort?

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

25. What is the time complexity of Bubble Sort?

Worst case: O(n²)

26. What is Selection Sort?

Selection sort repeatedly selects the smallest element and places it in the correct position.

27. What is Insertion Sort?

Insertion sort places each element in its correct position in the sorted part of the list.

28. What is the best case time complexity of Insertion Sort?

Best case: O(n)

29. What is stable sorting?

A stable sorting algorithm maintains the relative order of equal elements.

30. What is the difference between internal and external sorting?

Internal Sorting: Sorting performed in main memory.

External Sorting: Sorting performed using external storage like disk.

 

Unit-2:

1. What is a Linked List?

  • A linked list is a dynamic data structure consisting of nodes.
  • Each node contains data and a pointer to the next node.

2. What are the components of a linked list node?

  • Data field (stores information).
  • Link field (stores address of next node).

3. What is the starting node of a linked list called?

  • It is called the Head or Start node.
  • It stores the address of the first node.

4. What is meant by dynamic memory allocation in linked lists?

  • Memory is allocated during program execution.
  • Functions like malloc() are used.

5. What are the advantages of linked lists?

  • Dynamic size.
  • Efficient insertion and deletion.

6. What is a Singly Linked List?

  • Each node contains data and one pointer.
  • The pointer points to the next node.

7. What is the last node in a singly linked list?

  • The last node’s next pointer is NULL.
  • It indicates the end of the list.

8. What are the basic operations on singly linked lists?

  • Insertion and Deletion.
  • Traversal and Searching.

9. What is traversal in a linked list?

  • Visiting each node sequentially.
  • Used for displaying or processing data.

10. What is insertion in a singly linked list?

  • Adding a new node to the list.
  • It can be at beginning, end, or middle.

11. What is deletion in a singly linked list?

  • Removing a node from the list.
  • Memory of the node is freed.

12. What is searching in a linked list?

  • Finding a specific element in the list.
  • Done by traversing nodes sequentially.

13. What is a Doubly Linked List?

  • Each node has two pointers.
  • One points to previous node and another to next node.

14. What are the fields in a doubly linked list node?

  • Data field.
  • Two link fields (previous and next).

15. What is the advantage of a doubly linked list?

  • Traversal can be done in both directions.
  • Deletion is easier than singly linked list.

16. What is the disadvantage of doubly linked lists?

  • Requires more memory.
  • More pointer manipulation.

17. What is the first node condition in doubly linked list?

  • The previous pointer is NULL.
  • Next pointer points to second node.

18. What is a Circular Linked List?

  • The last node points to the first node.
  • There is no NULL pointer.

19. What is the advantage of circular linked lists?

  • Traversal can start at any node.
  • Useful for repeated operations.

20. What is the condition of the last node in circular linked list?

  • Last node’s next pointer points to first node.
  • Forms a loop structure.

21. What is the disadvantage of circular linked list?

  • More complex implementation.
  • Risk of infinite loops during traversal.

22. Difference between array and linked list?

  • Array uses contiguous memory.
  • Linked list uses non-contiguous memory.

23. What is the advantage of arrays over linked lists?

  • Faster random access using index.
  • Less memory overhead.

24. What is the advantage of linked lists over arrays?

  • Dynamic size.
  • Efficient insertion and deletion.

25. What is insertion at beginning?

  • New node is added before first node.
  • Start pointer is updated.

26. What is insertion at end?

  • New node is added after the last node.
  • Last node pointer is updated.

27. What is insertion at specific position?

  • Node inserted at a given position.
  • Links are adjusted accordingly.

28. What is deletion at beginning?

  • First node is removed.
  • Start pointer moves to next node.

29. What is deletion at end?

  • Last node is removed.
  • Previous node’s next pointer becomes NULL.

30. What is traversal operation?

  • Visiting each node sequentially.
  • Used to display list elements.

31. What is sequential search in linked list?

  • Compare key with each node.
  • Stop when element is found.

32. How are linked lists used in memory management?

  • Used in free memory lists.
  • Helps in dynamic memory allocation.

33. How are linked lists used in polynomial representation?

  • Each node stores coefficient and exponent.
  • Used for polynomial operations.

34. How are linked lists used in graph representation?

  • Used in adjacency list representation.
  • Stores vertices and edges efficiently.

35. What is a self-referential structure?

  • A structure containing a pointer to itself.
  • Used to create linked lists.

36. What is NULL pointer in linked list?

  • Indicates end of list.
  • No next node exists.

37. What is memory allocation function used in linked list?

  • malloc() function.
  • Allocates memory dynamically.

38. What is a header node?

  • A special node at the beginning.
  • Stores list information.

39. What is pointer in linked list?

  • Variable storing memory address.
  • Used to connect nodes.

40. What is node traversal condition in singly linked list?

  • Continue until pointer becomes NULL.
  • Move using next pointer.

41. What is node traversal condition in circular list?

  • Continue until pointer returns to start node.
  • Loop structure is maintained.

 

 


Comments

Post a Comment

Popular posts from this blog

Data Structure- Algorithm Introduction

 What is an algorithm?   An algorithm is a finite set of step by step instructions to solve a problem. In normal language, algorithm is defined as a sequence of statements which are used to perform a task.  In computer science, an algorithm can be defined as follows:   An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer.   Properties Every algorithm must satisfy the following properties:   1. Definiteness - Every step in an algorithm must be clear and unambiguous  2. Finiteness – Every algorithm must produce result within a finite number of steps.  3. Effectiveness - Every instruction must be executed in a finite amount of time.  4. Input & Output - Every algorithm must take zero or more number of inputs and must produce at least one output as result.  1.2 Performance Analysis In computer science there are multiple algorithms...
Read more