• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 3 fuera de 27 páginas
Examen

StudySet CS445 Term 2 Exam With Complete Solutions

Document preview thumbnail
Vista previa 3 fuera de 27 páginas

StudySet CS445 Term 2 Exam With Complete Solutions...

Vista previa del contenido

StudySet CS445 Term 2 Exam With
Complete Solutions



Consider the following code in the findWord method discussed in lecture:
answer = findWord(r, c+1, word, loc+1, bo);
if (!answer)
answer = findWord(r+1, c, word, loc+1, bo);
// more lines not shown
Explain the purpose of the if statement prior to the second call of findWord()
Select an answer and submit. For keyboard navigation, use the up/down arrow keys to
select an answer.
a) The second call will not typically be needed
b) We only try the next direction if we did not succeed in the previous direction
c) It is an error -- the "if" statement should not be there - ANSWER b) We only try the
next direction if we did not succeed in the previous direction

We can define the Towers of Hanoi solution in the following way:To move N disks from
start to end we Recursively move N-1 disks from _______ to _______ Move 1 disk from
start to end Recursively move N - 1 disks from _______ to _______ For each blank,
enter one of the values: start, middle, end. - ANSWER start to middle
middle to end

The worst case situation for InsertionSort of an array occurs when

a) The data is already sorted
b) The data is reverse sorted
c) The data is randomly distributed
d) All cases for InsertionSort have the same behavior - ANSWER b) The data is reverse
sorted

Assume you are in the last iteration of the outer loop for InsertionSort. Which statement
below is correct?
a) The last remaining item goes at the end of the array and no comparisons are needed

,b) The last remaining item must be moved all the way to the front of the array and N-1
comparisons are needed
c) The last remaining item could end up in any position within the array. - ANSWER c)
The last remaining item could end up in any position within the array.

In ShellSort, the last iteration of the outer loop
a) Has nothing left to do since the data is sorted by this point
b) Does a full InsertionSort of the data
c) InsertionSorts the data that are N/2 locations apart in the array
d) SelectionSorts the remaining items in the array - ANSWER b) Does a full
InsertionSort of the data

Consider the MergeSort algorithm as discussed in lecture. At what point in the algorithm
are the data actually compared to each other?
a) As the data are being divided before the recursive calls
b) In between the two recursive calls
c) After both recursive calls have completed
d) MergeSort is not a comparison-based sorting algorithm - ANSWER c) After both
recursive calls have completed

When a backtracking algorithm "backtracks", what is happening in the execution?

a) A new activation record is being pushed onto the run-time stack
b) An activation record is being popped off of the run-time stack
c) Execution continues using the same activation record
d) A loop iterates - ANSWER b) An activation record is being popped off of the run-time
stack

Consider the 8-Queens problem as discussed in lecture (with indices from 0 to 7). If a
queen CANNOT be placed in row 6 of column k, the algorithm will

a) Try to place a queen in row 5 of column k
b) Try to place a queen in row 7 of column k
c) Try to place a queen in row 0 of column k+1
d) Backtrack to column k-1 and resume in the next row there - ANSWER b) Try to place
a queen in row 7 of column k

Which of the following are true about a solution to the 8-Queens problem? Indicate all
true answers.

a) There is exactly 1 queen in each column of the board
b) There is exactly 1 queen in each row of the board
c) There is exactly 1 queen in each diagonal of the board - ANSWER a) There is exactly
1 queen in each column of the board
b) There is exactly 1 queen in each row of the board

, What does each recursive call represent in our 8-Queens problem solution?

a) Placing a queen somewhere within a given row of the board
b) Placing a queen somewhere within a given column of the board
c) Placing all of the queens on the board - ANSWER b) Placing a queen somewhere
within a given column of the board

When we backtrack from call K to call K-1 in our 8-Queens solution, what do we do
next?

a) Remove the queen from its current row in column K-1
b) Make a new recursive call to column K+1
c) Backtrack to column K-2 - ANSWER a) Remove the queen from its current row in
column K-1

In our FindWord solution (to find Strings in a 2-d grid of characters), if we start at
position (row, col) in the grid and we have been unsuccessful at finding the String in all
directions, what does this mean?

a) The String is not in the grid - there is no solution
b) The String is not found starting at position (row, col) but could be somewhere else -
ANSWER b) The String is not found starting at position (row, col) but could be
somewhere else

In the FindWord problem, if we succeed in finding a string at some position in the board,
why might we still want to backtrack / continue the search? - ANSWER To find more
than one solution

In the findWord() method that was discussed, in a given call we store the current
location, loc, that we are trying to match within the goal string (i.e. we want board[r][c]
== word.charAt(loc) to be true). When a call to findWord() backtracks, how do we
update the value of loc to go back to its previous value (i.e. one index smaller)?

a) We decrement loc so that it is assigned a smaller value (ex: loc = loc - 1).
b) We have a list of loc values stored and access the previous one, which should have
the previous value
c) When the previous call resumes the value of loc in its activation record is the value
that we want - ANSWER c) When the previous call resumes the value of loc in its
activation record is the value that we want

In the Towers of Hanoi solution, how many disks are actually moved in a single call to
the method? - ANSWER 1.0

In the Towers of Hanoi solution with N = 5, how many total moves must be performed? -
ANSWER 31.0

Información del documento

Subido en
28 de septiembre de 2026
Número de páginas
27
Escrito en
2026/2027
Tipo
Examen
Contiene
Preguntas y respuestas
$18.49

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Zayla
3.2
(20)
Vendido
163
Seguidores
13
Artículos
18577
Última venta
4 días hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes