CS 302 Midterm Exam QUESTIONS WITH CORRECT ANSWERS 100% VERIFIED|
GUARANTEED SUCCESS
What is the reason for using an adjacency matrix instead of an adjacency list to represent a
graph? - allow you to check if an edge exists between two vertices in O(1) time
- if graph is dense (a lot of edges) then a matrix is more space efficient
what data structure is commonly used to implement a graph adjacency list
What is the worst-case scenario for quick sort? O(n^2)
What algorithm is used to find the shortest path from x node to y node in a weighted graph?
Dijkstra's
Which sorting algorithm always used a pivot to partition the data quick sort
What is the Big O running time for merge sort n log n
Which of the following is true about Dijkstra's algorithm Dijkstra's algorithm uses a priority
queue to select the next node with the smallest known distance.
Which sorting algorithm is theoretically the fastest merge/quick sort
What does DFS stand for Depth First Search
Which graph searching algorithm should not be implemented recursively BFS
, What does Dijkstra's algorithm do Find the shortest path between two vertices.
For disjoint sets, which of the following is NOT a way to construct a union union by width
Name a sorting algorithm that is stable bubble, insertion, merge
Which sorting algorithm does not divide and conquer bogo/monkey sort
What container does BFS use queue
What container does DFS use stack
In a disjoint set, what is the difference between union by height and union by rank with path
compression union by height:
the height of the root is the number of elements in the longest path in the set.
union by rank:
equivalent to union by height but path compression is performed on find operations. each time
you call find(), the links field of all elements on the path to the root are updated so they all
equal the root
Which sorting algorithm involves selecting a random partition and sorting the elements on each
side of the partition quicksort
What is a disjoint set and how is union used with them a disjoint set partitions elements into
different sets. No item belongs to more than one set, but all items belong to some set. The
GUARANTEED SUCCESS
What is the reason for using an adjacency matrix instead of an adjacency list to represent a
graph? - allow you to check if an edge exists between two vertices in O(1) time
- if graph is dense (a lot of edges) then a matrix is more space efficient
what data structure is commonly used to implement a graph adjacency list
What is the worst-case scenario for quick sort? O(n^2)
What algorithm is used to find the shortest path from x node to y node in a weighted graph?
Dijkstra's
Which sorting algorithm always used a pivot to partition the data quick sort
What is the Big O running time for merge sort n log n
Which of the following is true about Dijkstra's algorithm Dijkstra's algorithm uses a priority
queue to select the next node with the smallest known distance.
Which sorting algorithm is theoretically the fastest merge/quick sort
What does DFS stand for Depth First Search
Which graph searching algorithm should not be implemented recursively BFS
, What does Dijkstra's algorithm do Find the shortest path between two vertices.
For disjoint sets, which of the following is NOT a way to construct a union union by width
Name a sorting algorithm that is stable bubble, insertion, merge
Which sorting algorithm does not divide and conquer bogo/monkey sort
What container does BFS use queue
What container does DFS use stack
In a disjoint set, what is the difference between union by height and union by rank with path
compression union by height:
the height of the root is the number of elements in the longest path in the set.
union by rank:
equivalent to union by height but path compression is performed on find operations. each time
you call find(), the links field of all elements on the path to the root are updated so they all
equal the root
Which sorting algorithm involves selecting a random partition and sorting the elements on each
side of the partition quicksort
What is a disjoint set and how is union used with them a disjoint set partitions elements into
different sets. No item belongs to more than one set, but all items belong to some set. The
