CSUN Computer Science Programming Assessment Lab Exam
This is a programming lab exam in which you will read a description of a problem drawn from typical material covered in COMP 110/182/282, and then write, compile, test, and submit a Java program to implement your solution. This exam is given on a regular basis to students who have finished their lower-division CS courses and who are now taking upper division courses such as COMP 380 or COMP 450. The purpose of the exam is to provide data to the CS Department on how well CS students have retained information from earlier courses. Your performance on this exam has no effect on your grade in this course, but the CS Department needs accurate data on student performance, so please take it seriously and do your best.
Instructions
· Read and answer the demographics questions provided below.
· Read the programming assignment, then at the computer, open a text editor, compose and test your solution.
· You may program your solution in either Java or C++. You are requested to limit the amount of time spent on the exam to one hour, and you should not consult any books, notes, or other resources.
· After you finish, compose an email to Professor Wang, and provide the source file to your solution as an attachment. Please remember to include your answers to the demographics questions in your source file. For your email subject header, please use COMP SCI PROGRAMMING ASSESSMENT EXAM.
Assignment: Linked List of Integers
In this problem you will define classes named Node and MyList which create a singly-linked list of nodes where each node holds one integer value. A skeleton version of the code with completed test drivers is already provided. You only need to complete several short methods. For simplicity, the implementation does not use generics. The list that you implement will hold values only of type integer.
Class Node will contain data members/fields to hold the value of the node, and a reference to the next node in the linked list. For this class, you will complete the following functions/methods:
· Default constructor
· Constructor with the integer value for that Node as input
· Get or “accessor” functions/methods for the value and next members/fields.
· Set or “mutator” functions/methods for the value and next members/fields.
Class MyList will contain a data member to hold a reference to the node at the head of the list. For this class, you will complete the following functions/methods:
· Default constructor
· A method/function to insert an integer value at the head of the list.
· A method/function to insert an integer value at the tail of the list.
· A method/function to delete the node at the head of the list and return its integer value.
· A method/function to delete the node at the tail of the list and return its integer value.
· A method to delete or clear all nodes from the list.
A function/method to print out the contents of the list to the display is predefined and provided for you in the skeleton (Java: toString(); C++: operator<<()).
Coding and Testing
You will be provided with a code skeleton as your starting point. The skeleton will include class skeletons, stubbed methods, and test drivers. You only need to complete the stubbed methods, and then execute the predefined drivers. Skeletons are provided in both Java and C++.
Test Drivers
There are 2 test drivers. Each driver tests additional methods arranged in increasing level of difficulty. Implement the methods and execute the test drivers in the following order:
Phase 1
· For class Node, complete all methods.
· For class MyList, complete the constructor, insertAtHead, and insertAtTail methods.
· Uncomment and run test driver 1.
Phase 2
· For class MyList, complete the deleteAtHead and deleteAtTail methods.
· Uncomment and run test driver 2.
Demographic Questions
Before submitting your work, at the top of your source file, please add as comments your responses to the following demographic questions. Your source file may remain anonymous.
1) What is your classification? A) Freshman B) Sophomore C) Junior D) Senior E) Grad
2) What is your Major? A) CS B) EE C) IS D) IS-IT E) Other
3) Where did you take COMP 110 or equivalent? A) CSUN B) Pierce C) Valley D) Canyons E) Other
4) Where did you take COMP 182 or equivalent? A) CSUN B) Pierce C) Valley D) Canyons E) Other
5) Where did you take COMP 282 or equivalent? A) CSUN B) Pierce C) Valley D) Canyons E) Other
6) Approximately how many years ago did you take COMP 110 or equivalent?
A) <= 1 B) 2 C) 3 D) 4 E) >= 5
7) What is the name/number of the course in which you are taking this exam (e.g, COMP 350)?
8) What is the year/semester in which your are taking this exam (e.g., Spring 2007)?
Java Code Skeleton
import java.util.*;
public class Driver {
public static void main(String[] args) {
testDriver1();
testDriver2();
}
public static void testDriver1() {
int[] data = {33, 19, 54, 26, 105, 449, 62, 91, 504, 67};
MyList list = new MyList();
for (int i=0; i<data.length; i++) {
if (i%2==0) {
list.insertAtHead(data[i]);
System.out.println("insert " + data[i] +
" at head: " + list);
}
else {
list.insertAtTail(data[i]);
System.out.println("insert " + data[i] +
" at tail: " + list);
}
}
}
public static void testDriver2() {
int[] data = {5,7,9,11};
MyList list = new MyList();
for (int j=1; j<=4; j++) {
System.out.println("Delete tests for " + j +
"-element list" + "\n");
list.clear();
for (int i=0; i<j; i++) list.insertAtTail(data[i]);
System.out.println("Original list: " + list);
list.deleteAtHead();
System.out.println("After deleteAtHead(): " + list
+ "\n");
list.clear();
for (int i=0; i<j; i++) list.insertAtTail(data[i]);
System.out.println("Original list: " + list);
list.deleteAtTail();
System.out.println("After deleteAtTail(): " + list
+ "\n");
}}
}
class Node {
private int value;
private Node next;
public Node() {
}
public Node(int v) {
}
public String toString() {
return Integer.toString(value);
}
public int getValue() {
return 0;
}
public void setValue(int v) {
}
public Node getNext() {
return null;
}
public void setNext(Node n) {
}
}
class MyList {
private Node head;
public MyList() {
}
public String toString() {
Node n = head;
String s = "";
while (n != null) {
s = s + n.toString() + " ";
n = n.getNext();
}
return s;
}
public void insertAtHead(int v) {
}
public void insertAtTail(int v) {
}
public int deleteAtHead() {
return 0;
}
public int deleteAtTail() {
return 0;
}
}
C++ Code Skeleton
#include <iostream>
#include <fstream>
using std::cin;
using std::cout;
using std::endl;
using std::ostream;
class Node {
public:
Node();
Node(int);
int getValue();
void setValue(int);
Node* getNext();
void setNext(Node* n);
private:
int value;
Node *next;
};
Node::Node() { }
Node::Node(int v) { }
int Node::getValue() { return 0; }
void Node::setValue(int v) { }
Node* Node::getNext() { return NULL; }
void Node::setNext(Node* n) { }
class MyList {
public:
MyList();
void insertAtHead(int);
void insertAtTail(int);
int deleteAtHead();
int deleteAtTail();
void insertAtPosition(int,int);
int deleteAtPosition(int);
void clear();
friend ostream& operator<<(ostream&, MyList&);
private:
Node* head;
};
MyList::MyList() { }
void MyList::insertAtHead(int v) { }
void MyList::insertAtTail(int v) { }
int MyList::deleteAtHead() { return 0; }
int MyList::deleteAtTail() { return 0; }
void MyList::insertAtPosition(int v, int pos) { }
int MyList::deleteAtPosition(int pos) { return 0; }
void MyList::clear() { }
ostream& operator<<(ostream& os, MyList& list) {
if (list.head==NULL)
os << "empty";
else {
Node *m = list.head;
while (m != NULL) {
os << m->getValue() << " ";
m = m->getNext();
}
}
return os;
}
void testDriver1() {
const int datalength = 10;
int data[] = {33, 19, 54, 26, 105, 449, 62, 91, 504, 67};
MyList list;
for (int i=0; i<datalength; i++) {
if (i%2==0) {
list.insertAtHead(data[i]);
cout << "insert " << data[i] << " at head: "
<< list << endl;
}
else {
list.insertAtTail(data[i]);
cout << "insert " << data[i] << " at tail: "
<< list << endl;
}
}
}
void testDriver2() {
int data[] = {5,7,9,11};
MyList list;
for (int j=1; j<=4; j++) {
// 1-element list tests
cout << "Delete tests for " << j << "-element list"
<< endl;
list.clear();
for (int i=0; i<j; i++) list.insertAtTail(data[i]);
cout << "Original list: " << list << endl;
list.deleteAtHead();
cout << "After deleteAtHead(): " << list << endl;
list.clear();
for (int i=0; i<j; i++) list.insertAtTail(data[i]);
cout << "Original list: " << list << endl;
list.deleteAtTail();
cout << "After deleteAtTail(): " << list << endl;
}
}
int main(void) {
testDriver1();
testDriver2();
return 0;
}
Output From Drivers
Compare your output to the following results:
Test Driver #1
insert 33 at head: 33
insert 19 at tail: 33 19
insert 54 at head: 54 33 19
insert 26 at tail: 54 33 19 26
insert 105 at head: 105 54 33 19 26
insert 449 at tail: 105 54 33 19 26 449
insert 62 at head: 62 105 54 33 19 26 449
insert 91 at tail: 62 105 54 33 19 26 449 91
insert 504 at head: 504 62 105 54 33 19 26 449 91
insert 67 at tail: 504 62 105 54 33 19 26 449 91 67
Delete tests for 1-element list
Test Driver #2
Delete tests for 1-element list
Original list: 5
After deleteAtHead(): empty
Original list: 5
After deleteAtTail(): empty
Delete tests for 2-element list
Original list: 5 7
After deleteAtHead(): 7
Original list: 5 7
After deleteAtTail(): 5
Delete tests for 3-element list
Original list: 5 7 9
After deleteAtHead(): 7 9
Original list: 5 7 9
After deleteAtTail(): 5 7
Delete tests for 4-element list
Original list: 5 7 9 11
After deleteAtHead(): 7 9 11
Original list: 5 7 9 11
After deleteAtTail(): 5 7 9
1