Sample Question Paper – I
Data Structures using C++
Unit 2: Sorting | Unit 3: Linked List
Total Marks: 16 Time: 1 Hour Max: 16 Marks
Instructions:
1. Section A is compulsory (5 questions × 1 mark each = 5 marks).
2. Section B: Attempt any 2 out of 3 questions (2 marks each = 4 marks).
3. Section C: Attempt any 2 out of 4 questions — 2 from Unit 2, 2 from Unit 3 (3 marks each = 6 marks [but
only 2 attempted = 6 marks]).
4. Write answers neatly. Traces and diagrams carry marks.
SECTION A – Answer All Questions [5 × 1 = 5 Marks]
Q1. What is a stable sorting algorithm? Give one example. [1 mark]
Q2. What is the best-case time complexity of Bubble Sort? [1 mark]
Q3. Define a Linked List. [1 mark]
Q4. What is the time complexity of inserting a node at the beginning of a singly [1 mark]
linked list?
Q5. Which sorting algorithm performs exactly n−1 swaps? [1 mark]
SECTION B – Attempt Any 2 out of 3 [2 × 2 = 4 Marks]
Q6. State and explain the time complexity of Insertion Sort in best, average, [2 marks]
and worst case.
(Unit 2)
Q7. Differentiate between in-place and out-of-place sorting with examples. [2 marks]
(Unit 2)
Q8. Write the algorithm to search for a key in a singly linked list. [2 marks]
(Unit 3)
SECTION C – Attempt Any 2 (1 from Unit 2, 1 from Unit 3) [2 × 3 = 6 Marks]
Note: Two questions are from Unit 2 (Sorting) and two from Unit 3 (Linked List). Attempt one from each.
Q9. Trace Bubble Sort on the array [5, 3, 8, 1, 2]. Show all passes and final [3 marks]
sorted array.
(Unit 2 – Sorting)
Q1 Explain Counting Sort with algorithm and example. State its time and [3 marks]
0. space complexity.
(Unit 2 – Sorting)
Q1 Write an algorithm to insert a node at a given position in a singly linked list. [3 marks]
1. Explain with an example.
(Unit 3 – Linked List)
Q1 Explain the deletion of a node by value in a singly linked list. Write the [3 marks]
2. algorithm and trace for deleting 30 from [10→20→30→40→NULL].
(Unit 3 – Linked List)
— End of Paper —
Sample Question Paper – II
Data Structures using C++
Unit 2: Sorting | Unit 3: Linked List
Total Marks: 16 Time: 1 Hour Max: 16 Marks
Instructions:
1. Section A is compulsory (5 questions × 1 mark each = 5 marks).
2. Section B: Attempt any 2 out of 3 questions (2 marks each = 4 marks).
3. Section C: Attempt any 2 out of 4 questions — 2 from Unit 2, 2 from Unit 3 (3 marks each = 6 marks [but
only 2 attempted = 6 marks]).
4. Write answers neatly. Traces and diagrams carry marks.
SECTION A – Answer All Questions [5 × 1 = 5 Marks]
Q1. What is the worst-case time complexity of Selection Sort? [1 mark]
Q2. Name one sorting algorithm that is NOT in-place. [1 mark]
Q3. What does the 'next' field in a linked list node store? [1 mark]
Q4. What is the time complexity of deleting the last node from a singly linked [1 mark]
list (with head pointer only)?
Q5. Which sorting algorithm is preferred for uniformly distributed real numbers? [1 mark]
SECTION B – Attempt Any 2 out of 3 [2 × 2 = 4 Marks]
Q6. Compare Bubble Sort and Selection Sort on the basis of stability, time [2 marks]
complexity, and number of swaps.
(Unit 2)
Q7. When is Counting Sort preferred over comparison-based sorting [2 marks]
algorithms? State its limitations.
(Unit 2)
Q8. Write an algorithm to insert a node at the end of a singly linked list (without [2 marks]
tail pointer). State its complexity.
(Unit 3)
SECTION C – Attempt Any 2 (1 from Unit 2, 1 from Unit 3) [2 × 3 = 6 Marks]
Note: Two questions are from Unit 2 (Sorting) and two from Unit 3 (Linked List). Attempt one from each.
Q9. Trace Insertion Sort on [4, 2, 7, 1, 5] showing each pass. Count the total [3 marks]
number of shifts performed.
(Unit 2 – Sorting)
Q1 Explain Bucket Sort with algorithm and example. Compare its best and [3 marks]
0. worst case complexities.
(Unit 2 – Sorting)
Q1 Explain insertion at the beginning and insertion at the end of a singly linked [3 marks]
1. list. Write algorithms for both and compare their time complexities.
(Unit 3 – Linked List)
Q1 Write a complete C++ program to create a singly linked list from user input [3 marks]
2. and display it. Explain each step.
(Unit 3 – Linked List)
— End of Paper —
Sample Question Paper – III
Data Structures using C++
Unit 2: Sorting | Unit 3: Linked List
Total Marks: 16 Time: 1 Hour Max: 16 Marks
Instructions:
1. Section A is compulsory (5 questions × 1 mark each = 5 marks).
2. Section B: Attempt any 2 out of 3 questions (2 marks each = 4 marks).
3. Section C: Attempt any 2 out of 4 questions — 2 from Unit 2, 2 from Unit 3 (3 marks each = 6 marks [but
only 2 attempted = 6 marks]).
4. Write answers neatly. Traces and diagrams carry marks.
SECTION A – Answer All Questions [5 × 1 = 5 Marks]
Q1. What is the average-case time complexity of Insertion Sort? [1 mark]
Q2. Define an in-place sorting algorithm. [1 mark]
Q3. How many bytes does a singly linked list node occupy on a 32-bit system [1 mark]
(int data + pointer)?
Q4. What is the time complexity of creating a new node in a linked list? [1 mark]
Q5. Which is the only comparison-based sort with O(n²) in all three cases (best, [1 mark]
average, worst)?
SECTION B – Attempt Any 2 out of 3 [2 × 2 = 4 Marks]
Q6. Explain Radix Sort with a small example. State when it is preferred over [2 marks]
other sorting techniques.
(Unit 2)
Q7. What is meant by sorting stability? Which of the following are stable: [2 marks]
Bubble, Selection, Counting? Justify.
(Unit 2)
Q8. Explain the searching operation in a singly linked list. Write the algorithm [2 marks]
and analyze its time complexity.
(Unit 3)
SECTION C – Attempt Any 2 (1 from Unit 2, 1 from Unit 3) [2 × 3 = 6 Marks]
Note: Two questions are from Unit 2 (Sorting) and two from Unit 3 (Linked List). Attempt one from each.
Q9. Trace Selection Sort on [64, 25, 12, 22, 11]. Show each pass and count [3 marks]
the number of swaps performed.
(Unit 2 – Sorting)
Q1 Compare Insertion Sort, Selection Sort, and Bubble Sort using: time [3 marks]
0. complexity (all cases), stability, and in-place property. Which is best for
nearly sorted data and why?
(Unit 2 – Sorting)
Q1 Explain deletion by position in a singly linked list. Write the algorithm and [3 marks]
1. trace deletion at position 2 from [10→20→30→40→NULL].
(Unit 3 – Linked List)
Q1 With a diagram, explain the structure of a singly linked list. Write algorithms [3 marks]
2. for: (i) inserting at end, (ii) searching a key.
(Unit 3 – Linked List)
— End of Paper —
Sample Question Paper – IV
Data Structures using C++
Unit 2: Sorting | Unit 3: Linked List
Total Marks: 16 Time: 1 Hour Max: 16 Marks
Instructions:
1. Section A is compulsory (5 questions × 1 mark each = 5 marks).
2. Section B: Attempt any 2 out of 3 questions (2 marks each = 4 marks).
3. Section C: Attempt any 2 out of 4 questions — 2 from Unit 2, 2 from Unit 3 (3 marks each = 6 marks [but
only 2 attempted = 6 marks]).
4. Write answers neatly. Traces and diagrams carry marks.
SECTION A – Answer All Questions [5 × 1 = 5 Marks]
Q1. What is the space complexity of Merge Sort? [1 mark]
Q2. State the best-case time complexity of Insertion Sort and the condition [1 mark]
under which it occurs.
Q3. Which node of a singly linked list stores NULL in its next field? [1 mark]
Q4. What is the difference between deletion by value and deletion by position [1 mark]
in a linked list?
Q5. Name the sorting algorithm that is best suited for integer data with a small [1 mark]
known range.
SECTION B – Attempt Any 2 out of 3 [2 × 2 = 4 Marks]
Q6. State and explain the time complexities of Counting Sort. Why does it [2 marks]
become inefficient when the key range k is very large?
(Unit 2)
Q7. Explain the concept of 'in-place' sorting. Which of the following are in- [2 marks]
place: Insertion Sort, Counting Sort, Bubble Sort, Radix Sort?
(Unit 2)
Q8. Write an algorithm to delete a node by value from a singly linked list. [2 marks]
Handle the case where the value is at the head.
(Unit 3)
SECTION C – Attempt Any 2 (1 from Unit 2, 1 from Unit 3) [2 × 3 = 6 Marks]
Note: Two questions are from Unit 2 (Sorting) and two from Unit 3 (Linked List). Attempt one from each.
Q9. Trace Bubble Sort on [8, 3, 6, 1, 9]. Show each pass clearly. State how [3 marks]
many comparisons were made in total.
(Unit 2 – Sorting)
Q1 Explain Radix Sort with algorithm and trace on [170, 45, 75, 90, 802, 24, 2, [3 marks]
0. 66]. State time and space complexity.
(Unit 2 – Sorting)
Q1 Explain all four types of insertion in a singly linked list: at beginning, at end, [3 marks]
1. at index, and after a given value. Write algorithms for each and state their
complexities.
(Unit 3 – Linked List)
Q1 Write a complete C++ program to: (i) create a singly linked list, (ii) search [3 marks]
2. for a value, (iii) delete a node by value, and display the list before and after
deletion.
(Unit 3 – Linked List)
— End of Paper —