PYQ – DATA STRUCTURES AND ALGORITHM (2418301) | SEMESTER 3RD (2ND YEAR) | Year 2022

Data Structure & Algorithm 2022 OLD PYQ.

Group A

 

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

(i) Which of the following is not component of data structure?

(a) Operations

(b) Storage structures

(c) Algorithms

(d) None of the above

(ii) _______ is a pile in which items are added at one end and removed from the other.

(a) Stack

(b) Queue

(c) List                                                                

(d) Tree

(iii) The number of elements in the adjacency matrix of a graph having 7 vertices is ______.

(a) 7

(b) 14

(c) 36

(d) 49

(iv) What would be number of zeros in the adjacency matrix of the given graph?

(a) 10

(b) 6

(c) 16

(d) 0

(v) In a stack, if a user tries to remove an element from an empty stack it is called ________.

(a) Underflow

(b) Empty collection

(c) Overflow

(d) Garbage collection

(vi) 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);

(vii) Which of the following concepts make extensive use of arrays? 

(a) Binary trees

(b) Scheduling of process

(c) Caching

(d) Spatial locality

(viii) What is the complexity of pre-order traversal in the iterative fashion?

(a) O(1)

(b) O(n)

(c) O(lgn)

(d) O(nlgn)

(ix) What is an external sorting algorithm?

(a) Algorithm that use tape or disk during sort.

(b) Algorithm that use main memory during sort.

(c) Algorithm that involve swapping.

(d) Algorithm that are considered in place.

 
(x) A connected planer graph having 6 vertices, 7 edges contains ________ regions.

(a) 15

(b) 3

(c) 1

(d) 11

 
(xi) The data structure required to cheek whether an expression contains a balanced parenthesis is _______.

(a) Stack

(b) Queue

(c) Array

(d) Tree

(xii) Which one of the following is an application of stack data structure?

(a) Managing function calls

(b) The stock span problem

(c) Arithmetic expression evaluation

(d) All of the above

(xiii) What is the order of a matrix?

(a) Number of rows × Number of columns

(b) Number of columns × Number of rows

(c) Number of rows × Number of rows

(d) None

(xiv) The postfix form of A *B+C/D is ?

(a) *AB/CD+

(b) AB *CD/+

(c) A *BC+/D

(d) ABCD+/*

 
(xv) The data structure required for Breadth first traversal on a graph is?

(a) Stack

(b) Array

(c) Queue

(d) Tree

(xvi) If the elements “A”, “B”, “C”, and “D” are placed in a queue and are deleted one at a time in what o will they be removed?

(a) DCAB  

(b) DCBA

(c) ABCD

(d) ABDC

(xvii) Which of the following is not a type of Queue?

(a) Ordinary queue

(b) Single ended queue

(c) Circular queue

(d) Priority queue

(xviii) Which of the following is non-linear data structure?

(a) Stack  

(b) Tree

(c) List

(d) Queue

(xix) How many passes dose an insertion sort-algorithm consist of?

(a) N

(b) N-1

(c) N+1

(d) N²

(xx) What is the average case running time of an insertion sort algorithm?

(a) O(n)

(b) O(nlgn)

(c) O(n²)

(d) O(lg)

 

Group:-"B"

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

 

2. Define time complexity and space complexity of an algorithm.

OR

How do you push elements in a linked stack? Explain with example.

 

3. Define complete binary tree. Give example.

OR

When does a graph become a tree? Explain with example.

 

4. What is sorting? How is sorting essential for database applications?  

OR

Discuss the worst case and best and case time complexity of binary search.

 

5. Solve the following :- a) ((A-(B+C)*D)/(E+F)) [Infix to postfix]

                                        b) (A+B)+C-(D-E)*F [Infix to postfix]

OR

Define pop operation on stack; when stack is said to be overflow?

 

6. What are the advantage and disadvantage of circular linked list? 

OR

Write formula to calculate address of an element in tow-dimensional and three-dimensional array.

 

 

Group:- "C"

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

 

7. Discuss the various operations that can be performed on a stack. Also discuss various application of    stack.

OR

Write a C-program to implement binary tree insertion, deletion with example.

 

8. Define quick sort. Sort the given values using quick sort:- 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72. 

OR

Discuss the concept of “Successor” and “Predecessor” in binary search tree.

 

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

OR

Define a recursion. Write a recursive program to calculate the factorial of a given number.

 

10. Draw a binary tree with following traversals:- In order: BCAEGDHFLJ Preorder: ABCDEGFHLJ  

OR

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

 

11. Define data structure. Discuss various application of data structure.

OR

Write short notes on:- a) Heap sort 

                                     b) Hashing technique.

 

 

*****