Q.1 Let P be a pointer to a singly linked list. Show how this list may be used as a stack. That is, write algorithms to push and pop elements. Specify the value of P when the stack is empty.
Q.2 What is an algorithm? What are the characteristics of a good algorithm?
Q.3 How do you find the complexity of an algorithm? What is the relation between the time and space complexities of an algorithm? Justify your answer with an example.
Q.4 Explain an efficient way of storing a sparse matrix in memory. Write a module to find the transpose of a sparse matrix stored in this way.
Q.5 Explain an efficient way of storing two symmetric matrices of the same order in memory.
Q.6 Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input : a b + c d +*f↑ .Ans:
Q.7 What are circular queues? Write down routines for inserting and deleting elements from a circular queue implemented using arrays.
Q.8 Given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to output the three traversal orders. Write an algorithm for checking validity of the input, i.e., the program must know if the input is disjoint, duplicated and has a loop.
Q.9 Two linked lists contain information of the same type in ascending order. Write a module to merge them to a single linked list that is sorted.
Q.10 What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the tree in Preorder, Inorder and postorder.
Q.11 What are expression trees? Represent the following expression using a tree. Comment on the result ((c*d)+e)
Q.12 How do you rotate a Binary Tree? Explain right and left rotations with the help of an example.
Q.13 Taking a suitable example explains how a general tree can be represented as a Binary Tree.
Q.14 What are the different ways of representing a graph? Represent the following graph using those ways.
Q.15 Show the result of running BFS and DFS on the directed graph given below using vertex 3 as source. Show the status of the data structure used at each stage.
Q.16 Write an algorithm for finding solution to the Tower’s of Hanoi problem. Explain the working of your algorithm (with 4 disks) with diagrams.
Q.17 Reverse the order of elements on a stack S
(i) using two additional stacks.
(ii) using one additional queue.
Q.18 Explain the representations of graph. Represent the given graph using any two methods
Q.19 Write short notes on any FOUR:-
(i) B Tree.
(ii) Time Complexity, Big O notation.
(iii) Merge Sort.
(iv) Threaded Binary Tree.
(v) Depth First Traversal.
Q.20 Define the term array. How are two-dimensional arrays represented in memory? Explain how address of an element is calculated in a two dimensional array.
Q.21 An, array, A contains n unique integers from the range x to y (x and y inclusive where n=y-). That is, there is one member that is not in A. Design an O(n) time algorithm for finding that number.
Q.22 Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.
Q.23 What are stacks? How can stacks be used to check whether an expression is correctly parenthized or not. For eg(()) is well formed but (() or )()( is not.
Q24. Write down any four applications of queues.
Q.25 Define a B-Tree.