Data Structures and Algorithms Flashcard

Front

What is the time complexity of picking an element in a binary search tree T that is smaller than the maximum element in T?

Back

Θ(1)

Front

What is an application of queues in computer science?

Back

Job scheduling, Print queue management, Network protocol implementation, All of the above.

Front

Which sorting algorithm has a time complexity of O(n log n)?

Back

Merge Sort.

Front

What is the output of sizeof(arr) for int arr[10] in C?

Back

40.

Front

What does the following pseudo-code do? function traverse(head): current = head while current != NULL: print(current.data) current = current.next

Back

Prints all elements of a linked list.

Front

Define a binary search tree (BST).

Back

A binary search tree is a data structure that maintains sorted order, where each node has at most two children, and the left child contains values less than the parent node, while the right child contains values greater.

Front

What is the average time complexity for searching an element in a balanced binary search tree?

Back

Θ(log n).

Front

What is a queue in data structures?

Back

A queue is a linear data structure that follows the First In First Out (FIFO) principle, where elements are added at the rear and removed from the front.

Front

What is the difference between a stack and a queue?

Back

A stack follows Last In First Out (LIFO) principle, while a queue follows First In First Out (FIFO) principle.

Front

What is the time complexity of the Quick Sort algorithm in the average case?

Back

O(n log n).