→ Lecture 16, 18, 20 → Rozpocznij Naukę / Ściągnij Fiszki MP3

Pytanie		Odpowiedź
Quick sort uses which of the following algorithm to implement sorting? rozpocznij naukę		divide and conquer
What is a randomized quick sort? rozpocznij naukę		quick sort with random choice of pivot
What is the auxiliary space complexity of randomized quick sort? rozpocznij naukę		O(log n)
What is the average time complexity of randomized quick sort? rozpocznij naukę		O(n log n)
Randomized quick sort is an in place sort. rozpocznij naukę		True
Randomized quick sort is a stable sort. rozpocznij naukę		False
What is the best case time complexity randomized quick sort? rozpocznij naukę		O(nlog n)
Which of the following is incorrect about randomized quicksort? rozpocznij naukę		it cannot have a time complexity of O(n^2) in any case
What is the worst case time complexity of randomized quicksort? rozpocznij naukę		O(n^2)
Using division method, in a given hash table of size 157, the key of value 172 be placed at position ____ rozpocznij naukę		15
Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored rozpocznij naukę		True
What is the average retrieval time when n keys hash to the same slot? rozpocznij naukę		Theta(n)
What is a hash table? rozpocznij naukę		A data structure used to store key-value pairs
How does a hash table work? rozpocznij naukę		It uses a hash function to map keys to array indices
What is the time complexity of inserting an element in a hash table? rozpocznij naukę		O(1)
What is the worst-case time complexity of searching for an element in a hash table? rozpocznij naukę		O(n)
What happens if two keys hash to the same index in a hash table? rozpocznij naukę		A collision occurs
Depth First Search is equivalent to which of the traversal in the Binary Trees? rozpocznij naukę		Pre-order Traversal
Time Complexity of DFS is? (V – number of vertices, E – number of edges) rozpocznij naukę		O(V + E)
The Data structure used in standard implementation of Breadth First Search is? rozpocznij naukę		Queue
The Depth First Search traversal of a graph will result into? rozpocznij naukę		Tree
When the Depth First Search of a graph is unique? rozpocznij naukę		When the graph is a Linked List
In Depth First Search, how many times a node is visited? rozpocznij naukę		Equivalent to number of indegree of the node

Lecture 16, 18, 20

Musisz się zalogować, by móc napisać komentarz.