# Data Structures Final Review

81 Questions  Settings  Related Topics
• 1.
Stack is an Abstract Class
• A.

True

• B.

False

• 2.
Stack is an Abstract Data Type
• A.

True

• B.

False

• 3.
Pez Dispenser Anaolgy
• A.

Queue

• B.

Stack

• C.

Array

• 4.
LIFO structire stands for...
• A.

Last In Furthest Out

• B.

Least In First Out

• C.

Last In First Out

• 5.
A queue is and ADT in which elemets are added and removed from one end only; first-in-first-out (FIFO) structure.
• A.

True

• B.

False

• 6.
The running time of RETREIVE call on a linked list is O(1) = constant
• A.

True

• B.

False

• 7.
Insert, Append, Delete, and Next are all valid list operations.
• A.

True

• B.

False

• 8.
An enque is the opposite of a deque
• A.

True

• B.

False

• 9.
A node at level X is also said to be a depth of X
• A.

True

• B.

False

• 10.
Postfix notation may not contain negative numbers
• A.

True

• B.

False

• 11.
An ordered tree in which each vertex has 0, 1, or 2 children
• 12.
The name of the second child of a vertex on a binary tree
• 13.
A node connected via edges to a higher node
• 14.
The unique vertex in a rooted tree
• 15.
A node connected via edges to a lower node
• 16.
If "X" is a descendent of "Y", then "Y" is a __________ of "X".
• 17.
A child (grandchild, great-grand-child, etc...) of a specific vertext.
• 18.
The length of the path from the root to the vertext of interst
• 19.
Any non-leaf vertext
• 20.
All the descendents of a vertex
• 21.
• A.

A

• B.

B

• C.

Neither

• 22.
The length of the longest path from a vertex to a leaf that is a descendent of the vertex
• A.

Height

• B.

Depth

• 23.
All parents have the same depth, but not necessarily the same height
• A.

True - parents

• B.

False - siblings

• 24.
Property of all trees
• A.

#Edges = #Nodes - 1

• B.

#Nodes = #Edges - 1

• 25.
An ordered tree in which each vertex has either no children, one child, or two children
• A.

Sub Tree

• B.

Ordered Tree

• C.

Binary Tree

• 26.
Every vertex has two children or is a leaf
• A.

Perfect Binary Tree

• B.

Full Binary Tree

• 27.
A Full Binary Tree in which all leaves have the same depth
• A.

Perfect Binary Tree

• B.

Full Binary Tree

• 28.
What is the In Order Traversal:
• 29.
Prior to inserting intoa B.S.T., you must sort the tree
• A.

True

• B.

False

• 30.
The "best case" search time for a B.S.T. is O(n). (where n = the number of nodes in the tree)
• A.

True

• B.

False

• 31.
A Red-Black tree is an BST tree
• A.

True

• B.

False

• 32.
A BST tree is always balanced
• A.

True

• B.

False

• 33.
All AVL trees are BST
• A.

True

• B.

False

• 34.
For a normal (double-linked) binary tree, 8 pointers are assigned to each node.
• A.

True

• B.

False

• 35.
Inserting a node in an AVL tree will sometimes change the height of the tree
• A.

True

• B.

False

• 36.
A splay tree is also an AVL
• A.

True

• B.

False

• 37.
A red-black tree is also a B.S.T.
• A.

True

• B.

False

• 38.
Red-Black trees are tree that have been restrctured with a heuristic similar to a self-organizing list
• A.

True

• B.

False

• 39.
A hash table tends to perform better overall (bot time and space) than an array, linked list, or balanced B.S.T.
• A.

True

• B.

False

• 40.
Linear probing is not a good solution for clustering
• A.

True

• B.

False

• 41.
Double hashing requires more "computational overhead" than linear probing.
• A.

True

• B.

False

• 42.
Rehashing guarentees a reduction in clustering
• A.

True

• B.

False

• 43.
Linear probing uses the numer of times the rehash function has been applied as a value in the hash formula
• A.

True

• B.

False

• 44.
What is a disadvantage of using buckets for collision resolution? Choose all that apply
• A.

The search is long

• B.

It takes longer to walk down

• C.

Wasted space

• D.

Not knowing how big the bucket is

• E.

The return time

• 45.
Choose two ways to resolve problems following a deletion in a list using linear probing. Choose all that apply
• A.

Use recursion

• B.

Using chain down the list

• C.

Shift Everything

• D.

Insert null in deleted vairable

• 46.
All ordered trees are binary trees
• A.

True

• B.

False

• 47.
Reading a book (cover to cover) is an example of Pre Order Traversal
• A.

True

• B.

False

• 48.
A post oder traversal may be used to evaluate an arithmetic expression
• A.

True

• B.

False

• 49.
General trees will always have fewer nodes than its binary tree representation
• A.

True

• B.

False

• 50.
Which are Binary Trees?
• A.

A

• B.

B

• C.

C

• D.

D

• E.

E

• 51.
Which are Full Binary Trees?
• A.

A

• B.

B

• C.

C

• D.

D

• E.

E

• 52.
Which are Perfect Binary Trees?
• A.

A

• B.

B

• C.

C

• D.

D

• E.

E

• 53.
Which are Binary Search Trees?
• A.

A

• B.

B

• C.

C

• D.

D

• E.

E

• 54.
Reading a book (cover to cover) is an example of Post Order Traversal
• A.

True

• B.

False

• 55.
A In Order traversal may be used to print an arithmetic expression
• A.

True

• B.

False

• 56.
For a normal (double linked) binary tree, __ pointers are assigned to each node
• 57.
The DIR command in DOS (which returns fil/folder sizes) untilizes a ___ order traversal of the directory tree structure
• 58.
The maximum height of a 14-node B.S.T. is 13
• A.

True

• B.

False

• 59.
The minimum height of a 14-node B.S.T. is 5
• A.

True

• B.

False

• 60.
The process of creating a B.S.T. (requires/does not require) sorting data.
• A.

Requires

• B.

Does Not Require

• 61.
In Stack Methods: ____ removes the top object of the stack and returns it.
• A.

PUSH(X)

• B.

POP()

• C.

SIZE()

• D.

IsStackEmpty()

• E.

TOP()

• 62.
In Stack Methods: ____ Inserts object X onto the stack.
• A.

PUSH(X)

• B.

POP()

• C.

SIZE()

• D.

IsStackEmpty()

• E.

TOP()

• 63.
In Stack Methods: ____ Returns a boolean inidcating if the stack is empty.
• A.

PUSH(X)

• B.

POP()

• C.

SIZE()

• D.

IsStackEmpty()

• E.

TOP()

• 64.
In Stack Methods: ____ rreturns the # of objects in the stack.
• A.

PUSH(X)

• B.

POP()

• C.

SIZE()

• D.

IsStackEmpty()

• E.

TOP()

• 65.
In Stack Methods: ____ returns the top object of the stack without removing it.
• A.

PUSH(X)

• B.

POP()

• C.

SIZE()

• D.

IsStackEmpty()

• E.

TOP()

• 66.
Which are the Stack Methods
• A.

Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()

• B.

POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()

• C.

Size(), Front(), Push(X), Pop()

• 67.
______ is a data structure in which elements are added to the rear and removed from the front. A First-In-First-Out (FIFO) structure
• 68.
To remove an elemnt from the end (queue)
• A.

Enqueue

• B.

Dequeue

• 69.
To insert an element at the rear (queue)
• A.

Enqueue

• B.

Dequeue

• 70.
Which are the Queue Methods
• A.

Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()

• B.

POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()

• C.

Size(), Front(), Push(X), Pop()

• 71.
____ is the technique used for inserting and accessing elements in a list in a relative constant time by manipulating the key to identify its location in the list
• 72.
A _____ function used to manipulate the key of an element in a list to identify its location in the list
• 73.
___ is the condition resulting when two or more keys produce the same hash location
• 74.
_____ is resolving a collison by computing a new hash location from a hash function that manipulates the original location rather than the elements key
• 75.
Resolving a hash collision by sequentially searching a hash table beginning at the location returned by the hash function
• A.

Clustering

• B.

Bucket

• C.

Linear Probing

• D.

Chain

• 76.
The tendency of elements to become unevenly distributed in the hash table
• A.

Clustering

• B.

Bucket

• C.

Linear Probing

• D.

Chain

• 77.
A linked list of elements that share the same hash location
• A.

Clustering

• B.

Bucket

• C.

Linear Probing

• D.

Chain

• 78.
A collection of elements associated with a particular hash location
• A.

Clustering

• B.

Bucket

• C.

Linear Probing

• D.

Chain

• 79.
______ probing is resolving a hash collision by using the rehashing formula
• 80.
_____ probing resolving a hash collision by generating pseudorandom hash values in successive applications of the rehash function
• 81.
______ hashing uses 2 hash funtions to calculate the probe value