CSC211 · TU past paper
Data Structures and Algorithms 2075 question paper
The complete TU 2075 exam paper for Data Structures and Algorithms (CSC211), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksNumericalConversion from infix to postfix/prefix exHideAnswer
How can you use stack to convert an infix expression to postfix? Convert infix expression (A+B)*(C-D) to postfix using stack.[10]
A stack is used to temporarily hold operators and parentheses so that operators are emitted to the output in the correct order of precedence. We scan the infix expression left to right and apply the following rules: 1. Operand → append d...
- 210 marksDefinition and Representation of Graphs, GHideAnswer
Discuss depth first and breadth first traversal of a graph with suitable example.[10]
Graph traversal means visiting every vertex of a graph exactly once in a systematic manner. The two standard traversal techniques are: 1. Breadth First Search (BFS) 2. Depth First Search (DFS) --- BFS is one of the simplest methods of gr...
- 310 marksNumericalDivide and Conquer SortingHideAnswer
Explain concept of divide and conquer algorithm. Hand test quick sort algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19). What is time complexity of quick sort algorithm?[10]
- Array to sort: $(78, 34, 21, 43, 7, 18, 9, 56, 38, 19)$, 10 elements. - Tasks: explain divide and conquer, hand-test quick sort, state time complexity. --- Divide and conquer is an algorithm design paradigm that solves a problem by rec...
- 45 marksBasic Concept of Stack, Stack as an ADT, SHideAnswer
Compare stack with queue. How is linear queue different from circular queue? [5]
--- Basis Stack Queue --------- Principle Last In First Out (LIFO) First In First Out (FIFO) End of Operation Insertion and deletion both occur at one end called the top Insertion occurs at the rear end and deletion occurs at the front e...
- 55 marksBasic Concept of Stack, Stack as an ADT, SHideAnswer
What is ADT? Discuss stack as an ADT. [5]
--- Definition: An Abstract Data Type (ADT) is a type or a class for objects whose behaviour is defined by a set of values and a set of operations. It does not specify how data will be organized in memory and what algorithms will be used...
- 65 marksPrinciple of Recursion, Comparison betweenHideAnswer
Define recursive algorithm? How do you implement recursive algorithm while writing computer programs? [5]
An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations by a computer. A recursive algorithm is an algorithm that solves a problem by defining the problem in terms of itself. The under...
- 75 marksBasic operations in Linked ListHideAnswer
What are benifits of using linked list over array? How can you insert a node in a singly linked list? [5]
--- Feature Linked List Array --------- Size Dynamic, grows/shrinks at runtime Fixed size, declared at compile time Insertion/Deletion Efficient (no shifting needed) Requires shifting of elements Memory Allocates memory as needed May was...
- 85 marksHashingHideAnswer
What is hashing? Discuss rehashing with example. [5]
Hashing is an efficient searching technique in which a key is placed at a direct accessible address for rapid search. Hashing provides direct access of records from a file no matter where the record is in the file, which reduces unnecess...
- 95 marksBinary Search Tree, Insertion, Deletion, THideAnswer
How do you traverse a binary tree? Discuss. [5]
Binary tree traversal is the process of visiting each node of a binary tree exactly once in a systematic order. Since a binary tree has three components (root, left subtree, right subtree), different orderings of visiting these component...
- 105 marksAsymptotic notations and common functionsHideAnswer
What do you mean by complexity of algorithm? How do you find time complexity? [5]
The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n, where n is the size of the input data. It is used to measure the efficiency of an algorithm. There are two main ...
- 115 marksIntroduction to Searching, Search AlgorithHideAnswer
How do you implement binary search algorithm? What is time complexity of this algorithm? [5]
Binary search is a searching algorithm that works only on sorted lists. It repeatedly divides the search space in half by comparing the target element with the middle element of the list. --- --- Consider sorted array: A = [10, 20, 30, 4...
- 125 marksDynamic memory allocation in CHideAnswer
Write short notes on: a. Dynamic memory allocation b. Game tree [5]
--- Dynamic memory allocation is the process of allocating memory to variables and data structures at runtime (during program execution), rather than at compile time. It is a key component of the variable part of space complexity, meanin...