ASSESSMENT TEST - 2

Posted by on
DATA STRUCTURES LABORATORY
ASSESSMENT TEST - 2
1. Which among the following data structures is used to implement recursion?
(a) Stack
(b) Queue
(c) Tree
(d) Graph

2. Which among the following is false about linked lists?
(a) They can have any number of pointers.
(b) They are examples of nonlinear data structures.
(c) They can be used to represent polyno­mials and sparse matrices.
(d) They can have dummy nodes at the be­ginning and end.

3. A tree with exactly 0 or 2 children in all the nodes is
(a) Strictly binary.
(b) Complete.
(c) Full.
(d) A heap.

4. What is the minimum number of nodes in a binary tree of depth 7, when the root is at level 0?
(a) 127
(b) 128
(c) 255
(d) 256

5. The number of branches in a binary tree with 30 nodes is
(a) 29
(b) 30
(c) 31
(d) 32

6. Which of the following applications may use a stack?

(a) A parentheses balancing program.
(b) Tracking of local variables at run time.
(c) Compiler Syntax Analyzer.
(d) All of the mentioned

7. Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation.
The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

(a) 1
(b) 2
(c) 3
(d) 4

8. The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?

(a) 600
(b) 350
(c) 650
(d) 588

9. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed?

(a) ABCD
(b) DCBA
(c) DCAB
(d) ABCD
10. A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?

(a) Queue
(b) Circular queue
(c) Dequeue
(d) None of the options

11. A normal queue, if implemented using an array of size MAX_SIZE, gets full when

(a) Rear = MAX_SIZE – 1
(b) Front = (rear + 1)mod MAX_SIZE
(c) Front = rear + 1
(d) Rear = front

12. What does the following function check for? (all necessary headers to be included and function is called from main)

#define MAX 10

   typedef struct stack
   {
        int top;
   int item[MAX];
   }stack;

   int function(stack *s)
   {
        if(s->top == -1)
       return 1;
    else return 0;
   }

(a) full stack
(b) invalid index
(c) empty stack
(d) infinite stack

13. What is the time complexity of pop() operation when the stack is implemented using an array?

(a) O(1)
(b) O(n)
(c) O(logn)
(d) O(nlogn)

14. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor. Select from the options the appropriate push() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.
class Node
{
        protected Node next;
        protected Object ele;
        Node()
        {
               this(null,null);
        }
        Node(Object e,Node n)
        {
               ele=e;
               next=n;
        }
        public void setNext(Node n)
        {
               next=n;
        }
        public void setEle(Object e)
        {
               ele=e;
        }
        public Node getNext()
        {
               return next;
        }
        public Object getEle()
        {
               return ele;
        }
}
 
class Stack
{
        Node first;
        int size=0;
        Stack()
        {
               first=null;
        }
}


(a)
public void push(Object item)
{
  Node temp = new Node(item,first);
  first = temp;
  size++;
}

(b)
public void push(Object item)
{
  Node temp = new Node(item,first);
  first = temp.getNext();
  size++;
}

(c)
public void push(Object item)
{
  Node temp = new Node();
  first = temp.getNext();
  first.setItem(item);
  size++;
}

d) none of the mentioned


15. What does the following piece of code do?
 
public Object function()
{
        if(isEmpty())
        return -999;
        else
        {
               Object high;
               high = q[front];
               return high;
        }
}

(a) Dequeue
(b) Enqueue
(c) Return the front element
(d) None of the mentioned

16. Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are right-handed. The number of women at the table is

(a) 2
(b) 3
(c) 4
(d) Can’t be determined.

17. What is common in three different types of traversals (Inorder, Preorder and Postorder)?

(a) Root is visited before right subtree
(b) Left subtree is always visited before right subtree
(c) Root is visited after left subtree
(d) None of the above

18. What does the following function do for a given binary tree?

int fun(struct node *root)
{
   if (root == NULL)
      return 0;
   if (root->left == NULL && root->right == NULL)
      return 0;
   return 1 + fun(root->left) + fun(root->right);
}


(a)    Counts leaf nodes
(b)   Counts internal nodes
(c)    Returns height where height is defined as number of edges on the path from root to deepest node
(d)    Return diameter where diameter is number of edges on the longest path between any two nodes.

19. Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?
(a)    Preorder and Inorder
(b)   Preorder and Postorder
(c)    Inorder and Postorder
(d)    None of the options

20. What does the above function do in general for the following C like pseudo code of a function that takes a Queue as an argument, and uses a stack S to do processing.

void fun(Queue *Q)
{
    Stack S;  // Say it creates an empty stack S

    // Run while Q is not empty
    while (!isEmpty(Q))
    {
        // deQueue an item from Q and push the dequeued item to S
        push(&S, deQueue(Q));
    }

    // Run while Stack S is not empty
    while (!isEmpty(&S))
    {
      // Pop an item from S and enqueue the poppped item to Q
      enQueue(Q, pop(&S));
    }
}


           
(a)    Removes the last from Q
(b)    Keeps the Q same as it was before the call
(c)    Makes Q empty
(d)   Reverses the Q


Comments

Post a Comment