final exam_DIS Flashcards
In the graph given below, which of the following nodes will be visited last if you apply breadth-first search starting from A?
H
An algorithm to traverse a directed graph must mark vertices when they have been visited.
True
Shortest path problem can be solved with an easy modification of the depth-first search algorithm
False
Depth-first search can use a queue for tracking visited nodes.
False
Breadth-first search can use a queue for tracking visited nodes
True
Adjacency matrix representation causes redundancy in undirected graphs since the matrix is always symmetric.
True
Depth-first search starts from the root of the graph.
False
Traveling salesman problem is an NP-complete problem.
True
Red-Black Tree does not need rotations since recoloring always keeps the tree balanced
False
If your application involves frequent insertions and deletions, then Red-Black tree should be preferred to AVL tree.
True
Each node stores at most 4 data values in a 2-3-4 Tree
False
The root of the tree is always red in a red-black tree.
False
In a directed graph, there may not be a path from one node to another.
True
There must be a root node in a directed graph which does not have an incoming arc
False
All the leaves are on the same level in a 2-3-4 Tree
True
Which of the following tree is used for external search?
B-Tree
A rotation is needed in an AVL Tree when the balance factor of a node becomes -3 or +3 after insertion
False
One simple rotation is sufficient to keep AVL Tree balanced after each insertion or deletion
False
ASCII is a variable-length coding scheme.
False
AVL Tree is a balanced binary search tree.
True
The worst case search time in AVL Tree is O(log2n)
True
The worst case computing time of merge sort is O(n*logn).
True
Radix sort operates in O(n+w) time, where w is the number of digits.
False
Quick sort requires more space than Radix sort.
False
Merge sort can be used both as an internal and an external sort.
True
Which of the following array is created after the first iteration of Radix sort, when the array contains {67,22,44,79,25,81,56,38}?
{81,22,44,25,56,67,38,79}
Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts.
True
The worst case computing time of quick sort is O(n*logn).
False
The best method to select a pivot in quick sort is selecting the first element as pivot.
False
Which of the following array is the result of the split operation, when the array contains {20,22,14,19,25,12} and 20 is selected as pivot in quick sort?
{19,12,14,20,25,22}
Which of the following array is created after the first iteration of binary merge sort, when the array contains {17,22,14,19,25,12,9,7}?
{17,22,14,19,12,25,7,9}
A heap can be used to implement a priority queue efficiently.
True
What is the worst case computing time of selection sort?
O(n2)
What is the worst case computing time of heap sort?
O(nlog2n)
What is the worst case computing time of bubble sort?
O(n2)
What is the worst case computing time of inserting an element to a heap?
O(log2n)
What is the worst case computing time of retrieving (without deleting) the maximum element in a heap?
O(1)
