www.padeepz.

net

EC8393 FUNDAMENTALS OF DATASTRUCTURES IN C

t
ne
UNIT I C PROGRAMMING BASICS
Structure of a C Program-compilation and linking processes-Constants, variables-Data Types-

.
Expressions using operators in C-Managing input and output operations-Decision making and

pz
branching-Looping statements. Arrays-Initialization-Declaration-One dimensional and two
dimensional arrays-Strings-String operations-String Arrays-Simple programs-sorting-searching-
matrix operation

ee PART-A
Q. BT
No Questions Level Competence
Distinguish between high level language and low level
1 BTL -4 Analyzing
language.
2 Compare the Compiler and Interpreter. BTL -2 Understanding
ad
3 Define programming language. BTL -1 Remembering
4 Tell the use of return type of printf() & scanf(). BTL -1 Remembering
Assess what operation is performed when the %f, %e and %g
5 BTL -5 Evaluating
format specifies are used to display the value.
6 What is a variable? BTL -1 Remembering
.p

Compare and contrast the prefix and postfix forms of the ++

7 BTL -2 Understanding
operator.
8 Distinguish the terms Break and Continue. BTL -4 Analyzing
w

9 Name the use of EOF. BTL -1 Remembering

10 Explain the various form of looping statement. BTL -5 Evaluating
11 Create a C code to print the text “Data Structures” using the arrays. BTL -6 Creating
Write the syntax of array declaration with an example. BTL -3 Applying
w

12
13 Identify the purpose of null statement. BTL -3 Applying
14 Analyze the need of null character at the end of string. BTL -4 Analyzing
15 Discuss the types of I/O statements available in C. BTL -6 Creating
w

16 How would you initialize the size of an array. BTL -1 Remembering

17 Show the declaration of a string. BTL -2 Understanding
18 Identify the features of array. BTL -3 Applying
19 Show the c code that narrates the difference between do-while BTL -2 Understanding

www.padeepz.net
 www.padeepz.net

and while loop.

Write a program using conditional operators to determine
20 BTL -1 Remembering
Whether a year entered is leap year or not.

PART-B
Q.

t
No Questions BT Level Competence

ne
1 Explain the constants, expressions and statements in C. (13) BTL -2 Understanding
2 i ) Compare various types of operators in C. (6)
BTL -4 Analyzing
ii) List and explain the various data types in C (7)
3 Describe the structure of a C program with an example. (13) BTL -1 Remembering
4 i) Write a Program to find the area and circumference of a

.
circle with radius r. (6) BTL -1 Remembering

pz
ii) Write a program to find the sum of first 100 integers. (7)
5 i) Write a C program to find whether the given year is leap
year or not. (7)
BTL -1 Remembering
ii) Write a C program to find whether the given number is
palindrome or not using C.
ee (6)
6 Compose a program to narrate about ‘for’, ‘while’ and ‘do
BTL -6 Creating
while’ looping statements. (13)
7 i) Assess C code for the reverse of a number. (7)
ii) Write a C program to determine the roots of quadratic BTL -5 Evaluating
equation. (6)
ad
8 i) Summarize the need of array variables. Describe it with
respect to arrays. Declaration of array & initialization. (6)
BTL- 2 Understanding
ii) Demonstrate a Program to reorder a one dimensional
array. (7)
9 What is a two dimensional array explain its initialization? (13) BTL -1 Remembering
.p

10 i) Develop a C program for performing Matrix operations. (6)

ii) Identify and explain the various ways of reading and BTL- 3 Applying
writing string in c. (7)
11 Distinguish Two dimensional and one dimensional array and
w

BTL- 4 Analyzing
explain it with example. And initialize it with example. (13)
12 Write and explain a C program to find the given number is
BTL-2 Understanding
palindrome or not without using string function. (13)
w

13 Write Short note on the following with examples

i) String and character array . (6) BTL -3 Applying
ii) String input & output. (7)
w

14 Analyze the various string functions with example. (13) BTL -4 Analyzing

PART-C
Q. Questions BT Level Competence

www.padeepz.net
 www.padeepz.net

No
1 Explain the terms keywords, identifiers, character set, constants and
BTL -5 Evaluating
variables along with examples. (15)
2 Develop a C program for the following:
i) To find the area and circumference of the circle. (7) BTL-6 Creating
ii) To find the sum of 100 integers. (8)

t
3 Examine the working of various string functions such as BTL -4 Analyzing

ne
strlen(),strcpy(),strcat(),strcmp(). (15)
4 Formulate a C program to search an element from an array. (15) BTL-6 Creating

.
UNIT II FUNCTIONS,POINTERS,STRUCTURES AND UNIONS

pz
Functions-Pass by value-Pass by reference-Recursion-Pointers-Definition-Initialization-Pointers
Arithmetic-Structures and unions-definition-Structure within a structure-Union-Programs using
structures and unions-Storage class-Preprocessor directives.

ee PART-A
Q. BT
No Questions Level Competence
1 Define the term user-defined function BTL -1 Remembering
2 Support your views on a function call with example. BTL -5 Evaluating
Invent the meaning of default arguments and command line
ad
3 BTL -6 Creating
arguments.
4 Develop the function declaration and definition with example. BTL -3 Applying
5 List out the use of library function. BTL -1 Remembering
6 Show the declaration of pointer along with definition. BTL -2 Understanding
.p

7 What is pointer arithmetic? BTL -1 Remembering

8 Define void pointer and null pointer. BTL -1 Remembering
9 Examine the term recursive function. BTL -4 Analyzing
10 Evaluate the meaning of function pointer. BTL -5 Evaluating
w

11 What is term structure? BTL -1 Remembering

12 Perform various operations that make use of structure. BTL -3 Applying
13 Find the use of operator on structure. BTL -1 Remembering
w

14 Distinguish Structure and array. BTL-4 Analyzing

15 Illustrate the need of typedef. BTL -2 Understanding
16 Apply your view on the term Union in C BTL -3 Applying
w

17 Discuss the operators used to access the structure members. BTL -6 Creating
18 Extend your views about malloc and calloc. BTL -2 Understanding
19 Compare the types of memory allocation. BTL -4 Analyzing
20 Summarize on initializing Unions. BTL -2 Understanding

www.padeepz.net
 www.padeepz.net

PART-B
Q.
No Questions BT Level Competence
1 i) Interpret function declaration and function definition. (6)
BTL -2 Understanding
ii) Summarize examples for the above. (7)
2 i) Compose a C program on computation of Sine series. (6)

t
BTL -6 Creating
ii) Formulate the applications of recursive function. (7)

ne
3 Analyze and write a C program to demonstrate the scientific BTL -4 Analyzing
calculator using built-in functions. (13)
4 List out the operations performed by pointers with example.
BTL -1 Remembering
(13)
5 Explain in detail about i) Array of pointers. (6)
BTL -2 Understanding

.
ii) Passing arrays to functions. (7)

pz
6 i) What is fixed argument functions? Explain. (6)
ii) What is a variable argument function? Explain. (7) BTL -1 Remembering
7 i) Criticize on changing the value of a variable using pass by
reference. (6) BTL-5 Evaluating
ii) Evaluate the program for swapping of two numbers. (7)
8 i) Develop the code for preparing student mark statement.
ee (6)
ii) Build your understanding about functions and structures. (7)
BTL- 3 Applying
9 Explain the structure with data member of various types and declare
two structure variable. Write a program to read data into these and BTL -2 Understanding
print the same. Define structure. (13)
10 Examine about structures and its operations. (13) BTL -4 Analyzing
ad
11 i) Tell about self-referential structures. (6)
ii) Define the process of accessing the structure member through BTL -1 Remembering
pointer using dynamic memory allocation. (7)
12 i) When is array of pointers used in structure? Narrate it. (6)
BTL- 1 Remembering
ii) Show how to use Union inside structure with example. (7)
.p

13 i) Apply your understanding on preparing a code for employee

payroll. (6) BTL- 3 Applying
ii) Develop the need of structured data type. (7)
14 Distinguish Unions and structures along with programming
BTL- 4 Analyzing
w

examples. (13)

PART-C
Q.
w

No Questions BT Level Competence

1 Explain a C program to implement employee payroll of a company
along with explanation. (15)
BTL -5 Evaluating
w

2 Develop a C program for the following:

i) To sort the given N names. (7) BTL-6 Creating
ii) To show the recursive function. (6)
3 Examine nested structures with a sample C program of your own
example. (15)
BTL -4 Analyzing

www.padeepz.net
 www.padeepz.net

4 Formulate a C program to read the details of the book name, author

name and price of 200 books in a library and display the total cost in BTL-6 Creating
your own terms. (15)

t
ne
UNIT III LINEAR DATA STRUCTURES

Arrays and its representation-Stacks and Queues-Linked list-Linked list based implementation of
Stacks and queues-Evaluation of Expression-Linked list based polynomial addition.

.
pz
PART-A
Q. BT
No Questions Level Competence
1 Where do we use data structures how it is classified? BTL -1 Remembering
2 Name ADT operations.
ee BTL -1 Remembering
3 Summarize linear data structures and Nonlinear data structures. BTL -2 Understanding
4 List the different types of linked list. BTL -1 Remembering
5 Contrast between array and linked list BTL -2 Understanding
6 Analyze the term single linked list. BTL -4 Analyzing
7 How to create a new node, give with an example? BTL -3 Applying
ad
8 Discuss the use of header pointer and null pointer. BTL -6 Creating
9 Apply your understanding about dummy header. BTL -3 Applying
10 Develop the circular linked list. BTL -3 Applying
11 Define push and pop operations BTL -1 Remembering
12 When did you use the stack in computer system? BTL -1 Remembering
.p

13 Compare stack and queue. BTL -5 Evaluating

Examine the conditions that are followed in the array
14 BTL -4 Analyzing
implementation of queue.
15 Compare and contrast stack and queue and give its application. BTL -2 Understanding
w

16 Analyze any two data structures used in operating system. BTL -4 Analyzing
17 Write about prefix, infix and postfix notations. BTL -1 Remembering
Compose the following expressions into postfix and prefix forms.
BTL -6 Creating
w

18
A+B*(C-D)(P-R).
19 Evaluate the value of the expression ab+c*d using stack. BTL -5 Evaluating
20 Show how ADT representation is used to evaluate arithmetic
BTL -2 Understanding
w

expression?

PART-B

www.padeepz.net
 www.padeepz.net

Q.
No Questions BT Level Competence
1 Explain array based implementation of list with example. (13) BTL -2 Understanding
2 Discuss in detail about linked list ADT with example. (13) BTL -6 Creating
3 List and explain the Queue ADT operation for insertion and deletion
routine in linked list. (13)
BTL -4 Analyzing

t
4 i) Write the concept of pointer implementation and cursor

ne
implementation. (6)
ii) Show a function to test whether a linked list is empty using BTL -1 Remembering
cursor implementation. (7)
5 i) Give the outline about the application of stack. (6)
BTL -2 Understanding
ii) Explain in detail about Circular linked list. (7)

.
6 (13) BTL -1
Describe about the implementation stack using linked list. Remembering

pz
7 Access the ADT operation for insertion and deletion routine in stack using
array implementation. (13)
BTL-5 Evaluating
8 Develop the array and linked list implementation of queue operation .(13) BTL- 3 Applying
9 i) Outline the applications of queue. (6)
ii) Compare stack and queue. (7) BTL -2 Understanding
10

11
(13)
ee
Analyze and evaluate the postfix expression 2 4 + 3 * 1 5 - 8 3 + * -.

Write a procedure to convert an infix expression a+b*c+(d*e+f)*g

BTL -4 Analyzing

BTL -1 Remembering
postfix notation. (13)
12 i) List the process of postfix valuation with an example. (6)
BTL- 1 Remembering
ad
ii) List and define the balancing symbols with example. (7)
13 Develop the process of conversion from infix expression to postfix using
stack. (13)
BTL- 3 Applying
14 Examine an algorithm to add and subtract two polynomials P1 and
P2. (13)
BTL- 4 Analyzing
.p

PART-C

Q.
w

No Questions BT Level Competence

1 Recommend a suitable c code to swap two adjacent elements by
adjusting only the pointers using:
BTL -5 Evaluating
w

a. Singly linked lists. (7)

b. Doubly linked lists. (8)
2 A deque is a data structure consisting of a list of items, on which the
w

following operations are possible:

Push (X,D): Insert item X on the front end of deque D. BTL-6 Creating
Pop(D): remove the front item from deque D and return it.
Inject(x,D): Insert item X on the rear end of deque D.

www.padeepz.net
 www.padeepz.net

Eject(D): Remove the rear item from deque that take O(1)
time per operation.

Combine the above mentioned operations and write a C code to

formulate deque operations.
(15)

t
ne
3 Examine an algorithm to implement Queue ADT. Give
BTL -4 Analyzing
relevant examples and diagrammatic representation. (15)
4 Design an algorithm to convert an infix expression to postfix
expression using stacks and apply to the expression (a+b- BTL-6 Creating
d*e+(f*g+h)*i). (15)

.
pz
UNIT IV NON- LINEAR DATA STRUCTURES

Trees-Binary Tree-Binary tree representation and traversal-Binary search tree-Application of

trees-Set representations-Union Find operation-Graph and its representation-Graph Traversal
ee PART-A
Q. BT
No Questions Level Competence
1 Compose the term height and depth of the tree. BTL -6 Creating
ad
2 Identify the number of trees possible with 3 nodes? BTL -3 Applying
3 Define Binary tree and list its properties? BTL -1 Remembering
4 What are the two methods of binary tree implementation? BTL -1 Remembering
5 Identify the differences between binary search with linear search. BTL -3 Applying
6 List the applications of binary tree. BTL -4 Analyzing
.p

7 Assess the different type of tree traversal. BTL -5 Evaluating

8 Name the type of binary tree. BTL -1 Remembering
9 Compose the term equivalence relation. BTL -6 Creating
w

10 Explain about union operation. BTL -2 Understanding

11 Label the different types of union. BTL -1 Remembering
12 Define Graph and Acyclic graph. BTL -1 Remembering
w

13 Compare and contrast in-degree and out degree of the graph. BTL -4 Analyzing
14 Construct an acyclic graph. BTL -3 Applying
15 List the different ways of representing graph. BTL -1 Remembering
w

16 Analyze the two traversal strategies used in traversing graph. BTL -4 Analyzing
17 Illustrate the Differences between path and Cycle of the graph. BTL -2 Understanding
18 Compare DFS and BFS. BTL -2 Understanding
19 Explain the tree and graph. BTL -2 Understanding

www.padeepz.net
 www.padeepz.net

20 Access about connected components. BTL -5 Evaluating

PART-B

t
Q.

ne
No Questions BT Level Competence
1 Write short note on the following terms related to tree:
i) Path (2)
ii) Degree (3)
iii) Level (2) BTL -1 Remembering

.
iv) Leaves (2)

pz
v) Child (2)
vi) Height (2)
2 Apply your understanding to explain about binary search tree and
draw the binary search tree for the following input list 60,
ee BTL -3 Applying
25,75,15,50,66,33,44. Trace an algorithm to delete the nodes 25, 75,
44 from the tree. (13)
3 Examine the various tree traversal and predict a binary tree with BTL -4
Preorder:ABCDEFGHI and Inorder:BCAEDGHF . (13) Analyzing
4 Describe the two applications of tree with a neat example. (13) BTL -2 Understanding
ad
5 Conclude the types of tree traversal methods? Explain it with
BTL -5 Evaluating
example and deduce a routine for each of them. (13)
6 i) Illustrate your understanding by finding the inorder, preorder
and postorder form for the following graph: (7)
.p

BTL - 2 Understanding
w
w

ii) Show some applications of trees. (6)

7 Analyze in detail the implementation of Binary Search Tree and BTL - 4
perform its operations. (13)
Analyzing
8 i) Analyze and explain the dynamic equivalence problem. (6)
w

ii) Examine the path compression algorithm and analyze the BTL -4 Analyzing
Union/Find algorithm used. (7)
9 Describe in detail about the smart union algorithm. (13) BTL -1 Remembering

www.padeepz.net
 www.padeepz.net

10 Define graph. List out the different ways for representing the graph
BTL -1 Remembering
and explain them with example. (13)
11 i) Relate the following graph using breadth first search. (7)

t
ne
BTL - 1 Remembering

i) Write about BFS and DFS with suitable example. (6)

.
12 i) Develop the following graph using depth first search. (7)

pz
BTL - 3 Applying
ee
ii) Construct a C routine for BFS and DFS. (6)
13 Interpret in detail about BFS and DFS with suitable examples. (13) BTL -2 Understanding
ad
14 Compose an example in detail about connected component. (13) BTL -6 Creating

PART-C

Q.
.p

No Questions BT Level Competence

1 Consider the following graph:
i) Evaluate the shortest path from A to all other vertices for the
following graph: (6) BTL -5 Evaluating
w

ii) Access the shortest unweighted path from B to all other vertices
for the graph. (7)
w
w

www.padeepz.net
 www.padeepz.net

t
ne
2 Develop binary search tree and do the following operations.

.
i) Show the result of inserting 3,1,4,6,9,2,5,7 into an initially empty
(6) BTL-6 Creating

pz
binary search tree.
ii) Show the result of deleting the root. (7)

3 Examine graph and construct a graph by considering five cities

(1).New Delhi,(2).Mumbai,(3)Chennai,(4).Bangalore and
ee
(5).Kolkata and the list of flights that connects these cities are
shown below:
Flight No. Origin Destination
(13)

101 2 3
102 3 2
ad
103 5 3 BTL -4 Analyzing
104 3 4
105 2 5
106 5 2
107 5 1
.p

108 1 4
109 5 4
110 4 5
w

4 Formulate the term binary search tree and do the following

operations.
i) Show the result of inserting 3,1,4,6,9,2,5,7 into an initially
BTL-6 Creating
empty binary search tree. (6)
w

ii) Show the result of deleting the root. (7)

w

UNIT V SEARCHING AND SORTING ALGORITHMS

Linear Search-Binary Search, Bubble Sort, Insertion Sort-Merge sort-Quick sort-Hash tables-
Overflow handling

www.padeepz.net
 www.padeepz.net

PART-A
Q. BT
No Questions Level Competence
1 Explain about sorting. BTL -2 Understanding
Label the two main classifications of sorting based on the source of
2 BTL -1 Remembering

t
data.

ne
3 Analyze the applications of external and internal sorting. BTL -4 Analyzing
4 What is the purpose of quick sort. BTL -1 Remembering
5 Assess the advantage of merge sort. BTL -5 Evaluating
6 Define median three partitioning. BTL -1 Remembering
7 Compare divide and conquer technique with merge sort. BTL -2 Understanding

.
8 What is the purpose of insertion sort. BTL -1 Remembering

pz
9 Summarize about merge sort. BTL -2 Understanding
10 List the advantages of merge sort. BTL -1 Remembering
11 Analyze the key characteristics of binary search. BTL -4 Analyzing
12 Compare the linear search with binary search. BTL -2 Understanding
13 Name the techniques used to choose the pivot element for quick sort.
ee BTL -1 Remembering
Analyze the term hashing.
14 BTL -4 Analyzing
15 Identify the advantage of merge sort. BTL -3 Applying
16 Create algorithm for insertion sort. BTL -6 Creating
17 Support your views about insertion sort with example. BTL -5 Evaluating
ad
Trace the steps of insertion sort 12, 19, 33, 26, 29, 35, 22. Construct
18 BTL -3 Applying
the total number of comparisons made during sorting.
19 Identify the time complexity of quick sort and binary search. BTL -3 Applying
Plan and rearrange the following numbers 45, 22,6,77,47,8 using
20 BTL -6 Creating
.p

insertion sort.

PART-B
w

Q.
No Questions BT Level Competence
w

1 Illustrate the correct sequence 3, 1, 4,7,5,9,2,6,5 using Insertion sort

BTL -2 Understanding
with routine. (13)
2 Elaborate about insertion sort with example and code. (13) BTL -6 Creating
w

3 Analyze and explain an algorithm for quick sort with example. (13) BTL -4 Analyzing
4 Summarize quick sort algorithm and trace the following list of
numbers: 90,77,60,99,55,88,66, 10. (13)
BTL -1 Remembering
5 Explain Merge sort routine and trace the following numbers 1, 13,
BTL -2 Understanding
24, 26, 2, 15, 27, 38. (13)

www.padeepz.net
 www.padeepz.net

6 Show an algorithm for merge sort and give its worst case, best case
BTL -1 Remembering
and average case analysis. (13)
7 Evaluate the linear search & binary search algorithm in detail with
BTL-5 Evaluating
an example for each. (13)
8 i) Identify the differences between linear search algorithm and

t
binary search algorithm. (7) BTL- 3 Applying

ne
ii) Experiment it with an example. (6)
9 Explain C Program to implement the linear search technique with an
example. (13) BTL -2 Understanding
10 Analyze your view about bubble sort technique with suitable
BTL -4 Analyzing
example. (13)

.
11 Briefly tell about on Hashing and overflow handling. (13) BTL -1 Remembering

pz
12 Describe binary search algorithm and search the element 22 from the
given list 2,7,14,4,17,5,19,8,22,9,25,12,27,14,28,33. (13)
BTL- 1 Remembering
13 Develop the technique insertion sort for the following 9, 7, 6, 15, 16,
BTL- 3 Applying
5, 10, 2 5, 26, 18, 11 . (13)
14 Analyze the algorithm for
ee
i) Quick sort. (6) BTL- 4 Analyzing
ii) Insertion sort. (7)

PART-C
ad
Q.
No Questions BT Level Competence
1 i). Conclude how quick sort processes the input 142, 543, 123, 65,
453, 879, 572, 434, 111, 242, 811, 102. (7)
BTL -5 Evaluating
.p

ii). For the quick sort implementation, Estimate the running time
when all keys are equal. (8)
2 Given an array containing only 0s and 1s in sorted order. Create a strategy
using any of the sorting techniques to do the following:
w

a. Find the first occurrence of 1 in array. (5) BTL-6 Creating

b. Find the last occurrence of 0. (5)
c. Find number of instances of 0s in sorted array. (5)
w

3 Analyze and explain C code to implement Insertion sort. (15) BTL -4 Analyzing
4 Create a hash table of size 10.Using linear probing insert the keys
BTL-6 Creating
72,27,36,24,63,81,92,101 into the table. (15)
w

www.padeepz.net