DSA 1 Semester Exam

 Q. Which notation is used to denote lower bound?

- The lower bound for an algorithm is denoted by the symbol Ω, called as omega.

Q. what are different asymptotic notations.
- There are three different notations: big O, big Theta (Θ), and big Omega (Ω).

-Q. Define omega (
) notation.
-Omega notation represents the lower bound of the running time of an algorithm.

Q. Define Theta notation.
- It represents upper and lower bound of an algorithm.

--Q. What are advantages of ADT?
-Advantages are:-
1. An ADT can be re-used at several places and it reduces coding efforts
2. Encapsulation ensures that data cannot be corrupted
3. ADT ensures a robust data structure


--Q. What is ADT ?
- Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations.

--Q. Define Data structure.
-A data structure is a specialized format for organizing, processing, retrieving and storing data.

Q. What are the component of space complexity?
-Space complexity is usually referred to as the amount of memory consumed by the algorithm. It is composed of two different spaces; Auxiliary space and Input space.

Q. Name the data structure used in recursion.
- Stack

Chapter 2: Array as a data structure.

1 mark

Q. State any two limitations of an array.

- Two limitations of an array are:

1) Fixed Size: Arrays have a fixed size, meaning that once they are created, their size cannot be changed dynamically.
2) Contiguous Memory Allocation: Arrays require contiguous memory allocation, which means that the elements of an array are stored in adjacent memory locations.

Q. What is worst and best time complexity of merge sort ?

- The worst and best time complexity of merge sort is O(n log n)

Q. What is time complexity of Quick Sort ?

- The average and best-case time complexity of Quick Sort is O(n log n), the worse is O(n^2).

Q. What is time complexity of bubble sort?

-The best-case time complexity of Bubble Sort is O(n). The average is O(n^2)

Q. Define stable sorting.

- Stable sorting refers to a sorting algorithm's ability to maintain the relative order of elements with equal values during the sorting process.

3 mark

-Q. What are the different ways of representing 2D arrays in memory? Give the formulae for address calculation. Explain with example.

Q. Write a short note on searching methods.

Q. Write an algorithm for binary search. Also state it's complexity.

5 mark

Q. Show all the steps of sorting the following data using quick sort. 26, 35, 24, 31, 11, 27, 19.

Q. Sort the following data using quick sort : 12, 24, 9, 46, 31, 53, 33.

Q. Sort the following elements using Insertion Sort (write passes) : 23, 6, 18, 29, 27, 4, 13.

Q. Sort the following numbers using insertion sort method: 30,40,10,50,25,35,15.

Q. Sort the following data using bubble sort : 13, 12, 14, 15, 19, 9.

Q. Sort the following data using bubble sort: 32, 51, 85, 66, 23, 13, 10, 57.

Chapter 3: Linked List.

 1 mark

Q. Explain node structure of SLL.

-The node structure of a singly linked list (SLL) typically includes two components: a data element and a next pointer. The data element holds the value or information that the node represents. The next pointer is a reference to the next node in the linked list.

Q. what is circular linked list.

- A circular linked list is a variation of a linked list in which the last node's next pointer points back to the first node instead of being null or empty. This creates a circular structure, where traversal can continue indefinitely in a loop.

Q. Write node structure for a Doubly Circular Linked List.

Q. Define node structure of singly linked list.

Q. “A Linked List can only be traversal sequentially”. State True/ False.

3 mark

-Q. Write a short note on generalized linked list.

5 mark

Q. Write a ‘C’ function to insert and delete an element at particular position in SLL

Q. Write a ‘C’ function to display even element (data) in a single linked list of integer.

-Q. Write ‘C’ function to reverse a linked list.

Chapter 4: Stack

1mark

Q. State the principle on which stack works.

Q. What are applications of stack?

-Q. List different operation of stack

Q. Consider operations performed on a stack push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop. What is the sequence of popped out values are ?

Q. What are the postfix and prefix forms of the expression

A + B * (C - D)/(P - R)

Q. Define stack.

Q. Define multiple stack.

3 mark

Q. Give the output of the following code. 

int i = 1, x, y

 init stack ( );

 while (i < = 5) 

{

 Push (i * 5); 

i = i + 1; 

} 

x = POP ( ); 

x = POP ( ); 

Push (i * 5); 

y = POP ( ); 

Push (x + y) 

x = POP ( ); 

y = POP ( ); 

Push (x + y); 

while (! stack empty ( )) 

Printf(“%d”, POP ( ));

Q. Give the output of the following sample code :  

initstack (s)

 push (s, 9); 

push (s, 4); 

i = pop (s); 

while (i > 0) 

{ 

 push (s, i*i); i – –; 

} 

while (! stack empty (s)) 

printf(“%d\n”, pop (s));

Q. Give output of the following code:

int i=1,x,y,z;

initstack();

while(i<3)

{

push(i*i);

i=i+1;

}

x=pop();

y=pop();

push(i*i);

2=pop();

push(x+y+z);

push(x*y);

while(!stack empty())

printf("\n %d",pop());

4  mark

Q.Consider given infix expression (u + v * w). Write its postfix expression. Also show steps to evaluate the postfix expression using stack. Given : u = 3, v = 4, w = 2

Q. Convert the following infix expression to postfix expression showing the contents of stack at each step :

(A + (B * C – (D/E
F) * G) * H)

Q. Evaluate the following expression using stack.

A + B * C - D

Given data : A=4, B=3, C=5, and D=1.

First convert expression to postfix.

5 mark

Q. Write a ‘C’ program to implement stack using singly linked list.

Q. Write a 'C' function to push and pop for stack using singly linked list.

Q. Convert the infix expression A * B $ C + D * E/F into postfix expression. Assume $ for exponentiation and has highest priority. 

Q. Convert the infix expression : A | B $ C + D * E – A * C to postfix notation show the stack contents.

Chapter 5: Queue

1 mark

Q. Define doubly ended queue.

Q. Write a statement to increment rear in a circular queue implemented using array.

Q. Define Double Ended Queue

Q. “A priority queue is implemented using array of stacks”. State True or False.

3 mark

--Q. Define Priority Queue. 

-Q. List the types of priority queue.

5 mark

Q. Write a ‘C’ Function to add and delete element from a linear queue (Dynamic implementation).

--Q. Write a ‘C’ function to ADD and REMOVE elements from circular queue implemented using array.

Q.Write a ‘C’ program to implement circular queue as an array.