Font size
WorksheetsADS_SDA
Total questions: 85
Worksheet time: 43mins
Array elements ____ before a binary search can be perfomed
summed
sorted
set to zero
positive of the mentioned
none of the mentioned
When two identifiers are hashed into the same bucket, it is known as
Collision
Synonyms
Overflow
When you run recursive methods, the computer creates for you:
Stack
Queue
Heap
LinkedList
Hashing gives each item
A sequential address
No address
A logarithmic address
A unique address
What is the time complexity of finding the maximum element in a max-heap?
O(1)
O(Log n)
O(n)
O(n^2)
Specity ArrayList advantages over LinkedList
arrayList is better for string and accessing the data
arrayList is better for manipulating the data
cadding and removing an element
none of the mentioned
What does the Hash table look like?
An array of multi-linked lists
Table of arrays
An array of singly-linked lists
Graph
What is the maximum number of elements that can be stored in a stack of size N?
N
N-1
2N-1
42500
A binary tree is a data structure where each node has at most two children.
True
False
Suppose we have an O(n) time algorithm that finds the median of an unsorted array. Now consider a QuickSort implementation where we first find the median using the above algorithm, then use the median as a pivot. What will be the worst-case time complexity of this modified QuickSort?
O (logn)
O (n^2)
O (nlogn)
O (n^2 logn)
_ is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity..
Big O notation
Counting operations
Linear complexity
None of the listed
Select time complexity of heap sort.
O (nlogn)
O (logn)
O(n)
O(n-1)
Given an unsorted array. The array has this property that every element in the array is at most k distance from its position in a sorted array where k is a positive integer smaller than the size of an array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
None of the mentioned
Heap Sort with time complexity O(nlogk)
Quick Sort with time complexity O(kLogk)
Merge Sort with time complexity O(kLogk)
What is Breadth First Search (BFS)? An algorithm used to traverse a tree or graph data structure
An algorithm used to traverse a tree or graph data structure
An algorithm used to sort an array in ascending order
An algorithm used to search for a specific element in a linked list
An algorithm used to find the maximum sum of a subarray in an array
The hashCode is used to get an index of chain by hash0) method
True
False
Which of the following are types of LinkedList
singly-linked, doubly linked, multi-linked
singly-linked, circular-linked, multi-linked
singly-linked, doubly-linked, circular-linked
circular-linked, doubly-linked, multi-linked
Which data structure can be used to implement a queue?
Array
LinkedList
Stack
Tree
Recursion can be implemented with just using loops
True
False
Which of the following set 1 related to set 2?
Set 1
a. Linear search
b. Binary search
c. Hash table
Set 2
i. Collision
ii. Both sorted and unsorted array
iii. Only sorted array
. a-iii, b-ii, c-i. a-iii, b-ii, c-i
a- ii, b - iii, c-i
a-i, b-iii, c-ii. a-i, b-ii, c-iii
. a-i, b-ii, c-iii
Choose worst case of quick sort when the selected pivot point is always the smallest or largest
O(logn)
O(n)
O(n-1)
O(n^2)
Recursion is implemented by the queue, and each time you invoke a method, the method is placed on top of the queue.
True
False
In recursion the value of control variable moves towards the value in condition
True
False
Specify ArrayList advantages over LinkedList
less memory usage
arrayList is better for manipulating the data
adding and removing an element
none of the mentioned
When 2 elements map to the same slot in the hash table, it is called
collision
searching
sorting
none of the mentioned
What is a cycle in a graph?
A path that starts and ends at the same vertex
A path that connects all vertices in the graph
A path that contains at least one repeated vertex
A path that contains at least one repeated edge
Which of the following is true about add() method ofArrayList?
method inserts the specified element at the specified position in this list
method has a return value
method inserts value to the next node of the specified element
all of the above
The worst case running times of Bubble sort, Merge sort and Quick sort, respectively, are:
O(n log n), O(n log n) and O(n²)
O(n), O(n²) and O(n Log n)
O(n²), O(n log n) and O(n log n)
O(n), O(n log n) and O(n)
Following code finds a specific number in the sorted array (or return -1 if the value isn't in the array).
static int searchSorted(int arr[], int 1, int r. int x)
if (r == 1) {
int mid 1 (r-1)/2;
if (arr[mid] == x) return mid;
if (arr[mid]> x)
return searchSorted(arr, 1, mid - 1, x);
return searchSorted(arr, mid 1, r, x);
return -1;
What is the time complexity of this algorithm?
O (logn)
O(n^2)
O (nlogn)
O (n)
What will be print when the following code executes?
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(7);
arcaylist.add(8);
arrayList.add(9);
System.out.println(arraylist.remove(0));
7
8
9
0
What is the minimum number of elements in a heap with height 3?
7
8
15
16
What is a Stack data structure?
A data structure that follows LIFO (Last-In-First-Out) order
A data structure that follows FIFO (First-In-First-Out) order
A data structure that allows random access to elements
A data structure that stores elements in a sorted manner
Which operation adds an element to the top of the stack?
push()
pop()
peek()
size()
What is double-linked list?
each node points to the next node
each node points to the next and previous nodes
. last node points to the first
each node points to all previous nodes
What happens when DFS encounters a node that has already been visited?
. The algorithm continues without visiting the node again
The algorithm restarts from the beginning of the graph
The algorithm backtracks to the previous node and continues from there
The algorithm marks the node as visited again
Consider a hash table with 7 slots. The hash function is h(x) = x % 7. The collision are resolved by chaining. The following 7 keys are inserted in the order: 12, 66, 45, 86, 49, 8, 20. Find the maximum and minimum chain lengths (the max, min linked list sizes) in the hash table.
3 and 0, respectively
2 and 0, respectively
1 and 0, respectively
2 and 1, respectively
Which data structure can be used to implement a heap?
Array
LinkedList
Queue
Tree
What is the focus of determining the order of growth?
Leading coefficients
Lower-order terms
Dominant terms
All terms
How Horner's method is used to hash string of length L?
Ladds/divides
. L multiples/subtract
L multiplies/adds
L subtract/divide
For the Binary Search Tree is the following statement True or False: All nodes of left subtree are more than the root node.
True
False
What is a min-heap?
A heap in which the smallest element is at the root.
A heap in which the largest element is at the root
A heap that is empty.
A heap that contains only one element.
Data structure that has the same size throughout the program on
Array
ArrayList
LinkedList
HashTable
Which of the following operations can be performed on a binary search tree in O (logN) time?
Insertion
Deletion
Search
All of the above
This method will return true only in case if;
public static boolean check (String s){
return s.length() >= 2 && (s.charAt(0) == s.charAt(1) || check(s.substring(1))); }
. The string s contains two or more of the same character that are next to each other
The string s contains two or more of the same characters
The string s starts with two or more of the same characters.
The string s ends with two or more of the same characters
In a graph with multiple connected components, how many times will BFS be called?
Once
Twice
The number of connected components
The number of edges in the graph
What is the time complexity for adding an element at the beginning of LinkedList?
O(o)
O(1)
O(n^2)
O(logn)
Recursive code tends to be bigger in size compared to code based on iteration
True
False
What is the time complexity of searching for a value in a binary search tree of N nodes in the worst case?
O(n^2)
O(logn)
O(n)
O(nlogn)
What is a binary tree?
Aibar
A tree with at Most Two children per node
Elfbar
KTL
The load Factor is a current capacity of the hash table
True
False
Big-O notation of the following expression is equal to linear complexity. O(n)+O(n*n) O(n)
true
false
What is the maximum number of nodes in a binary tree of height h?
2^h-1
h^2
2*h
hl
Array elements must be ____ before a binary search can be performed
summed
sorted
set to zero
positive numbers
Which sorting algorithm is best suited for sorting linked lists?
Merge Sort
Quick Sort
Bubble Sort
None of the mentioned
Let us consider a list of numbers (12, 40, 96, 33, 57, 81, 8) and has table size is 10.
What is the order elements (from index 0 to size - 1) in the hash table by using the hash function h(x) = x % size of hash table?40, 81, 12, 33, null, null, 96, 57, 8, null
40, 81, 12, 33, null, null, 96, 57, 8, null
8, 12, 33, 40, 57, 81, 96, null, null, null
null, null, 57, 96, 12, null, 40, 33, 8, 81
null, null, null, 8, 12, 33, 40, 57, 81, 96
Consider a 13 element hash table for which h(key) = key % 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 102 be inserted, if the keys 99, 15, 63 and 102 are inserted in that order?
12
11
0
None of the mentioned
Can a constant time algorithm have loops or recursive calls?
No, it is not possible
Yes, but only if the number of iterations or calls is independent of the input size
Yes, but only if the number of iterations or calls is proportional to the input size
Yes, but only if the number of iterations or calls is greater than the input size
Which statement is the correct declaration and initialization of an ArrayList of String values?
ArrayList<String> name
name = ArrayList<String>();
ArrayList<String> name;
name = new ArrayList<String>();
ArrayList name;
name = new ArrayList<String>();
String<ArrayList> name;
name = new String<ArrayList>();
None of the mentioned
LinkedList can NOT be of generic type <T>
True
False
What advantage does a linked list have over an array?a. Size of the list doesn't need to be mentioned at the beginning of the program
Size of the list doesn't need to be mentioned at the beginning of the program
You can add or remove elements from the middle of the list.
The linked list doesn't have a size limit
all of the above
Which data structure can be used to implement a stack?
Array
Linked List
Queue
Tree
We can use the following function below to determine the sum of an array of numbers. What is the Big O notation for this algorithm?
static int[] array={36,14,1,7,21};
public static int sumOfSequentialArray(int[] array) { int sum=0;
for (int i=0; i<array.length; i++){
}
}
sum+=array[i];
return sum;
O(n)
O(logn)
O(1)
O(n*n)
The time complexity of the given example is:
public static int fib(int n) { if(n<=1) return n;
return fib(n-2)+ fib(n-1);
}exponential
exponential
logarithmic
linearithmic
quadratic
Our algorithm needs to find every index where the item exists. The algorithm is below. What is the Big O runtime for this algorithm?
public static void main(String[] args) {
List<String> values = List.of("A", "B", "C", "B"); String item = "B";
List<Integer> indices = new ArrayList<>();
for (int i = 0; i < values.size(); i++) {
if (Objects.equals (values.get(i), item)) { indices.add(i); }
}
System.out.println(indices);
O(log n)
O(nlogn)
O(n)
O(1)
Look at square numbers: square(1) = 1; square(N) = square(N-1) + 2N -1
Which method below successfully implements this definition?
int square( int N ){
if ( N==1 ) {
return 1;
}
else
{
return square(N-1) + 2*N - 1;
}
}
int square( int N ){
if ( N&1 ) {
return 1;
}
else
{
return N*N;
}
int square( int N ){
if ( N=1 ) {
return 1;
}
else
{
return square(N-1) + 2*N - 1;
}
}
int square( int N ){
if ( N==1 )
{
return 1;
}
else {
return square(N);
}
}
Which traversal visits the left subtree first, then the root node, and finally the right subtree?
Preorder traversal
Inorder traversal
Postorder traversal
Lvl-order traversal
Specify ArrayList advantages over LinkedList
increasing the size
arrayList is better for manipulating the data
more memory usage
arrayList is better for storing and accessing the data
What will be the output of the following code:
int factorial(int n) {
if(n == 0)
return 1;
else
return n * factorial(n-1);
}
int main() {
int number = 5;
cout<<factorial(number);
return 0;
}
0
1
5
120
What data structure is commonoly used to implement BFS?
Stack
Queue
Heap
Binary tree
Data structure that can increase by itself
Array
ArrayList
LinkedList
HashTable
Binary Search can be categorized into which of the following?
Brute Force technique
Divide and conquer
Greedy algorithm
Dynamic programming
All of the mentioned
Choose a worst case time complexity of insertion sort algorithm.
O(n)
O(n^2)
O(n-1)
O(1)
Which of the following is not a typical application of queues?
Process scheduling
Message passing between processes
Breadth-first search algorithm
Depth-first search algorithm
What will be print when the following code executes?
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(7);
arcaylist.add(8);
arrayList.add(9);
System.out.println(arraylist.remove(0));
7
8
9
0
When 2 elements map to the same slot in the hash table, it is called
collision
searching
sorting
none of the mentioned
What does the Hash table look like?
An array of multi-linked lists
Table of arrays
. An array of singly-linked lists
Graph
Unlike that of selection sort, the running time of insertion sort depends on the initial order of the items in the input.
True
False
In Hashing so-called hash code can be used as a way to narrow down our search when looking for the item in the set
True
false
____ is a data structure that can efficiently support the basic priority-queue operations
String objects
Binary heap
Node
Linked lists
What index value is used to locate the last element in the numbers ArrayList?
numbers.size()
numbers.length() - 1
numbers.size()-1
numbers.length()
Which of the following operations can be perfomed on a binary search tree in O(log N) time?
insertion
delection
search
all the mentions
Data structure that has same size throughput the program
array
arrayList
LinkedList
HashTable
Big O-notation of the following expression is equal to linear complexity
True
False
Consider a hash table with 7 slots.The hash function is (не видно) array will look like:
49,8,86,66,45,12,20
12,66,45,86,49,8,20
20,12,45,66,86,8,49
8,12,20,45,49,66,86
The worst case running times of Insertion sort,merge sort and quick sort ,respectively ,are:
O(n log n),O(n log n) and O(n^2)
O(n^2),O(n^2) and O(n log n)
O(n^2),O(n log n) and O(n log n)
O(n^2),O(n log n) and O(n^2)
What is the maximum number of nodes in a binary tree of height h?
2^h-1
h^2
2*h
hl
