Deck 20: Data Structures

Question 1

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 1

C

Question 2

Which of the following is not a dynamic data structure?

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

Answer 2

C

Question 3

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

Answer 3

D

Question 4

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 5

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 6

Given that the line
Delete newPtr;
Just executed, what can you conclude?

A) The memory referenced by newPtr is released only if it is needed by the system.
B) The pointer newPtr is of type void *.
C) The pointer newPtr only exists if there was an error freeing the memory.
D) The pointer newPtr still exists.

Question 7

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 8

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 9

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

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

Question 11

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

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

Question 12

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 13

The __________ operator takes as an argument the type of object being allocated and returns a __________.

A) new, pointer to an object of that type.
B) delete, reference to an object of that type.
C) delete, copy of the object of that type.
D) sizeof, reference to an object of that type.

Question 14

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 15

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 16

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.

Question 17

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 18

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 19

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