Data Structures & Algorithms BSSE/BSIT UOS — University of Sargodha
Discussion
Ask a question about this paper, or help someone else with theirs. Answers are emailed to whoever asked.
No questions yet — be the first to ask.
Paper text
Department of Computer Science and IT
University of Sargodha
Final Term Exam: Data Structure and Algorithms
Class: BSSE (R) , BSSE (S), BSIT (ss1), BSIT (ss2)
Marks: 60
Time: 2 hours
1. Specify the ADT of Stack using an interface and give an implement of the interface using linked list. (10)
2. Specify the ADT of Queue using an interface and give an implement of the interface using array. (10)
3. Write down the procedure of selection sort algorithm and find its time complexity. (10)
4. Give an implementation of insertion sort algorithm and find its worst-case time complexity. (10)
5. Assume a recursive sorting algorithm like merge sort that at each step divides an array with length n into two arrays each with length n/2. Moreover the complexity of its merge routine is O(n^2). Write the recursive equation and solve the equation using recursive tree. (10)
6. Traverse the following graph using breath-first algorithm. Answer should contain Queue at each step and parameter values of vertices (i.e. parent of vertex and distance from source node). (10)
[Graph image]
Take S to be the source vertex.