CS301 MCQs SOLVED FINALTERM EXAM PAPERS

Question No: 1 ( Marks: 1 ) - Please choose one
A solution is said to be efficient if it solves the problem within its resource constraints i.e. hardware and time.
► True (Page 4)
► False
Question No: 2 ( Marks: 1 ) - Please choose one
Which one of the following is known as "Last-In, First-Out" or LIFO Data Structure?
► Linked List
► Stack (Page 54)
► Queue
► Tree
Question No: 3 ( Marks: 1 ) - Please choose one
What will be postfix expression of the following infix expression?
Infix Expression : a+b*c-d
► ab+c*d-
► abc*+d-
► abc+*d-
► abcd+*-
Question No: 4 ( Marks: 1 ) - Please choose one
For compiler a postfix expression is easier to evaluate than infix expression?
► True
► False
Question No: 5 ( Marks: 1 ) - Please choose one
Consider the following pseudo code
declare a stack of characters
while ( there are more characters in the word to read )
{read a character
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"?
► selpa
► selppa
► apples
► aaappppplleess
Question No: 6 ( Marks: 1 ) - Please choose one
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)?
► 4 2
► 0 2 4
► 0 2
► 2 4
Question No: 7 ( Marks: 1 ) - Please choose one
If there are N external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?
► N -1 (Page 304)
► N+1
► N+2
► N
Question No: 8 ( Marks: 1 ) - Please choose one
If there are N internal nodes in a binary tree then what will be the no. of external nodes in this binary tree?
► N -1
► N
► N +1 (Page 303)
► N +2
Question No: 9 ( Marks: 1 ) - Please choose one
If we have 1000 sets each containing a single different person. Which of the following relation will be true on
each set:
► Reflexive (page 387)
► Symmetric
► Transitive
► Associative
Question No: 10 ( Marks: 1 ) - Please choose one
Which one of the following is NOT the property of equivalence relation:
► Reflexive
► Symmetric
► Transitive
► Associative (page 387)
Question No: 11 ( Marks: 1 ) - Please choose one
A binary tree of N nodes has _______.
► Log10 N levels
► Log2 N levels (Page 212)
► N / 2 levels
► N x 2 levels
Question No: 12 ( Marks: 1 ) - Please choose one
The easiest case of deleting a node from BST is the case in which the node to be deleted ___________.
► Is a leaf node (Page 173)
► Has left subtree only
► Has right subtree only
► Has both left and right subtree
Question No: 13 ( Marks: 1 ) - Please choose one
If there are N elements in an array then the number of maximum steps needed to find an element using Binary
Search is _______ .
► N
► N
2
► Nlog2N
► log2N (page 440)
Question No: 14 ( Marks: 1 ) - Please choose one
Merge sort and quick sort both fall into the same category of sorting algorithms. What is this category?
► O(nlogn) sorts
► Interchange sort (not sure)
► Average time is quadratic
► None of the given options. (Page 488)
Question No: 15 ( Marks: 1 ) - Please choose one
If one pointer of the node in a binary tree is NULL then it will be a/an _______ .
► External node (Page 303)
► Root node
► Inner node
► Leaf node
Question No: 16 ( Marks: 1 ) - Please choose one
We convert the ________ pointers of binary to threads in threaded binary tree.
► Left
► Right
► NULL (Page 312)
► None of the given options
Question No: 17 ( Marks: 1 ) - Please choose one
If the bottom level of a binary tree is NOT completely filled, depicts that the tree is NOT a
► Expression tree
► Threaded binary tree
► complete Binary tree (Page 323)
► Perfectly complete Binary tree
Question No: 18 ( Marks: 1 ) - Please choose one
What is the best definition of a collision in a hash table?
► Two entries are identical except for their keys.
► Two entries with different data have the exact same key
► Two entries with different keys have the same exact hash value. (page 464)
►Two entries with the exact same key have different hash values.
Question No: 19 ( Marks: 1 ) - Please choose one
Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items
are now guaranteed to be in their final spot (never to be moved again )
► 21
► 41
► 42 Click here for detail
► 43
Question No: 20 ( Marks: 1 ) - Please choose on
Suppose you implement a Min heap (with the smallest element on top) in an array. Consider the different arrays
below; determine the one that cannot possibly be a heap:
► 16, 18, 20, 22, 24, 28, 30
► 16, 20, 18, 24, 22, 30, 28
► 16, 24, 18, 28, 30, 20, 22
► 16, 24, 20, 30, 28, 18, 22 (page 334)
Question No: 21 ( Marks: 1 ) - Please choose one
Do you see any problem in the code of nextInOrder below:
TreeNode * nextInorder(TreeNode * p)
{
if(p->RTH == thread)
return( p->R );
else {
p = p->R;
while(p->LTH == child)
p = p->R;
return p;
}
}
► The function has no problem and will fulfill the purpose successfully.
► The function cannot be compile as it has syntax error.
► The function has logical problem, therefore, it will not work properly.
► The function will be compiled but will throw runtime exception immediately after the control is
transferred to this function.
Question No: 22 ( Marks: 1 ) - Please choose one
Which of the following statement is correct about find(x) operation:
► A find(x) on element x is performed by returning exactly the same node that is found.
► A find(x) on element x is performed by returning the root of the tree containing x. Click here for detail
► A find(x) on element x is performed by returning the whole tree itself containing x.
► A find(x) on element x is performed by returning TRUE.
Question No: 23 ( Marks: 1 ) - Please choose on
Which of the following statement is NOT correct about find operation:
► It is not a requirement that a find operation returns any specific name, just that finds on two elements
return the same answer if and only if they are in the same set.
► One idea might be to use a tree to represent each set, since each element in a tree has the same root,
thus the root can be used to name the set.
► Initially each set contains one element.
► Initially each set contains one element and it does not make sense to make a tree of one node only.
Question No: 24 ( Marks: 1 ) - Please choose one
In complete binary tree the bottom level is filled from ________
► Left to right (Page 323)
► Right to left
► Not filled at all
► None of the given options
Question No: 25 ( Marks: 1 ) - Please choose one
Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).
► 0 3 8 9 1 7 5 2 6 4 (Page 477)
► 2 6 4 0 3 8 9 1 7 5
► 2 6 4 9 1 7 0 3 8 5
► 0 3 8 2 6 4 9 1 7 5
Question No: 26 ( Marks: 1 ) - Please choose one
What requirement is placed on an array, so that binary search may be used to locate an entry?
► The array elements must form a heap.
► The array must have at least 2 entries.
► The array must be sorted.
► The array‟s size must be a power of two

========================================================================

Question No: 1 ( Marks: 1 ) - Please choose one
Which one of the following operations returns top value of the stack?
► Push
► Pop
► Top (page 53)
► First
Question No: 2 ( Marks: 1 ) - Please choose one
Compiler uses which one of the following in Function calls,
► Stack (page 80)
► Queue
► Binary Search Tree
► AVL Tree
Question No: 3 ( Marks: 1 ) – Please choose one
Every AVL is _________________
► Binary Tree
► Complete Binary Tree
► None of these
► Binary Search Tree
Question No: 4 ( Marks: 1 ) – Please choose one
If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have?
► 54
► 55
► 56
► 57 (page 303)
Question No: 5 ( Marks: 1 ) - Please choose one
If there are 23 external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?
► 23
► 24
► 21
► 22 (page 303)
Question No: 6 ( Marks: 1 ) - Please choose one
Which one of the following is not an example of equivalence relation?
► Electrical connectivity
► Set of people
► <= relation (page 388)
► Set of pixels
Question No: 7 ( Marks: 1 ) - Please choose one
Binary Search is an algorithm of searching, used with the ______ data.
► Sorted (page 432)
► Unsorted
► Heterogeneous
► Random
Question No: 8 ( Marks: 1 ) - Please choose one
Which one of the following is NOT true regarding the skip list?
► Each list Si contains the special keys + infinity and - infinity.
► List S0 contains the keys of S in non-decreasing order.
► Each list is a subsequence of the previous one.
► List Sh contains only the n special keys. (page 446)
Question No: 9 ( Marks: 1 ) - Please choose one
A simple sorting algorithm like selection sort or bubble sort has a worst-case of
► O(1) time because all lists take the same amount of time to sort
► O(n) time because it has to perform n swaps to order the list.
► O(n2) time because sorting 1 element takes O(n) time - After 1 pass through the list,either of these
algorithms can guarantee that 1 element is sorted. (page 487)
► O(n3) time, because the worst case has really random input which takes longer to sort.
Question No: 10 ( Marks: 1 ) - Please choose one
Which of the following is a property of binary tree?
► A binary tree of N external nodes has N internal node.
► A binary tree of N internal nodes has N+ 1 external node. (page 303)
► A binary tree of N external nodes has N+ 1 internal node.
► A binary tree of N internal nodes has N- 1 external node.
Question No: 11 ( Marks: 1 ) - Please choose one
By using __________we avoid the recursive method of traversing a Tree, which makes use of stacks and
consumes a lot of memory and time.
► Binary tree only
► Threaded binary tree (page 306 )
► Heap data structure
► Huffman encoding
Question No: 12 ( Marks: 1 ) - Please choose one
Which of the following statement is true about dummy node of threaded binary tree?
► This dummy node never has a value.
► This dummy node has always some dummy value.
► This dummy node has either no value or some dummy value. (Page 321)
► This dummy node has always some integer value.
Question No: 13 ( Marks: 1 ) - Please choose one
For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is
► N – (h – 1)
► N – (h + 1) (page 373)
► N – 1
► N – 1 + h

Question No: 14 ( Marks: 1 ) - Please choose one
What is the best definition of a collision in a hash table?
► Two entries are identical except for their keys.
► Two entries with different data have the exact same key
► Two entries with different keys have the same exact hash value. (page 464)
► Two entries with the exact same key have different hash values.

Question No: 15 ( Marks: 1 ) - Please choose one
Which formula is the best approximation for the depth of a heap with n nodes?
► log (base 2) of n (page 353)
► The number of digits in n (base 10), e.g., 145 has three digits
► The square root of n
► n
Question No: 16 ( Marks: 1 ) - Please choose one
Which of the following statement is NOT correct about find operation:
► It is not a requirement that a find operation returns any specific name, just that finds on two elements
return the same answer if and only if they are in the same set.
► One idea might be to use a tree to represent each set, since each element in a tree has the same
root, thus the root can be used to name the set.
► Initially each set contains one element.
► Initially each set contains one element and it does not make sense to make a tree of one node only.
Question No: 17 ( Marks: 1 ) - Please choose one
Which of the following is not true regarding the maze generation?
► Randomly remove walls until the entrance and exit cells are in the same set.
► Removing a wall is the same as doing a union operation.
► Remove a randomly chosen wall if the cells it separates are already in the same set. (page 424)
► Do not remove a randomly chosen wall if the cells it separates are already in the same set.
Question No: 18 ( Marks: 1 ) – Please choose one
In threaded binary tree the NULL pointers are replaced by ,
► preorder successor or predecessor
► inorder successor or predecessor (page 307)
► postorder successor or predecessor
► NULL pointers are not replaced
Question No: 19 ( Marks: 1 ) - Please choose one
Which of the given option is NOT a factor in Union by Size:
► Maintain sizes (number of nodes) of all trees, and during union.
► Make smaller tree, the subtree of the larger one.
► Make the larger tree, the subtree of the smaller one. (page 408)
► Implementation: for each root node i, instead of setting parent[i] to -1, set it to -k if tree rooted at i has k
nodes.
Question No: 20 ( Marks: 1 ) - Please choose one
Suppose we had a hash table whose hash function is “n % 12”, if the number 35 is already in the hash table,
which of the following numbers would cause a collision?
► 144
► 145
► 143
► 148
Question No: 21 ( Marks: 1 ) - Please choose o
What requirement is placed on an array, so that binary search may be used to locate an entry?
► The array elements must form a heap.
► The array must have at least 2 entries.
► The array must be sorted. ANSWER
► The array‟s size must be a power of two
Question No: 22 ( Marks: 1 ) - Please choose one
A binary tree with 24 internal nodes has ______ external nodes.
► 22
► 23
► 48
► 25 (page 303)
Question No: 23 ( Marks: 1 ) - Please choose on
In case of deleting a node from AVL tree, rotation could be prolong to the root node.
► Yes (Page 267)
► No
Question No: 24 ( Marks: 1 ) - Please choose one
when we have declared the size of the array, it is not possible to increase or decrease it during the
________of the program.
► Declaration
► Execution (page 17)
► Defining
► None of the abov
Question No: 25 ( Marks: 1 ) - Please choose one
it will be efficient to place stack elements at the start of the list because insertion and removal take
_______time.
► Variable
► Constant (page 60)
► Inconsistent
► None of the above
Question No: 26 ( Marks: 1 ) - Please choose one
_______ is the stack characteristic but _______was implemented because of the size limitation of the
array.
► isFull(),isEmpty()
► pop(), push()
► isEmpty() , isFull() (page 59)
► push(),pop()