R22
[Accredited by NAAC A+ & NBA, Approved by AICTE New Delhi & Permanently Affiliated to JNTUH]
Aziznagar Gate, ChilkurBalaji Road, Hyderabad - 500 075. Subject Code: A223504
II B Tech I SEMESTER REGULAR & SUPPLEMENTARY EXAMINATION, DEC/JAN-2024
Subject: Data Structures Time: 3 hours
Branch: CSE, IT, AI, CSE(AI-ML), CSE(DS), AI-DS Max. Marks: 60
Note: This Question Paper contains two Parts A and B. Answer all the questions.
Part A is compulsory which carries 10 marks. Ten questions from five units.
Part-B consists of 5 Questions (numbered from 11 to 15) carrying 10 marks each.
Bloom's Level:
Remember L1 Apply L3 Evaluate L5
Understand L2 Analyze L4 Create L6
PART-A Outcomes
BL Marks
ANSWER ALL THE QUESTIONS 10Q x 1M=10 Marks CO PO
1 What are the main operations performed on a stack? List the types of queues. 1 1 L1 1M
2 What is the definition of a stack, and how is it used in expression evaluation? 1 1 L1 1M
Compare array-based and linked-list-based representations of binary trees with
3 2 2 L2 1M
examples.
4 Explain the difference between preorder and inorder tree traversal with an example. 2 1 L2 1M
5 Define AVL tree. What is its primary purpose? 3 2 L1 1M
6 What are the key differences between a B-tree and a B+ tree? 4 2 L1 1M
7 What is the difference between a directed and an undirected graph? 4 1 L1 1M
8 Explain the role of the priority queue in Dijkstra’s algorithm for finding the shortest path. 5 2 L2 1M
9 Describe how linear probing works to resolve collisions. 5 1 L2 1M
10 What is rehashing in the context of hash tables? 6 1 L1 1M
PART-B
ANSWER ALL THE QUESTIONS 5Q x 10M = 50Marks
Given the infix expression (A+B) x C - D, apply the steps to convert it into both prefix
11 i) 1 1 L3 10M
and postfix notations using a stack.
[OR]
Demonstrate the insertion (enqueue) and deletion (dequeue) operations in a circular
queue with an example, starting from an empty queue of size 5. Show the queue status
ii) 1 1 L2 10M
after each operation: Enqueue 10, 20, 30, Dequeue, Enqueue 40, 50, Dequeue, Enqueue
60.
Analyze the advantages of using an extended binary tree to represent algebraic
12 i) 2 2 L4 10M
expressions. How does this representation help in simplifying expression evaluation?
[OR]
Construct a full binary tree from the following set of values:
ii) 2 1 L3 10M
[10, 20, 30, 40, 50, 60, 70]. Demonstrate how the tree evolves with each insertion.
Analyze the advantages and disadvantages of AVL Trees compared to Binary Search
13 i) 3 1 L4 10M
Trees (BST). When would you prefer one over the other?
[OR]
Consider a Binary Search Tree (BST) with the following elements:
ii) [15, 25, 10, 20, 30]. Analyze the tree's performance in terms of search operations when 3 2 L4 10M
it becomes unbalanced.
Given a graph with 6 vertices (A, B, C, D, E, F) and the following edges:
14 i) A-B, A-C, B-D, C-E, D-F, E-F, perform a breadth-first search (BFS) starting from 4 2 3 10M
vertex A. Show the order of traversal and explain how BFS works in this scenario.
[OR]
Make use of depth-first search (DFS) algorithm on a graph with vertices (1, 2, 3, 4, 5)
ii) and the following edges: (1, 2), (1, 3), (2, 4), (3, 5). Draw the DFS tree and demonstrate 4 1 L3 10M
the order in which vertices are visited.
15 i) Discuss hash functions and illustrate separate chaining and linear probing with example 4 2 L3 10M
[OR]
Design a hash table that uses double hashing for collision resolution. Insert the following
keys: 15, 23, 37, 44, 56. Discuss the choice of the secondary hash function and evaluate
ii) 5 2 L5 10M
how well double hashing handles clustering compared to other collision resolution
techniques.
***VJIT(A)***