II/BCA/203 Student's Copy
2 0 1 8
CBCS
2nd Semester
BACHELOR OF COMPUTER APPLICATIONS
Paper No. BCA-203
Data Structure using C
Full Marks 75
Time 3 hours
PART A—OBJECTIVE
Marks 25
The figures in the margin indicate full marks for the questions
SECTION—I
Marks 15
1. Tick the correct answer in the brackets provided 1×10=10
The amount of memory used by an algorithm until it completes its
execution of a program is
time complexity
space complexity
dynamic programming
complexity of algorithm
/539 1 Contd.
All the automatic variables or local variables are stored in
stack
heap
permanent storage area
ROM
A pointer to a function is declared as
type *funptr()
type
type
type *funptr
Which of the following sorting techniques is inefficient when there are
more elements?
Bubble sort
Selection sort
Insertion sort
Quicksort
The time complexity of quicksort algorithm is
O
O (log
O n
O log
The postfix notation is also called
suffix notation
reverse Polish notation
Both and
Polish notation
II/BCA/203/539 2 Contd.
The queue which provides a means to insert and remove items at both
ends of the queue is
linear queue
circular queue
priority queue
deque
The linked list which has no null pointers, hence all pointers contain
valid address is
single-linked list
circular-linked list
double-linked list
All of the above
The number of edges for a tree with n vertices is
n
n
n

The number of edges for a complete graph with n nodes is
n
n
n
n
II/BCA/203/539 3 Contd.
2. Tick whether the following statements are True or False 1×5=5
A void pointer is a generic pointer that can represent any pointer type.
T F
In binary search technique, elements are eliminated by half in each
pass.
T F
Input-restricted deque allows insertion at both ends but allows
deletion at one end.
T F
The data items in the linked list are in consecutive memory location.
T F
BFS traversal algorithm uses a stack to keep track of vertices which
need to be processed.
T F
II/BCA/203/539 4 Contd.
SECTION—II
Marks 10
Answer the following questions 2×5=10
1. Define an abstract data type (ADT). Give one example.
2. Show how bubble sort processes the inputs
2
3. Transform the following infix expression to prefix expression

4. Define a linked list. What is the disadvantage of linked lists?
5. Write the properties of binary search tree.
PART B—DESCRIPTIVE
Marks 50
The figures in the margin indicate full marks for the questions
1. Answer the following questions
What is dynamic memory allocation? Explain the dynamic memory
allocation functions. 1+4
Define a data structure. Explain the concept for 'arrys of pointers' with
an example. 1+4
II/BCA/203/539 5 Contd.
OR
Define an algorithm. What is space and time complexity of an
algorithm? 1+3
What is a pointer? Explain the concept for 'pointer and function' with
an example. 1+5
2. Write the function code for implementation of linear search technique. 4
Write a C program for sorting a list of numbers in an array using
quicksort. 6
OR
Write a C program for implementation of binary search technique. 6
Write a C program for sorting a list of numbers in an array using
selection sort. 4
3. Write the functions code of push() and operations in a stack using
an array. 5
Evaluate the given postfix expression 5
6 5 2 3 8 3
using stack.
OR
Convert the given infix expression
A Ù
into postfix expression using stack. 5
Write the functions code of insert() and display() operation of an
ordinary queue. 5
4. Write the advantages of linked lists. 4
Write the functions code for inserting, deleting nodes at the beginning
of a single-linked list. 6
OR
What is the disadvantage of ordinary queue? How can you overcome
this disadvantage? 4
II/BCA/203/539 6 Contd.
Write the functions code for creating and displaying nodes of a circular
linked list. 6
5. Construct a binary tree from the given pre-order and in-order
sequence 5
Pre-order n1, n2, n3, n4, n5, n6, n7, n8, n9
In-order n6, n2, n1, n4, n3, n5, n9, n7, n8
What are depth-first search and breadth-first search of a graph?
Explain with a diagram. 5
OR
Traverse the following binary tree in pre-order, in-order, and
post-order. 5
Construct a minimal spanning tree for the graph shown below
starting at vertex 5