Download PTU. I.K. Gujral Punjab Technical University (IKGPTU) M.Tech. CSE 1st Semester 75154 ADVANCED DATA STRUCTURES Question Paper.

1 | M-75154 (S35)-1048

Roll No. Total No. of Pages : 01
Total No. of Questions : 08
M.Tech. (CSE Engg.) (2018 Batch) (Sem.?1)
Subject Code : MTCS-102-18
M.Code : 75154
Time : 3 Hrs. Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :
1.Attempt any FIVE questions out of EIGHT questions.
2.Each question carries TWELVE marks.

1. Write a C program or algorithm to :
a. Create a BST.
b. Display the node values in ascending order
c. Traverse from left to right crossing each level
d. Count the number of terminals and non terminals Explain how is a binary tree is
represented in memory?
2. a. What are recursive techniques and what are their disadvantages? How do various
compilers implement them internally? From where is memory allocated to recursive
algorithms?
b. How are recursive algorithms reformulated/converted into non recursive routines?
3. What is a hash function? How many hash functions are there that map from a source set of
size n to the integers from 1 to m? How many bits does it take to represent them? What if
the source set consists of character strings of length up to 20? Assume there are 100
possible characters.
4. What is a B+ tree? Consider a B+-tree in which the maximum number of keys in a node
is 7. What is the minimum number of keys in any non-root node?
5. Write Short notes on :
a. Standard and compressed tries
b. Strings operations
6. Write pseudo code for insertion, searching and deletion from a separate chaining hash
table. Explain with the help of example.
7. What is an expression tree? Write a program to create and evaluate an expression tree.
8. What are the recent trends in hashing? Explain with examples.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any