- Description
DAT 305 Wk 5 – Apply – Cumulative Exam
Question 1
A linked list stores items in an unspecified order.
Question 2
A node in binary tree can have zero, one, or two children.
Question 3
A list node’s data can store a record with multiple subitems.
- Question 4
Items stored in an array can be accessed using a positional index.
- Question 5
The statement below that assigns x with y is a constant time operation.
y = 10
x = y
- Question 6
A loop is never a constant time operation.
- Question 7
Integers will be placed into buckets based on the 1’s digit. More buckets are needed for an array with one thousand integers than for an array with one hundred integers.
- Question 8
Consider integers X and Y, such that X < Y. X will always be in a lower bucket than Y.
- Question 9
All integers from an array could be placed into the same bucket, even if the array has no duplicates.
- Question 10
When sorting an array of n 3-digit integers, RadixSort’s worst-case time complexity is O(n).
- Question 11
When sorting an array with n elements, the maximum number of elements that RadixSort may put in a bucket is n.
In
- Question 12
RadixSort has a space complexity of O(1).
- Question 13
Given a list with items 40, 888, -3, 2, what does GetLength(list) return?
Hide other options
4
Fails
- Question 14
Given a list with items ‘Z’, ‘A’, ‘B’, Sort(list) yields ‘A’, ‘B’, ‘Z’.
- Question 15
If a list ADT has operations like Sort or PrintReverse, the list is clearly implemented using an array.
- Question 16
Each node in a doubly-linked list contains data and _____ pointer(s).
Hide other options
two
one
- Question 17
Given a doubly-linked list with nodes 20, 67, 11, node 20 is the _____.
Hide other options
head
tail
- Question 18
Given a doubly-linked list with nodes 4, 7, 5, 1, node 7’s previous pointer points to node _____.
Hide other options
4
5
- Question 19
Given a doubly-linked list with nodes 8, 12, 7, 3, node 7’s next pointer points to node _____.
Hide other options
12
3
- Question 20
ListTraverse begins with _____.
Hide other options
a specified list node
the list’s head node
the list’s tail node
- Question 21
Given numList is: 5, 8, 2, 1.
ListTraverse(numsList) visits _____ node(s).
Hide other options
one
two
four
- Question 22
ListTraverse can be used to traverse a doubly-linked list.
- Question 23
The length of an array-based list equals the list’s array allocation size.
- Question 24
An item can be appended to an array-based list, provided the length is less than the array’s allocated size.
- Question 25
Given rosterQueue: 400, 313, 270, 514, 119, what does GetLength(rosterQueue) return?
Hide other options
400
5
- Question 26
Which operation determines if the queue contains no items?
Hide other options
IsEmpty
Peek
- Question 27
Given parkingQueue: 1, 8, 3, what are the queue contents after Peek(parkingQueue)?
Hide other options
1, 8, 3
8, 3
- Question 28
Given parkingQueue: 2, 9, 4, what are the contents of the queue after Pop(parkingQueue)?
Hide other options
9, 4
2, 9, 4
- Question 29
Given that parkingQueue has no items (i.e., is empty), what does GetLength(parkingQueue) return?
Hide other options
-1
0
Undefined
- Question 30
A 100 element hash table has 100 _____.
Hide other options
items
buckets
- Question 31
A hash function computes a bucket index from an item’s _____.
Hide other options
integer value
key
- Question 32
For a well-designed hash table, searching requires _____ on average.
Hide other options
O(1)
O(N)
O(log N)
- Question 33
A company will store all employees in a hash table. Each employee item consists of a name, department, and employee ID number. Which is the most appropriate key?
Hide other options
Name
Department
Employee ID number
- Question 34
Encryption and decryption are synonymous.
- Question 35
Cryptography is used heavily in internet communications.
- Question 36
The Caeser cipher is an encryption algorithm that works well to secure data for modern digital communications.
In
- Question 37
A file in a file system tree is always a leaf node.
- Question 38
A directory in a file system tree is always an internal node.
In
- Question 39
Using a tree data structure to implement a file system requires that each directory node support a variable number of children.
- Question 40
BSTInsert will not work if the tree’s root is null.
- Question 41
BSTReplaceChild will not work if the parent pointer is null.
- Question 42
BSTRemoveKey will not work if the key is not in the tree.
- Question 43
BSTRemoveNode will not work to remove the last node in a tree.
- Question 44
BSTRemoveKey uses BSTRemoveNode.
- Question 45
BSTRemoveNode uses BSTRemoveKey.
- Question 46
BSTRemoveNode may use recursion.
- Question 47
BSTRemoveKey will not properly update parent pointers when a non-root node is being removed.
- Question 48
All calls to BSTRemoveNode to remove a non-root node will result in a call to BSTReplaceChild.
- Question 49
The longer a street is, the more vertices will be needed to represent that street.
- Question 50
Using the physical distance between vertices as edge weights will often suffice in contexts where the fastest route needs to be found.
- Question 51
Navigation software would have no need to place a vertex on a road in a location where the road does not intersect any other roads.
- Question 52
If navigation software uses GPS to automatically determine the start location for a route, the vertex closest to the GPS coordinates can be used as the starting vertex.
- Question 53
Suppose a graph is used to represent airline flights. Vertices represent airports and edge weights represent flight durations. The weight of an edge connecting two airport vertices may change based on _____.
Hide other options
flight delays
weather conditions
flight cost
- Question 54
Suppose a graph is used to represent airline flights. Vertices represent airports and edge weights represent flight durations. Edges in the graph could potentially be added or removed during a single day’s worth of flights.
- Question 55
If the MakeChange function were to make change for 101, what would be the result?
Hide other options
101 pennies
4 quarters and 1 penny
3 quarters, 2 dimes, 1 nickel, and 1 penny
- Question 56
A greedy algorithm is attempting to minimize costs and has a choice between two items with equivalent functionality: the first costing $5 and the second costing $7. Which will be chosen?
Hide other options
The $5 item
The $7 item
The algorithm needs more information to choose
- Question 57
A greedy algorithm always finds an optimal solution.