Download PTU B.Tech 2021 Jan CSE 3rd Sem 76436 Data Structure And Algorithms Question Paper

Download PTU (Punjab Technical University) B.Tech (Bachelor of Technology) / BE (Bachelor of Engineering) 2021 January CSE 3rd Sem 76436 Data Structure And Algorithms Previous Question Paper

Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (CSE) (2018 Batch) (Sem.?3)
DATA STRUCTURE & ALGORITHMS
Subject Code : BTCS-301-18
M.Code : 76436
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O CANDIDAT ES :
1 .
SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks
each.
2 .
SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents
have to atte mpt any FOUR q ues tions.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
have to atte mpt any T WO questio ns.
SECTION-A
Write briefly :
1.
Write at least three differences between linear and binary search.
2.
Write pseudo code to implement circular queue.
3.
Stacks are used to implement recursion in programming languages. Explain why?
4.
Evaluate below postfix expression.
2 3 2 ^ ^ 8 2 / / 5 2 * 6 ? +
5.
Write pseudo code to find maximum element in a singly linked list. Consider node in
linked list has `data' field storing an integer.
6.
Explain left and right rotations in an AVL tree.
7.
Create the BST after inserting following elements in order in an empty BST.
5, 6, 3, 2, 4, 7, 9, 1
8.
What is in-place sorting?
9.
What are stable sorting techniques?
10. What is Time complexity of quick sort in worst case? And why?
1 | M-76436
(S2)- 284

---

SECTION-B
11. Solve the below recurrence relation using substitution method.
n
2T
C
;
n 1
T n
2
1
;
n
1
12. Write pseudo code to implement queue using stack i.e. implement insert and delete
operation of queue using push and pop.
13. A queue can be implemented using single linked list in two ways. One implementation
has front at head and rear at tail of linked list. Other implementation has front at tail and
rear at head of linked list. Which implementation among two is efficient and why?
14. Create hash table of length 13 for the following keys entered in the same order using
below hash function. Linear probing is used to resolve collision.
Keys : {4684, 4879, 5651, 1829, 1082, 7107, 1628, 2438, 3951, 4758, 6967, 4989}
Hash function : (sum of all digits)% 13
15. Give the brief introduction to threaded Binary trees?
SECTION-C
16. Graph data structure can be very efficient in finding shortest path between two cities.
Show with an example.
17. Explain :
a) Difference between connected and unconnected graph.
b) Discuss pros and cons of Adjacency matrix representation of a graph.
18. How a multidimensional array is represented in memory? Explain the program which
reads two matrices?
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
2 | M-76436
(S2)- 284

---