Chapter 17

[Skip Breadcrumb Navigation]

Home

Student Resources

Quizzes

Chapter 17

Linked Data Structures

This activity contains 10 questions.

What will the following program output?


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}


// Main class
int main()
{	
	IntNode *head = NULL, *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);
		if (head==NULL) {
			head = temp;
		}
		else {
			temp->next = head;;
			head = temp;
		}
	}
	// Output list
	temp = head;
	while (temp->next != NULL) {
		cout << temp->num << " ";
		temp = temp->next;
	}
	cout << endl;
	return 0;
}

1 2 3 44 3 2 14 3 2 1 00 1 2 3 4

Which of the following routines will correctly delete the linked list that is created?


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);
		if (head==NULL) {
			head = temp;
		}
		else {
			temp->next = head;;
			head = temp;
		}
	}
	// Output list
	temp = head;
	while (temp != NULL) {
		cout << temp->num << " ";
		temp = temp->next;
	}
	cout << endl;

	// CODE TO DELETE LIST GOES HERE

	return 0;
}

temp = head;
while (temp != NULL) {
	temp = temp->next;	
	delete temp;
}

temp = head;
while (temp != NULL) {
	delete temp;
	temp = temp->next;	
}

while (head != NULL) {
	temp = head;
	head = head->next;
	delete temp;
}

while (head->next != NULL) {
	temp = head;
	head = head->next;
	delete temp;
}

The following program constructs a list of numbers as follows:

0 => 1 => 2 => 3 => 4 => NULL

Which of the following code snippets inserts a node with the number 101 between the node with 2 and the node with 3? i.e. the list should look like:

0 => 1 => 2 => 101 => 3 => 4 => NULL


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);
		if (head==NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = temp;
		}
	}

	// CODE TO INSERT GOES HERE
	
	return 0;
}

temp = new IntNode(101);
head->next->next = temp;
temp->next = head->next->next;

temp = new IntNode(101);
temp->next = head->next->next->next;
head->next->next->next = temp;

temp = new IntNode(101);
temp->next = head->next->next;
head->next->next = temp;

temp = new IntNode(101);
head->next->next->next = temp;
temp->next = head->next->next->next;

The following program constructs a list of numbers as follows:

0 => 1 => 2 => 3 => 4 => NULL

Which of the following code snippets deletes the node with the number 3 from the list? i.e. the list should look like:

0 => 1 => 2 => 4 => NULL


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);
		if (head==NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = temp;
		}
	}

	// CODE TO DELETE GOES HERE
	
	return 0;
}

temp = head->next->next->next;
head->next->next = temp->next;
delete temp;

temp = head->next->next->next;
delete temp;
head->next->next->next = temp->next;

head->next->next->next = head->next->next->next;
temp = head->next->next->next;
delete temp;

temp = head->next->next->next;
head->next->next->next = temp->next;
delete temp;

What is the output of the following program?


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}


bool DeleteNode(IntNode *head, int target)
{
	IntNode *temp = head, *previous = NULL;

	while (temp!=NULL) {
		if (temp->num == target) {
			if (previous == NULL) {
			  head = head->next;
			  delete temp;
			  return true;
			}
			else {
			  previous->next = temp->next;
			  delete temp;
			  return true;
			}
		}
		else {
			previous = temp;
			temp = temp->next;
		}
	}
	return false;
}

void OutputList(IntNode *temp)
{
	while (temp != NULL) {
		cout << temp->num << " ";
		temp = temp->next;
	}
	cout << endl;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);
		if (head==NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = temp;
		}
	}

	DeleteNode(head, 3);
	OutputList(head);
	DeleteNode(head, 0);
	OutputList(head);

	// Destroy list
	while (head != NULL) {
		temp = head;
		head = head->next;
		delete temp;
	}
	
	return 0;
}

0 1 2 3 4
0 1 2 3 40 1 2 4
1 2 3 40 1 2 4
(unknown number) and likely a crash0 1 2 4
1 2 4

The following program constructs a circular linked list. That is, the next pointer at the tail of the list refers back to the head of the list. Which of the following code snippets correctly outputs the contents of the circular linked list once?


class IntNode
{
public:
 int num;
 IntNode *next;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);		
		if (head==NULL) {
			head = temp;
			tail = temp;	
			temp->next = head;
		}
		else {
			tail->next = temp;
			tail = temp;
			temp->next = head;
		}
	}

	// CODE TO OUTPUT GOES HERE

	return 0;
}

temp = head;
do {
	if (temp!=NULL) {
		cout << temp->num << " ";
		temp=temp->next;
	}
} while (temp!=head);
cout << endl;

temp = head->next;
while (temp != head) {
	cout << temp->num << " ";
	temp=temp->next;
}
cout << endl;

while (temp != NULL) {
	cout << temp->num << " ";
	temp = temp->next;
}
cout << endl;

temp = head;
do {
	if (temp!=NULL) {
		temp=temp->next;
		cout << temp->num << " ";
	}
} while (temp!=head);
cout << endl;

The following code constructs a doubly linked list of integers. The next field points to the next node in the list, while the previous field points to the previous node. This code constructs the list:

NULL <== 0 <==> 1 <==> 2 <==> 3 <==> 4 ==> NULL

Which of the following DeleteNode routines correctly searches for the node containing the target value and deletes it from the list?


class IntNode
{
public:
 int num;
 IntNode *next, *previous;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	previous = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	previous = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);		
		if (head==NULL) {
			head = temp;
			temp->previous = tail;
			tail = temp;
		}
		else {
			tail->next = temp;
			temp->previous = tail;
			tail = temp;
		}
	}

	// Sample DeleteNode calls
	DeleteNode(head, 3);
	DeleteNode(head, 0);

	// Destroy list
	while (head != NULL) {
		temp = head;
		head = head->next;
		delete temp;
	}
	return 0;
}

void DeleteNode(IntNode *head, int target)
{
  IntNode *temp = head;

  while (temp!=NULL) {
 	if (temp->num == target) {
		if (temp->previous != NULL) {
		  temp->previous->next = temp->next;
		}
		if (temp->next != NULL) {
		  temp->next->previous = 
		    		  temp->previous;
		}
		if (temp==head) {
			head=head->next;
		}			
		delete temp;
		return;
	}
	temp=temp->next;
  }
}

void DeleteNode(IntNode *&head, int target)
{
  IntNode *temp = head;

  while (temp!=NULL) {
 	if (temp->num == target) {
	  temp->previous->next = temp->next;	
	  temp->next->previous = 
	    		  temp->previous;
	  if (temp==head) {
		head=head->next;
	  }			
	  delete temp;
 	  return;
	}
	temp=temp->next;
  }
}

void DeleteNode(IntNode *head, int target)
{
  IntNode *temp = head;

  while (temp!=NULL) {
 	if (temp->num == target) {
		if (temp->previous != NULL) {
		  temp->previous->next = temp->next;
		}
		if (temp->next != NULL) {
		  temp->next->previous = 
		    		  temp->previous;
		}			
		delete temp;
		return;
	}
	temp=temp->next;
  }
}

void DeleteNode(IntNode *&head, int target)
{
  IntNode *temp = head;

  while (temp!=NULL) {
 	if (temp->num == target) {
		if (temp->previous != NULL) {
		  temp->previous->next = temp->next;
		}
		if (temp->next != NULL) {
		  temp->next->previous = 
		    		  temp->previous;
		}
		if (temp==head) {
			head=head->next;
		}			
		delete temp;
		return;
	}
	temp=temp->next;
  }
}

NULL <== 0 <==> 1 <==> 2 <==> 3 <==> 4 ==> NULL

Which of the following code snippets will insert the value 101 into the list between the nodes with 2 and 3? e.g. the list should contain:

NULL <== 0 <==> 1 <==> 2 <==> 101 <==> 3 <==> 4 ==> NULL


class IntNode
{
public:
 int num;
 IntNode *next, *previous;
 IntNode();
 IntNode(int n);
};

IntNode::IntNode()
{
	next = NULL;
	previous = NULL;
	num = -1;
}

IntNode::IntNode(int n)
{
	next = NULL;
	previous = NULL;
	num = n;
}

// Main class
int main()
{	
	IntNode *head = NULL, *tail = NULL;
	IntNode *temp = NULL;

	// Construct linked list
	for (int i=0; i<5; i++) {
		temp = new IntNode(i);		
		if (head==NULL) {
			head = temp;
			temp->previous = tail;
			tail = temp;
		}
		else {
			tail->next = temp;
			temp->previous = tail;
			tail = temp;
		}
	}

	// CODE TO INSERT WOULD GO HERE

	// Destroy list
	while (head != NULL) {
		temp = head;
		head = head->next;
		delete temp;
	}
	return 0;
}

temp = new IntNode(101);
temp->previous = head->next->next;
temp->next = head->next->next->next;
head->next->next->next = temp;

temp = new IntNode(101);
temp->previous = head->next->next;
temp->next = head->next->next->next;
head->next->next->next = temp;
head->next->next->next->previous = temp;

temp = new IntNode(101);
temp->previous = head->next->next;
temp->next = head->next->next->next;
head->next->next->next = temp;
temp->next->previous = temp;

temp = new IntNode(101);
temp->previous = head->next->next;
temp->next = head->next->next->next;

What is a common purpose of an iterator?

An iterator is another term for a pointer.An iterator is used to cycle through a data structure and typically includes overloaded operators such as ++ and -- for easy access.An iterator refers to the template that is used to cycle through elements of a linked list.An iterator is used to access the contents of a pointer to a structure or class.

What is the output of the following code? It constructs a binary tree of numbers.


class Node
{
 public:
   int num;
   Node *left, *right;
   Node();
   Node(int n);
};

Node::Node()
{
  left=NULL;
  right=NULL;
  num=0;
}

Node::Node(int n)
{
  left=NULL;
  right=NULL;
  num=n;
}

void AddToTree(Node *root, Node *newNode)
{
  if (root->num > newNode->num) {
          if (root->left != NULL) AddToTree(root->left, newNode);
          else root->left = newNode;
  }
  else {
          if (root->right != NULL) AddToTree(root->right, newNode);
          else root->right= newNode;
  }
}


void PrintTree(Node *root)
{
	if (root!=NULL) {
		cout << root->num << " ";
		PrintTree(root->left);
		PrintTree(root->right);
	}
}

void DeleteTree(Node *root)
{
	if (root != NULL) {
		DeleteTree(root->left);
		DeleteTree(root->right);
		delete root;
	}
}

void main()
{
  Node *root = new Node(10);  
  AddToTree(root, new Node(5));
  AddToTree(root, new Node(15));  
  AddToTree(root, new Node(20));
  AddToTree(root, new Node(7));
  AddToTree(root, new Node(1));
  PrintTree(root);
  DeleteTree(root);
}

1 5 7 10 15 201 7 5 20 15 1020 15 10 7 5 110 5 1 7 15 20

The Submit Answers for Grading feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Submit Answers for Grading button below will not work.

The following Submit Answers for Grading button is provided in its place and will clear your answers:
The Clear Answers and Start Over feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Clear Answers and Start Over button below will not work.

The following Clear Answers button is provided in its place and will clear your answers:

Your browser either does not support scripting or you have turned scripting off. Because of this, the answer choices will NOT appear in a different order each time the page is loaded, though that is mentioned below. Note that you do not need this feature to use this site.

Answer choices in this exercise appear in a different order each time the page is loaded.