2081
Bsc CSIT / Semester 3 / Science
Computer Science and Information Technology
Data Structure and Algorithms
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Time: 3 Hours
Candidates are required to give their answers in their own words as far as practicable.
The figures in the margin indicate full marks.
Attempt any TWO question.
Define circular queue. How queue differ from stack. Write a program to implement linear queue.
What is AVL tree? How heap differ from tree? Construct an AVL tree for data 24,12,8,15,35,30,57,40,45 and 78.
Define list. How can you use linked list to implement stack? Explain circular linked list.
Attempt any EIGHT question.
Explain big oh notation in brief. Find big oh of the following function: f(x) = 5x4 + 9x2 + 7x + 9.
Convert the infix expression A+(((B-C)*(D-E)+F)/G)$(H-I) into post expression using stack.
Write a program to find GCD of two numbers using recursion.
What is the application of spanning tree? Draw a MST of a graph containing any 8 vertices and 11 edges with arbitrary edge costs.
Sort the number {82, 73, 12, 39, 26, 88, 2, 9, 60, 41} using shell sort.
What is hashing? how do you apply linear probing and rehashing explain with example.
What is the algorithm for node insertion and deletion from specified position from doubly linked list.
What is linear queue? Why do we need circular queue? Explain.
Write short notes on:
a. Breadth First traversal of graph
b. TOH
*** END OF QUESTION PAPER ***
1. Circular Queue Definition A Circular Queue is a linear data structure where the last position is connected back to the first position to form a circle. - It overcomes the limitation of a linear
1. AVL Tree Definition An AVL Tree is a self-balancing binary search tree (BST) in which the height difference between the left and right subtrees of any node is at most 1. - Named after Adelson-Ve
1. Definition of List A List is a linear data structure that stores a sequence of elements. - Elements are arranged in a specific order. - Each element can be accessed, inserted, or deleted. -
1. Definition of Big-O Notation Big-O notation (O) is an asymptotic notation used to describe the upper bound of the time or space complexity of an algorithm. It represents the worst-case performanc
1. Definition Infix Expression An infix expression is an expression in which the operator is written between operands. Example: A + B Postfix Expression A postfix expression (Reverse Polish No
And more questions available on this page.