DipIETE – CS (NEW
SCHEME) - Code: DC54
Code: DC54 Subject:
DATA STRUCTURES
Time: 3 Hours
Max. Marks: 100
NOTE: There are 9 Questions
in all.
·
Question 1 is compulsory and carries
20 marks. Answer to Q.1 must be written in the space provided for it in the
answer book supplied and nowhere else.
·
Out of the remaining EIGHT Questions,
answer any FIVE Questions. Each question carries 16 marks.
·
Any required data not explicitly
given, may be suitably assumed and stated.
Q.1 Choose the correct or the best alternative
in the following: (2
10)
a. When the working storage variables get
allocated_______________.
(A) at compile time (B) at the starting of the runtime
(C) at the end of the
runtime (D) None of these
b. The recursive functions are evaluated using__________.
(A) stacks (B) queues
(C) priority queues (D) binary tree
c. Which
of the following types of expressions do not require precedence rules for
evaluation?
(A) Fully parenthesised infix expression.
(B)
Postfix expression.
(C) Partially parenthesised infix expression.
(D)
None of the above.
d. Which
of the following opens a file?
(A) fopen (B) fscanf
(C) open (D) None
e. The
number of comparision in bubble sort is___________.
(A) O(n)2 (B) O(n2)
(C) Both (A) & (B) (D) none of the
above
f. The
sorting technique where array to be sorted is partitioned again and again in
such a way that all elements less than or equal to partitioning element appear
before it and those which are greater appear after it, is called__________.
(A) merge sort (B) quick sort
(C) selection sort (D) none of these
g. If the characters 'D',
'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a
time, in what order will they be removed?
(A) ABCD (B) DCAB
(C) ABDC (D) DCBA
h.
A Linked list can grow and shrink in
size dynamically at__________.
(A) beginning (B) runtime
(C) ending (D) None of the Above
i. In
a comple binary tree, if the parent is at nth position, then the children will
be at________.
(A) n+1,n+2 (B) 2n,2n–1
(C) 2n,2n+1 (D) 2n+1, 2n–1
j. A
directed graph T without any cycles is called__________.
(A) a tree graph (B) a directed
acyclic graph
(C) connected graph (D) All of
above
Answer any
FIVE Questions out of EIGHT Questions.
Each
question carries 16 marks.
Q.2 a. Explain
different storage classes with an example for each and also explain scope and
life time of the variable. (8)
b. What
is stack overhead in recursion? Explain
with example how to calculate stack overheads in recursion. (8)
Q.3 a. Define:
(i) Nested structures (ii) Array of structure. Write a program by making use of
the above concept to store student information and display the same. (10)
b. Develop a C program to write
data of students such as name, roll number, marks in to a file. Further read
the data from the file and display it on the screen. (6)
Q.4 a. What
is an array? How it is represented in memory? Explain. (5)
b. Write
an algorithm/program to find transpose of given matrix. (5)
c. Derive the average, worst case time complexity
of quick sort. (6)
Q.5 a. Describe
the various operations of Stack. List its applications. (6)
b. Write
a C program to implement a stack of characters. (10)
Q.6 a. Write
C function to: (8)
(i) Insert a node in to a singly linked list by
using recursive program.
(ii) Delete a specified node in a singly linked
list.
b. Write
C functions for sorting and reversing a linked list. (8)
Q.7 a. Implement concatenation of two circular
singly linked lists List 1 and List 2. (8)
b. What
are the limitations of linear queue over the circular queue? (8)
Q.8 a. What is a tree? How it is different from
binary tree? Give the structure of a node of a binary tree. (6)
b. Write
C function for deleting a node from binary search tree considering all
possibilities.
(10)
Q.9 a. What is a graph? Give a diagramatic
representation of an adjacency list representation of a graph. (8)
b. What
is minimum spanning tree? Find the minimum spanning tree for the graph. (8)