Font size
WorksheetsECS 36C Quizizz
Total questions: 29
Worksheet time: 6mins
Which of these is a divide and conquer algorithm?
Merge Sort
Insertion Sort
Bubble Sort
Selection Sort
What algorithm is used to find the shortest path in a graph?
Linear Search
Binary Search
Dijkstra's
Depth First Search
What data structure uses LIFO?
Linked List
Stack
Queue
Array
What is the worst case time complexity of a linear search?
O(log n)
O(1)
O(n^2)
O(n)
In its most basic form, what does a node in a Linked List consist of?
Data
One area for data, and one area with a pointer to the next node in the list
Pointers to the head and tail of the Linked List
An adjacency matrix
What makes a tree 'binary'?
Each node has two parent nodes
Each edge is bi-directional
Each node can have at most two child nodes
The tree has two root nodes
What is the tree height?
The maximum number of edges between the root node and a leaf node
The number of internal nodes
The number of leaf nodes
The total number of edges in the tree
Does a Linked List have a fixed size in memory?
Yes
No
Which data structure uses FIFO?
Array
Queue
Stack
Linked List
Which data structure allows us to access any element directly?
Stack
Queue
Linked List
Array
What is the worst-case time complexity of Bubble Sort?
O(n log n)
O(n^2)
O(logn)
O(n)
What kind of graph does Dijkstra's Algorithm not work with?
Directed
Undirected
Graphs with negative weights
Weighted
Which of these algorithms are usually implemented using recursion?
Merge sort
Bubble sort
Radix sort
Selection sort
What is recursion in programming?
A function that calls itself
When the shortest path cannot be found
A syntax error
Going in negative cycles
If an AVL tree has '2' as the balance factor (rhs-lhs), what kind of rotation is done to self-balance?
Down
Up
Right
Left
What is good about using arrays in algorithms?
No shifting operations in memory needed when array elements are deleted or inserted
In memory, an array element does not have to come right after the previous element
Memory usage is dynamic: memory usage is automatically adjusted by the number of elements in the array
Array elements can be accessed directly
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is
In the following answers, the operator '^' indicates power.
2^i
2^(i-1)
2^(i+1)
2^[(i+1)/2]
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
2^h -1
2^(h-1) – 1
2^(h+1) -1
2*(h+1)
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.
a
b
c
d
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is
i-1
floor(i/2)
ceil(i/2)
(i+2)/2
Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?
14,13,8,12,10
14,12,13,10,8
14,13,12,8,10
14,13,12,10,8
How is a value searched for in a Binary Search Tree? (fill-in-the-blank)
(a)
If we are deleting node 13, which node will replace 13 (or the in-order successor of 13)?
14
19
18
DNE
Because the adjacency matrix is symmetric, what do we know about the graph?
(a)
What is the next vertex to be visited after C is visited?
A
B
F
G
In Union-Find Cycle Detection, how is a cycle detected?
When a new union if found
When two vertices belong to diffent unions
When there is a higher number of negative vertices than positive ones
When two vertices already belong to the same union
Radix sort must use a ______ algorithm to sort the values correctly.
in-place
stable
cubic
online
What is the post-order traversal of this tree?
(a)
This is a picture of:
(note: 6 is the left child of 3)
Full Tree
Complete Tree
Balanced Binary Tree
Graph
