CPSC 260 - Final Exam - 2006 T2 - Questi...
CPSC_260_-_Final_Exam_-_2006_T2_-_Questions.pdf-MARKING KEY The University of British
Showing 9-10 out of 20
CPSC 260 - Final Exam - 2006 T2 - Questions.pdf-MA...
CPSC_260_-_Final_Exam_-_2006_T2_-_Questions.pdf-MARKING KEY The University of British
CPSC 260 - Final Exam - 2006 T2 - Q...
CPSC_260_-_Final_Exam_-_2006_T2_-_Questions.pdf-MARKING KEY The University of British
Page 9
Name:
MARKING KEY
Student No:
MARKING KEY
CPSC 260 Final Examination
Monday, April 23, 2007
Page 9 of
20
The linked list implementation for
Set
that we will use maintains a singly-linked
list of nodes that are
in sorted order
, smallest first. The member variable
list
will be
NULL
if there are no elements in a
Set
, otherwise it points to the
Node
that contains the smallest element. There are no dummy nodes
used in this implementation. This is very similar to the implementation used in Lab 9, except that the
elements are kept in sorted
order rather than in random order.
The complete definition
for the
insert()
method is provided here. It may be helpful in answering the
questions that follow.
template<typename Item_type>
void Set<Item_type>::insert( Item_type entry )
// Mutator
// PRE:
(none)
// POST: If entry is not already in the Set, the entry is added,
//
otherwise, nothing happens
{
// Find where entry fits into the sorted linked list, and then
// return immediately if the entry is already in the Set
SetNode* ptr;
SetNode* q = NULL;
for( ptr = list;
ptr && ptr->item < entry;
ptr = ptr->next )
q = ptr;
if ( ptr && ptr->item == entry ) return;
// Construct a new node to hold this integer
SetNode* newNode = new SetNode;
newNode->item = entry;
// Insert the new node into our list
if ( q )
{
newNode->next = q->next;
// q points to previous element
q->next = newNode;
}
else
{
newNode->next = list;
// there is no previous element
list = newNode;
}
// Increment the 'count' variable
count++;
}
Continue on to the next page…
You may remove this page from the exam booklet.


Page 10
Name:
MARKING KEY
Student No:
MARKING KEY
CPSC 260 Final Examination
Monday, April 23, 2007
Page 10 of
20
2. Linked list diagrams { 13 marks }
Consider the following function that uses the
Set
template class. Assume that the class is declared as
on the earlier page of this exam, and that the implementation keeps the items in increasing
order in a
sorted linked list
. Use the implementation given earlier for
insert()
as a guide.
int main()
{
Set<double> X;
X.insert( 3.0 );
X.insert( 1.0 );
X.insert( 4.0 );
X.insert( 1.0 );
X.insert( 5.0 );
X.insert( 9.0 );
X.erase( X.get(1) * X.get(0) );
X.insert( X.get(3) - X.get(2) );
}
(a)
{ 4 marks }
Draw a complete
diagram of the
Set X
immediately after the first
invocation of
insert()
has returned. Some of the diagram has been filled in for you. You must complete the
diagram, including all pointers
and all numeric values
for member variables.
(b)
{ 9 marks }
Draw a complete
diagram of the
Set X
immediately after the last
invocation of
insert()
has returned. Some of the diagram has been filled in for you. You must complete the
diagram, including all pointers
and all numeric values
for member variables.
count
list
1
next
item
3.0
next
item
9.0
count
list
4


Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
UBC Vancouver
UBC_Vancouver
School:
Object-Oriented_Programming
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades

Students also viewed documents