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

# Data Structures (CS301)

Multiple Choice Questions (MCQs)

## Objective Questions

1. 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
2. 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
3. Which one of the following is NOT the property of equivalence relation:

1. Reflexive
2. Symmetric
3. Transitive
4. Associative
4. 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
5. 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
6. 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
7. A binary tree with 24 internal nodes has ________ external nodes.

1. 22
2. 23
3. 48
4. 25
8. 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
9. Searching an element in an AVL tree takes maximum _______ time (where n is number of nodes in AVL tree).

1. Log2(n+1)
2. Log2(n+1) -1
3. 1.44 Log2n
4. 1.66 Log2n
10. Every AVL is ___________.

1. Binary Tree
2. Complete Binary Tree
3. Binary Search Tree
4. None of the given
11. Every AVL is ___________.

1. Ternary Tree
2. Complete Binary Tree
3. Heap
4. Binary Search Tree
12. 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
13. 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
14. A binary tree of N nodes has _____________ .

1. Log10 N levels
2. Log2 N levels
3. N / 2 levels
4. N x 2 levels
15. _________ only removes items in reverse order as they were entered.

1. Stack
2. Queue
3. Both of the given
4. None of the given
16. 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+*-
17. For compiler, a postfix expression is easier to evaluate than infix expression?

1. True
2. False
18. 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
19. Which one of the following is known as "Last-In, First-Out" or LIFO Data Structure?

2. Stack
3. Queue
4. Tree
20. 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
21. Each node in singly link list has,

1. 1 pointer
2. 2 pointers
3. 3 pointers
4. 4 pointers
22. Parameters in function call are passed using,

1. Stack
2. Queue
3. Binary Search Tree
4. AVL Tree
23. The ________ method of list data structure removes the element residing at the current position

2. Next
3. Remove
4. Find
24. Insertion in a linked list can be done at

1. Front only
2. Back only
3. Somewhere in middle only
4. Front, Back and somewhere in the middle
25. An array is a group of ________ memory locations.

1. Scattered
2. Isolated
3. Random (non-consecutive)
4. Consecutive
26. Which of the following applications may use a stack?

2. Parentheses balancing program
3. Buffering messages
4. Waiting list
27. Consider the following expression:
x - y * a + b / c
Which of the following is a correct equivalent expression for the above?

1. x y -a * b +c /
2. x *y a - b c / +
3. x y a * - b c / +
4. x y a * - b/ + c
28. Non-recursive calls are faster than which of the following calls?

1. Parameterized
2. Recursive
3. Function
4. Non-Function
29. The balance of a node is the result of "height of left subtree" ________ "height of right subtree".

1. Plus
2. Minus
3. Multiply
4. Divided by
30. A complete binary tree having "N" nodes consists of ________ Levels.

1. Log2 (N+1) -1
2. Log2 (N-1) -1
3. Log2 (N+1) +1
4. Log2 (N-1) +1
31. In the poat-order traversal of a binary search tree, nodes process as:

1. Left-subtree, Right-subtree, Root
2. Rightt-subtree, Root, Left-subtree
3. Left-subtree, Root, Right-subtree
4. Rightt-subtree, Left-subtree, Root
32. The simplest case in a BST to delete a node is:

1. When the node, that is to be deleted is root node
2. When the node, that is to be deleted has both left and right child
3. When the node, that is to be deleted has only one child
4. When the node, that is to be deleted is a leaf node
33. If class A defines class B as its friend, then:

1. Class A can access private members of Class B
2. Class B can access only the public members of Class A
3. Class A can access only the public members of Class B
4. Class B can access private members of Class A
34. In the statement int& a=b;

1. a and b pointing to two different memory location
2. a and b are two different names of the same memory location
3. a and b are two different variable names
4. b hold the address of variable a
35. The main use of AVL tree is:

1. Searching of data
2. Storing of data
3. Insertion of data
4. Security of data
36. In simple implementation of stack, isFull() method is used due to ________.

1. Limitation of array
2. Strength of array
37. Write in postfix form 5 * (9 - 7)

1. 5 (9 7 -) *
2. 5 9 * 7 -
3. 5 9 7 - *
4. 5 (9 7 -)
38. What will be result of following postfix expression?

1 2 3 * + 2 -

1. 3
2. 4
3. 5
4. 10
39. An array x of 100 integers is declared as

1. int x = ;
2. int x;
3. integer array x = 100;
4. integer x [] = 100;
40. What is the maximum depth of recursive calls a function may make?

1. 1
2. 2
3. n (where n is the argument)
4. There is no fixed maximum
41. A Linear Data Structure is the data structure in which data elements are arranged in a sequence or a linear list. Which of the following is Non Linear Data Structure?

1. Arrays
3. Binary Search Trees
4. Stack
42. The new operation in C++ for dynamically allocating memory returns,

1. Size of the memory it has allocated
2. Pointer to the memory it has allocated
3. Both size and pointer to the memory it has allocated
4. Value of the memory it has allocated
43. In ________, a programmer uses two pointers in the node, i.e. one to point to next node and the other to point to the previous node.

3. Array
4. Structure
44. The expression AB+C* is called?

1. Prefix expression
2. Postfix expression
3. Infix expression
4. Prefix and Infix expression
45. Consider the function X as under
int X (int& Value)
{
return Value;
}
Now a and b are integers in a calling function. Which one of the following is a valid call to the above function X?

1. a = X(b);
2. a = X(&b);
3. a = X(*b);
4. a = X(&*b);
46. Each node in Binary Search Tree has

1. 1 pointer
2. 2 pointers
3. 3 pointers
4. 4 pointers
47. Suppose n is the number of nodes in a complete Binary Tree, then maximum steps required for a search operation are

1. Log2 (n+1) -1
2. Log2 (n+1)
3. Log2 (n) -1
4. Log2 (n)
48. The next field in the last node of a singly-linked list is set to ________.

1. NAN
2. 1
3. 'NULL
4. -1
49. A queue where the dequeue operation does not depend upon FIFO, is called:

1. enqueue
2. simple queue
3. stack
4. priority queue
50. a * (b+c)-d is an example of ________ expression.

1. infix
2. prefix
3. postfix
4. allfix
51. Which one of the following calling methods does not change the original value of the argument in the calling function?

1. Call by passing the value of the argument
2. Call by passing reference of the argument
3. Call by passing the address of the argument
4. Call by passing pointer of the argument
52. Which of the following statement is NOT true for reference variable?

1. Once a reference is created, it cannot be later made to reference another object.
2. Reference cannot be NULL
3. References can be uninitialized.
4. It is not possible to refer directly to a reference object after it is defined.
53. Each operator in a postfix expression refers to the previous ________ operand(s).

1. One
2. Two
3. Three
4. Four
54. Which one of the following statement is correct?

1. Array size is fixed once it is created
2. Link List size is fixed once it is created
3. Binary Search Tree size is fixed once it is created
4. AVL Tree size is fixed once it is created
55. Linked list always contains elements that can be described as,

1. Redundant
2. Recursive
3. Self-referential
4. Bidirectional
56. One difference between a queue and a stack is

1. Queues require dynamic memory, but stacks do not.
2. Stacks require dynamic memory, but queues do not.
3. Queues use two ends of the structure, stacks use only one.
4. Stacks use two ends of the structure, queues use only one.
57. Stack and Queue can be implemented using ________.

2. Binary Tree
3. Binary Search Tree
4. AVL Tree
58. New items are added at the ________ of the stack.

1. Bottom
2. Middle
3. Top
4. Center
59. ________ is the stack characteristic but ________ was implemented because of the size limitation of the array.

1. isFull(), isEmpty()
2. pop(), push()
3. isEmpty(), isFull()
4. push(), pop()
60. The difference between a "Binary Tree (BT)" and a "Binary Search Tree (BST)" is that,

1. A BST has two children per node whereas a BT can have none, one or two children per node
2. In BST nodes are inserted based on the values they contain
3. In BT nodes are inserted based on the values they contain
4. There is no difference
61. Which of the following operations returns "most recently entered value" from the stack?

1. Push
2. Recent
3. Top
4. First
62. Which of the following is correct about AVL Tree?

1. It is identical to BST except height of the left and right subtrees can differ by at least 1.
2. It is identical to BST except height of the left and right subtrees must differ by at least 1.
3. It is not identical to BST, it is totally different kind of tree.
4. It is identical to BST except height of the left and right subtrees can differ by at most 1.
63. In the call by ________ methodology, a copy of the object is passed to the called function.

1. Reference
2. Value
3. Reference & Value
4. Copy of the object can not be passed
64. Recursive call of a function use ________ data structure.

2. Queue
3. Stack
4. Table
65. The variables which are destroyed automatically when a function's execution ends are:

1. Global variables
2. Local variables defined inside function body
3. Variables (objects) defined inside function body dynamically
4. Variables (objects) defined inside function body statically
66. The worst case of searching in binary search tree (BST) is:

1. When the data inserted in BST is sorted
2. When the height of left sub-tree is greater than right sub-tree
3. When the height of right sub-tree is greater than left sub-tree
4. When the tree is balanced
67. 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.
68. 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.

## Course Codes

Select a course code for Objective Questions:

Select a course code for Subjective Questions: