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
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