Model Question Paper — Data Structures, II Semester B.C.
A Degree Examination
DCCA211 | MODEL QUESTION PAPER
II Semester B.C.A Degree Examination
COMPUTER SCIENCE
Data Structures (SEP Scheme)
Time : 3 Hours
Maximum Marks : 80
Instructions to Candidates: Answer all the Sections.
Section – A
(10×2=20)Answer any Ten of the following. Each question carries Two marks.
1. Define Data Structures and give two examples.
2. What is an Abstract Data Type (ADT)? Give one example.
3. Distinguish between time complexity and space complexity.
4. Define asymptotic notation. Name any two types.
5. What is a sparse matrix? Mention any two applications.
6. Write the syntax of any two built-in string functions with examples.
7. What are the basic operations of a linear array?
8. List the characteristics of a singly linked list.
9. Define recursion and give one example.
10. What is a stack? State its two main operations.
11. Distinguish between a simple queue and a circular queue.
12. Differentiate between a tree and a binary tree.
13. Define a graph. What is an adjacency matrix?
14. What is hashing? Define a hash function.
Section – B
(6×5=30)Answer any Six of the following. Each question carries Five marks.
15. Explain the classification of data structures with a neat diagram.
16. Explain best case, average case, and worst case time complexity with an example for
linear search.
17. Write an algorithm to insert and delete elements from a linear array. Illustrate with an
example.
18. Write a C program to perform the following string operations: length, concatenation,
and string comparison.
19. Explain the garbage collection process in the context of linked lists.
20. Convert the infix expression A + (B * C) − ((D / E) + F) to postfix form. Show all steps.
21. Write an algorithm for insertion and deletion in a circular queue using arrays.
22. Construct a Binary Search Tree for the values: 45, 30, 60, 20, 40, 55, 70, 10, 25. Show
each insertion step.
23. Explain the BFS traversal algorithm for a graph with an example.
24. Describe any three collision resolution techniques used in hashing.
Section – C
(3×10=30)Answer any Three of the following. Each question carries Ten marks.
25. Write a C program to illustrate the working of the following string built-in
functions: strlen(), strcat(), strcmp(), strcpy(), and strrev(). Explain each function with
output.
26.
a. Write an algorithm to insert a node at the beginning, middle, and end of a singly
linked list. (5)
b. Define circular linked list. Explain singly and doubly circular linked lists with
diagrams and examples. (5)
27.
a. Write algorithms for PUSH and POP operations on a stack using arrays.
Implement and evaluate the postfix expression: 5 3 2 * + 8 −. (5)
b. Explain the Towers of Hanoi problem. Write a recursive algorithm and trace its
execution for n = 3 disks. (5)
28.
a. Write algorithms for in-order, pre-order, and post-order traversal of a binary tree.
Illustrate with an example tree. (6)
b. Explain AVL trees. Show single and double rotations with examples. (4)
29.
a. Explain B-Trees with an example. State their applications in external
searching. (5)
b. Consider the graph with vertices {1, 2, 3, 4, 5, 6} and edges {(1,2),(1,3),(1,4),(2,5),
(3,5),(4,6),(5,6)}. Starting from vertex 1, traverse the graph using DFS and BFS.
Show the visited order. (5)
Section – A
(10×2=20)Answer any Ten of the following. Each question carries Two marks.
1. What is the time–space trade-off in algorithm design?
2. Define Big-O notation. Give one example.
3. What is a multidimensional array? Give its general form.
4. Define pattern matching. Name any one pattern matching algorithm.
5. Distinguish between strcpy() and strcat() with syntax.
6. What is a header linked list? Give any one use.
7. State the difference between a doubly linked list and a singly linked list.
8. Define Polish notation. What is its significance?
9. What is a priority queue? Give an example application.
10. Define a complete binary tree with an example.
11. What is a heap? Name its two types.
12. Define an AVL tree. What is the balance factor?
13. What is a collision in hashing? Why does it occur?
14. Distinguish between DFS and BFS graph traversal.
Section – B
(6×5=30)Answer any Six of the following. Each question carries Five marks.
15. Explain the algorithmic notations and control structures used in algorithm writing with
examples.
16. Write an algorithm for binary search. Trace it for the key 42 in the array: 5, 12, 23, 42,
67, 89, 95.
17. Explain the representation of sparse matrices. Write an algorithm to add two sparse
matrices.
18. Explain word processing and pattern matching. Describe the naive pattern matching
algorithm with an example.
19. Write a C program to perform insertion and deletion at any position in a singly linked list.
20. Evaluate the postfix expression: 8 2 3 + * 4 −. Show the stack state at each step.
21. Write an algorithm for insert and delete operations on a doubly-ended queue (Deque)
using arrays.
22. Explain Red-Black Tree properties. Show insertion of the values 10, 20, 30, 15 into an
empty Red-Black Tree.
23. Explain the components of hashing. Describe the division and mid-square hash functions
with examples.
Section – C
(3×10=30)Answer any Three of the following. Each question carries Ten marks.
24.
a. Explain the representation of arrays in memory. Write algorithms for traversal
and searching (linear search) of a linear array. (5)
b. Explain bubble sort and selection sort with worked examples. Compare their time
complexities. (5)
25.
a. Write an algorithm to insert a node at the end and delete a node from a doubly
linked list. Illustrate with a diagram. (5)
b. Explain memory allocation and garbage collection in linked lists. How does the OS
reclaim free nodes? (5)
26.
a. Write a C program implementing a stack using a linked list. Demonstrate PUSH,
POP, and display operations. (5)
b. Convert the infix expression ((A − B) * (C + D)) / (E + F * G) to postfix using a stack.
Show each step in a table. (5)
27.
a. Explain heaps and heap sort. Build a max-heap from the values: 35, 15, 50, 10,
25, 45, 5. Trace the sort. (6)
b. What are B-Trees? Construct a B-Tree of order 3 by inserting: 10, 20, 5, 6, 12, 30,
7, 17. (4)
28.
a. Write a C program to implement a circular queue using arrays. Include enqueue,
dequeue, and display operations. (5)
b. Consider a graph with 7 vertices. Apply DFS starting from vertex 1 and show the
DFS tree, discovery times, and finish times. (5)