Question 1

If you have a 1000-element balanced binary search tree, what is the maximum number of comparisons that may be needed to find an element in the tree?

Accepted Answer

C

Question 2

A linked list has the functions insertAtFront, removeFromFront, insertAtBack and removeFromBack, which perform operations on nodes exactly as their names describe. Which two functions would most naturally model the enqueue and dequeue operations, respectively, of a queue?

Accepted Answer

enqueue operation represents adding an element to the back of the queue, which is equivalent to inserting a node at the end of the linked list using the insertAtBack function. Therefore, insertAtBack would be the most natural function to model the enqueue operation.
dequeue operation represents removing an element from the front of the queue, which is equivalent to removing a node from the beginning of the linked list using the removeFromFront function. Therefore, removeFromFront would be the most natural function to model the dequeue operation. Thus, the correct choice is option B, which models enqueue with insertAtBack and dequeue with removeFromFront.

Question 3

How many pointers are contained as data members in the nodes of a circular, doubly linked list of integers with five nodes?

Accepted Answer

In a circular, doubly linked list, each node contains two pointers: one to the next node and one to the previous node. With five nodes, this results in a total of 5 * 2 = 10 pointers.

Question 4

What kind of linked list begins with a pointer to the first node, and each node contains a pointer to the next node, and the pointer in the last node points back to the first node?

Accepted Answer

A circular singly-linked list fits the description given, as it begins with a pointer to the first node and each node contains a pointer to the next node. Additionally, the pointer in the last node points back to the first node, making it circular. A doubly-linked list has pointers to both the previous and next nodes, and a singly-linked list only has pointers to the next node, so they do not fit the full description.

Question 5

Which of the following is a self-referential object?

Accepted Answer

Class C is self-referential because it contains a pointer to an object of the same class (SelfRefer). This creates a self-referential loop where an instance of the class contains a pointer to another instance of the same class. This allows for recursive functions and data structures. The other choices do not contain this self-referential loop.

Question 6

Which data structure represents a waiting line and limits insertions to be made at the back of the data structure and limits removals to be made from the front?

Accepted Answer

A Queue represents a waiting line and follows the principle of "First In First Out" (FIFO) where the elements added first are the ones removed first. Hence, insertions are made at the back of the queue and removals are made from the front. This makes it a suitable data structure for modeling real-world scenarios, such as waiting lines in a store or a bank.

Question 7

A queue performs the following commands (in pseudo-code): enqueue 4, 6, 8, 3, 1
Dequeue three elements
Enqueue 3, 1, 5, 6
Dequeue two elements
What number is now at the front of the queue?

Accepted Answer

After enqueueing 4, 6, 8, 3, 1 and dequeuing three elements, the queue contains 3 and 1. Then, enqueueing 3, 1, 5, 6, we have the queue 3, 1, 3, 1, 5, 6. When we dequeue two elements, we have the queue 3, 1, 5, 6. Therefore, the number at the front of the queue is 3.

Question 8

The pointer member in a self-referential class is referred to as a:

Accepted Answer

The pointer member in a self-referential class is typically used to link to another instance of the same class, thus it is commonly referred to as a "link".

Question 9

For a non-empty linked list, select the code that should appear in a function that adds a node to the end of the list. newPtr is a pointer to the new node to be added and lastPtr is a pointer to the current last node. Each node contains a pointer nextPtr.

Accepted Answer

Option A correctly adds the new node to the end of the list by setting the next pointer of the current last node to the new node, and then updating the last pointer to point to the new node.

Question 10

Select the incorrect statement. Binary search trees (regardless of the order in which the values are inserted into the tree):

Accepted Answer

Binary search trees do not always have the same shape for a particular set of data; their structure can vary significantly depending on the order in which values are inserted.

Question 11

A stack is initially empty, then the following commands are performed: push 5
Push 7
Pop
Push 10
Push 5
Pop
Which of the following is the correct stack after those commands (assume the top of the stack is on the left)?

Accepted Answer

After performing the operations, the stack will have 10 and 5, with 10 at the top.

Question 12

Which of the following is not a dynamic data structure?

Accepted Answer

Arrays are not dynamically resizable, meaning that once an array is created, its size cannot be changed dynamically during runtime. In contrast, linked lists, stacks, and binary trees are all dynamic data structures that can change in size during the execution of a program.

Question 13

__________ is not an advantage of linked lists when compared to arrays.

Accepted Answer

Arrays allow direct access to any element using the index, whereas linked lists require traversing through the list to reach a specific element. Therefore, direct access to any list element is not an advantage of linked lists over arrays. The other options, such as dynamic memory allocation, efficient insertion and deletion, and not needing to allocate extra space, are advantages of linked lists over arrays.

Question 14

In general, linked lists allow:

Accepted Answer

The answer of In general, linked lists allow:
...

Question 15

Which of the following statements about stacks is incorrect?

Accepted Answer

Stacks are actually last-in, first-out (LIFO) data structures, where the last element added to the stack will be the first one to be removed. Choice A, C, and D are correct statements.

Question 16

Which of the following tasks would a binary search tree not be well suited for?

Accepted Answer

Binary search trees can efficiently perform search, sorting and duplicate elimination operations. However, reversing an unsorted sequence requires traversing the tree in a specific order, which may not be possible for binary search trees as the nodes are arranged according to a specific order, either in ascending or descending order. Therefore, a binary search tree is not well suited for reversing an unsorted sequence.

Question 17

If you add the following nodes to a binary search tree in the order they appear (left-to-right): 6 34 17 19 16 10 23 3
What will be the output of a postorder traversal of the resulting tree?

Accepted Answer

In a postorder traversal, nodes are visited in the order of left child, right child, and then the parent node. After adding the nodes to a binary search tree in the given order, the tree structure will be such that 3, 10, 16, 23, 19, 17, 34, and finally 6 are visited in this sequence during a postorder traversal.

Quiz 19: Custom Templatized Data Structures