JNTU
JNTU B.Tech IV DATA STRUCTURES Previous Question Paper (July/August - 2022 - R18)
Answer any five questions. All questions carry equal marks.
Main
What is a stack? Explain various operations performed on stack with sample Pseudo code and examples.
Answer
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed. It can be visualized as a vertical collection of elements where insertion and deletion occur only at one end, known as the top.
The primary operations performed on a stack are:
- Push: Adds an element to the top of the stack. If the stack is full, it results in a stack overflow condition.
- Pop: Removes and returns the top element of the stack. If the stack is empty, it results in a stack underflow condition.
- Peek (or Top): Returns the top element without removing it.
- isEmpty: Checks if the stack contains no elements.
Pseudo code for stack operations using an array:
if top == MAX-1 then error "Overflow"
top = top + 1
S[top] = x
Pop(S):
if top == -1 then error "Underflow"
x = S[top]
top = top - 1
return x
Example: Consider a stack of size 3. Initially, the stack is empty (top = -1).
1. Push(10): top becomes 0, stack = [10].
2. Push(20): top becomes 1, stack = [10, 20].
3. Pop(): returns 20, top becomes 0, stack = [10].
4. Push(30): top becomes 1, stack = [10, 30].
Write down the applications of stacks and queues.
Answer
Stacks and queues are fundamental data structures with distinct applications based on their LIFO (Last-In-First-Out) and FIFO (First-In-First-Out) properties, respectively.
Applications of Stacks:
- Expression Evaluation and Conversion: Used for converting infix expressions to postfix or prefix notations and evaluating postfix expressions.
- Function Call Management: The system stack stores activation records, return addresses, and local variables during recursive function calls.
- Undo Mechanisms: Text editors use stacks to keep track of operations to allow users to revert changes.
- Syntax Parsing: Compilers use stacks to check for balanced parentheses and matching tags in markup languages.
- Backtracking: Used in algorithms for solving puzzles like mazes or N-Queens.
Applications of Queues:
- CPU Scheduling: Operating systems use queues (e.g., Round Robin) to manage processes waiting for CPU time.
- Data Buffering: Used in IO buffers, such as printer spooling or keyboard input buffers, to handle asynchronous data transfer.
- Breadth-First Search (BFS): Queues are essential for traversing graphs or trees level by level.
- Message Queuing: Facilitates communication between different processes or systems in distributed computing.
- Resource Allocation: Managing shared resources where requests are served in the order they arrive.
Give the algorithm to perform search operation of an element in a linked list and explain the same.
Answer
Sign in to view the complete answer paper.
What is a dictionary? Explain skip list representation for implementing dictionary.
Answer
Sign in to view the complete answer paper.
What is hashing? Explain various hash functions.
Answer
Sign in to view the complete answer paper.
Illustrate linear probing and quadratic probing techniques with example.
Answer
Sign in to view the complete answer paper.
What are binary search trees? Explain insertion, deletion and search operations on binary search trees.
Answer
Sign in to view the complete answer paper.
What are Red-Black trees? Explain with examples.
Answer
Sign in to view the complete answer paper.
What are graphs? Explain various graph traversal techniques.
Answer
Sign in to view the complete answer paper.
Explain Knuth-Morris-Pratt pattern matching algorithm.
Answer
Sign in to view the complete answer paper.