Question

   vi. Assume that a linked list stores the data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list. What is the result to the linked list of       the following instructions? Assume that newNode          is a Node, already constructed.

newNode.data = 1;

                        newNode.next = head.next;

                        head = newNode;

      a. The value 1 is inserted into the linked list before 20

      b. The value 1 is inserted into the linked list after 11 and before 13

      c. The value 1 is inserted into the linked list before 11 and it is now at the head of the list

      d. The value 1 is inserted into the linked list after 20 and the rest of the list is lost

      e. None of the above

5. Suppose we have a stack S and a queue Q. Draw the contents of both S and Q at each step.           Stack S;

            Queue Q;

            S.push(3); S.push(2); S.push(1)

            Q.enqueue(3); Q.enqueue(2); Q.enqueue(1);

            int x = S.pop(); int y = Q.dequeue();

            Q.enqueue(x); S.push(y);

            Q.enqueue(Q.dequeue());      

            S.push(Q.peek()); // peek() function reads the front of a queue without deleting it

6. Using stack, check if the following expression is correct or not. Show the steps:

                                    a+((b+3)-(c*d)+e

7. Using stack convert the infix expression (A * B + C) + C ^ (F + G) to equivalent postfix expression.

8. Show how you can search for the key value 70, in the following array of data using binary search.

30, 70, 10, 15, 80, 20, 90, 11, 12

9. Show the steps to sort the following data using Selection sort algorithm.

10	5	11	8	7

10. What are the factors you will consider to select the proper data structures and memory allocation mechanism when building an algorithm

Answer 1

1. What are the problems of performing the following operations in an Array:

• Insertion in the middle
• Removing elements from the beginning/middle/end
  
  - Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.

When is it appropriate to use an array data structures?
Ans - In arrays, the elements can be accessed randomly by using the index number.

What is the major disadvantage of using an array data structure?
Ans -

• The number of elements to be stored in an array should be known in advance.
• An array is a static structure (which means the array is of fixed size). Once declared the size of the array cannot be modified. The memory which is allocated to it cannot be increased or decreased.
• Insertion and deletion are quite difficult in an array as the elements are stored in consecutive memory locations and the shifting operation is costly.
• Allocating more memory than the requirement leads to wastage of memory space and less allocation of memory also leads to a problem.

Write the differences between a linked list and an array?
Ans -
Array -

Array elements can be accessed randomly using the array index.

Memory is allocated during the compile time (Static memory allocation).

LinkedList -

Random accessing is not possible in linked lists. The elements will have to be accessed sequentially.

Memory is allocated during the run-time (Dynamic memory allocation)

4. Answer the following questions:

            i. It is easy to insert and delete elements in Linked List over Array. True

            ii. Random data access is not allowed in a typical implementation of Linked Lists. True

            iii. The size of an array has to be pre-decided whereas the size of a linked list can change during run time. True

            iv. Which of the following is not a dynamic data structure?

c. Array.

            v. In general, Linked Lists allow (choose the correct one) :

            a. Insertions and removals anywhere.

            vi. Assume that a linked list stores the data, 20, 11, 13, 19, 12, 14 in that order. Assume that Node head references the first item in the list. What is the result to the linked list of       the following instructions? Assume that newNode          is a Node, already constructed.

newNode.data = 1;

                        newNode.next = head.next;

                        head = newNode;

      c. The value 1 is inserted into the linked list before 11 and it is now at the head of the list

Following ss are the answers of the questions until the last one -