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

Roll No.

Total No. of Questions : 18

Total No. of Pages : 02

--- Content provided by FirstRanker.com ---

B.Tech. (CSE) (2018 Batch) (Sem.-3)

DATA STRUCTURE & ALGORITHMS

Subject Code : BTCS-301-18

M.Code: 76436

Time: 3 Hrs.

--- Content provided by FirstRanker.com ---

Max. Marks : 60

INSTRUCTIONS TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.

--- Content provided by FirstRanker.com ---

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?

--- Content provided by FirstRanker.com ---

4. Evaluate below postfix expression.
   8 2 / 3 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.
   

   --- Content provided by FirstRanker.com ---

   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?

FirstRanker.com 1| M-76436

--- Content provided by FirstRanker.com ---

(S2)-284

SECTION-B

11. Solve the below recurrence relation using substitution method.
    T(n)=2T +C; n>1
    ;
    

    --- Content provided by FirstRanker.com ---

    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}
    

    --- Content provided by FirstRanker.com ---

    Hash function : (sum of all digits)% 13
15. Give the brief introduction to threaded Binary trees?

16. Graph data structure can be very cient in finding shortest path between two cities. Show with an example.
17. Explain:
    a) Difference between connected and unconnected graph.
    

    --- Content provided by FirstRanker.com ---

    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.

FirstRanker.com 2 | M-76436

(S2)-284

--- Content provided by FirstRanker.com ---