III Semester

Course 6: Data Structures using C

Credits -3
Course Objectives
To introduce the fundamental concept of data structures and to emphasize the
importance of various data structures in developing and implementing efficient
algorithms.
Course Outcomes
Upon successful completion of the course, a student will be able to:
1. Understand various Data Structures for data storage and processing.
2. Realize Linked List Data Structure for various operations
3. Analyse step by step and develop algorithms to solve real world problems by
implementing Stacks, Queues data structures.
4. Understand and implement various searching & sorting techniques.
5. Understand the Non-Linear Data Structures such as Binary Trees and Graphs
UNIT-I
Basic Concepts: Algorithm-Definition and characteristics, Algorithm Analysis-Space
Complexity, Time Complexity, Asymptotic Notation.
Introduction to Data structures: Definition, Types of Data structures, Abstract Data Types
(ADT), Difference between Abstract Data Types, Data Types, and Data Structures.
Arrays-Concept of Arrays, Single dimensional array, two-dimensional array, Operations on
arrays with Algorithms (searching, traversing, inserting, deleting)
UNIT-II
Linked List: Concept of Linked Lists, Representation of linked lists in Memory, Comparison
between Linked List and Array, Types of Linked Lists - Singly Linked list, Doubly Linked
list,
Circularly Singly Linked list, Circularly Doubly Linked list;
Implementation of Linked List ADT: Creating a List, Traversing a linked list, Searching
linked list, Insertion and deletion into linked list (At first Node, Specified Position, Last
node), Application of linked lists
UNIT-III
Stacks: Introduction to stack ADT, Representation of stacks with array and Linked List,
Implementation of stacks, Application of stacks - Polish Notations - Converting Infix to Post
Fix Notation - Evaluation of Post Fix Notation, Recursive function evaluation
Queues: Introduction to Queue ADT, Representation of Queues with array and Linked List,
Implementation of Queues, Application of Queues ,Types of Queues- Circular Queue,
Priority Queue
UNIT-IV
Searching: Linear or Sequential Search, Binary Search and Indexed Sequential Search
Sorting: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort and Merge Sort
UNIT-V
Binary Trees: Concept of Non- Linear Data Structures, Introduction Binary Trees, Types of
Trees, Basic Definition of Binary Trees, Properties of Binary Trees, Representation of Binary
Trees, Operations on a Binary Search Tree, Binary Tree Traversal, Applications of Binary
Tree.
Graphs: Introduction to Graphs, Terms Associated with Graphs, Sequential Representation
of
Graphs, Linked Representation of Graphs, Traversal of Graphs (DFS, BFS), Application of
Graphs.
Text Books:
1. Horowitz and Sahani, “Fundamentals of Data Structures”, Galgotia Publications Pvt Ltd
Delhi India.
2. A.K. Sharma ,Data Structure Using C, Pearson Education India.
3. “Data Structures Using C” Balagurusamy E. TMH
Reference Books
1. “Data Structures through C”, Yashavant Kanetkar, BPB Publications
2. Rajesh K. Shukla, “Data Structure Using C and C++” Wiley Dreamtech Publication.
3. Lipschutz, “Data Structures” Schaum’s Outline Series, Tata Mcgraw-hill (India) Pvt. Ltd .
4. Michael T. Goodrich, Roberto Tamassia, David M. Mount “Data Structures and
Algorithms in C++”, Wiley India.
Blueprint for Data Structures using C

Total No of
Section Marks
Unit-1 Unit-2 Unit-3 Unit-4 Unit-5 questi questions
allotted
o ns answered
Short
Sectio n- Answer
2 2 2 2 2 10 5 5X 4=20
A Questio
ns
Essay
Sectio n-
Questio 2 2 2 2 2 10 5 5X8=40
B
ns

Total Marks = 60

In Section –B, for each question internal choice has to be given

II BSc (Computer Science) Semester -III
DATA STRUCTURES USING C
MODEL PAPER

Time : 3 hrs Total : 60 M

SECTION-A
Answer any FIVE of the following questions 5 X 4 = 20 M

1. Define ADT?

2. Explain about Time and Space complexity of an algorithm?

3. Explain different types of arrays?

4. Write an algorithm on Binary Search?

5. Explain about applications of Stack?

6. Explain representation of linked list in memory.?

7. Explain about Bubble sort algorithm?

8. Explain properties of Binary trees?

9. Explain sequential representation of graphs?

10. What is the application of graphs?

SECTION-B
Answer ALL the following questions 5 X 8 = 40 M

11. a) Explain in detail Linear Data Structures and Non-Linear Data

Structures?

OR
b) Explain insertion and deletion operation on arrays.
12. a) Define linked list? Explain types of linked lists with their representation.
OR
b) How to create and traverse a single linked list in c?
13. a) What is Stack? Explain operations on Stack?

OR
b) What is Circular Queue? Explain operations on Circular Queue?

14. a) Explain Insertion Sort algorithm with an example.

OR

b) Explain Merge Sort algorithm with an example.

15. a) Discuss in detail Binary Tree Traversal algorithms?

OR

b) What is Graph? Explain about BFS (Breadth First

Search) Traversal?
II BSc (Computer Science)
Semester- III
Question Bank

ESSAY QUESTION EACH QUESTION - 8 MARKS

1. Explain in detail types of datastructures.

2. Explain insertion and deletion operation on arrays.

3. Explain searching and traversing operation on arrays.

4. What is Stack? Explain about algorithms for push, pop display operations on
Stack using arrays?
5. What is Queue? Explain about algorithms for insertion, deletion display
operations on Queue using arrays?
6. What is Circular Queue? Explain about algorithms for insertion, deletion
display operations on Circular Queue using arrays?
7. What is Single Linked List? Write algorithms for insertion, deletion, display
operations on Single Linked List?
8. What is Double Linked List? Write algorithms for creation and display
operations on Double Linked List?
9. Explain about Bubble Sort Algorithm with example?

10. Explain about Quick Sort Algorithm with example?

11. Explain about Merge Sort Algorithm with example?

12. Explain about Insertion Sort Algorithm with example?

13. Explain about Selection Sort Algorithm with example?

14. Explain about Binary Search Algorithm with example?

15. What is Binary Tree? Explain about inorder, pre order and post order traversal
algorithms on Binary Tree ?

16. What is Binary search Tree ? Explain algorithms for creation and
insertion of node into Binary search Ttree ?
17. Explain about DFS(Depth First Search) algorithm on a Graph with example?

18. Explain about BFS( Breadth First Search) algorithm on a Graph with example
?

SHORT ANSWER QUESTION EACH QUESTION - 4 MARKS

1. What is Data structure and write about classification data structures?

2. What is Array ? write algorithm for linear Search operation on array?

3. Write short notes Priority Queue ?

4. Explain about advantages and disadvantages of Singly Linked List ?

5. Write algorithm for Linear search ?

6. Write algorithm for Selection sort ?

7. Write algorithm for Insertion sort ?

8. Explain about Linear Search algorithm example ?

9. Write short notes on Time/Space Complexity of an algorithm?

10. Write about Binary Tree representation methods?

11. What is Binary Search Tree ?

12. What is Directed Graph explain with example ?

13. Write Linked representation of Graphs.

14. Write sequential representation of Graphs.

15. Write the application of graphs.

III Semester
Course 6: Data Structures Using C Practical
Credits -1
List of Experiments:
1. Write a program to read ‘N’ numbers of elements into an array and also perform the
following operation on an array
a. Add an element at the beginning of an array
b. Insert an element at given index of array
c. Update an element using a values and index
d. Delete an existing element
2. Write Program to implement Single Linked List with insertion, deletion and traversal
operations
3. Write Program to implement doubly Linked List with insertion, deletion and
traversal operations
4. Write Programs to implement the Stack operations using an array
5. Write a program using stacks to convert a given infix expression to postfix
6. Write Programs to implement the Stack operations using Linked List.
7. Write Programs to implement the Queue operations using an array.
8. Write Programs to implement the Queue operations using Linked List.
9. Write a program for Binary Search Tree Traversals
10. Write a program to search an item in a given list using the following Searching
Algorithms
a. Linear Search
b. Binary Search.
11. Write a program for implementation of the following Sorting Algorithms
a. Bubble Sort
b. Insertion Sort
c. Quick Sort