Download AKTU B-Tech 3rd Sem 2015-2016 NCS 301 Data Structures Using C Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2015-2016 NCS 301 Data Structures Using C Question Paper

Printed Pages: 4 ? 280 ? NCS-301
(Following Paper ID andRoll No. to be ?lled in your
Answer: Book)
Roll No.
B.Tech.
(SEM. III) THEORY EXAMINATION, 2015?16
DATA STRUCTURES USINGC
[Time:3 hours] [MaximumMarksleO
Section?A i
Q.1 Attempt all parts. All parts carry equal marks. Write
answer of each part in short (10X2=20)
(a)
(d)
(e)
.7 nodes?
Given a 2-D array A [-100:100,-5:50]. Find the
address of elementA [99,49] considering the base
address 10 and each element requires 4 bytes for
storage. Follow row major order.
What are the various asymptotic notations? Explain
the Bi g Oh notation.
What are the notations used in evaluation of
arithmetic expressions using pre?x and post?x
forms?
Clas'sify the hashing ?mctions? based on the various
methods by which the key value is found:
What is the maximum height of any AVL tree with
(1)

(f) If the Tower of Hanoi is operated on n=10 disks,
calculate the total number of moves.
(g) De?ne connected and strongly connected graph.
(h) Translate in?x expression into its equivalent post
?x expression: A*(B+D)/E?F*(G+H/K).
(i) For tree construction which is the suitable and
ef?cient data'structure and why?
(i) Explain the application of sparse matrices?
Section-B
Note: Attempt any five questions from this section.
(5 X 10=5 0)
\
2. Consider the linear arraysAAA[5:50], BBB[ -5: 10] and
CCC [1 :8]
a) F ind the number of elements in each array.
b) Suppose base (AAA).=300 and w=4 words per
memory cell for AAA. Find the address of
AAA[15],AAA[35] andAAA[55].
* 3. Describe all rotations in AVL tree. Construct AVL tree
from the followings nodes: B, C, G, E, F, D,A.
4. Explain binary search tree and its operatiOns. make a
binary search tree for the following sequence of numbers,
show all steps: 45, 32,90, 34,68, 72, 15,24, 30,66, 11, 50, 10.
(2)
Q8;
Explain Djiksatra?s algorithm with suitable example.
Write a C-Function for Linked List Implementation of I
stack. Write all the Primitive Operations. .
Draw a binary tree which following traversal:
Inorder: D B H EAl F .l C G
Preorder: ABDEHCFIJ G
Consider the following undirected graph.
F 17 E
a) Find the adjacency list representation of the graph.
b) F ind a minimum cost spanning tree by Kruskal?s
algorithm. ' I ?
O
(3) P.T.O.

How do you calculate the complexity of sorting
algorithms? Also write a recursive function in- ?C? to
implement the merge sort on given set of integers.
Section?C
Attempt any two questions from this section.
10.
11.
_ 12.
(2x15=30)
What are doubly- linked lists? Write a C program to create
doubly linked list.? '
OR
How do you ?nd the complexity of an algorithm? What
is the relation between the time and space complexities
of an algorithm? J ustify your answer with an example.
Write an algorithm for ?nding solution to the Tower of
Hanoi problem. Explain the working of your algorithm
(with 4 disks) with diagrams.
De?ne a B-Tree. What are the applications of B-Tree?
Draw a B-Tree of order 4 by insertion of the follOwing
keys in order: 2, U,A, I, w, L, P, X, C, J, D, M, T, B, Q, E,
H,$K,N,R,G,Y,F,0,V. ?
_x_.
(4) . _ 18000