Font size
WorksheetsCS 241 Practice Test Week 4
Total questions: 86
Worksheet time: 19hrs 23mins
Assume that there is a function len that returns the length of a given array. Now consider the following definition for the function combine:
Which of the following loop bodies will result in the combine returning a new list with the contents of list1 preceding the contents of list2?
if ( i < len ( list1 ) ) result[i] ← list1[i]
else result[i] ← list2[i - len( list1 )]
end if
if ( i < len ( list1 ) ) result[i] ← list1[i]
else result[i] ← list2[len( list1 ) - i]
end if
if ( i < len ( list1 ) ) result[i] ← list1[i]
else i ← 0 result[i] ← list2[i + len( list1 )]
end if
if ( i < len ( list1 ) ) result[i] ← list1[i]
else result[i] ← list2[i]
end if
Assume there is a function swap(int [] array, int index1, int index2 ) which swaps the cells at index1 and index2 in array. Also assume that there is a function len which returns the length of an array. Now consider the function reverse which should reverse the order of the contents of the given array:
Which of the following calls to swap in the loop body will cause reverse to function properly?
swap ( list, i, i + len ( list ) )
swap ( list, i, len ( list ) - i )
swap ( list, i, len ( list ) - ( i - 1 ) )
swap ( list, i, len ( list ) - i - 1 )
Assume that there is a procedure len which returns the length of an array. Now consider the function leftShift, which should shift the contents of all elements in a given array to a lower index, wrapping around to the end of the array if necessary:
Which of the following could be substituted for <condition> to cause leftshift to function as intended?
j < i
j < len ( list ) + i
j < len ( list ) - 1
j < len ( list )
Assume that there is a function len which returns the length of an array. Now consider the procedure histogram ( result , data ) which should fill each index of result with the number of matching elements in the array data,
such that if the value of data was { 2, 4, 2, 1, 0 }, the value of result after execution will be { 1, 1, 2, 0, 1 }:
Which of the following pre-conditions must be true for histogram to execute without error?
result's last index must be greater than or equal to data's greatest value
result's greatest value must be greater than data's greatest value
result's greatest value must be greater than data's last index
result's last index must be greater than data's last index
Assume that there is a function len which returns the length of an array. Now consider the function fun:
What is returned by fun?
The least value in list
The index of the greatest value in list
The index of the least value in list
The greatest value in list
Assume that there is a function len which returns the length of an array. Now consider the function stuff:
The post condition of stuff is that it returns the largest value of list. Which pre-condition listed below is necessary to meet this post-condition?
list must contain only values greater than 0
list must contain only values greater than -1
list's largest value must be greater than or equal to 0.
list's largest value must be greater than 0.
The intended post-condition of the loop is that list contains values in the Fibonacci sequence { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 }. Which loop body will accomplish this post-condition?
if ( i > 1 )
list[ i ] ← list [ i - 1 ] + list [ i - 2 ]
end if
if ( i < 10 )
list[ i + 2 ] ← list [ i ] + list [ i + 1 ]
end if
if (i < 1)
list[ i + 2 ] ← list [ i ] + list [ i + 1 ]
end if
if (i < 10)
list[ i ] ← list [ i - 1 ] + list [ i - 2 ]
end if
Which choice shown below is NOT a valid declaration of an array?
int [] list
float nums []
char array letters
boolean flags
Which of the following is a feature of arrays?
Arrays are primitive data types
For a 0-based array of length 5, the index of the last cell is 5
Arrays are indexed
None of the above
Which of the following statements about arrays is NOT correct?
Access to array elements is achieved through a process called indexing.
Arrays are able to contain primitive values, objects, and even other arrays.
Arrays are stored in contiguous memory.
Arrays are dynamic, able to grow or shrink in size.
All of the elements of an array must be of the same type of data.
Given the pseudocode segment below, which of the choices shown has a false value?
int list [] ← {5, 4, 3, 2, 1}
list[4]*2 ≠ list[2]
len(list) ≥ list[0]
list[0] > list[3]
list[3] ≤ list[2] - list[4]
list.length == list[1]
Which loop shown below will correctly traverse the given array, outputting the values in order from front to back?
int list [] ← {5, 4, 3, 2, 1}
for(int x ← len(list)-1; x ≥ 0; x ← x + 1)
print list[x]
for(int x ← len(list)-1; x ≥ 0; x ← x + 1)
print list[x]
for(int x ← len(list)-1; x ≥ 0; x ← x - 1)
print list[x]
for(int x ← len(list); x > 0; x ← x - 1)
print list[x]
for(int x ← 0; x < list.length; x ← x + 1)
print list[x]
Which loop shown below will correctly traverse the given array, outputting the values in order from the back of the array to the front?
int list [] ← {5, 4, 3, 2, 1}
for(int x ← 0; x ≤ list.length; x ← x + 1)
print list[x]
for(int x ← len(list); x > 0; x ← x - 1)
print list[x]
for(int x ← len(list)-1; x ≥ 0; x ← x + 1)
print list[x]
for(int x ← 0; x < list.length; x ← x + 1)
print list[x]
for(int x ← len(list)-1; x ≥ 0; x ← x - 1)
print list[x]
Assume there is a function swap which, as a post-condition of execution, swaps the values of two indexed positions in an array parameter named list. Which of the following is the correct function declaration for this function?
swap (pass-by-value int [] list, pass-by-reference int index1, pass-by-reference int index2)
swap (pass-by-reference int [] list, pass-by-reference int index1, pass-by-reference int index2)
swap (pass-by-value int [] list, pass-by-value int index1, pass-by-value int index2)
swap (pass-by-value int [] list, pass-by-reference int index1, pass-by-value int index2)
How many integers can be stored in a 2D array with the definition:
int [][] grid ← new int[ 5 ][ 10 ]
5
50
10
36
Consider the following block of code, which declares a 2D array named grid with sub-arrays of unspecified length:
How many integers can grid contain after this code is executed?
15
36
12
9
Assume a function len has been defined that returns the number of elements in an array. A programmer is trying to implement matrix multiplication, where two non-empty row-major matrices A and B of at least 1x1 size are multiplied to create a new matrix. The number of columns of A is equivalent to the number of rows of B. If A is n x m elements and B is m x p elements, the result R will be n x p elements. If A and B are 2D arrays, which of the following correctly declares R?
int [][] R ← new int [ len( A ) ][ len( B ) ]
int [][] R ← new int [ len( A[0] ) ][ len( B ) ]
int [][] R ← new int [ len( A[0] ) ][ len( B[0] ) ]
int [][] R ← new int [ len( A ) ][ len( B[0] ) ]
Assume there is a function len which returns the number of elements in an array. Consider the function int greatest(pass-by-reference int [][] grid ), which accepts parameter grid as a 2D array with at least one row and one column. Its intended post-condition is that it will return the greatest value in the array.
The inner loop of the function has been written incorrectly and does not always successfully complete its post-condition. Choose a value for grid which will cause highest to return an incorrect value.
{ { 6, 5, 4 }, { 3, 2, 1 } }
{ { 1, 2, 3 }, { 4, 5, 6 } }
{ { 1, 2 }, { 3, 4 } }
{ { 4, 3 }, { 2, 1 } }
Assume a function len has been defined which returns the number of elements in an array. Now consider a function flatten (pass-by-reference int [] square, pass-by-reference int [] flat). The post-condition of flatten is that flat should have the contents of square, copied row by row. For example, if square contains:
{ { A, B, C }, { D, E, F } } then after execution flat should contain
{ A, B, C, D, E, F }. Which function body for flatten will achieve the specified post-condition?
for (int i ← 0; i < len( square ); i ← i + 1)
for (int j ← 0; j < len( square[0] ); j ← j + 1)
flat[ i * len ( square ) + j ] ← square[ i ][ j ] end for end for
for (int i ← 0; i < len( square ); i ← i + 1)
for (int j ← 0; j < len( square[0] ); j ← j + 1)
flat[ i * len ( square[ 0 ] ) + j ] ← square[ i ][ j ] end for end for
for (int i ← 0; i < len( square ); i ← i + 1)
for (int j ← 0; j < len( square[0] ); j ← j + 1)
flat[ i + j * len ( square ) ] ← square[ i ][ j ] end for end for
for (int i ← 0; i < len( square ); i ← i + 1)
for (int j ← 0; j < len( square[0] ); j ← j + 1)
flat[ i + j * len ( square [ 0 ]) ] ← square[ i ][ j ] end for end for
Which of the following situations would be best suited for storage in a 2D array?
A number sequence of unknown length
A decision tree
A student record with fields of differing data types
An image made of rows and columns of pixels
Which of the following describes a characteristic of stacks?
Ordered by value
First in, first out
Last in, first out
Last in, last out
Which of the following does not describe a behavior of stacks?
peek returns and removes the top element of the stack
pop returns and removes the last element pushed
peek returns the last element pushed
push adds an element to the stack
A stack object has had 8 calls to push, 5 calls to pop and 3 calls to peek. How many elements does it currently contain?
5
8
0
3
Assume there is a function len which returns the number of elements in an array. Now consider the function function reverse( pass-by-reference int [] list ), with the post-condition that elements of list are left in reverse order:
All elements of list are pushed in order to the stack.
list is then
filled in the reverse order in which all elements were pushed.
All elements of list are pushed in order to the stack.
list is then filled in the order in which all elements were pushed.
All elements of list are pushed in reverse order to the stack.
list is
then filled in the reverse order in which all elements were pushed
All elements of list are pushed in reverse order to the stack.
list is
then filled in the order in which all elements were pushed.
What is returned by a subsequent call to s.peek( )?
8
6
9
3
Consider the following implementation of a Stack class, where the class variables contents and highest are accessible for reading and writing by all methods in the class:
Which of the following is a valid implementation of peek, assuming a pre-condition that the stack is not empty?
int peek( ) highest ← highest - 1
end peek
int peek( ) return contents[ highest ]
end peek
int peek( ) highest ← highest - 1
return contents[ highest + 1 ]end peek
int peek( ) highest ← highest - 1
return contents[ highest ]end peek
Which of the following is a true statement about a queue?
The "pop" operation will remove and return the tail element of a tail.
The "pop" operation will return the tail element of a queue.
The "pop" operation will remove and return the head element of a queue.
Popping from a queue functions in the same way as popping from a stack.
Which of the following is a characteristic of queues?
Peeking will remove and return the value at the front of the queue
Peeking will return the value that has been the queue longest
Peeking will return the value at the front of the queue
Peeking will remove and return the value that has been in the queue least
Which of the following is an appropriate use of queues?
A place for storing received messages, to be handled in order of receipt
A list of visited destinations that can be used for backtracking
A searchable list of values
Maintaining an ascending list of items ordered by values
What is returned by a subsequent call to q.peek( )?
3
9
8
6
Consider the following implementation of a Queue class, where contents, front and rear are accessible for reading and writing by all members of the class:
If front represents the index of the array with the item at the front of the queue and rear represents the index of the array with the item at the end of the queue, what is a description of an implementation of pop that would work with this Queue class?
Retrieve the element at contents[ rear ], update the value of rear to represent the new rear of the list.
Retrieve the element at contents[ rear ], update the value of front to represent the new front of the list.
Retrieve the element at contents[ front ], update the value of rear to represent the new rear of the list.
Retrieve the element at contents[ front ], update the value of front to represent the new front of the list.
Assume there is a function now which returns the current time as an integer. Now consider the following two classes, where timestamp and text are readable and writeable by Receiver:
If each subsequent call to nextMessage() should print the timestamp and text of the oldest message received and remove it, which is a valid implementation of nextMessage()?
print q.peek().timestamp
print q.peek().text
print q.pop().timestamp
print q.pop().text
print q.pop().timestamp
print q.peek().text
print q.peek().timestamp
print q.pop().text
Which of the following does not describe a feature of linked lists?
Abstract data type
O(N) complexity to access any node in the list
Fixed length
Dynamically allocated in memory
Which of the following is not a true statement about this linked list?
There are three nodes in this list
null represents a node that exists but does not contain a value
The head node contains the value 5
head.next.next.item is equal to 6
Assume there is a function tail which returns a reference to the last Node of a linked list, given the head Node. For this problem, also assume there is a non-empty linked list reference declared as list.
Now consider the following line of code:
Node temp ← tail ( list )
Immediately after this line of code is executed, which of the following conditions will be true, according to the post-condition of tail
temp.next.item is equal to null
temp.item is equal to 0
temp is equal to null
temp.next is equal to null
Assume there is a function tail which returns a reference to the last Node of a list. Assuming that there is a reference head which points to the head Node of a linked list, which of the following pseudo-code descriptions would append a Node with the value newItem to the end of the list?
Create a new Node with the value newItem; set the tail Node's item value to the new Node
Set the tail Node's item value to the newItem
Create a new Node with the value newItem; set the tail Node's next link to the new Node
Set the tail Node's next link to the newItem
Assuming that a Node reference head is null, which of the following code blocks will NOT result in the Linked List pictured above?
head ← new Node( )
head.item ← 5
head.next ← new Node ( )
head.next.item ← 3
head.next.next ← new Node ( )
head.next.next.item ← 6
head ← new Node( )
head.next ← new Node ( )
head.next.next ← new Node ( )
head.item ← 5
head.next.item ← 3
head.next.next.item ← 6
head ← new Node( )
head.item ← 5
head.next ← new Node ( )
head.item ← 3
head.next ← new Node ( )
head.item ← 6
head ← new Node( )
head.item ← 5
temp ← new Node()
temp.item ← 3
head.next ← temp
temp ← new Node()
temp.item ← 6
head.next.next ← temp
What will be printed by the above block of code?
int num ← 0
Node temp ← head
while ( temp ≠ null )
if ( temp.item == 3 )
print num
end if
num ← num + 1
temp ← temp.next
end while
0
3
2
1
If this is a general tree, as described by this curriculum, from which array was this tree built?
{ 6, 5, 3, 7, 2 }
{ 7, 5, 2, 6, 3 }
{ 7, 2, 5, 3, 6 }
{ 6, 5, 7, 2, 3 }
Which nodes are considered leaf nodes?
7, 2
3, 7, 2
5, 3, 7, 2
6, 5
Which nodes are considered parent nodes?
3, 7, 2
6, 5
7, 2
6, 5, 3
If a new node was to be inserted with the maintaining this tree's completeness, where would it be inserted?
The right child of 7
The left child of 7
The right child of 3
The left child of 3
Which statement is false?
The root is 6
The tree is complete
The tree is full
The tree has three leaves
The tree is perfect
Which statement is true?
All nodes except for 6 are child nodes
6, 5 and 3 are parent nodes
Only 6 and 5 are root nodes
Only 7, 2 and 3 are child nodes
Which of the following statements about Tree Traversals are true?
Traversals delete all nodes of a tree
Traversals access all nodes
Traversals print all nodes of a tree
Traversals add all cells of an array to a tree
Which of the following is not a type of traversal of a tree?
Sorted-order
Post-order
In-order
Pre-order
Which of the following is a pre-order traversal of this tree?
7, 5, 2, 6, 3
6, 5, 7, 2, 3
7, 2, 5, 3, 6
2, 3, 5, 6, 7
Which of the following is a in-order traversal of this tree?
7, 5, 2, 6, 3
7, 2, 5, 3, 6
6, 5, 7, 2, 3
2, 3, 5, 6, 7
Which of the following is a post-order traversal of this tree?
7, 5, 2, 6, 3
7, 2, 5, 3, 6
2, 3, 5, 6, 7
6, 5, 7, 2, 3
If a new node with the value 8 was to be inserted while preserving the properties of the binary search tree, where would it be inserted?
The left child of 5
The left child of 7
The right child of 7
The right child of 5
Which of the following arrays does not represent a possible order in which values were inserted?
{ 6, 2, 5, 3, 7 }
{ 6, 7, 3, 5, 2 }
{ 6, 3, 7, 2, 5 }
{ 6, 3, 7, 5, 2 }
Which of the following represents an in-order traversal of the tree?
2, 3, 5, 6, 7
6, 3, 7, 2, 5
6, 3, 2, 5, 7
7, 6, 5, 3, 2
Which of the following statements is not true for binary search trees, as described in this curriculum?
Every child node to the right of a node is greater than or equal to the parent node
An in-order traversal of a binary search tree will always traverse elements in order of ascending values
Every child node to the left of a node is less than or equal to the parent node
The root node is the value that was inserted first
Which of the following statements is true for binary search trees, as specified for this curriculum?
A pre-order traversal of a binary search tree will traverse nodes in the order in which they were added to the binary search tree.
The greatest value is the right most node of the last level of every binary search tree
The smallest value is the left most node of the last level of every binary search tree
The root node is the value that was inserted first
A binary search tree is built from an array. Which of the following statements is true?
In-order traversals of this tree will visit nodes in ascending order of value.
Any traversal of this tree will visit nodes in ascending order of value.
Post-order traversals of this tree will visit nodes in descending order of value.
Pre-order traversals of this tree will visit nodes in the order of which they were added to the tree
If the value 4 is inserted, where would its final position be after the heap state was maintained?
The left child of 3
The root of the heap
The left child of 7
The right child of 3
If the value 1 is inserted, where would its final position be after the heap state was maintained?
The right child of 4
The left child of 3
The left child of 7
The root of the heap
If the value 2 was removed during a heap traversal, what value would become the new root after the heap state was maintained?
7
6
5
3
If the value 2 was added to the heap and minimum heap state was maintained, where would be the final position of the new node containing 2?
The right child of the root
The left child of the root
The left child of 3
The root of the tree
Which of the following statements is true for all minimum heap trees?
The root is always the median value
The tree is always full
The tree is always complete
Left child nodes are always less than their parent nodes
Which of the following statements is false for minimum heap trees?
New nodes always become the new root.
The root will always be the smallest value in a minimum heap tree.
After adding a node, minimum heap state must be maintained.
After removing a node, minimum heap state must be maintained.
The adjacency matrix of a 4-node graph is given below. How many direct connection paths exist in the graph that is represented by this matrix?
10
9
8
7
Which choice below is best described by the following statement?
Linear data structure contained in static, contiguous memory, where all items can be easily assigned and accessed using an indexing process, allowing for quick and easy data management.
Linked List
Array
Graph
Tree
After the integer elements 5, 3, 7, 1, 2, 4 are correctly inserted into a minimum heap tree, with the value 5 as the initial root, which choice below represents the pre-order traversal of the tree?
5 2 3 1 7 4
1 2 3 4 5 7
5 3 2 7 4 1
1 2 5 3 4 7
After the integer elements 5, 3, 7, 1, 2, 4 are correctly inserted into a binary search tree, and the value 6 is then added to the tree, which statement below best describes the resulting position of the node that contains the 6?
Root node
Right child of 4
Left child of 1
Left child of 7
If a linked list contains N elements, and only the head of the list is referenced, which statement below best describes how many steps it will take to insert another element at the back of the list?
N steps
N/2 steps
One step
N*2 steps
What is output by the code shown below, where length represents the number of elements?
char [][] lets ←
{{'H','O','W'},{'N','O','W'},{'B','R','O','W','N'},{'C','O','W'}}
print lets.length * lets[2].length
15
12
20
8
Which choices are true about one dimensional arrays? Check all that apply.
An array can contain elements of different data types at the same time.
Values are stored in contiguous memory.
Once an array has been created, it is static, and cannot grow or shrink in size.
Values are accessed using an indexing process.
After the integer elements 5, 3, 7, 1, 2, 4 are correctly inserted into an ascending order binary search tree, what is the resulting in-order traversal? Fill in the blank with the correct sequence of digits with no spaces between.
(a)
What is output by the following code sequence?
Queue q ← new Queue()
q.push(7)
q.push(3)
q.push(q.peek() * 2)
q.push(q.pop() + q.pop() + q.peek())
print q.peek()
(a)
What is output by the following code sequence?
Stack s ← new Stack()
s.push(7)
s.push(3)
s.push(s.peek() * 2)
s.push(s.pop() + s.pop() + s.peek())
print s.pop()
(a)
Which choice below is best described by the following statement?
Data structure that resembles a waiting line in a cafeteria, where elements join the list at the back, and are accessed or removed from the list at the front.
Queue
Linked List
Stack
Array
Graph
After the integer elements 5, 3, 7, 1, 2, 4 are correctly inserted into a minimum heap tree, with the value 5 as the initial root, and the value 6 added to the heap, which term or terms below best describes the resulting tree? Check all that apply.
Balanced tree
Complete tree
Full tree
Which choice below is best described by the following statement?
Data structure containing several nodes, often called vertices, which are connected to other nodes using edges, which can be directed or undirected.
Queue
Stack
Graph
Linked List
Tree
What is output by the code shown below?
int [][] grid ← new grid[3][4]
for(int r ← 0;r < grid.length;r ← r + 1)
for(int c ← 0;c < grid[r].length;c ← c + 1)
grid[r][c] ← r * c
print grid[2][3]
2
5
12
6
Using the class definition and diagram shown, with the linked list at the top of the diagram referenced by Node p, match the statements provided in the correct sequence to correctly construct and insert the new node into the list, resulting in the list shown in the lower portion of the diagram.
class Node
int data
Node next
end class
//code statements to create list in upper portion of diagram
//containing four nodes with values 6, 2, 5 and 4
//sequence of statements to construct and correctly insert
1 ?
2 ?
3 ?
4 ?
5 ?
Node t = new Node()
t.data = 7
Node temp = p.next.next
p.next.next = t
t.next = temp
Node t = new Node()
t.data = 7
Node temp = p.next.next.next
p.next.next.next = t
t.next = temp
Which choice is NOT true about two dimensional arrays?
Values are stored in contiguous memory.
All elements contained in the array must be of the same data type.
The number of columns in each row can be different.
Values are accessed using an indexing process, where the first index represents the column, and the second represents the row.
A special kind of queue is required where elements are inserted in natural ascending order, often called a priority queue. The element popped from the front of this queue is always the smallest item in the list. Which of the following data structures will best implement this requirement?
Minimum heap
Array
Binary Search Tree
Linked List
What is output by the code shown below?
int [] list ← {7,2,3,8,1,3}
print list[2] + list[ list[2] ]
(a)
Which choice below is best described by the following statement?
Data structure containing several nodes, each of which can point to two other nodes, often referred to as children.
Tree
Linked List
Queue
Graph
Stack
Which choice below is best described by the following statement?
Data structure where insertion or deletion of elements is
restricted to only one end of the list.
Array
Stack
Graph
Queue
Tree
A linear data structure required is to be flexible in size, where elements can be added and accessed anywhere in the list. Which of the following data structures meets these requirements?
Stack
Tree
Array
Graph
Linked List
Referring to graph illustration, which choices represent possible paths within the graph? Check all valid paths.
BEABDC
ABEDBA
EADCBD
DABEDC
Using the class definition, diagram and partial code shown, which code segment will correctly replace <code> resulting in temp referencing the final node of the list? Check all that apply.
class Node
int data
Node next
end class
//client code
//code to create list shown
//code to reference the final node in the list using temp
Node temp = p
while(<code>)
temp = temp.next
temp.next != null
temp != 5
temp != null
temp.next == null
temp.data != 4
What is the resulting array after the code segment shown below is executed? Write the answer in the blank in the exact format as shown in the bolded portion below, beginning with an open brace, listing elements separated by commas, no spaces between, ending with a closing brace.
int [] list ← {7,2,3,8,1,3}
for(int x ← 1; x < list.length; x++)
list[x] += list[x-1]
//Required answer format
n0,n1,n2,n3,n4,n5
(a)
Using the tree node class definition below, partial client code is shown for a inserting characters of the string "PETUNIA" into a binary search tree, resulting in the tree displayed. Which choice best replaces <code> to correctly insert the next node into the tree?
class TreeNode
char data
Node left
Node right
end class
//client code
TreeNode root = new TreeNode()
root.data = 'P'
TreeNode temp = new Node()
temp.data = 'E'
root.left = temp
temp = new Node()
temp.data = 'T'
root.right = temp
temp = new Node()
temp.data = 'U'
root.right.right = temp
temp = new Node()
temp.data = 'N'
<code>
root.left.left = temp
root.right.left = temp
root.right.right = temp
root.left.right = temp
