MCA_DCA6202_Advanced Data Structure__InternalAssignments_Set1&2

COURSE CODE & NAMEDCA6202 – Advanced Data Structure


Q1. A. What is time complexity and space complexity? Analyze the performance   of   Binary   Search   using   time   and   space complexities. 5


An algorithm is a step by step procedure for solving a particular problem. One major purpose of this text is to develop efficient algorithms for the processing of our data. The efficiency of the algorithm is depending on the time and space it uses. The complexity of an algorithm is the function which gives the running time and/ or space in terms of the input size. Each of our algorithms will involve a particular data structure. The data structure which we choose will depend on many things, including the data and   the   frequency   with   which   various   data   operation   are   applied. Sometimes the choice of data structure involves a time- space tradeoff by increasing the amount of space for storing the data, one may be able to reduce the time needed for processing the data, or vice versa. So, we may not always be able to use the

B.            Write an algorithm/pseudocode to delete the node following a given node in linked list.           5


Deletion Algorithm: We have algorithms for deletion from linked list in various situations. The first one deletes the node following a given node and the second one deletes the node with a given ITEM of information.All of our deletion algorithms will return the memory space of the deleted node N to the beginning of the AVAIL list. Accordingly, all of our algorithms will include the following pair of assignments, where LOC is

Q2.  What are the applications of stack?        10       


Applications of Stack:

Arithmetic Expression

Generally in all arithmetic expression the operators are placed in between the operands, this is called infix notation.

A+B and (X+Y)* Z

In some type of notation the operator is placed before its two operands, this is called prefix notation or polish notation. Its Half solved only

Buy Complete from our online store

MUJ Fully solved assignment available for session Jul/Aug 2021,

Lowest price guarantee with quality.

Charges INR 200 only per assignment. For more information you can get via mail or Whats app also

Mail id is

Our website

After mail, we will reply you instant or maximum

1 hour.

Otherwise you can also contact on our

whatsapp no 8791490301.

Contact no is +91 87-55555-879

Q3A. Explain the postorder traversals on binary tree.          5         

Ans (a).

Postorder traversals on binary tree:

In  postorder  traversal,  traversal  starts  with  the  left  most  subtree  then proceeds with right sub tree and print the parent of those nodes.

1)  Traverse the

B.            What  is  a  binary  search  tree?  What  are  the  common operations that can be performed on binary search trees?      5         

Ans (b).

Binary Search Tree: T is a binary tree. Then T is called binary search tree if each node of n of T has the following property. The value at n is greater than every value in the left subtree of n and is less than every value in the right subtree of n. We can say one of the most important data structure is binary search tree. This enables one to search for and find an element with an average running time f(n)=O(log2 n). It


Q4 A. What  is  static  memory  allocation  and  dynamic  memory allocation?      5

Ans (a).

Static Memory Allocation: Static Memory Allocation, also known as Compile-time Memory Allocation, is used for the allocation of memory during the process of compilation of data in a fixed size. The compiler allocates memory

5. What is an AVL tree. How do you perform search operation in an AVL tree? Explain with the help of an example.        10      

Ans (5).

AVL tree: An  AVL  tree  is another  balanced binary search tree  named  after their inventors, Adelson-Velskii and Landis. An empty binary tree is an AVL tree. A non empty binary tree T is an AVL tree if given TL and TR to be the left and right subtrees of T and h(TL) and h(TR) to be the heights of subtrees TL and TR

Q6  A. Give algorithm/pseudocode for DFS. Demonstrate DFS using suitable example?   5       

Ans (a):

Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from the dead end towards the most recent node that is yet to be completely unexplored.

B.            Design an algorithm/ pseudocode for selection sort.          5         

Ans (b):

Selection sort: Selection sort is one of the sorting techniques that is typically used for sequencing small lists. It starts by comparing the entire list for the lowest item and moves it to the #1 position. It then compares the rest of the list for the next-lowest item and places it in the #2 position and so on until all items