Data Structure I Practice Test 2

1. What is the functionality of the following piece of code?

public void function(Object item)
{
	Node temp=new Node(item,trail);
	if(isEmpty())
	{
		head.setNext(temp);
		temp.setNext(trail);
	}
	else
	{
		Node cur=head.getNext();
		while(cur.getNext()!=trail)
		{
			cur=cur.getNext();
		}
		cur.setNext(temp);
	}
	size++;
}

Insert at the rear end of the dequeue

Fetch the element at the front end of the dequeue

Fetch the element at the rear end of the dequeue

Insert at the front end of the dequeue

2. Evaluation of infix expression is done based on precedence of operators.

True

False

3. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = dup;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = cur
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

4. You are asked to perform a queue operation using a stack. Assume the size of the stack is some value 'n' and there are 'm' number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).

Data is insufficient

O(m*n)

O(n)

O(m)

5. Which of the following program prints the index of every matching parenthesis?

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
           try
           {
             int p = stk.pop() + 1;
             System.out.println("')' at index "+(i)+" matched with ')' at index "+p);
           }
           catch(Exception e)
           {
              System.out.println("')' at index "+(i)+" is unmatched");
           }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop();
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
            System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
          try
          {
            int p = stk.pop() + 1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {    
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop() +1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }            
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

6. Which of the following code snippet is used to convert decimal to binary numbers?

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[++index] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

public void convertBinary(int num)
 {
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[++index] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
  }

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[index++] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
}

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[index++] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

7. Using the evaluation of prefix algorithm, evaluate +-9 2 7.

8. Find the output of the following prefix expression.