Deck 19: Custom Templatized Data Structures

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?

A) 500
B) 20
C) 10
D) 8

Answer 1

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?

A) insertAtBack and removeFromBack.
B) insertAtBack and removeFromFront.
C) removeFromFront and insertAtFront.
D) removeFromFront and insertAtBack.

Answer 2

B

Question 3

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

A) 5
B) 8
C) 10
D) 15

Answer 3

C

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?

A) Circular, singly-linked list.
B) Circular, doubly-linked list.
C) Singly-linked list.
D) Doubly-linked list.

Question 5

Which of the following is a self-referential object?

A) class SelfRefer {
Int* xPtr;
};
B) class selfRefer {
SelfRefer x;
};
C) class SelfRefer {
SelfRefer* xPtr;
};
D) class SelfRefer1 {
SelfRefer2 x;
};
Class SelfRefer2
{
SelfRefer1 x;
};

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?

A) Stack.
B) Queue.
C) Binary tree.
D) Linked list.

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?

A) 3
B) 4
C) 5
D) 6

Question 8

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

A) Link.
B) Connector.
C) Tie.
D) Referrer.

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.

A) lastPtr->nextPtr = newPtr; lastPtr = newPtr
B) lastPtr = newPtr; lastPtr->nextPtr = newPtr
C) newPtr->nextPtr = lastPtr; lastPtr = newPtr
D) lastPtr = newPtr; newPtr->nextPtr = lastPtr

Question 10

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

A) Always have multiple links per node.
B) Can be sorted efficiently.
C) Always have the same shape for a particular set of data.
D) Are nonlinear data structures.

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

A) 5 10 7 5
B) 5 10
C) 7 5
D) 10 5

Question 12

Which of the following is not a dynamic data structure?

A) Linked list.
B) Stack.
C) Array.
D) Binary tree.

Question 13

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

A) Dynamic memory allocation.
B) Efficient insertion and deletion.
C) Direct access to any list element.
D) No need to allocate extra space, "just in case."

Question 14

In general, linked lists allow:

A) Insertions and removals anywhere.
B) Insertions and removals only at one end.
C) Insertions at the back and removals from the front.
D) None of the above.

Question 15

Which of the following statements about stacks is incorrect?

A) Stacks can be implemented using linked lists.
B) Stacks are first-in, first-out (FIFO) data structures.
C) New nodes can only be added to the top of the stack.
D) The last node (at the bottom) of a stack has a null (0) link.

Question 16

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

A) Duplicate elimination.
B) Searching.
C) Sorting.
D) 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?

A) 3 10 16 23 19 17 34 6
B) 3 6 17 16 10 19 23 34
C) 6 3 34 17 16 10 19 23
D) 10 16 23 19 17 34 3 6