DATA STRUCTURE USING C. QUESTION PAPER 2019

Sub Code: - 1618401

2019(Even)

Time : 3Hrs

      Semester  IV(New)       

  DATA STRUCTURE       

Full Marks : 70

Pass marks : 28

                                                                                                                                                          
 Group A

Choose the most suitable answer from the following options: -   (1*20=20)

(i) How do you initialize an array in C?
(a) int arr [3] =(1,2,3);
(b) int arr (3) ={1,2,3};
(c) int arr[3]= {1,2,3};
(d) int arr(3) =(1,2,3);

(ii) Which of the following concepts make extensive use of arrays?
(a) Binary tree
(b) Scheduling of processes
(c) Catching
(d) Spatial locality

(iii) What us the order of a matrix?
(a) number of rows x number of columns
(b) number of columns x number of rows
(c) number of rows x number of rows
(d) number of columns x number of columns

(iv) Process of inserting an element in stack is called______________
(a)Create
(b) Push
(c) Evaluation
(d)  Pop

(v) The data structure required to check whether an expression contains balanced parenthesis is? 
(a) Stack
(b) Queue
(c) Array
(d) Tree

(vi) Which data structure is needed to convert infix notation to postfix notation?
(a) Branch
(b) Tree
(c) Queue
(d) Stack

(vii) A linear collection of data elements where the linear node is given of pointer is called?
(a) Linked List
(b) Node List
(c) Primitive List
(d) None of the above

(viii) A linear list of elements in which deletion can be done from one end (front) and insertion can take place only  at the other end (rear) is known as: -
(a) Queue
(b) Stack
(c) Tree
(d) Link list

(ix) Which of the following is false about a doubly linked list?
(a) We can navigate in both directions 
(b) It require more space than a singly lined list
(c) The insertion and deletion of a node take a bit longer
(d) None of the mentioned 

(x)  What differentiates a circular linked list from normal linked list?
(a) You cannot have the next pointer point to null in a circular linked list
(b) It is faster to traverse the circular linked list
(c) You may or may not have the “next” pointer point to null in a circular linked list
(d) All of the mentioned

(xi) What is the complexity of searching for a particular element in a singly linked list?
(a) O (n)
(b) O (1)
(c) log n
(d) n log n

(xii) Binary trees can have how many children? 
(a) 2
(b) Any number of children
(c) 0 or 1 or 2
(d) 0 or 1

(xiii) What is the time complexity of pre-order traversal in the iterative fashion? 
(a) O (1)
(b) O (n)
(c) O (log n)
(d) ) O (n log n)

(xiv) Which of the following is false about a binary search tree?
(a) The left child is always lesser than its parent
(b) The right child s always greater than its parent
(c) The left and right sub tree should also be binary search tree
(d) None of the mentioned

(xv) What is an external sorting algorithm?
(a) Algorithm that uses tape or disk during the sort
(b) Algorithm that uses main memory during the sort
(c) Algorithm that involves swapping
(d) Algorithm that are considered in place

(xvi) Quick sort can be categorized into which of the following?
(a) Brute force technique
(b) Divide and conquer
(c) Greedy algorithm
(d) Dynamic programming

(xvii) What is the number of edges present in a complete graph having n vertices?
(a) (n*(n+1))/2
(b)(n*(n-1))/2 
(c) n
(d) Information gives in insufficient

(xviii) A connected planer graph having 6 vertices 7 edges contains ____________ regions
(a) 15
(b) 3
(c) 1
(d) 11

(xix) Depth first search is equivalent to which of the traversal in the Binary Tree
(a) Pre-order traversal
(b) Post-order traversal
(c) Level-order traversal
(d) In-order traversal

(xx) What would be the number of zero’s in the adjacency matrix of any given graph?
(a) 10
(b) 6
(c) 16
(d) 0

Group:-"B"

➥ Answer all Five Questions: -               (5*4=20) 

2. What is an array? How is it represented in memory?

OR

What do you mean by complexity? How it is useful.

3. Write formula to calculate address of element in three-dimensional array.

OR

Write difference between row major and column major.

4. Define pop operation on stack. When stack is said to be overflow?

OR

Give definition of infix, prefix, and postfix notation and Tail recursion.

5. What are the advantages and disadvantages of circular linked list?

OR

What are the advantages and disadvantages of doubly linked list?

6. What us pre-order and post-order traversal with example?

OR

What is in-order and post-order traversal with example?

Group:- "C"

➥ Answer all Five Questions: -                         (5*6=30) 

7. Explain selection sort algorithm with suitable example in detail.

OR 

Explain quick short algorithm using suitable example.

8. What is priority of queue? Write C program to implement priority queue using array? 

OR

Explain “Queue overflow” and “Queue underflow” error message with suitable example.

9. Discuss various operations that can be performed on a stack. Also discuss various applications on stack.

OR

Draw the binary tree to represent the following expression:
(5+4*(6-7)/(5+8))

10. Explain applications of linked stack and linked queue in detail.

OR

Convert following infix expression to prefix and postfix expression.

a.     (A+ B) * C – (D – E)* (F + G)

b.     (A + (B * C))

11. Explain two dimensional array. How two dimensional array can be represented in memory.

OR

Distinguish between best worst and average case complexities of an algorithm in detail.

              Thanks.