JNTU
JNTU B.Tech II DATA STRUCTURES Previous Question Paper (August/September - 2022 - R18)
Answer any five questions. All questions carry equal marks.
Main
The following numbers 10, 20, 50, 30, 90, 60 (Top) are present in a stack of size 10. Perform the following operations in sequence: pop(), push(30), push(40), pop(), push(60), pop(), pop(), pop(). What is the peek element at last? Draw and explain it.
Answer
Initial stack (Top is 60): [10, 20, 50, 30, 90, 60].
- pop(): Removes 60. Stack: [10, 20, 50, 30, 90].
- push(30): Adds 30. Stack: [10, 20, 50, 30, 90, 30].
- push(40): Adds 40. Stack: [10, 20, 50, 30, 90, 30, 40].
- pop(): Removes 40. Stack: [10, 20, 50, 30, 90, 30].
- push(60): Adds 60. Stack: [10, 20, 50, 30, 90, 30, 60].
- pop(): Removes 60. Stack: [10, 20, 50, 30, 90, 30].
- pop(): Removes 30. Stack: [10, 20, 50, 30, 90].
- pop(): Removes 90. Stack: [10, 20, 50, 30].
The final stack is [10, 20, 50, 30], where 30 is at the top. The peek element is 30.
Implement a queue data structure using Single Linked list.
Answer
A queue implemented with a linked list uses two pointers: front (to dequeue) and rear (to enqueue). Each node contains data and a next pointer.
struct Node { int data; struct Node* next; };
struct Queue { struct Node *front, *rear; };
void enqueue(struct Queue* q, int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val; newNode->next = NULL;
if (q->rear == NULL) { q->front = q->rear = newNode; return; }
q->rear->next = newNode; q->rear = newNode;
}
int dequeue(struct Queue* q) {
if (q->front == NULL) return -1;
struct Node* temp = q->front;
int val = temp->data;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
free(temp); return val;
}Enqueue operation adds a node at the rear in O(1) time, and dequeue removes a node from the front in O(1) time.
The Professor Lilly is very strict in class room. She never gives the attendance to those who are coming last in her class. Write a function to help Professor to delete the last occurrence of a student from the list.
Answer
Sign in to view the complete answer paper.
Implement a stack data structure using Single Linked list.
Answer
Sign in to view the complete answer paper.
Explain how Insertion, Deletion and Search is done in skip lists with example.
Answer
Sign in to view the complete answer paper.
What is the expected number of probes for both successful and unsuccessful searches in a linear probing table with load factor 0.25?
Answer
Sign in to view the complete answer paper.
Given the input (4371, 1323, 6173, 4199, 4344, 9679, 19891), a fixed table size of 10, and a hash function H(X) = X mod 10, show the resulting quadratic probing hash table.
Answer
Sign in to view the complete answer paper.
Outline Double Hashing with an example.
Answer
Sign in to view the complete answer paper.
In an initially empty AVL tree insert the following keys: DEC, JAN, APR, MAR, JUL, AUG, OCT, FEB, NOV. Draw AVL tree after every insertion and apply rotations where ever necessary.
Answer
Sign in to view the complete answer paper.
Briefly discuss about different cases of imbalance that might be caused by a red-black tree insertion and corresponding methods to rebalance the tree.
Answer
Sign in to view the complete answer paper.
Construct Splay tree with the following node values: 18, 10, 5, 28, 13, 25, 42, 3, 56, 2, 68, 1, 90. And perform normal splaying at nodes 1 and at node 90.
Answer
Sign in to view the complete answer paper.
Explain insertion operation with following numbers into Red Black tree: 45, 10, 8, 9, 34, 35, 12, 60, 90.
Answer
Sign in to view the complete answer paper.
Assume a list containing 4500 records is to be sorted using a computer with internal memory capable of sorting at most 750 records at a time and input list is maintained on a disk that has block length of 250 records. For this scenario explain how external sorting may be performed to accomplish the task.
Answer
Sign in to view the complete answer paper.
Compare BFS and DFS with suitable examples.
Answer
Sign in to view the complete answer paper.
Solve the Boyer-Moore algorithm for the following Example:
Text: ABCABCDABABCDABCDABDE
Pattern: ABCDABD
Answer
Sign in to view the complete answer paper.
Solve the Knuth Morris-Pratt algorithm for the following Example:
Text: HEREISASIMPLEEXAMPLE
Pattern: EXAMPLE
Answer
Sign in to view the complete answer paper.