Introduction
txt，
void Shift_bigNumber(struct bigNumber N1,struct bigNumber N2,unsigned int R)
{
int i,j;
i=0;
j=R;
while(jdigit[i]=N1.digit[j];
i++;
j++;
}
j=0;
while(jdigit[i]=N1.digit[j];
i++;
j++;
}
if(idigit[i]=’\0’;
}
}
Requirement
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 1 of 14
FINAL EXAMINATION
INTRODUCTION TO ALGORITHMS AND PROGRAMMING II
03-60-141-01
U N I V E R S I T Y O F W I N D S O R
S C H O O L O F C O M P U T E R S C I E N C E
Fall 2009
Last Name:
First Name:
Student ID:
P LEASE READ CAREFULLY BEFORE YOU START
1. This is a CLOSED book test; no notes, textbooks, calculators or
computer aids are allowed.
2. PRINT your name legibly and clearly with your Student ID in the
space indicated above.
3. You will be asked to sign your name, once during the exam (sign-in)
and once before leaving the exam room (sign-out).
4. Check the correct lecture section that you are registered in above.
5. Answer all the questions in the space provided. DO NOT REMOVE
any pages or attach any papers to this test or you will void your test
and receive a mark of zero. If you need more space please request an
additional exam booklet which MUST be returned with this exam
paper with your name and ID clearly written on it.
6. You are not allowed to give or receive unauthorized help with your
test. Any misconduct, as outlined by the Senate bylaw 31 article I,
will be reported accordingly. Such misconduct includes any
attempt, by any means whatsoever, to copy answers from other
students, or to receive any unauthorized assistance answering
any and all questions.
7. Unclear or undocumented code will not be graded and receive a
mark of zero.
8. You have 3 hours to complete this test.
9. Final examinations papers are not returned to students.
10. You may view your exam paper during the specified date and time to
be posted by your respective instructor.
11. Document your code where necessary. (For questions that ask
you to write a function, write both prototype and definition, with
proper documentation, you do not need to write a main). State all
your assumptions and all header file includes that you may use.
Good Luck!
I AGREE TO THE ABOVE TERMS AND WILL NEITHER RECEIVE
NOR GIVE UNAUTHORIZED HELP ON THIS EXAM
S IGNATURE D ATE
M ARKS :
Q1
/10
Q2
/10
Q3- A
/10
Q3- B
/10
Q4
/10
Q5
/40
TOTAL:
/90
S IGN HERE
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 2 of 14
Q1. [10 MARKS] Consider the following definitions:
// your code must be scalable
#define MAX 10
struct bigNumber {
char digit[MAX]; // a digit is between ‘0’ and ‘9’ inclusive
};
Write and document a function called Shift_bigNumber that takes as parameters two bigNumber data types as defined
above named N1 and N2, and a third parameter an unsigned int data type R. The task of the function is to move the digits
of N1 to N2 such that all digits are shifted R times to the left, with the leftmost digits re-entering from the right. (The
example below is intended to illustrate only – your answer must be general.)
For example:
// assume the following declarations.
struct bigNumber N1={‘2’,’0’,’5’,’7’,’3’,’1’,’4’,’0’,’9’,’1’};
struct bigNumber N2;
unsigned int R = 4;
Shift_bigNumber(N1, N2, R); // N2 will be {‘3’,’1’,’4’,’0’,’9’,’1’,’2’,’0’,’5’,’7’}
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 3 of 14
Q2. [10 MARKS] What is the output of the following program? Show your work by carefully drawing the memory
allocations to support your answer.
#include
#include
struct demo {
int num1;
int num2;
struct demo ptrNext;
};
void main() {
int N[]={2,8,2,7,9,-1};
int M[]={1,2,3,4,5,6};
int n=0;
struct demo ptrTemp=NULL;
struct demo ptrLast=NULL;
struct demo ptrFirst=NULL;
while (N[n]!=-1) {
ptrTemp = (struct demo)(malloc(sizeof(struct demo)));
ptrTemp->num1 = N[n];
ptrTemp->num2 = M[n];
ptrTemp->ptrNext = NULL;
if (n==0) {
ptrFirst = ptrTemp;
ptrLast = ptrTemp;
}
else {
if (ptrTemp->num >= ptrLast->num) {
ptrLast->ptrNext = ptrTemp;
ptrLast = ptrTemp;
}
else {
ptrTemp->ptrNext = ptrFirst;
ptrFirst = ptrTemp;
}
}
n++;
}
ptrTemp = ptrFirst;
n = 0;
while(ptrFirst != NULL) {
printf(“%d: %d %d\n”, n, ptrTemp->num1, ptrTemp->num2);
ptrTemp = ptrFirst->ptrNext;
free(ptrFirst);
ptrFirst = ptrTemp;
n++;
}
}
OUTPUT:
0: 7
1: 7
2: 2
3: 8
4: 14
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 4 of 14
Q3. a. [10 MARKS] Write and Document a self-referential structure definition called “contact” that stores the
FirstName (char[41]), LastName (char[41]) and id (int) of a contact in the space provided. Then, complete the
program as requested by the documentation located inside the program. (Do not use global variables).
#include
#include
#include
/ Write and document the self-referential structure definition for ‘contact’ below: /
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
void main( )
{ / Dynamically create a ‘contact’ record in a SINGLE STATEMENT (including declarations) /
————————————————————————————————–
————————————————————————————————–
/ Initialize the values of the new record to: John Doe, id=10 /
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
/ Create a second record linked to the first one, do this in a SINGLE STATEMENT without
declaring any additional pointer variables /
————————————————————————————————–
/ Initialize the values of the second record to: Will Smith, id=20 (without declaring new
variables) /
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
————————————————————————————————–
/ Call the recursive function PrintList to print all the records to the console (one statement) /
————————————————————————————————–
/ Call the recursive function ClearList that erases all the records from memory (one statement) /
————————————————————————————————–
}
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 5 of 14
Q3. b-i. [5 MARKS] Develop the recursive function called PrintList as used in program 3a. Write the prototype and
definition (implementation) with complete documentation. PrintList displays all the records stored in the linked list to the
screen. Use the format: LastName, FirstName ID to display each record.
Q3. b-ii. [5 MARKS] Develop the recursive function called ClearList as used in program 3a. Write the prototype and
definition (implementation) with complete documentation. ClearList erases all the dynamic records from memory.
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 6 of 14
Q4. [10 MARKS] Write and document a C function called FindToken that accepts two parameters: a null terminated
character array (string) called S in reference to the string to be searched, and a second string parameter called T. The
string T is a list of characters (not including the ‘\0’) that are tokens, or characters to be searched for in S. The function
may not modify either S or K. It will return a character pointer to the position of the first character in K that is found in S,
if it is found in S, or NULL otherwise.
For example:
printf(“%s”, *FindToken(“are exams over yet?”, “zypqt”)); // will display “yet?”
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 7 of 14
Q5. [40 MARKS] Write and document a complete C program to satisfy the following requirements.
Given a sequential text file that has the following layout where each line is one record containing the following fields
(separated by a single space):
int sid (any positive integer – a student id)
char name[50] (full name of student)
float gpa (student grade point average)
The file may contain any number of records; however, you may assume that the computer memory is large enough to
accommodate the size of the input file. Each record is on a separate line.
You must write a complete C program to include the following features:
1. Define a proper structure to accommodate the storage of the records in memory. (call the structure: student)
2. Design and declare all variables and functions as appropriate to do the processing as required for this program
(You may use global variables).
3. Write all necessary code to:
a. Read the records from the input file (called “studentlist.dat”)
b. Sort all the records by the “sid” field in ascending order. (Hint: use insertion sort while reading)
c. Display the results on the screen (ie. standard output, stdout) in descending order.
d. Write your results back into the file “studentlist.dat” and thereby overriding its contents, and where the
records are now stored in the file (the results in the file will be in ascending order as shown in the
example below).
Given the following sample sequential text file to illustrate:
Sample contents of “employeelist.dat” before processing:
2 john_doe 4.50
4 mary_jane 3.10
3 bob_smith 1.00
1 britney_spears 5.00
5 david_letterman 4.30
Sample contents of “employeelist.dat” after processing (i.e. after executing the
program):
1 britney_spears 5.00
2 john_doe 4.50
3 bob_smith 1.00
4 mary_jane 3.10
5 david_letterman 4.30
Requirements:
- Your program should be able to handle a file with any number of records.
- Write all functions necessary and explain the process of your technique (Write your algorithm clearly and
document your code!)
- The full name is stored with an underscore character substituting the space character. When displayed on the
screen however, the underscore character is replaced by a space character.
- You may assume that the records have a unique sid.
P LEASE USE THE ATTACHED PAGES AND THE OUTLINED GUIDE TO COMPLETE THIS QUESTION
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 8 of 14
// #include’s [1 mark]
// structure definition [5 marks]
// global variables [2 marks]
// function prototypes [2 marks]
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 9 of 14
// main function (no menu required – just invoke the function calls to
// satisfy the request program sequence) [5 marks]
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 10 of 14
// Code all necessary functions here [25 marks]
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 11 of 14
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 12 of 14
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 13 of 14
© 2009 by Dr. Robert D. Kent – All Rights Reserved. No part of this document may be reproduced without written author permission.
Page 14 of 14