S
Santi Ruiz
Guest
----------------------------------------------------------------------
| http://advctest.4t.com/ |
----------------------------------------------------------------------
This is the final Advance C examination at DMIT (D.M.I.T / Douglas
Mawson's Institute of Technology).
Advance is a branch of the Diplom in I.T. (Information Technology)
which is operational in Panorama (Adelaide 5000, South Australia,
Australia)
----------------------------------------------------------------------
RIPPED FROM THE TAFE SYSTEM:
C:\Data_Files\SUBJECT_RESOURCES_DMI\d_PrgC(C)\Assessments_04S1\test2\dPrgC_Test2B\dPrgC_Test2B_04S1_01.doc
STRAIGHT FROM SANTI RUIZ'S COMPUTER!!!
1st semester 2004 class at Douglas Mawson's' Institute of Technology
(TAFESA) with SANTI RUIZ.
----------------------------------------------------------------------
Regards,
Santi Ruiz < santruiz@dmi.tafe.sa.edu.au >
Principal Lecturer IT Studies
TAFE SA
Work: 82072878
Mob: 0401 125 172
----------------------------------------------------------------------
TEXT VERSION:::
RIPPED FROM THE TAFE SYSTEM:
C:\Data_Files\SUBJECT_RESOURCES_DMI\d_PrgC(C)\Assessments_04S1\test2\dPrgC_Test2B\dPrgC_Test2B_04S1_01.doc
STRAIGHT FROM SANTI RUIZ'S COMPUTER!!!
1st semester 2004 class at Douglas Mawson's' Institute of Technology
(TAFESA) with SANTI RUIZ.
tafesa
PROGRAMMING LANGUAGE C Š
TEST TWO
Two Hour Test
NAME: .
LECTURER:
YOU ARE ALLOWED TO USE
The lecture notes handed out
OR
a textbook
YOU MUST NOT USE OR ACCESS SOLUTIONS TO PAST TEST
PAPERS OR TRIAL TESTS
Question
Competency Achieved/Comments
Part A Theory
Part B Practical
Merit
The Instructor should forward this section to the Lecturers Assistant
if a resit is required.
Students need to make an appointment with the Lecturers Assistant to
do their resit.
Office Use Only
RESIT NOTIFICATION
Student Name
Lecturer Name
Assessment paper attempted
dPrgC_Test2_03S2_01.doc
Assessment paper for resit
Other Instructions for LA
Question
Resit Needed
Part A Theory
Part B Practical
ASSESSMENT INSTRUCTIONS
* To be assessed as competent you must correctly complete the core
component, which consists of all questions from Sections A and B.
* You will only be eligible for merit points if you successfully
complete the questions from the core section.
* You only need to attempt the merit question if you wish to gain
merit points towards a Credit or Distinction grade. The merit section
is worth a maximum of 2 merit points. No half points will be allocated
but 1 merit point may be achieved if an attempt is made that
sufficiently demonstrates the correct approach but is incomplete.
Performance Criteria for This Assessment
(Including underpinning knowledge)
ELEMENT
PERFORMANCE CRITERIA
Code each program module
2. The approach to be taken in coding and the modules and links
required is planned.
3. Code is created that conforms to organisational standards and those
agreed to by the development team.
PART A THEORY
Question1. Double Linked List.
The following is the DeleteList function for the single linked list
implementations of the LIST ADT.
/*
Pre: The linked list L has been created, L is not empty, and
0<=i<n,
Where n is the number of entries in L.
Post: The entry in position I of L has been returned as x
and deleted
From L; the entries in all later positions (provided I <
n) have
Their position numbers decreased by 1.
Uses: SetPosition.
*/
Void DeleteList(int I, ListEntry *x, List *L)
{
ListNode *current;
ListNode *temp;
if ((I < 0) || (I >= L->count))
printf("Error: Attempt to delete a nonexistent entry.");
else
{
if (I == 0)
{
Temp = L->head;
L->head = L->head->next;
}
else
{
SetPosition(i-1, L, &current);
Temp = current->next;
Current->next = temp->next;
}
*x = temp->entry;
free(temp);
L->count--;
}
}
(a) Make the necessary modifications to the DeleteList function to
make it work for a double-linked list according to the following
double-linked list datatypes and prototypes. You can assume the
SetPosition function has been written for the double linked list. You
do not need to write SetPosition.
Typedef struct listnode {
ListEntry entry;
Struct listnode *next;
Struct listnode *prev;
} ListNode;
Typedef struct list {
int count;
ListNode *current;
int currPos;
} List;
/*
Pre: p is a valid position on list list; 0 <=p < list->count.
Post: The list-current and list->currPos fields have been set to
the list node
At position p.
*/
Void SetPosition(Position p, List *list);
YOUR ANSWER: DeleteList for a double linked list:
1. void DeleteList(int I, ListEntry *x, List *L)
2. {
3. ListNode *current;
4. ListNode *temp;
5. if ((I < 0) || (I >= L->count))
6. printf("Error: Attempt to delete
a nonexistent entry");
7. else
8. {
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28. }
29. *x = temp->entry
30. free(temp);
31. L->count--;
32. }
33. }
(b) Demonstrate how your solution works by annotating the following
diagrams with line numbers from your solution indicating which lines
of your code make the necessary changes to the pointers in the
following example deletes.
DeleteList (0, &Entry, &L);
DeleteList (2, &Entry, &L);
DeleteList (3, &Entry, &L);
D
C
B
A
L
Current
Count=4
currPos=0
D
C
B
A
L
Current
Count=4
CurrPos=0
D
C
B
A
L
Current
Count=4
currPos=0
Question 2 Searching
(a) Name at least two conditions under which sequential search of a
list is preferable to binary search
(b) Using the following list of numbers demonstrate your
understanding of the provided binary search code (next page) by
documenting how the bottom, top and middle index values change in
searching for the number 55 :
NOTE: The binary search function provided does NOT do an equality
check within the loop. This reduces the number of comparisons needed.
10 12 16 30 35 45 50 55 100
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
/* Binary1Search: forgetful version of binary search.
Pre: The contiguous list list has been created.
Post: if an entity in list has key equal to target, then in function
returns the location of the first such entry (success). Otherwise the
function returns -1 (failure).
*/
Int Binary1Search(List list, KeyType target)
{
Int bottom, middle, top;
Top list.count 1;
Bottom = 0;
While (top > bottom) {
Middle = (top + bottom) / 2;
If (GT(target, list.entry[middle].key))
Bottom = middle + 1;
Else
Top = middle;
}
If (top == -1)
Return -1;
If (EQ(list.entry[top].key, target))
Return top;
Else
Return -1;
}
Question 3 Sorting
(a) A stable sort is one in which the order of entries with
duplicate keys is maintained once the sorting has been done. Determine
if the Insertion Sort, as provided in the textbook (DATA STRUCTURES &
PROGRAM DESIGN IN C SECOND EDITION by ROBERT KRUSE/C.L. TONDO/BRUCE
LEUNG), is stable and how may moves and comparisons are needed in
sorting the following list with the integer field as the key. The sort
is stable if 22,e still comes before 22,x in the sorted list:
12,a 21,b 33,d 22,e 22,x
(b) Describe the purpose of the partitioning step in the QuickSort
algorithm. Use the following list as an example. Take the pivot to be
the centre (or left centre) item.
Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay
Ron Jan
Question 4 Trees
(a) Explain the differences between a binary tree and a binary
search tree.
(b) Show how a binary search tree would look like if the keys below
were input into an initially empty tree.
(i) 8, 4, 12, 2, 6, 1, 3, 5, 7, 10, 14, 9, 11, 13, 15
(ii) 15, 13, 3, 2, 11, 7, 9, 6, 5, 4, 10, 12, 8, 14, 1
(c) Write down the order in which the nodes would be visited using
each of inorder, preorder and postorder transversal for your answer to
(i) above.
(d) Which traversal order should be used to save the contents of a
binary tree to a file so that the same binary tree can be recreated by
sequentially reading the data from the file?
PART B PRACTICAL
Question 5 Searching
You have been provided with code for a list implemented as a linked
list, listl.c, listl.h, tstlistl.c. Complete the partially provided
sequential search function, SeqSearchSortedList, in listl.c that could
be used for type char entries, that is, for simplicity in this version
we are assuming that the key field is the entry field. The version of
sequential search should meet the following requirements:
* It is to be written specifically for this implementation.
* It should make use of the pre-condition that the list is in
order.
Note that the EQ and LT macros are already provided. Add some code to
the tstlistl.c program to test your solution.
Question 6 Sorting
Complete the provided example code EgQSort.c so that the array is
output in order of the field NumOcc in the TWord struct and then the
Word field of the TWord struct by using the ANSI C qsort function.
MERIT SECTION
Only attempt this section once you have complete Part A and B and are
confident it is correct
Write and test the procedure RevList which reverses the order of the
items in a singly linked list. For example if the list L contains the
following characters :
L.head->a->b->c->d-|
It would become :
L.head->D->C->B->A-|
The function should traverse the list only once. The function is to be
included in the single linked list implementation of the list ADT, it
should be written specifically for this implementation. The header for
the function should be as follows
Void RevList(List *L);
/*
Pre: ListL has been created
Post: The entries in L have been reversed. Has no effect if the
list is empty.
*/
You need to provide
* A copy of the provided listl.c, listl.h that includes RevList.c
* A copy of tstlist.c that includes some testing of RevList.c,
including testing a call to RevList with an empty list.
HINT: Each node in the original list ends up pointing to its
predecessor, except for the first node which has no predecessor. Use
some temporary pointers (e.g. previous, current and next) and move
through the list adjusting the temporary pointers accordingly.)
| http://advctest.4t.com/ |
----------------------------------------------------------------------
This is the final Advance C examination at DMIT (D.M.I.T / Douglas
Mawson's Institute of Technology).
Advance is a branch of the Diplom in I.T. (Information Technology)
which is operational in Panorama (Adelaide 5000, South Australia,
Australia)
----------------------------------------------------------------------
RIPPED FROM THE TAFE SYSTEM:
C:\Data_Files\SUBJECT_RESOURCES_DMI\d_PrgC(C)\Assessments_04S1\test2\dPrgC_Test2B\dPrgC_Test2B_04S1_01.doc
STRAIGHT FROM SANTI RUIZ'S COMPUTER!!!
1st semester 2004 class at Douglas Mawson's' Institute of Technology
(TAFESA) with SANTI RUIZ.
----------------------------------------------------------------------
Regards,
Santi Ruiz < santruiz@dmi.tafe.sa.edu.au >
Principal Lecturer IT Studies
TAFE SA
Work: 82072878
Mob: 0401 125 172
----------------------------------------------------------------------
TEXT VERSION:::
RIPPED FROM THE TAFE SYSTEM:
C:\Data_Files\SUBJECT_RESOURCES_DMI\d_PrgC(C)\Assessments_04S1\test2\dPrgC_Test2B\dPrgC_Test2B_04S1_01.doc
STRAIGHT FROM SANTI RUIZ'S COMPUTER!!!
1st semester 2004 class at Douglas Mawson's' Institute of Technology
(TAFESA) with SANTI RUIZ.
tafesa
PROGRAMMING LANGUAGE C Š
TEST TWO
Two Hour Test
NAME: .
LECTURER:
YOU ARE ALLOWED TO USE
The lecture notes handed out
OR
a textbook
YOU MUST NOT USE OR ACCESS SOLUTIONS TO PAST TEST
PAPERS OR TRIAL TESTS
Question
Competency Achieved/Comments
Part A Theory
Part B Practical
Merit
The Instructor should forward this section to the Lecturers Assistant
if a resit is required.
Students need to make an appointment with the Lecturers Assistant to
do their resit.
Office Use Only
RESIT NOTIFICATION
Student Name
Lecturer Name
Assessment paper attempted
dPrgC_Test2_03S2_01.doc
Assessment paper for resit
Other Instructions for LA
Question
Resit Needed
Part A Theory
Part B Practical
ASSESSMENT INSTRUCTIONS
* To be assessed as competent you must correctly complete the core
component, which consists of all questions from Sections A and B.
* You will only be eligible for merit points if you successfully
complete the questions from the core section.
* You only need to attempt the merit question if you wish to gain
merit points towards a Credit or Distinction grade. The merit section
is worth a maximum of 2 merit points. No half points will be allocated
but 1 merit point may be achieved if an attempt is made that
sufficiently demonstrates the correct approach but is incomplete.
Performance Criteria for This Assessment
(Including underpinning knowledge)
ELEMENT
PERFORMANCE CRITERIA
Code each program module
2. The approach to be taken in coding and the modules and links
required is planned.
3. Code is created that conforms to organisational standards and those
agreed to by the development team.
PART A THEORY
Question1. Double Linked List.
The following is the DeleteList function for the single linked list
implementations of the LIST ADT.
/*
Pre: The linked list L has been created, L is not empty, and
0<=i<n,
Where n is the number of entries in L.
Post: The entry in position I of L has been returned as x
and deleted
From L; the entries in all later positions (provided I <
n) have
Their position numbers decreased by 1.
Uses: SetPosition.
*/
Void DeleteList(int I, ListEntry *x, List *L)
{
ListNode *current;
ListNode *temp;
if ((I < 0) || (I >= L->count))
printf("Error: Attempt to delete a nonexistent entry.");
else
{
if (I == 0)
{
Temp = L->head;
L->head = L->head->next;
}
else
{
SetPosition(i-1, L, &current);
Temp = current->next;
Current->next = temp->next;
}
*x = temp->entry;
free(temp);
L->count--;
}
}
(a) Make the necessary modifications to the DeleteList function to
make it work for a double-linked list according to the following
double-linked list datatypes and prototypes. You can assume the
SetPosition function has been written for the double linked list. You
do not need to write SetPosition.
Typedef struct listnode {
ListEntry entry;
Struct listnode *next;
Struct listnode *prev;
} ListNode;
Typedef struct list {
int count;
ListNode *current;
int currPos;
} List;
/*
Pre: p is a valid position on list list; 0 <=p < list->count.
Post: The list-current and list->currPos fields have been set to
the list node
At position p.
*/
Void SetPosition(Position p, List *list);
YOUR ANSWER: DeleteList for a double linked list:
1. void DeleteList(int I, ListEntry *x, List *L)
2. {
3. ListNode *current;
4. ListNode *temp;
5. if ((I < 0) || (I >= L->count))
6. printf("Error: Attempt to delete
a nonexistent entry");
7. else
8. {
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28. }
29. *x = temp->entry
30. free(temp);
31. L->count--;
32. }
33. }
(b) Demonstrate how your solution works by annotating the following
diagrams with line numbers from your solution indicating which lines
of your code make the necessary changes to the pointers in the
following example deletes.
DeleteList (0, &Entry, &L);
DeleteList (2, &Entry, &L);
DeleteList (3, &Entry, &L);
D
C
B
A
L
Current
Count=4
currPos=0
D
C
B
A
L
Current
Count=4
CurrPos=0
D
C
B
A
L
Current
Count=4
currPos=0
Question 2 Searching
(a) Name at least two conditions under which sequential search of a
list is preferable to binary search
(b) Using the following list of numbers demonstrate your
understanding of the provided binary search code (next page) by
documenting how the bottom, top and middle index values change in
searching for the number 55 :
NOTE: The binary search function provided does NOT do an equality
check within the loop. This reduces the number of comparisons needed.
10 12 16 30 35 45 50 55 100
#define EQ(a,b) ((a) == (b))
#define LT(a,b) ((a) < (b))
/* Binary1Search: forgetful version of binary search.
Pre: The contiguous list list has been created.
Post: if an entity in list has key equal to target, then in function
returns the location of the first such entry (success). Otherwise the
function returns -1 (failure).
*/
Int Binary1Search(List list, KeyType target)
{
Int bottom, middle, top;
Top list.count 1;
Bottom = 0;
While (top > bottom) {
Middle = (top + bottom) / 2;
If (GT(target, list.entry[middle].key))
Bottom = middle + 1;
Else
Top = middle;
}
If (top == -1)
Return -1;
If (EQ(list.entry[top].key, target))
Return top;
Else
Return -1;
}
Question 3 Sorting
(a) A stable sort is one in which the order of entries with
duplicate keys is maintained once the sorting has been done. Determine
if the Insertion Sort, as provided in the textbook (DATA STRUCTURES &
PROGRAM DESIGN IN C SECOND EDITION by ROBERT KRUSE/C.L. TONDO/BRUCE
LEUNG), is stable and how may moves and comparisons are needed in
sorting the following list with the integer field as the key. The sort
is stable if 22,e still comes before 22,x in the sorted list:
12,a 21,b 33,d 22,e 22,x
(b) Describe the purpose of the partitioning step in the QuickSort
algorithm. Use the following list as an example. Take the pivot to be
the centre (or left centre) item.
Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay
Ron Jan
Question 4 Trees
(a) Explain the differences between a binary tree and a binary
search tree.
(b) Show how a binary search tree would look like if the keys below
were input into an initially empty tree.
(i) 8, 4, 12, 2, 6, 1, 3, 5, 7, 10, 14, 9, 11, 13, 15
(ii) 15, 13, 3, 2, 11, 7, 9, 6, 5, 4, 10, 12, 8, 14, 1
(c) Write down the order in which the nodes would be visited using
each of inorder, preorder and postorder transversal for your answer to
(i) above.
(d) Which traversal order should be used to save the contents of a
binary tree to a file so that the same binary tree can be recreated by
sequentially reading the data from the file?
PART B PRACTICAL
Question 5 Searching
You have been provided with code for a list implemented as a linked
list, listl.c, listl.h, tstlistl.c. Complete the partially provided
sequential search function, SeqSearchSortedList, in listl.c that could
be used for type char entries, that is, for simplicity in this version
we are assuming that the key field is the entry field. The version of
sequential search should meet the following requirements:
* It is to be written specifically for this implementation.
* It should make use of the pre-condition that the list is in
order.
Note that the EQ and LT macros are already provided. Add some code to
the tstlistl.c program to test your solution.
Question 6 Sorting
Complete the provided example code EgQSort.c so that the array is
output in order of the field NumOcc in the TWord struct and then the
Word field of the TWord struct by using the ANSI C qsort function.
MERIT SECTION
Only attempt this section once you have complete Part A and B and are
confident it is correct
Write and test the procedure RevList which reverses the order of the
items in a singly linked list. For example if the list L contains the
following characters :
L.head->a->b->c->d-|
It would become :
L.head->D->C->B->A-|
The function should traverse the list only once. The function is to be
included in the single linked list implementation of the list ADT, it
should be written specifically for this implementation. The header for
the function should be as follows
Void RevList(List *L);
/*
Pre: ListL has been created
Post: The entries in L have been reversed. Has no effect if the
list is empty.
*/
You need to provide
* A copy of the provided listl.c, listl.h that includes RevList.c
* A copy of tstlist.c that includes some testing of RevList.c,
including testing a call to RevList with an empty list.
HINT: Each node in the original list ends up pointing to its
predecessor, except for the first node which has no predecessor. Use
some temporary pointers (e.g. previous, current and next) and move
through the list adjusting the temporary pointers accordingly.)