Elementary Sorting Methods

19 December, 2001COMP 102 -- Final Exam Page 1 of 16

THE HONG KONG UNIVERSITY OF SCIENCE AND TECHNOLOGY

Department of Computer Science

COMP 102: Computer and Programming Fundamentals I

Fall 2001 Final Examination

Version A

Date: 19 December 2001Time: 12:30-3:30 pm

Venue: Hall

This exam contains 10 questions in 16 pages. Please count the pages.

You have 3 hours to complete this exam.

Problem

Your points

Max points

Problem

Your points

Max points

Subtotal

Your total points

100

Please identify yourself: Lecture/Lab section

Name

Student ID

Signature

1. (6 points) For each of the follow C++ code segments, mark it with “CORRECT” if it is correct and “WRONG” if it is NOT correct. You should consider both syntax and logical correctness.
______a)int array[4] ={ 0, 1, 2, 3, 4 };
______b)int x[5];

x[0] = 0;
______c)void fn (const int x[ ] ) {

if ( x[0] < 0) x[0] = 0;

}
______d)char message[ ] = "Hello";
______e)char message[6];

message = "Hello";
______f)int array[2,3];

2. (10 points) The following program shows the result of a battle between the Taliban and Pashtun tribesmen in Afghanistan. The function call count(taliban) uses enumeration to store the values in the taliban array. What will the report function print on the screen?

#include <iostream.h>

#include <string.h>

enum {totalfighters, fighters, prisoners, dead, totaldead};

const int FIGHTERS = 500;

void count(int army[]);

// This function produces the values {221, 31, 19, 11, 160} when it is

// called with the taliban array.

// The values are {452, 146, 35, 39, 121} for the pashtun array.

void report(int army[], char name[], char city[]){

cout < "Current " < name < " dead: " < army[dead] < endl;

cout < "Current " < name < " prisoners: "

< army[prisoners] < endl;

cout < "Remaining " < name < " fighters in " < city < ": "

< army[fighters] < endl;

cout < "The " < name < " has lost " < army[totaldead]

< " fighters." < endl;

cout < "Total remaining " < name < " fighters: "

< army[totalfighters] < endl < endl;

}

int main () {

int taliban[5] = {FIGHTERS, 0, 0, 0, 0};

int pashtun[5] = {FIGHTERS, 0, 0, 0, 0};

count(taliban);

report(taliban, "Taliban", "Kandahar");

count(pashtun);

pashtun[totalfighters] += taliban[prisoners];

report(pashtun, "Pashtun", "Kandahar");

return 0;

}

Answer: Complete the following output produced by the report function:

Current Taliban dead: ______

Current Taliban prisoners: ______

Remaining Taliban fighters in Kandahar: ______

The Taliban has lost ______fighters.

Total remaining Taliban fighters: ______

Current Pashtun dead: ______

Current Pashtun prisoners: ______

Remaining Pashtun fighters in Kandahar: ______

The Pashtun has lost ______fighters.

Total remaining Pashtun fighters: ______

3. (10 points) This is the selection sort algorithm discussed in the lecture for sorting int arrays:

void select(int data[], int size){

int temp;

int max_index = 0;

for (int rightmost=size-1; rightmost>0; rightmost--){

for(int current=1; current<=rightmost; current++){

if (data[current] > data[max_index])

max_index = current;

}

if(data[max_index] > data[rightmost]){

temp = data[max_index];

data[max_index] = data[rightmost];

data[rightmost] = temp;

}

Using the select function above as reference, make minimal changes to make it work for the composer array shown in the main function below.Sort the array elements in alphabetical order. On the nextpage, for each line that needs to be modified, cross out that line and write the modified version in the blank space immediately following that line.

int main() {

char composer[ARRAY_SIZE][STRING_SIZE] = {"Mozart",

"Beethoven", "Bach", "Handel", "Stravinsky",

"Berlioz", "Harrison", "Lansky", "Wagner",

"Debussy"};

int index;

select(composer, ARRAY_SIZE);

cout < endl < "After sorting: ";

for (index = 0; index<ARRAY_SIZE; index++)

cout < composer[index] <" ";

cout < endl;

return 0;

}

void select(int data[], int size){

______

int temp;

______

int max_index;

______

for(int rightmost=size-1; rightmost>0; rightmost--){

______

for (int current=1; current <= rightmost; current++) {

______

if (data[current] > data[max_index])

______

max_index = current; }

______

if (data[max_index] > data[rightmost]) {

______

temp = data[max_index];

______

data[max_index] = data[rightmost];

______

data[rightmost] = temp; }

______

} // outer for loop

______

}

4. (15 points total) The following program generates 5 random numbers and puts them in the first row of a 2-dimensional array. The program completes some mathematical calculations on the numbers and fills in a “magic square” in the other 4 rows of the array.

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

const int SIZE = 5;

void writesquare(int magic[][SIZE]);

int setnumber (int thiscol, int magic[][SIZE]){

int newnumber;

bool taken;

do {

taken = false;

newnumber = rand()%SIZE;

for (int col = 0; col <= thiscol; col++){

if (magic[0][col] == newnumber)

taken = true;

}

} while (taken == true);

return newnumber;

}

int main() {

int magic[SIZE][SIZE];

srand(time(0));

for(int row = 0; row < SIZE; row++){

for(int col = 0; col < SIZE; col++){

if (row < 1){

if (col < 1)

magic[0][0] = 0;

else

magic[row][col] = setnumber(col, magic);

}

else {

if (col < 1)

magic[row][0] = SIZE – magic[0][row];

else

magic[row][col] = (magic[0][col]+magic[row][0]) % SIZE;

}

writesquare(magic);

return 0;

}

a)(10 points) The setnumber() function generates the 5 random numbers for the first row. Assume that the random number function rand() in the setnumber function produces the following number sequence: {0, 3, 4, 3, 11, 0, 7, 6,…}. In the following grid, please write out the content of the magic array.

void void writesquare(int magic[][SIZE]){
}

b)(5 points) In the box below, complete the writesquare() function to print SIZE rows of numbers in the magic array.

5. (10 points) The following program reads a musical note list in a text file “input.txt” and converts the alphabetic characters to numbers (which represent the frequencies of musical notes). Please insert the necessary statements to write out the note list into a file called “output.txt”. Between each column there is a tab(‘\t’) character. is the new-line character.

6. (5 points) What does the following program print on the screen?

#include <iostream.h>

int luckynumber = 808;

void moreluck(int& thisnumber) {

luckynumber = luckynumber + 8;

cout < luckynumber < endl;

thisnumber = thisnumber + 8;

cout < thisnumber < endl;

}

void addluck(int thisnumber) {

thisnumber = thisnumber + 8;

cout < thisnumber < endl;

}

int main () {

int luckynumber = 880;

addluck(luckynumber);

cout < luckynumber < endl;

moreluck(luckynumber);

cout < luckynumber < endl;

return 0;

}

Answer (use as many lines as needed):

______

7.( 5 points) What is the output of the following code, when the input from the keyboard is: 1912589R2D2Hello

( is the new line character.)

#include <iostream.h>
#include <ctype.h>
int main(){
int count = 0;
cout <"Enter a line of input:\n";
char next;
cin.get(next);
do{
if ((count%2) == 0)
cout.put(next);
count++;
cin.get(next);
} while(isdigit(next) & (next != '\n'));
cout < "END"<endl;
return 0;
}

Answer (use as many lines as needed):

______

8. (10 points) Write a recursive function Balance, that takes three integer inputs: current_balance, interest_rate, years and returns a value of double type representing the balance, with interest compounded annually, by the end of that number of years. For example, Balance(1000,10,1) returns the value of 1100, and Balance(1000,10,2) returns the value of 1210.

9. (10 points) Complete the definition of function string_concat on the next page. The function will copy two strings, in order, into a third string up to the specified length. For example, the output of the program in the box below would be:

Merry Chr

Merry Christmas!

The third string should always have the end of string character ‘\0‘. The string_concat function must have these six parameters:

char s1[];//string 1

int num1 ;// number of characters in s1

char s2[];//string 2

int num2; //number of characters in s2

char s3[]; //string 3

int size3; //size of s3 including the last ‘\0‘.

#include <iostream.h>
void string_concat(char s1[], int num1, char s2[],
int num2, char s3[], int size3);
int main()
{
char s1[20] = "Merry ";
char s2[20] = "Christmas!";
char s3[3] = {0};
char s4[10] = {0};
char s5[20] = {0};
string_concat(s1,6, s2,10, s3, 3);
cout < s3 < endl ;
string_concat(s1,6, s2,10, s4, 10);
cout < s4 < endl ;
string_concat(s1,6, s2,10, s5, 20);
cout < s5 < endl ;
return 0;
}
void string_concat(char s1[], int num1, char s2[],
int num2, char s3[], int size3)
{
}

You are not allowed to use any string manipulation function from the <string.h> library.

10. (19 points) In our homework assignment part two, you have used the following structure to represent the users’ accounts.

const int USER_LEN = 20; const int PASS_LEN = 8;

struct ACCOUNT {

char name[USER_LEN+1] ;

char password[PASS_LEN+1] ;

int expire_month, expire_year; //expiry date

double limit;

};

a)(6 points) Write a function

int cmp_date(ACCOUNT customer, int year, int month)

that compares the expiry date of parameter customer with a given date represented by the integer parameters year and month. The function should return –1, 0, or 1 if the expiry date of customer is earlier, the same as, or later than the given date respectively.

b)
B)(3 points) Below is a function that reports the occurrences of an integer in a sorted array using ordered linear search. It is different from the version in the lecture notes; it can report multiple occurrences of the searching value.

void multi_linear_search(int data[], int size, int value) {

for (int index=0; index<size; index++) {

if (data[index] > value)

break;

else if (data[index] == value)

cout < “Found at position “ < index < endl;

}

The following program calls this version of linear search. What is the output?

int main() {

int a[10] = {-5, -3, -3, 0, 2, 2, 2, 4, 10, 10};

multi_linear_search(a, 10, 2);

return 0;

}

c)(10 points) Assume you are given an array of ACCOUNT whose elements are sorted in chronological order by expiry date. This means the first element in the array has the earliest expiry date. Make minimal changes to the multi_linear_search function below so that it displays the indices of the accounts whose expiry dates are the same as a specified date, which is a parameter of the following structure.

struct DATE {

int year;

int month;

};

For a line that requires changes, you should first cross it out and then write down the modified code in the space below the line. (Hint: use the function you have defined in part a).

//The first line is already changed for you:

void multi_linear_search_2(ACCOUNT customers[], int size, DATE date)

{

for (int index=0; index<size; index++) {

______

if (data[index] > value)

______

break;

______

else if (data[index] == value)

______

cout < “Found at position “ < index < endl;

______

}