Data Structures and Algorithms (Question and Answers) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

1. Show the list configuration resulting from each series of list operations using the List ADT of Figure 4.1. Assume that lists L1 and L2 are empty at the beginning of each series. Show where the current position is in the list.

(a) L1.append(10);

L1.append(20);

L1.append(15);

(b) L2.append(10);

L2.append(20);

L2.append(15);

L2.moveToStart();

L2.insert(39);

L2.next();

L2.insert(12);

Ans: LI -> 10,20,15

L2 ->10,20,15

L2 ->39,10,20,15

L2 => 39,12,19,20,15

2. Using the list ADT, write a function to interchange the current element and the one following it.

void interchange(list *l)

{ 

    list *curr = l;

    list *curr_next = l->next;

    while(l->next != null)

    {

          temp->info = curr_next->info;

          curr_next->info = curr->info;

          curr->info = temp->info;

          curr = curr->next;

          curr_next = curr_next->next;

          temp = null;

     }

}

3. Singly Linked List 

   a) Consists of less space

   b) Can be traversed from one end only

   c) Consists of two nodes Info and Next

   Doubly Linked List

  a) Consists of more space

b) Can be traversed from both ends

c) Consists of three nodes prev, info and next

                     

4.   Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n. We want to define time taken by an algorithm without depending on the implementation details. 

Best Case Complexity of Linear Search :- O(1)

Worst Case Complexity of Linear Search :- O(n)

 

5. Int Count = 0;

    while(LIST->next != NULL)

    {

         If(LIST->info == ITEM)

              Count++;

          LIST = LIST->next;

     }

 

Frequency Count :- A heuristic that keeps the elements of a list ordered by number of times each element is the target of a search.

Stepwise refinement technique : Start with the initial problem statement. Break it into a few general steps. Take each "step", and break it further into more detailed steps. Keep repeating the process on each "step", until you get a breakdown that is pretty specific, and can be written more or less in pseudocode.  

6. What is a Circular Queue?

A Circular Queue is a special version of queue where the last element of the queue is connected to the first element of the queue forming a circle.

The operations are performed based on FIFO (First In First Out) principle. It is also called ‘Ring Buffer’. 
 

In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we can not insert the next element even if there is a space in front of queue.

 7. Free memory blocks of size 60K, 25K, 12K, 20K, 35K, 45K and 40K are available in this order. Show the memory allocation for a sequence of job requests of size 22K, 10K, 42K, and 31K (in this order) in First Fit, Best Fit and Worst Fit allocation strategies.

First Fit: 22k in 60K, 10K in 25K, 42K in 45K, 30K in 35K

Best Fit: 22K in 25K, 10K in 12K, 42K in 45K, 30K in 35K

Worst Fit: 22K in 60K, 10K in 35K, 42K in 45K, 31K in 40K

8. START

• Step 1 -> Take two string as str1 and str2.
• Step 2 -> Move to the last position of first string let it be i.
• Step 3 -> Now Loop over second string with j = 0
• Assign the character str1[i] = str2[j]
• Increment i and j and repeat till the last element of j.
• End Loop
• Step 3 -> Print str1.

9 (a)

Following is a simple stack based iterative process to print Preorder traversal. 

1.      Create an empty stack nodeStack and push root node to stack. 

2.      Do the following while nodeStack is not empty. 

1.      Pop an item from the stack and print it. 

2.      Push right child of a popped item to stack 

3.      Push left child of a popped item to stack

The right child is pushed before the left child to make sure that the left subtree is processed first.

(b) 573169248

      136752948

      631758492

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds