Font size
WorksheetsEC8393_FDS_MODEL_EXAM_1_PART A
Total questions: 30
Worksheet time: 30mins
Where is linear searching used?
When the list has only a few elements
When performing a single search in an unordered list
Used all the time
When the list has only a few elements and When performing a single search in an unordered list
What is the best case for linear search?
O(nlogn)
O(logn)
O(n)
O(1)
What is the best case and worst case complexity of ordered linear search?
O(nlogn), O(logn)
O(logn), O(nlogn)
O(n), O(1)
O(1), O(n)
What is the advantage of recursive approach than an iterative approach?
Consumes less memory
Less code and easy to implement
Consumes more memory
More code has to be written
Binary Search can be categorized into which of the following?
Brute Force technique
Divide and conquer
Greedy algorithm
Dynamic programming
What is the time complexity of binary search with iteration?
O(nlogn)
O(logn)
O(n)
O(n2)
What is an external sorting algorithm?
Algorithm that uses tape or disk during the sort
Algorithm that uses main memory during the sort
Algorithm that involves swapping
Algorithm that are considered ‘in place’
What is the worst case complexity of bubble sort?
O(nlogn)
O(logn)
O(n)
O(n2)
Which of the following sorting algorithms is the fastest?
Merge sort
Quick sort
Insertion sort
Shell sort
Which of the following methods is the most effective for picking the pivot element?
first element
last element
median-of-three partitioning
random element
If several elements are competing for the same bucket in the hash table, what is it called?
Diffusion
Replication
Collision
Duplication
What is a hash function?
A function has allocated memory to keys
A function that computes the location of the key in the array
A function that creates an array
A function that computes the location of the values in the array
Which of the following is not a collision resolution strategy for open addressing?
Linear probing
Quadratic probing
Double hashing
Rehashing
Which scheme uses a randomization approach?
hashing by division
hashing by multiplication
universal hashing
open addressing
What is the maximum number of children that a binary tree node can have?
0
1
2
3
How many common operations are performed in a binary tree?
2
3
4
5
General ordered tree can be encoded into binary trees.
True
False
If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?
2i+1
2i+2
2i
4i
What is the speciality about the inorder traversal of a binary search tree?
It traverses in a non increasing order
It traverses in an increasing order
It traverses in a random fashion
None of the mentioned
What does the following piece of code do?
public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
}
Preorder traversal
Inorder traversal
Postorder traversal
Level order traversal
The number of edges from the root to the node is called __________ of the tree.
Height
Depth
Length
Width
What is a full binary tree?
Each node has exactly zero or two children
Each node has exactly two children
All the leaves are at the same level
Each node has exactly one or two children
What data structures are used to implement BFS and DFS respectively?
Linked Lists and Stacks
Queues and Stacks
Stacks and Queues
All of the above
What strategies are used in BFS and DFS traversals respectively?
Level by level and depth wise
Depth wise and level by level
Children before siblings and siblings before children
Siblings before children and children before siblings
Which of these operators have the highest order of precedence?
‘(‘ and ‘)’
‘*’ and ‘/’
‘~’ and ‘^’
‘+’ and ‘-‘
While evaluating a postfix expression, when an operator is encountered, what is the correct operation to be performed?
push it directly on to the stack
pop 2 operands, evaluate them and push the result on to the stack
pop the entire stack
ignore the operator
Which of the following is not an application of stack?
evaluation of postfix expression
conversion of infix to postfix expression
balancing symbols
line at ticket counter
The data structure required to check whether an expression contains balanced parenthesis is?
Stack
Queue
Array
Tree
The postfix form of A*B+C/D is?
*AB/CD+
AB*CD/+
A*BC+/D
ABCD+/*
Which data structure is used for implementing recursion?
Queue
Stack
Array
List
