Some Important Question Data Structure-BCA

UNIT I: Introduc on to Data Structures and Algorithms

Theory/Conceptual Ques ons:

1. Define data structure. Explain its types.

2. What is an algorithm? Discuss me and space complexity with examples.

3. Explain Asympto c Nota ons: Big O, Omega (Ω), and Theta (Θ) with graphs and
examples.

4. Differen ate between algorithms and subalgorithms.

UNIT II: Arrays, Linked Lists, Stacks, and Queues

Arrays:

1. Explain linear and mul dimensional arrays. How is a 2D array represented in

Linked Lists:

1. Write an algorithm to insert and delete a node in a singly linked list.

2. Compare singly, doubly, and circular linked lists.

3. What is garbage collec on in context of linked lists?

Stacks and Queues:

1. Write a C program to evaluate a pos ix expression using stack.

2. Convert the infix expression A + B * (C - D) to pos ix.

3. What are circular queues and how are they implemented?

4. Define priority queue and double-ended queue (Deque).

UNIT III: Trees

1. Define binary tree and explain its proper es.

2. Write algorithms for preorder, inorder, and postorder tree traversal (recursive and
stack-based).

3. What is a binary search tree? Write an algorithm to search, insert, and delete in a
BST.
4. What are AVL Trees? Men on their advantages over normal BSTs.

5. Define B-trees. Where are they used?

UNIT IV: Graphs

1. Define a graph and explain its types (simple, directed, mul graph, weighted).

2. Explain the adjacency matrix and adjacency list representa ons of graphs.

3. Write an algorithm for BFS and DFS traversal.

4. What is a spanning tree? How is it different from a graph?

5. Discuss applica ons of graphs in real-world scenarios (e.g., networking, maps).

UNIT V: Sor ng and Searching

Sor ng Algorithms:

1. Write the algorithm and analyze me complexity of:

o Bubble Sort

o Inser on Sort

o Selec on Sort

o Quick Sort

o Merge Sort

2. Compare all sor ng algorithms based on me and space complexi es.

Searching Algorithms:

1. Differen ate between linear search and binary search with examples.

2. Write C code to implement binary search.

3. What is hashing? Explain different hashing techniques (e.g., chaining, open

4. What are the advantages of hash tables over arrays?

Frequently Asked Programming Tasks

1. Implement a stack using arrays and linked list.

3. Write a program to traverse a binary tree using inorder traversal.

4. Write a program to convert infix to pos ix expression.

5. Implement BFS and DFS on a graph using adjacency list.

UNIT-WISE IMPORTANT QUESTIONS

UNIT I – Introduc on to Data Structures and Algorithms

1. Define data structure. What are its types?

2. Differen ate between primi ve and non-primi ve data structures.

3. What is an algorithm? Explain characteris cs of a good algorithm.

4. Define me and space complexity with suitable examples.

5. Explain Big O, Ω (Omega), and Θ (Theta) nota ons with graphs.

6. What is the me-space tradeoff?

UNIT II – Arrays, Linked Lists, Stacks and Queues

Arrays:

1. What is a linear array? How is it stored in memory?

2. Derive the formula for address calcula on in row-major and column-major order.

3. What are sparse matrices? How are they stored?

Linked Lists:

4. What is a linked list? Explain different types with diagrams:

o Singly linked list

o Doubly linked list

o Circular linked list

5. Write algorithms for inser on and dele on in a singly linked list.

6. What is garbage collec on? How is it related to linked lists?

7. What is a stack? Write opera ons using arrays and linked lists.

8. Convert an infix expression to pos ix. Example: (A + B) * (C - D)

9. Evaluate a pos ix expression using a stack.

10. What is a queue? Differen ate between:

o Simple Queue

o Circular Queue

o Priority Queue

o Dequeue (Double-ended queue)

UNIT III – Trees

1. Define binary tree and explain its proper es.

2. Explain:

o Preorder traversal

o Inorder traversal

o Postorder traversal

3. What is a binary search tree (BST)? Write algorithms for:

o Inser on

o Searching

o Dele on

4. Define AVL Tree. What are its advantages?

5. Write a short note on:

o M-ary Trees

o B-Trees (defini on only)

UNIT IV – Graphs

1. Define graph and its types (directed, undirected, mul graph).

2. Differen ate between adjacency matrix and adjacency list.

o Breadth-First Search (BFS)

o Depth-First Search (DFS)

4. What is a spanning tree?

5. Explain inser on and searching opera ons in graphs.

UNIT V – Sor ng and Searching

Sor ng:

1. Explain the working of:

o Bubble Sort

o Inser on Sort

o Selec on Sort

o Quick Sort

o Merge Sort

2. Compare all sor ng algorithms by me and space complexity.

Searching:

3. What is linear search? How does it work?

4. Explain binary search with a step-by-step example.

5. What is hashing? Explain:

o Hash func ons

o Collision resolu on techniques (e.g., chaining, open addressing)

Extra Tips for Exams:

 Prac ce code for linked list, stack, queue, tree traversal, and sor ng.

 Understand and draw diagrams of trees, linked lists, and graphs.

 Revise complexity analysis of all sor ng algorithms.

 Focus on wri ng clean algorithms or C code for basic opera ons.

BCA – Semester II

Subject: Data Structures (BCAT 006)

Time: 3 Hours | Maximum Marks: 70

Instruc ons:

 A empt any FIVE ques ons.

 All ques ons carry equal marks.

 Illustrate your answers with neat diagrams and examples where necessary.

Q1. (a) Define data structure. Explain the classifica on of data structures with
examples.

(b) Explain asympto c nota ons – Big O, Omega (Ω), and Theta (Θ) with graphical examples.
(7 + 7 = 14 marks)

Q2. (a) Explain how linear arrays are stored in memory.

(b) Derive the address calcula on formula for 2D arrays in row-major and column-major
order.
(c) Write a program to insert an element in an array at a given posi on.
(4 + 4 + 6 = 14 marks)

Q3. (a) What is a linked list? Explain types of linked lists with diagrams.

(b) Write an algorithm to delete a node from a singly linked list.

Q4. (a) Define a stack. Explain array and linked list implementa on of stack.
(b) Convert the infix expression (A + B) * (C - D) into pos ix and evaluate it using stack.
(7 + 7 = 14 marks)

Q5. (a) Define a binary search tree (BST). Write an algorithm for inser on in BST.

(b) Perform inorder, preorder, and postorder traversal on the following tree:

markdown

CopyEdit

10

/ \

5 15

/\ \

3 7 20

(6 + 8 = 14 marks)

Q6. (a) What is a graph? Explain adjacency matrix and adjacency list representa ons.

(b) Write BFS and DFS traversal algorithms.

Q7. (a) Write and explain bubble sort and quick sort algorithms with examples.

(b) Compare selec on sort, inser on sort, and merge sort based on me complexity.
(8 + 6 = 14 marks)

Q8. (a) What is hashing? Explain any two collision resolu on techniques.

(b) Write an algorithm for binary search and explain it with an example.
(6 + 8 = 14 marks)