Exam Details
Subject | data structures and problem solving | |
Paper | ||
Exam / Course | m.tech | |
Department | ||
Organization | Institute Of Aeronautical Engineering | |
Position | ||
Exam Date | February, 2018 | |
City, State | telangana, hyderabad |
Question Paper
Hall Ticket No Question Paper Code: BCS002
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Regular) January/February, 2018
Regulation: IARE-R16
DATA STRUCTURES AND PROBLEM SOLVING
(Computer Science and Engineering)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Consider the code in Table 1 snippets. Derive the time complexity
Table 1
int count N 1000 int count N 1000
for (int i i for (int i i i
for (int j j for (int j j
Explain briefly stack data structure along with algorithms for push and pop operation.
2. Explain briefly array based internal representation of heap with a suitable example.
What is the space complexity of the following code? Justify your answer int sum(int int
int sum for(i i sum sum return sum;
UNIT II
3. Write algorithms for dictionary search and insertion using skip list.
Demonstrate the insertion of the keys 28, 19, 15, 20, 33, 12, 17, and 10 into a hash table with
collisions resolved by chaining. Let the table have 9 slots, and let the hash function be k
mod 9.
4. Describe linear probing and quadratic probing with suitable example.
Given the values 2341, 4234, 2839, 430, 22, 397, 3920, a hash table of size and hash function
x mod show the resulting tables after inserting the values in the given order with
each of these collision strategies: separate chaining, linear probing, quadratic probing and double
hashing
Page 1 of 2
UNIT III
5. Explain Depth First Search Method.
Assume that you have been given the following binary tree shown in Figure 1. Write Java function
to perform InOrder traversal of this tree using iterative and recursive approach.
Figure 1
6. Discuss Dijkstra's algorithm w.r.t data structure with a suitable example.
Use Kruskal's algorithm to find a minimum spanning tree of the given graph in Figure 2. Draw
the resulting spanning tree and list the edges in the order they are picked by Kruskal's algorithm.
Figure 2
UNIT IV
7. Outline the steps for searching an element in AVL tree.
Write two methods in Java to find the successor and predecessor of a given node. Assume that
a class Tree Node that represents nodes in the BST already exists.
8. Show result of inserting 7 into an empty AVL tree.
Design a class to find the Kth largest element in a Binary Search Tree.
UNIT V
9. What is B-Tree? List any four properties of B-Tree.
What is KNUTH-MORRIS-PRATT Algorithm? Outline the Algorithm
10. Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, and
8 into an initially empty red-black tree.
How text compression can be done using Huffman coding? Describe clearly.
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
M.Tech I Semester End Examinations (Regular) January/February, 2018
Regulation: IARE-R16
DATA STRUCTURES AND PROBLEM SOLVING
(Computer Science and Engineering)
Time: 3 Hours Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Consider the code in Table 1 snippets. Derive the time complexity
Table 1
int count N 1000 int count N 1000
for (int i i for (int i i i
for (int j j for (int j j
Explain briefly stack data structure along with algorithms for push and pop operation.
2. Explain briefly array based internal representation of heap with a suitable example.
What is the space complexity of the following code? Justify your answer int sum(int int
int sum for(i i sum sum return sum;
UNIT II
3. Write algorithms for dictionary search and insertion using skip list.
Demonstrate the insertion of the keys 28, 19, 15, 20, 33, 12, 17, and 10 into a hash table with
collisions resolved by chaining. Let the table have 9 slots, and let the hash function be k
mod 9.
4. Describe linear probing and quadratic probing with suitable example.
Given the values 2341, 4234, 2839, 430, 22, 397, 3920, a hash table of size and hash function
x mod show the resulting tables after inserting the values in the given order with
each of these collision strategies: separate chaining, linear probing, quadratic probing and double
hashing
Page 1 of 2
UNIT III
5. Explain Depth First Search Method.
Assume that you have been given the following binary tree shown in Figure 1. Write Java function
to perform InOrder traversal of this tree using iterative and recursive approach.
Figure 1
6. Discuss Dijkstra's algorithm w.r.t data structure with a suitable example.
Use Kruskal's algorithm to find a minimum spanning tree of the given graph in Figure 2. Draw
the resulting spanning tree and list the edges in the order they are picked by Kruskal's algorithm.
Figure 2
UNIT IV
7. Outline the steps for searching an element in AVL tree.
Write two methods in Java to find the successor and predecessor of a given node. Assume that
a class Tree Node that represents nodes in the BST already exists.
8. Show result of inserting 7 into an empty AVL tree.
Design a class to find the Kth largest element in a Binary Search Tree.
UNIT V
9. What is B-Tree? List any four properties of B-Tree.
What is KNUTH-MORRIS-PRATT Algorithm? Outline the Algorithm
10. Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, and
8 into an initially empty red-black tree.
How text compression can be done using Huffman coding? Describe clearly.
Other Question Papers
Subjects
- ac to dc converters
- advanced cad
- advanced concrete technology
- advanced data structures
- advanced database management system
- advanced mechanics of solids
- advanced reinforced concrete design
- advanced solid mechanics
- advanced steel design
- advanced structural analysis
- advanced web technologies
- big data analytics
- computer aided manufacturing
- computer aided process planning
- computer architecture
- computer oriented numerical methods
- cyber security
- data science
- data structures and problem solving
- dc to ac converters
- design for manufacturing and assembly
- design for manufacturing mems and micro systems
- design of hydraulic and pneumatic system
- distributed operated system
- earthquake resistant design of buildings
- embedded c
- embedded networking
- embedded real time operating systems
- embedded system architecture
- embedded system design
- embedded wireless sensor networks
- english for research paper writing
- finite element method
- flexible ac transmission systems
- flexible manufacturing system
- foundations of data science
- foundations of data sciences
- fpga architecture and applications
- hardware and software co-design
- high performance architecture
- intelligent controllers
- internet of things
- introduction to aerospace engineering
- mathematical foundation of computer
- mathematical methods in engineering
- matrix methods of structural analysis
- micro controllers and programmable digital signal processing
- multilevel inverters
- numerical method for partial differential equations
- power electronic control of ac drives
- power electronic control of dc drives
- power quality
- precision engineering
- principles of distributed embedded systems
- programmable logic controllers and their applications
- rapid prototype technologies
- rehabilitation and retrofitting of structures
- renewable energy systems
- research methodology
- soft computing
- special machines and their controllers
- stress analysis and vibration
- structural dynamics
- structural health monitoring
- theory of elasticity and plasticity
- theory of thin plates and shells
- web intelligent and algorithm
- wireless lan’s and pan’s
- wireless lans and pans
- wireless sensor networks