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

Printed Pages: 4                                                                                            280 NCS-301

(Following Paper ID and Roll No. to be filled in your
Answer Book)

--- Content provided by FirstRanker.com ---

Paper ID :110301                                                                                                                Roll No.

B.Tech.

(SEM. III) THEORY EXAMINATION, 2015–16

DATA STRUCTURES USING C

[Time:3 hours]                                                                                                                       [MaximumMarks:100

--- Content provided by​ FirstRanker.com ---

Section-A

Q.1 Attempt all parts. All parts carry equal marks. Write answer of each part in short. (10×2=20)

1. Given a 2-D array A [-100:100,-5:50]. Find the address of element A [99,49] considering the base address 10 and each element requires 4 bytes for storage. Follow row major order.
2. What are the various asymptotic notations? Explain the Big Oh notation.
3. What are the notations used in evaluation of arithmetic expressions using prefix and postfix forms?

--- Content provided by FirstRanker.com ---

4. Classify the hashing functions based on the various methods by which the key value is found.
5. What is the maximum height of any AVL tree with 7 nodes? (1)
6. If the Tower of Hanoi is operated on n=10 disks, calculate the total number of moves.
7. Define connected and strongly connected graph.
8. Translate infix expression into its equivalent post fix expression: A*(B+D)/E-F*(G+H/K).

--- Content provided by FirstRanker.com ---

9. For tree construction which is the suitable and efficient data structure and why?
10. Explain the application of sparse matrices?

Section-B

Note: Attempt any five questions from this section. (5×10=50)

2. Consider the linear arrays AAA[5:50], BBB[ -5:10] and CCC [1:8]
   1. Find the number of elements in each array.

   --- Content provided by‌ FirstRanker.com ---

   2. Suppose base (AAA).=300 and w=4 words per memory cell for AAA. Find the address of AAA[15],AAA[35] and AAA[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.
5. Explain Djiksatra's algorithm with suitable example.

--- Content provided by FirstRanker.com ---

6. Write a C-Function for Linked List Implementation of stack. Write all the Primitive Operations.
7. Draw a binary tree which following traversal:
   Inorder: DBHEAIFJCG
   Preorder: ABDEHCFIJ G
8. Consider the following undirected graph.
   

   --- Content provided by‍ FirstRanker.com ---

   1. Find the adjacency list representation of the graph.
   2. Find a minimum cost spanning tree by Kruskal's algorithm.
9. 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. FirstRanker.com

Section-C

--- Content provided by FirstRanker.com ---

Attempt any two questions from this section. (2×15=30)

10. What are doubly linked lists? Write a C program to create doubly linked list.
    OR
    How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example.
11. Write an algorithm for finding solution to the Tower of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams.

--- Content provided by FirstRanker.com ---

12. Define 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: Z, U, A, I, W, L, P, X, C, J, D, M, T, B, Q, E, H, S, K, N, R, G, Y, F, O, V.

-X-