Back to Other Questions [Of this Course]
👁️ 129 views
University of Barishal Logo

University of Barishal

Department of Computer Science and Engineering

Final Exam

Course Title: Data Structures (CSE-1201)

Semester: 2nd | Session: 22-23

Time: 180 minutes | Marks: 60.00

Exam Date: November 28, 2024

View 46 Topic-wise Questions for this Course

(Answer any FIVE questions)

1.

a) Differentiate between data types and data structures. Provide examples of each.

Please SUBSCRIBE to view full question

Topics: Basic Data Structure Solution is Coming!
3 Marks
b) Why is knowledge of data structures important for computer science students?

Please SUBSCRIBE to view full question

Topics: Basic Data Structure Solution is Coming!
3 Marks
c) What do you mean by growth of function? Briefly describe the following (a), (b) and (c) of the figure.

Please SUBSCRIBE to view full question

Topics: Growth Function Solution is Coming!
3 Marks
d) Define and explain the concept of an Abstract Data Type (ADT). How does it relate to data structures?

Please SUBSCRIBE to view full question

Topics: Basic Data Structure , Data Types Solution is Coming!
3 Marks
2.

a) Write down the algorithm for Insertion Sort and analyze its time complexity in best, average, and worst cases.

Please SUBSCRIBE to view full question

Topics: Insertion Sort , Space Complexity , Time Complexity Solution is Coming!
3 Marks
b) Sort the following items using the Shell Sort algorithm: {7, 19, 24, 13, 31, 8, 82, 18, 44, 63, 5, 29}

Please SUBSCRIBE to view full question

Topics: Shell Sorting Solution is Coming!
5 Marks
c) Using Quick Sort, sort the array A = (2, 8, 7, 1, 3, 5, 6, 4). Describe the role of the partition function and how to select the pivot.

Please SUBSCRIBE to view full question

Topics: Quick Sort Solution is Coming!
4 Marks
3.

a) Insert and delete elements in a Binary Search Tree (BST) using the numbers 33, 50, 45, 52, 12, 10. Draw the tree after each operation.

Please SUBSCRIBE to view full question

Topics: Binary Search Tree (BST) Solution is Coming!
3 Marks
b) Define a heap. Represent the heap as an array and perform the following operations: · Insert 25. · Delete 86 and 11 from the heap. . Sort the elements in descending order using Heap Sort.

Please SUBSCRIBE to view full question

Topics: Heap Sort Solution is Coming!
3 Marks
c) Why do we need postfix and prefix notation over infix notation? Translate the infix notation A*(B+D)/E-F*(G+H/K) to its equivalent postfix notation using stack.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
d) Compare and contrast BSTs and heaps. When would you prefer one over the other?

Please SUBSCRIBE to view full question

Topics: Binary Search Tree (BST) , Heap Solution is Coming!
2 Marks
4.

a) Draw a graph from the adjacency list: adj (y) = [x], adj (x) = [z], adj (z) = [y, w], adj (w) = [x], adj (s) = [z, w], adj (v) = [s, w], adj (t) = [u, v], adj (u) = [v].

Please SUBSCRIBE to view full question

Topics: Graph Algorithms Solution is Coming!
2 Marks
b) Create the adjacency and incidence matrices for the graph above. What are the advantages of using an adjacency matrix over an adjacency list for graph traversal?

Please SUBSCRIBE to view full question

Topics: Adjacency List , Adjacency Matrix Solution is Coming!
3 Marks
c) Identify the tree, back, forward, and cross edges for the graph.

Please SUBSCRIBE to view full question

Topics: Graph Representation Solution is Coming!
4 Marks
d) Write down the algorithms for the BFS algorithm.

Please SUBSCRIBE to view full question

Topics: Breadth First Search (BFS) Solution is Coming!
3 Marks
5.

a) Write recursive formulas for: • Fibonacci sequence. • GCD calculation. • Tower of Hanoi problem.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
4 Marks
b) What data structure is commonly used to implement recursion? Why?

Please SUBSCRIBE to view full question

Topics: Recursion Solution is Coming!
2 Marks
c) What do you mean by disjoint set data structure? Suppose that CONNECTED- COMPONENTS is run on the undirected graph G=(V,E), where V = { a, b, c, d, e, f, g, h, i, j, k} and the edges of E are processed in the order (d, i), (f, k), (g, i), (b, g), (a, h), (i, j), (d, k), (b, j), (d, f), (g, j), (a, e). List the vertices in each connected component after each iteration of lines 3-5.

Please SUBSCRIBE to view full question

Topics: Disjoint Set Solution is Coming!
4 Marks
d) How can you differentiate hash table from the direct addressing table?

Please SUBSCRIBE to view full question

Topics: Direct Addressing Table , Hash Table Solution is Coming!
2 Marks
6.

a) Implement a queue using two stacks. Analyze the time complexity of enqueue and dequeue operations.

Please SUBSCRIBE to view full question

Topics: Queue , Time Complexity Solution is Coming!
3 Marks
b) For a circular queue with FRONT = 2, REAR = 4, and QUEUE: __, A, C, D, __, __, describe the state after: • Adding F. • Deleting two elements. • Adding K, L, M. • Deleting two elements.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
c) Describe how a priority queue can be used to implement: • A FIFO queue. • A stack

Please SUBSCRIBE to view full question

Topics: Priority Queue , Stack Solution is Coming!
3 Marks
d) Define divide and conquer. A well-known problem in UVA- 374: Big Mod Problem, calculate B^P % M for large B, P and M using an efficient algorithm. Write down the program for calculating the solutions.

Please SUBSCRIBE to view full question

Topics: Divide and Conquer Solution is Coming!
3 Marks
7.

a) Use a hash table of size 7 with separate chaining, linear probing, and double hashing to insert: 19, 26, 13, 48, 17. Show the resulting tables.

Please SUBSCRIBE to view full question

Topics: Hash Table Solution is Coming!
3 Marks
b) Explain how collision resolution techniques like chaining and double hashing affect performance.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
c) Solve the problems Longest Common Subsequence (LCS) using dynamic programming for strings ABCBDAB and BDCAB. Write the DP table and explain the solution.

Please SUBSCRIBE to view full question

Topics: Dynamic Programming (DP) , Longest Common Subsequence (LCS) Solution is Coming!
3 Marks
d) What do you mean by MST? Find the MST for the following graph using PRIM'S algorithm. Is prims a Greedy algorithm?

Please SUBSCRIBE to view full question

Topics: Greedy Algorithm , Minimum Spanning Tree (MST) , Prim's Algorithm Solution is Coming!
3 Marks
8.

a) Define divide and conquer. How does it apply to Merge Sort and Quick Sort.

Please SUBSCRIBE to view full question

Topics: Divide and Conquer , Merge Sort , Quick Sort Solution is Coming!
3 Marks
b) Define complete binary tree. Traverse the given tree using In-order, Preorder and Post-order traversals.

Please SUBSCRIBE to view full question

Topics: Binary Search Tree (BST) Solution is Coming!
3 Marks
c) A well renowned UVA Problem: 10334, Suppose we put two panes of glass back-to-back. How many ways an are there for light rays to pass through or be reflected after changing direction n times? Following figure shows the situations when the value of n is 0. 1 and 2. Now your task is to write down the program for input 0, 1, 2: output will be 1, 2, and 3 re Figure for Q-8(a)(ii)

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
d) Working Modulo With q = 11, how many spurious hits does Rabin-Karp encounter when looking for pattern, P = 26 in text, T = 3141592653589793? Elaborate your answer.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
3 Marks
View 46 Topic-wise Questions for this Course

Contributors of this Question:

Role Name Date
Uploaded By: Dip Dey Nov. 28, 2024, 6:45 p.m.
Converted By (Img/PDF to Text): Obaydul Hasan Nayeem Oct. 17, 2025, 12:28 a.m.
Reviewed By: N/A N/A
Back to Other Questions [Of this Course]