=========================preview======================
(COMP152)[2011](s)midterm~3319^_35063.pdf
Back to COMP152 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY

Department of Computer Science & Engineering
COMP 152: Object-Oriented Programming and Data Structures
Spring 2011
Midterm Examination

Date: Saturday, 2 April 2011
Time: 10:30am C 12:00pm
Instructor: Albert Chung (L1)/ Long Quan (L2)/ Gary Chan (L3)
Venue: LTC/ LTJ/ LTB

.
This is a closed-book examination. However, you are allowed to bring with you a piece of A4-sized paper with notes written or typed on both sides for use in the examination.

.
Your answers will be graded according to correctness, ef.ciency, precision, and clarity.

.
During the examination, you must put aside your calculators, mobile phones, PDAs and all other electronic devices. All mobile phones must be turned off.

.
You may use the reverse side of the pages for your rough work or continuation of work. This booklet has 16 single-sided pages. Please check that all pages are properly printed before you start working.


Student name: English nickname (if any):
Student ID: Email: Lecture and lab:

I have not violated the Academic Honor Code in this examination (signature):


Question Your score
Maximum score

Question
Your score
Maximum score






1a

12
2d

7
1b
6
2e
2
1c
12
2f
2
2a
4
2g
12
2b
12
2h
12
2c
7
2i
12

Total
100



1. Linked List Manipulation (30 points total)
A SortedListclass is a list of linked integers sorted in ascending order. It is implemented by a singly linked list de.ned below:
class Node{

public:

int data;

Node* next; // NULL for the last node

};

typedef Node* NodePtr;

class SortedList {
public:
... // constructor, destructor and other
// members you dont need to worry about

void insertNode(int item); // part (a)

void merge(const SortedList& list); // part (b)

void split(SortedList& outlist); // part (c)

private:
Nodeptr head; // pointer to the first node, NULL if empty
};

There is no header/sentinel/dummy node in the list. You are to implement the three member functions indicated above by manipulating the underlying linked list pointed by head.
(a)
(12 points) Implement the insertNode()member function which inserts a new node with value item to the list. The ascending order of the list should be preserved after the insertion. Note that the value does not need to be unique.

(b)
(6 points) Implement the merge() function which copies the items of the list list

and merges them into the current list to form a sorted list.
In this part, we will NOT grade you on ef.ciency; however, if you come up with a
correct ef.cient algorithm, you will get a bonus of 3 points.


(c)
(12 points) Implement the split() member function, which splits the list into two smaller lists the list on which the split function is called holds the .rst half, and outList holds the second half. You should split the original list into 2 lists without crea