BCA 2nd Semester - Data Structures (BCA 203)
SECTION A - Short Answers (2 Marks Each)
1. Data Structure:
A data structure is a way of organizing and storing data in a computer so that it can be accessed and
modified efficiently.
2. Sorting Techniques:
Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort.
3. Linked List:
A linked list is a linear data structure where each element is a separate object, known as a node, that
contains data and a reference to the next node.
4. Stack:
A stack is a linear data structure that follows LIFO (Last-In, First-Out) principle.
5. Linked List Representation:
Each node contains two fields: data and next. The last node points to NULL.
6. Sparse Matrix:
A matrix with the majority of elements as zero.
7. Binary Tree:
A tree structure where each node has at most two children.
BCA 2nd Semester - Data Structures (BCA 203)
8. Non-terminal vs Leaf Node:
Non-terminal node has children. Leaf node has no children.
9. Binary Search Tree:
A binary tree where the left node has smaller values and the right has larger values.
10. Applications of Linked List:
- Dynamic memory allocation
- Implementing stacks/queues
11. Priority Queue:
A queue where each element has a priority and elements with higher priority are dequeued first.
12. Directed Graph:
A graph in which edges have directions. Example: A -> B.
SECTION B - Long Answers (10 Marks Each)
Q13:
a) Linear Search: It checks each element one by one until the target is found.
b) Selection Sort Algorithm:
1. Repeat from i = 0 to n-2:
2. Find the minimum in unsorted part.
BCA 2nd Semester - Data Structures (BCA 203)
3. Swap it with the first element.
Q14:
a) Linked List Advantages:
- Dynamic size
- Efficient insertion/deletion
b) Insertion Sort in C:
void insertionSort(int arr[], int n) {
for(int i=1; i<n; i++) {
int key = arr[i], j = i-1;
while(j >= 0 && arr[j] > key) arr[j+1] = arr[j--];
arr[j+1] = key;
Q15:
a) Bubble Sort in C:
void bubbleSort(int arr[], int n) {
for(int i=0; i<n-1; i++)
for(int j=0; j<n-i-1; j++)
if(arr[j]>arr[j+1]) swap(arr[j], arr[j+1]);
b) Binary Search:
Advantages: Fast in sorted data
Disadvantages: Only works on sorted data
BCA 2nd Semester - Data Structures (BCA 203)
Q16:
a) Applications:
Stacks (function calls), Queues (scheduling), Trees (file systems), Graphs (maps)
b) Factorial using Recursion:
int factorial(int n) {
if(n==0) return 1;
return n * factorial(n-1);
Q17:
Linked List Types:
- Singly: One pointer
- Doubly: Two pointers (prev, next)
- Circular: Last node points to first
Q18:
Stack Program:
push(), pop(), display() using array and menu-driven loop
Q19:
a) Definitions:
Graph - set of vertices/edges
Edge - connection
Vertex - node
BCA 2nd Semester - Data Structures (BCA 203)
Null Graph - no edges
Leaf Node - no children
b) DFS:
Start from a node, visit unvisited neighbors recursively.
Q20:
a) Dynamic Memory Allocation:
malloc(), calloc(), realloc(), free()
b) Infix to Postfix:
(a + b) * (m / n) + (x + y)
Postfix: a b + m n / * x y + +
