Data Structures in C Programming - Full
Exam Answers
PART – A (10 × 1 = 10 Marks)
Answer all questions.
1. 1. Best case time complexity of linear search:
Answer: O(1). The element is found at the first position.
2. 2. What is an array?
Answer: An array is a collection of similar data types stored in contiguous memory
locations.
3. 3. What is a double ended queue?
Answer: A double-ended queue (deque) is a linear data structure where insertion and
deletion can be done from both ends.
4. 4. What is a circular queue?
Answer: A circular queue is a queue where the last position is connected back to the
first, forming a circle.
5. 5. Define recursion:
Answer: Recursion is a function that calls itself to solve a smaller subproblem.
6. 6. What is binary search?
Answer: Binary search is a search algorithm that divides a sorted array into halves to
find the target value. Time complexity is O(log n).
7. 7. What is a complete binary tree?
Answer: A binary tree in which all levels are completely filled except possibly the last,
and all nodes are as far left as possible.
8. 8. Maximum number of edges in a simple graph with n vertices:
Answer: n(n - 1)/2.
9. 9. What is a minimum spanning tree?
Answer: A subset of edges in a graph that connects all vertices with the minimum total
weight and no cycles.
10. 10. Postfix form of (A + B) * C:
Answer: AB+C*
PART – B (5 × 2 = 10 Marks)
Answer all questions.
11. 11. Difference between best, worst, and average case time complexities:
Best Case – Minimum time (e.g., O(1) in linear search).
Worst Case – Maximum time (e.g., O(n) if element is last).
Average Case – Expected time (e.g., O(n/2) ≈ O(n)).
12. 12. Applications of Stack:
- Expression evaluation and conversion
- Function call management
- Undo operations
- Backtracking algorithms
13. 13. Need for circular queue:
To reuse the space created by dequeued elements and avoid overflow in a linear queue
by connecting rear to front.
14. 14. AVL Tree:
A self-balancing binary search tree where the difference in heights (balance factor) of
left and right subtrees is -1, 0, or +1.
15. 15. Difference between BFS and DFS:
BFS: Level-order traversal using a queue.
DFS: Depth-first traversal using stack or recursion.
PART – C (5 × 12 = 60 Marks)
Answer all questions.
16. 16. (a) Types of Data Structures:
Linear: Array, Stack, Queue, Linked List. Non-linear: Tree, Graph. Explained with
examples and uses.
17. 16. (b) Array Operations with C Examples:
Operations like Traversal, Insertion, Deletion, Search, and Update with sample C code
provided.
18. 17. (a) Types of Linked Lists with Diagrams:
Explains singly, doubly, circular, and circular doubly linked lists with their structure and
use-cases.
19. 17. (b) C Program for Stack Using Arrays:
Push, Pop, Display operations implemented in C using arrays and explained clearly.
20. 18. (a) C Program for Queue Insert/Delete Using Arrays:
Queue operations: Enqueue, Dequeue, and Display written in C using arrays with full
explanation.
21. 18. (b) C Program for Infix to Postfix Conversion:
Infix to Postfix conversion using stack with precedence handling; complete C program
included.
22. 19. (a) C Program to Insert/Delete in Binary Search Tree:
BST explained with insert and delete functions and a working C program showing
Inorder traversal.
23. 19. (b) C Program for Tree Traversals:
Shows Inorder, Preorder, and Postorder tree traversal techniques using recursion in C.
24. 20. (a) Prim’s and Kruskal’s Algorithms with Example:
Explains both algorithms for Minimum Spanning Tree with edge selection, working, and
comparison.
25. 20. (b) Dijkstra’s Algorithm with Example:
Step-by-step shortest path algorithm from a source node using greedy method with
example and logic.
