Data Structure I Practice Test 5

1. What is the time complexity of pre-order traversal in the iterative fashion?

O(n)

O(nlogn)

O(1)

O(logn)

2. What is the longest length path for a node x in random binary search tree for the insertion process?

x²

4.311 log x

log x

3. In a full binary tree if number of internal nodes is I, then number of nodes N are?

N = I – 1

N = I + 1

N = 2*I

N = 2*I + 1

4. A full binary tree can be generated using ______

post-order traversal

in-order traversal

post-order and pre-order traversal

pre-order traversal

5. Select the code snippet which performs level-order traversal.

public static void levelOrder(Tree root) 
{  
    Queue<Node> queue=new LinkedList<Node>();  
    queue.add(root);  
    while(!queue.isEmpty())  
    {  
        Node tempNode=queue.poll();  
        System.out.println("%d ",tempNode.data);  
        if(tempNode.right!=null)  
        queue.add(tempNode.left);  
        if(tempNode.left!=null)  
        queue.add(tempNode.right);  
    }  
}

public static void levelOrder(Tree root) 
{  
    Queue<Node> queue=new LinkedList<Node>();  
    queue.add(root);  
    while(!queue.isEmpty())  
    {  
        Node tempNode=queue.poll();  
        System.out.println("%d ",tempNode.data);  
        if(tempNode.left!=null)  
        queue.add(tempNode.left);  
        if(tempNode.right!=null)  
        queue.add(tempNode.right);  
    }  
}

public static void levelOrder(Tree root) 
{  
    Queue<Node> queue=new LinkedList<Node>();  
    queue.add(root);  
    while(!queue.isEmpty())  
    {  
        Node tempNode=queue.poll();  
        System.out.println("%d ",tempNode.data);  
        if(tempNode.left!=null)  
        queue.add(tempNode.right);  
        if(tempNode.right!=null)  
        queue.add(tempNode.left);  
    }  
}

public static void levelOrder(Tree root) 
{  
    Queue<Node> queue=new LinkedList<Node>();  
    queue.add(root);  
    while(!queue.isEmpty())  
    {  
        Node tempNode=queue.poll();  
        System.out.println("%d ",tempNode.data);  
        if(tempNode.right!=null)  
        queue.add(tempNode.left.left);  
        if(tempNode.left!=null)  
        queue.add(tempNode.right.right);  
    }  
}

6. Which of the below diagram is following AVL tree property?
i.
ii.

only ii

i is not a binary search tree

only i

only i and ii

7. What is a Cartesian tree?

a tree which obeys cartesian product

a skip list in the form of tree

a tree which obeys heap property only

a tree which obeys heap property and whose inorder traversal yields the given sequence

8. Select the code snippet that performs post-order traversal iteratively.

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
            node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.right;
            }
	    node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
	while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeLeft;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

9. Which of the following graph traversals closely imitates level order traversal of a binary tree?

Binary Search

Depth First Search

Depth & Breadth First Search

Breadth First Search

10. Figure below is a balanced binary tree. If a node inserted as child of the node R, how many nodes will become unbalanced?

« Prev - Data Structure I Practice Test 4

» Next - Data Structure I Practice Test 6