BIT201 · TU past paper
Data Structures and Algorithms 2078 question paper
The complete TU 2078 exam paper for Data Structures and Algorithms (BIT201), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksNumericalInfix to postfix conversion using stackHideAnswer
Explain algorithm to convert an infix expression to postfix using stack? Use this algorithm to convert (A+B)*C-D to postfix.[10]
- Infix expression to convert: $(A+B)C-D$ - Data structure to use: Stack - Task: (a) explain the algorithm, (b) apply it to the given expression. All required data is present. --- Operator Precedence --------------------- ^ 3 (highest) ,...
- 210 marksNumericalDijkstra's algorithm for shortest pathHideAnswer
What is shortest path algorithm? Use Dijkstra's algorithm to find shortest path between the vertices of a and z in the graph given below.[10]
Problem asks for: definition of shortest path algorithm + Dijkstra applied to find shortest path from vertex $a$ to vertex $z$. Critical issue: The actual graph image is NOT provided in the question. Edge weights and connectivity cannot ...
- 310 marksNumericalMerge sort algorithm and tracingHideAnswer
Explain merge sort along with its time complexity. Use this algorithm to sort array of numbers given below: 25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11[10]
Array to sort (n = 13): $$[25,\ 37,\ 48,\ 25,\ 23,\ 17,\ 31,\ 45,\ 7,\ 21,\ 15,\ 8,\ 11]$$ Indices 0 to 12. No values missing; all data is readable. --- Merge Sort is a divide and conquer algorithm. It: - Divides the array into two halve...
- 45 marksArray as an ADTHideAnswer
What is data Structure? Explain an array as an abstract data type. [5]
A data structure is a systematic way of organizing, storing, and managing data in a computer so that it can be accessed and modified efficiently. In other words, a data structure defines: - The logical relationship between data elements ...
- 55 marksBig O notation with examplesHideAnswer
Explain big oh(O) notation with suitable example. [5]
Big Oh notation (O) is used to describe the upper bound of an algorithm's running time or space complexity. It represents the worst-case scenario of an algorithm's growth rate. Formally, a function f(n) = O(g(n)) if and only if there exi...
- 65 marksPriority queue definition and implementatiHideAnswer
Define priority queue. How do you implement priority queue? Explain. [5]
A priority queue is an abstract data type (ADT) similar to a regular queue, but each element has an associated priority value. Elements are served (removed) based on their priority rather than their insertion order: - The element with th...
- 75 marksTower of Hanoi algorithm and tracingHideAnswer
Define recursion. Explain Tower of Hanoi algorithm in detail. [5]
Recursion is a programming technique in which a function calls itself directly or indirectly to solve a problem. A recursive function solves a problem by breaking it down into smaller subproblems of the same type until it reaches a base ...
- 85 marksQueue implementation using linked listHideAnswer
How can you implement queue using linked list? Explain. [5]
A queue is a linear data structure that follows the FIFO (First In, First Out) principle. Using a linked list to implement a queue allows dynamic memory allocation, avoiding the fixed-size limitation of array-based queues. Two pointers a...
- 95 marksBinary tree definition and applicationsHideAnswer
What is binary tree? Explain different application of binary tree. [5]
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A binary tree consists of: - Root node - the topmost node of the tree - Left subtree - a binary tree o...
- 105 marksComparison between sequential and binary sHideAnswer
Explain sequential search. How is it different from binary search? [5]
Sequential search (also called linear search) is the simplest searching technique in which each element of the array or list is examined one by one, from the beginning to the end, until the desired element (key) is found or the entire li...
- 115 marksQuadratic probing collision resolutionHideAnswer
Define hashing. Explain quadratic probing with example. [5]
Hashing and Quadratic Probing
Definition of Hashing
Hashing is a technique used to map a key to a specific location (index) in a hash table using a hash function. The hash function computes an index from the key, allowing for O(1) average-case time complexity for insertion, deletion, and search operations.
Hash Function: $$h(k) = k \mod m$$ where
kis the key andmis the size of the hash table.A collision occurs when two different keys map to the same index. Various collision resolution techniques are used to handle this.
Quadratic Probing
Quadratic Probing is an open addressing collision resolution technique. When a collision occurs at index
h(k), instead of checking the next sequential slot (as in linear probing), it probes slots at quadratic intervals.Probe Sequence Formula:
$$h_i(k) = (h(k) + i^2) \mod m$$
where:
h(k)= initial hash valuei= probe number (i = 0, 1, 2, 3, ...)m= size of the hash table
Advantage over Linear Probing: Quadratic probing reduces primary clustering (long chains of consecutive filled slots).
Example
Insert the keys: 18, 26, 35, 9, 64 into a hash table of size m = 7
Hash function:
h(k) = k mod 7Key h(k) = k mod 7 Probe Final Index 18 18 mod 7 = 4 i=0, slot 4 is empty 4 26 26 mod 7 = 5 i=0, slot 5 is empty 5 35 35 mod 7 = 0 i=0, slot 0 is empty 0 9 9 mod 7 = 2 i=0, slot 2 is empty 2 64 64 mod 7 = 1 i=0, slot 1 is empty 1 Now insert key = 26 again (to show collision), suppose we insert key = 19:
h(19) = 19 mod 7 = 5→ slot 5 is occupied (collision!)- Probe i=1:
(5 + 1²) mod 7 = 6→ slot 6 is empty → insert at 6
Final Hash Table:
Index Key 0 35 1 64 2 9 3 -- 4 18 5 26 6 19
Summary
Feature Detail Probe formula h(k, i) = (h(k) + i²) mod mCollision handling Quadratic jumps Avoids Primary clustering Drawback May cause secondary clustering; may not probe all slots if mis not prime - 125 marksGraph traversal definitionHideAnswer
What is graph traversal? Explain breadth first search. [5]
Graph traversal refers to the process of visiting each vertex (node) in a graph exactly once in a systematic manner. Unlike trees, graphs may contain cycles, so we need to keep track of visited vertices to avoid processing the same verte...