In the name of ALLAH, the most beneficient, the most merciful

## Data Structures (CS301)

Multiple Choice Questions (MCQs)

## Objective Questions

### Question

If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is ___________.

1. N
2. N2
3. Nlog2N
4. log2N

### Question

If we have 1000 sets each containing a single different person. Which of the following relation will be true on each set:

1. Reflexive
2. Symmetric
3. Transitive
4. Associative

### Question

Which one of the following is NOT the property of equivalence relation:

1. Reflexive
2. Symmetric
3. Transitive
4. Associative

### Question

If there are N external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?

1. N -1
2. N+1
3. N+2
4. N

### Question

If there are N internal nodes in a binary tree then what will be the no. of external nodes in this binary tree?

1. N -1
2. N
3. N +1
4. N +2

### Question

If there are 23 external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?

1. 23
2. 24
3. 22
4. 21

### Question

A binary tree with 24 internal nodes has ________ external nodes.

1. 22
2. 23
3. 48
4. 25

### Question

If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have?

1. 54
2. 57
3. 56
4. 55

### Question

Searching an element in an AVL tree takes maximum _______ time (where n is no. of nodes in AVL tree).

1. Log2(n+1)
2. Log2(n+1) -1
3. 1.44 Log2n
4. 1.66 Log2n

### Question

Every AVL is ___________.

1. Binary Tree
2. Complete Binary Tree
3. Binary Search Tree
4. None of these

### Question

The easiest case of deleting a node from BST is the case in which the node to be deleted _________.

1. Is a leaf node
2. Has left subtree only
3. Has right subtree only
4. Has both left and right subtree

### Question

Consider the following function:
void test_a(int n)
{
cout << n << " ";
if (n>0)
test_a(n-2);
}

What is printed by the call test_a(4)?

1. 4 2 0
2. 0 2 4
3. 0 2
4. 2 4

### Question

A binary tree of N nodes has _____________ .

1. Log10 N levels
2. Log2 N levels
3. N / 2 levels
4. N x 2 levels

### Question

_________ only removes items in reverse order as they were entered.

1. Stack
2. Queue
3. Both of these
4. None of these

### Question

What will be postfix expression of the following infix expression?
Infix Expression : a+b*c-d

1. ab+c*d-
2. abc*+d-
3. abc+*d-
4. abcd+*-

### Question

For compiler, a postfix expression is easier to evaluate than infix expression?

1. True
2. False

### Question

Consider the following pseudo code
declare a stack of characters
while ( there are more characters in the word to read )
{
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}

What is written to the screen for the input "apples"?

1. selpa
2. selppa
3. apples
4. aaappppplleess

### Question

Which one of the following is known as "Last-In, First-Out" or LIFO Data Structure?

2. Stack
3. Queue
4. Tree

### Question

A solution is said to be efficient if it solves the problem within its resource constraints i.e. hardware and time.

1. True
2. False

### Question

Here is a small function definition:
void f(int i, int &k)
{
i = 1;
k = 2;
}

Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?

1. Both x and y are still 0.
2. x is now 1, but y is still 0.
3. x is still 0, but y is now 2.
4. x is now 1, and y is now 2.

### Question

Select the one FALSE statement about binary trees:

1. Every binary tree has at least one node.
2. Every non-empty tree has exactly one root node.
3. Every node has at most two children.
4. Every non-root node has exactly one parent.