Introduction to Algorithms

Midterm exam, $2024\mathrm{.}04\mathrm{.}22$: $14\mathrm{.}00-16\mathrm{.}00$

$($b$)$ To move a node down in the heap to restore the heap$-$order property

$($c$)$ To insert a new node into the heap

$($d$)$ To remove the maximum node from the heap $43$ What is the purpose of the sink$()$ method in a binary heap implementation?

$($a$)$ To move a node up in the heap to restore the heaporder property

$($b$)$ To move a node down in the heap to restore the heap$-$order property

$($c$)$ To insert a new node into the heap

$($d$)$ To remove the maximum node from the heap

$44$ What is the purpose of the compareTo$()$ method in the Comparable interface?

$($a$)$ To compare two objects and determine their order

$($b$)$ To convert an object to a string

$($c$)$ To check if two objects are equal

$($d$)$ To create a copy of an object

$45$ What is the purpose of the hasNext$()$ and next$()$ methods in the Iterator interface?

$($a$)$ To check if there are more elements to iterate over and to access the next element

$($b$)$ To add and remove elements from a collection

$($c$)$ To sort the elements in a collection

$($d$)$ To search for an element in a collection $46$ What is the primary factor that determines the exponent $"$b$"$ in the power$-$law relationship of an algorithm's running time $)=(a{N}^b?$

$($a$)$ The hardware specifications of the computer

$($b$)$ The programming language used to implement the algorithm

$($c$)$ The number of input elements $($N$)$

$($d$)$ The inherent efficiency of the algorithm itself $47$ When analyzing the memory usage of a Java object, what contributes to its "object overhead"?

$($a$)$ The memory used by its instance variables

$($b$)$ The memory used by its methods

$($c$)$ The memory used for internal housekeeping information and object references

$($d$)$ The memory used for padding to align the object size to a multiple of $8$ bytes

Name:

Student ID:

$48$ In the context of algorithm analysis, what is the difference between "amortized analysis" and "worst$-$case analysis"?

$($a$)$ Amortized analysis considers the average cost of operations over a sequence, while worst$-$case analysis focuses on the cost of the most expensive operation

$($b$)$ Worst$-$case analysis considers the average cost of operations over a sequence, while amortized analysis focuses on the cost of the most expensive operation

$($c$)$ Amortized analysis is used for recursive algorithms, while worst$-$case analysis is used for iterative algorithms

$($d$)$ They are essentially the same concept and can be used interchangeably

$49$ When implementing a queue using a linked list, what is the most efficient approach for enqueue and dequeue operations?

$($a$)$ Insert and remove elements from the same end of the linked list

$($b$)$ Insert elements at the front and remove elements from the end of the linked list

$($c$)$ Insert elements at the end and remove elements from the front of the linked list

$($d$)$ Insert and remove elements from the middle of the linked list

$50$ What is the primary reason for using a "resizing array" implementation for a stack, compared to a fixed$-$size array

$($a$)$ A resizing array allows for more efficient use of memory, as it can grow and shrink dynamically bas on the number of elements

$($b$)$ A resizing array enables faster access to elements compared to a fixed$-$size array

$($c$)$ A resizing array simplifies the implementation of $t$ stack, as there is no need to handle overflow conditions

$($d$)$ A resizing array allows for more efficient sorting searching operations compared to a fixed$-$size at

$-----$ End of questions

$\frac{4}{41}$