DipIETE – CS (NEW SCHEME)   –   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:                                  (210)

             a.  Dynamic memory allocation is done at

(A) compile time (B) run time

(C) link time (D) none

             b. Which one of the following statement is true with respect to recursion

(A) recursion increases the speed of execution                                                                   

                  (B) recursion decreases the speed of execution

(C) recursion is better than iteration      

                  (D) none

             c.  When does memory get allocated for a structure?

(A) When we define the variable of the structure                                                                

                  (B) When the variable of this structure is used in the program

(C) None of the options are correct     

                  (D) When we declare the structure name

             d.  What does SEEK_SET, SEEK_CUR and SEEK_END signify for the function fseek()?

(A) SEEK_SET : offset is relative to beginning of the file

SEEK_CUR : offset is relative to the current position in the file

                        SEEK_END : offset is relative to end of the file                                                           

(B) SEEK_CUR : offset is relative to beginning of the file

SEEK_SET : offset is relative to the current position in the file

                        SEEK_END : offset is relative to end of the file

(C) SEEK_END : offset is relative to beginning of the file

SEEK_SET : offset is relative to the current position in the file

(D) none

             e.  The complexity of merge sort algorithm is

(A) O(n) (B) O(log n)

(C) O(n²) (D) O(n log n)

             f.   For binary search, in what order should the data not be?

(A) Increasing (B) Decreasing

(C) Random (D) Sorted

             g.   __________ form of access is used to add and remove elements from a stack

(A) LIFO (B) FIFO

(C) Either (A) or (B) (D) None of the above

             h.  A _______ in a linked list is a structure that has at least two fields, one contains the data, the other a link.

(A) Pointer (B) Node

(C) Head pointer (D) Metadata

             i.   Which of the following trees is a valid binary search tree?

(A)                                                       (B) 

                  (C)                                                       (D) 

             j.   If every node u in G is adjacent to every other node v in G, the graph G is said to be

(A) isolated (B) complete

(C) finite (D) strongly connected                                         

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

  Q.2     a.   What is dynamic memory allocation? What are its merits? Explain any three functions that support dynamic allocation. (8)

             b.   What is recursion? Compare iteration with recursion. Write the recursive definition for the factorial of a number. (8)

Q.3     a.   Define a structure student consisting of name and marks as its members. Declare an array of structure for N students. Read the information about the students from keyboard. Write a function that displays the student information having highest marks among N students. (8)

b.   What is union? How is it different from structure?  With a suitable example show how union is declared and used in C. (8)

Q.4     a.   What is a heap? Write a ‘C’ program to sort an array of integers using the heap sort method. Also give the time complexity.                                   (10)

             b.   List the various searching techniques. Explain binary search with example.           (6)

  Q.5     a.   Write a C Program to simulate an ordinary queue using linked list.                       (8)

             b.   Develop a step by step algorithm or (C-program) to convert the given infix expression to prefix expression.                                                            (8)

Q.6     a.   What is a linked list? What are its advantages and disadvantages as compared to an array? Write a C program to reverse the given linked list.                                                              (8)

             b.   Write a C function to

                   (i)  count the number of nodes of a linked list

                   (ii) merge two sorted lists                                                                                   (8)

Q.7     a.   What is a circular queue?  What is the advantage of circular queue over ordinary queue?  Write the implementation of a circular queue using array.                                                    (8)

             b.   Write a C Program for creating and displaying the elements of a doubly linked list.              (8)

  Q.8     a.   Define the following

(i)   Binary tree                                   

                   (ii)  Full Binary tree

                   (iii) Almost Complete Binary tree

                   (iv)  Binary Search tree (8)

             b.   A Binary tree T has 9 nodes.  The inorder and preorder traversals of T yield the following sequences of nodes:

                   Inorder   : E A C K F H D B G

                   Preorder : F A E K C D H G B

                   Draw the tree T.                                                                                                (8)

Q.9     a.   What is a spanning tree?  Find all spanning trees of the graph G shown below:

(10)

             b.   Write a note on directed acyclic graph. (6)