Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/27

Click to flip

27 Cards in this Set

  • Front
  • Back
1
1
1. Suppose your program contains the following type definitions:
struct Box
{
string name;
int number;
Box *next;
};
typedef Box* BoxPtr;
What is the output produced by the following code?
BoxPtr head;
head = new Box;
head->name = "Sally";
head->number = 18;
cout << (*head).name << endl;
cout << head->name << endl;
cout << (*head).number << endl;
cout << head->number << endl;
1. Sally
Sally
18
18
Note that (*head).name and head->name mean the same thing. Similarly,
(*head).number and head->number mean the same thing.
2. Suppose that your program contains the type definitions and code given in Self-Test
Exercise 1. That code creates a node that contains the string "Sally" and the number
18. What code would you add to set the value of the member variable next of this
node equal to NULL?
2. The best answer is
head->next = NULL;
However, the following is also correct:
(*head).next = NULL;
3. Given the following structure definition:
struct ListNode
{
string item;
int count;
ListNode *link;
};
ListNode *head = new ListNode;
Give code to assign the string "Wilbur's brother Orville" to the member variable
item of the variable to which head points.
3. head->item = "Wilbur's brother Orville";
4. Write type definitions for the nodes and pointers in a linked list. Call the node type
NodeType and call the pointer type PointerType. The linked lists will be lists of
letters.
4. class NodeType
{
public:
NodeType( ){}
NodeType(char theData, NodeType* theLink)
: data(theData), link(theLink){}
NodeType* getLink( ) const { return link; }
char getData( ) const { return data; }
void setData(char theData) { data = theData; }
void setLink(NodeType* pointer) { link = pointer; }
private:
char data;
NodeType *link;
};
typedef NodeType* PointerType;
5. A linked list is normally referred to via a pointer that points to the first node in the
list, but an empty list has no first node. What pointer value is normally used to represent
an empty list?
5. The value NULL is used to indicate an empty list.
6. Suppose your program contains the following type definitions and pointer variable
declarations:
struct Node
{
double data;
Node *next;
};
typedef Node* Pointer;
Pointer p1, p2;
Suppose p1 points to a node of the above type that is in a linked list. Write code
that will make p1 point to the next node in this linked list. (The pointer p2 is for
the next exercise and has nothing to do with this exercise.)
6. p1 = p1-> next;
7. Suppose your program contains type definitions and pointer variable declarations as
in Self-Test Exercise 6. Suppose further that p2 points to a node of the above type
that is in a linked list and which is not the last node on the list. Write code that will
delete the node after the node pointed to by p2. After this code is executed, the linked
list should be the same, except that there will be one less node in the linked list.
(Hint: You may want to declare another pointer variable to use.)
7. Pointer discard;
discard = p2->next;//discard points to the node to be deleted.
p2->next = discard->next;
This is sufficient to delete the node from the linked list. However, if you are not using
this node for something else, you should destroy the node with a call to delete as
follows:
delete discard;
8. Suppose your program contains the following type definitions and pointer variable
declarations:
class Node
{
public:
Node(double theData, Node* theLink)
: data(theData), next(theLink){}
Node* getLink( ) const { return next; }
double getData( ) const { return data; }
void setData(double theData) { data = theData; }
void setLink(Node* pointer) { next = pointer; }
private:
double data;
Node *next;
};
typedef Node* Pointer;
Pointer p1, p2;
Suppose p1 points to a node of the above type that is in a linked list. Write code
that will make p1 point to the next node in this linked list. (The pointer p2 is for
the next exercise and has nothing to do with this exercise.)
8. p1 = p1->getLink( );
9. Suppose your program contains type definitions and pointer variable declarations as in
Self-Test Exercise 8. Suppose further that p2 points to a node of the above type that is
in a linked list and which is not the last node on the list. Write code that will delete the
node after the node pointed to by p2. After this code is executed, the linked list should
be the same, except that there will be one less node in the linked list. (Hint: You may
want to declare another pointer variable to use.)
9. Pointer discard;
discard = p2->getLink( );//points to node to be deleted.
p2->setLink(discard->getLink( ));
This is sufficient to delete the node from the linked list. However, if you are not using
this node for something else, you should destroy the node with a call to delete as
follows:
delete discard;
10. Choose an ending to the following statement, and explain:
For a large array and a large list holding the same type objects, inserting a new
object at a known location into the middle of a linked list compared to insertion in
an array is
a. more efficient.
b. less efficient.
c. about the same.
10. a. Inserting a new item at a known location into a large linked list is more efficient
than inserting into a large array. If you are inserting into a list, you have about five operations,
most of which are pointer assignments, regardless of the list size. If you insert
into an array, on the average you have to move about half the array entries to insert a
data item.
For small lists, the answer is c, about the same.
11. Give the definition of the member function push of the template class Stack
described in Displays 17.13 and 17.15.
11. Note that this function is essentially the same as
headInsert
in Display 17.11.
template<class T>
void Stack<T>::push(T stackFrame)
{
top = new Node<T>(stackFrame, top);
}
12. Give the definition of the copy constructor for the template class Stack described in
Displays 17.13 and 17.15.
12.
//Uses cstddef:
template<class T>
Stack<T>::Stack(const Stack<T>& aStack)
{
if (aStack.isEmpty( ))
top = NULL;
else
{
Node<T> *temp = aStack.top;//temp moves
//through the nodes from top to bottom of aStack.
Node<T> *end;//Points to end of the new stack.
end = new Node<T>(temp->getData( ), NULL);
top = end;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//move temp to second node
//or NULL if there is no second node.
while (temp != NULL)
{
end->setLink(
new Node<T>(temp->getData( ), NULL));
temp = temp->getLink( );
end = end->getLink( );
}
//end->link == NULL;
}
}
13. Give the definition of the overloaded assignment operator for the template class
Stack described in Displays 17.13 and 17.15.
13. template<class T>
Stack<T>& Stack<T>::operator =(const Stack<T>& rightSide)
{
if (top == rightSide.top) //if two stacks are the same
return *this;
else //send left side back to freestore
{
T next;
while (! isEmpty( ))
next = pop( );//remove calls delete.
}
if (rightSide.isEmpty())
{
top = NULL;
return *this;
}
else
{
Node<T> *temp = rightSide.top;//temp moves through
//the nodes from front top to bottom of rightSide.
Node<T> *end;//Points to end of the left-side stack.
end = new Node<T>(temp->getData( ), NULL);
top = end;;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink();//Move temp to second node
//or set to NULL if there is no second node.
while (temp != NULL)
{
end->setLink(
new Node<T>(temp->getData(), NULL));
temp = temp->getLink();
end = end->getLink();
}
//end->link == NULL;
return *this;
}
}
14. Give the definitions for the default (zero-argument) constructor and the member
functions Queue<T>::isEmpty for the template class Queue (Display 17.16).
14. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>::Queue( ) : front(NULL), back(NULL)
{
//Intentionally empty.
}
//Uses cstddef:
template<class T>
bool Queue<T>::isEmpty( ) const
{
return (back == NULL);//front == NULL would also work
}
15. Give the definitions for the member functions Queue<T>::add and
Queue<T>::remove for the template class Queue (Display 17.16).
15. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
void Queue<T>::add(T item)
{
if (isEmpty( ))
front = back = new Node<T>(item, NULL);//Sets both
//front and back to point to the only node
else
{
back->setLink(new Node<T>(item, NULL));
back = back->getLink( );
}
}
//Uses cstdlib and iostream:
template<class T>
T Queue<T>::remove( )
{
if (isEmpty( ))
{
cout << "Error: Removing an item from an empty queue.\n";
exit(1);
}
T result = front->getData( );
Node<T> *discard;
discard = front;
front = front->getLink( );
if (front == NULL) //if you removed the last node
back = NULL;
delete discard;
return result;
}
16. Give the definition for the destructor for the template class Queue (Display 17.16).
16. The following should be placed in the namespace QueueSavitch:
template<class T>
Queue<T>::~Queue( )
{
T next;
while (! isEmpty( ))
next = remove( );//remove calls delete.
}
17. Give the definition for the copy constructor for the template class Queue (Display
17.16).
17. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>::Queue(const Queue<T>& aQueue)
{
if (aQueue.isEmpty( ))
front = back = NULL;
else
{
Node<T> *temp = aQueue.front;//temp moves
//through the nodes from front to back of aQueue.
back = new Node<T>(temp->getData( ), NULL);
front = back;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//temp now points to second
//node or NULL if there is no second node.
while (temp != NULL)
{
back->setLink(new Node<T>(temp->getData( ), NULL));
back = back->getLink( );
temp = temp->getLink( );
}
//back->link == NULL
}
}
18. Give the definition for the overloaded assignment operator for the template class
Queue (Display 17.16).
18. The following should be placed in the namespace QueueSavitch:
//Uses cstddef:
template<class T>
Queue<T>& Queue<T>::operator =(const Queue<T>& rightSide)
{
if (front == rightSide.front)//if the queues are the same
return *this;
else //send left side back to freestore
{
T next;
while (! isEmpty( ))
next = remove( );//remove calls delete.
}
if (rightSide.isEmpty( ))
{
front = back = NULL;
return *this;
}
else
{
Node<T> *temp = rightSide.front;//temp moves
//through the nodes from front to back of rightSide.
back = new Node<T>(temp->getData( ), NULL);
front = back;
//First node created and filled with data.
//New nodes are now added AFTER this first node.
temp = temp->getLink( );//temp now points to second
//node or NULL if there is no second node.
while (temp != NULL)
{
back->setLink(
new Node<T>(temp->getData( ), NULL));
back = back->getLink( );
temp = temp->getLink( );
}
//back->link == NULL;
return *this;
}
}
19. Write the definition of the template function inQ shown below. Use iterators. Use
the definition of Queue given in Display 17.20.
template<class T>
bool inQ(Queue<T> q, T target);
//Returns true if target is in the queue q;
//otherwise, returns false.
19. using namespace ListNodeSavitch;
using namespace QueueSavitch;
template<class T>
bool inQ(Queue<T> q, T target)
{
Queue<T>::Iterator i;
i = q.begin( );
while ((i != q.end( )) && (*i != target))
i++;
return (i != q.end());
}
Note that the following return statement does not work, since it can cause a
dereferencing of NULL, which is illegal. The error would be a runtime error, not a
compiler error.
return (*i == target);
20. Define the following member functions, which could be added to the class
SearchTree in Display 17.24. These functions display the data encountered in a
preorder and postorder traversal of the tree, respectively. Define a private helping
function for each function, as we did for SearchTree<T>::inorderShow.
void SearchTree<T>::preorderShow( ) const
void SearchTree<T>::postorderShow( ) const
20. The template class SearchTree needs function declarations added. These are just the
definitions.
template<class T> //uses iostream:
void SearchTree<T>::preorderShow( ) const
{
preorderShow(root);
}
template<class T> //uses iostream:
void SearchTree<T>::preorderShow(
TreeNode<T>* subTreeRoot) const
{
if (subTreeRoot != NULL)
{
cout << subTreeRoot->data << " ";
preorderShow(subTreeRoot->leftLink);
preorderShow(subTreeRoot->rightLink);
}
}
template<class T> //uses iostream:
void SearchTree<T>::postorderShow( ) const
{
postorderShow(root);
}
template<class T> //uses iostream:
void SearchTree<T>::postorderShow(
TreeNode<T>* subTreeRoot) const
{
if (subTreeRoot != NULL)
{
postorderShow(subTreeRoot->leftLink);
postorderShow(subTreeRoot->rightLink);
cout << subTreeRoot->data << " ";
}
}
A ___ is a struct or class object that has one or more member variables that are
pointer variables. These nodes can be connected by their member pointer variables
to produce data structures that can grow and shrink in size while your program is
running.
node
A ___ ___ is a list of nodes in which each node contains a pointer to the next
node in the list.
linked list
The end of a linked list (or other linked data structure) is indicated by setting the
pointer member variable equal to ___.
NULL
A ___ is a first-in/last-out data structure. A ___ is a first-in/first-out data structure.
Both can be implemented using a linked list.
stack
queue
An ___ is a construct (typically an object of some iterator class) that allows you
to cycle through data items stored in a data structure.
iterator
A ___ is a data structure whose nodes have two (or more) member variables for
pointers to other nodes. If a tree satisfies the Binary Search Tree Storage Rule, then
a function can be designed to rapidly find data in the tree.
tree