Punjab University 2011-2nd Year B.C.A Computer Application Data Structure Using 'C', : - Question Paper

Questions:9 Roll No. ................
Sub Code:0893 Exam. Code:121

BCA-2nd Year
2041
DATA STRUCTURE USING 'C'

Time Allowed: 3 Hours Maximum Marks:90

Note:- Attempt 5 ques. in all. Attempt 1 ques. from every
Sections A, B, C and D.Question No. IX is compulsory.

SECTION-A

I. (a) What is a queue ? elaborate the operations that can be
performed on a queue ?

(b) Can Multiple stacks be housed in a single array ? If yes,
explain how.

(c) What is the advantage of housing a stack in a linked list ?
[Marks 6,6,6=18]

II. (a) Write a C program to implement the different operations on
a Single Linked list.

(b) Write an algorithm to evaluate arithmetic expressions using
stacks.[Marks 9,9=18]

SECTION-B

III. (a) Write functions in C to Insert and Delete a node from a
Binary Search Tree.

(b) How is an AVL tree various from a Binary tree ? How is
a node inserted in an AVL tree ?[Marks 9,9=18]

IV. (a) What is a Binary tree ? Write algorithm to implement different
operations on a Binary tree.

(b) Draw an example tree to show how deletion takes place in
a Binary tree.[Marks 12,6=18]

SECTION-C

V. (a) What is a graph ? How is it various from a tree ? discuss
one application of graphs in detail.

(b) Explain the BFS traversal of a graph with an example write
a 'C' function to implement it.[Marks 9,9=18]

VI. (a) What are the different ways in which graphs can be represented
in computer memory ? define their corresponding merits
and limitations.

(b) Use an example to discuss the concept of Depth-First graph
traversal.[Marks 12,6=18]

SECTION-D

VII. (a) Write algorithm of Bubble Sort. Show how it works for
sorting the subsequent list in ascending order:

90, 80, 10, 20, 40, 10

(b) Explain Binary Search Technique.[Marks 12,6=18]

VIII. What is the advantage of using the principle of Divide and Conquer
for sorting ? discuss any 2 algorithms which use this principle.
Show how both sort the subsequent list:

20, 40, 15, 60, 80, 11.

(Compulsory Question)

IX. (a) Define a data structure. What is its need ?
(b) Distinguish ranging from linear and non-linear data structures.
(c) What are the advantages of linked list in comparison to an
array ?
(d) What are abstract data kinds ? provide examples.
(e) Write an algorithm to insert a node in a circular queue.
(f) Draw a tree and write its INORDER Traversal.
(g) What is a complete binary tree ? How is its height
calculated ?
(h) For a graph define:
(i) Degree of a vertex
(ii) Path.
(i) What is Linear Search ?[Marks 9x2=18]

Earning:   Approval pending.