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.