Name:Date: 14May2005
12
3
4
T
Number:
EEE 212 -Algorithms & Data Structures
2ndMidterm Exam
Instructor: Dr. Hasan Demirel
Read the Following Instructions Carefully:
- The duration of the exam is strictly 120 minutes. No extra time will be given.
- Answer each question to a separate sheet on your answers booklet.
Q U E S T I O N S& SOLUTIONS
------
1.Given that we have a linearly linked list pointed by list, where each node of the list contains the employee information including the name, ID number and salary of an employee.
(a)(%3) Write an appropriate node structure definition for the list.
typdef struct{
char name[20];
long ID;
float salary;
}EMPLOYEE;
struct node{
EMPLOYEE info;
struct node *next;
};
typedef struct node nodeptr;
(b) (%7) Write a function, DeleteFirst, that deletes the first node of the list. The function returns the pointer to the beginning of the new list.
nodeptr *DeleteFirst(nodeptr *plist)
{
nodeptr *p;
p = plist-> next; /*I assume that the list contains at least 1 node*/
free(plist);
return p;
}
(c) (%15)Write another function, DeleteUnderAv, which deletes the nodes with employees receiving salaries, less than the average salary of all the employees in the list. The function returns the number of deleted nodes.
int DeleteAv(nodeptr *plist)
{
int count=0;
float sum=0.0, ave;
nodeptr *p;
p = plist;
while(p->next != NULL){
sum = sum + p->info.salary;
count++;
p=p->next;
}
ave = sum/count;
count=0;
p = plist;
/*The following loop will check all the nodes except the first node*/
while(p->next != NULL){
if(p->next->info.salary < ave){
deleteafter(p);
count++;
p=p->next;
}
}
/*The following if statement checks the first node only*/
if(plist->info.salary < ave){
p=plist;
plist=plist->next;
free(p);
count++;
}
return count;
}
void deleteafter(nodeptr *p)
{
nodeptr *q;
q=p->next;
p-next=q-next;
free(q);/*Note that I am not saving info part*/
}
------
2.Assume that there is a circular linked list that keeps the customer information staying in a Hotel. Each node in the list contains the name and the room number of each customer in the hotel.
(a)(%3) Write an appropriate node structure definition for the circular linked list.
typdef struct{
char name[20];
int RoomNo;
}CUSTOMER;
struct node{
CUSTOMER info;
struct node *next;
};
typedef struct node nodeptr;
(b)(%22) Write a function, CreateCircular, that receives a pointer,clist,as an argument pointing a single node circular list which is the header node. The customer information is entered by the user and inserted into the circular list until the user enters -1 as the room number to terminate. The function returns the number of inserted nodes to the list.
int CreateCircular(nodeptr *clist)
{
CUSTOMER a;
int count=0;
nodeptr *p;
p = clist;
do{
printf(“Enter the Name and the Room Number (Enter -1 as the Room Number to stop)\n”);
scanf(“%s”,a.name);
scanf(“%d”,&a.RoomNo);
if(a.RoomNo != -1){
insertafter(p,a);
p=p->next;
count++;
}
}while(a.RoomNo != -1);
return count;
}
void insertafter(nodeptr *p, CUSTOMER x)
{
nodeptr *q;
q=getnode();
q->info = x;
q->next = p->next;
p->next = q;
}
nodeptr *getnode(void)
{
nodeptr *p;
p = (nodeptr *) malloc(sizeof(nodeptr));
return p;
}
------
3.Assume that there is a doubly circular list where each node contains the name and the total points of each team in a football league. The list has a header node containing a flag variable and is pointed by a pointer called dlist. The flag is 1 for the header and 0 for the other nodes.
(a)(%3) Write an appropriate node structure for the doubly linked list.
typdef struct{
char name[20];
int TotPoints;
}FOOTBALL;
struct node{
int flag;
FOOTBALL info;
struct node *right;
struct node *left;
};
typedef struct node nodeptr;
(b)(%15) Write a function, ListSort, to sort the teams according to their total points in descending order.
void ListSort(nodeptr *dlist)
{
int pass, i, size=0;
FOOTBALL hold;
nodeptr *p;
p=dlist;
while(p->flag !=1){
size++;
p=p->right;
}
for(pass=1;pass<=size-1;pass++){
for(i=0;i<=size-2;i++){
if(p->info.TotPoints < p->right->info.TotPoints){
hold = p->info;
p->info = p->right->info;
p->right->info = hold;
}
}
}
}
(c)(%7) Assuming that the league list is sorted as in (b), write another function to display the teams with the highest and the lowest points respectively.
void HighLow(nodeptr *p)
{
printf(“The team with the Highest Point is %s\n The team with the Lowest Point is %s\n, p ->info.name, p ->left->info.name);
}
------
4.(a) (%10) Consider the following node structure definition for a Binary Tree.
struct node{
char letter;
struct node *left, *right, *father;
};
typedef struct node nodeptr;
Trace the following function to determine the output according to the Binary Tree given below.
void myfunction(nodeptr *tptr)
{
if(tptr == NULL)
return;
else{
myfunction(tptr->rigth);
printf(“%c”, tptr->letter);
myfunction(tptr->left);
}
}
Tracing the given recursive function would result the traversal of all of the binary tree nodes. During the traversal of the tree the letter in each node will be printed in the right – root – left order. The output of this recursive function is given below:
ALGORITHIMS
(b) (%15) Given that we have a pointer, lptr,pointing one of the leaf nodes of a Binary Tree, write a function, LeafDepth, that follows the required links until it reaches the root node. Consider the node structure given in (a) where the father pointer points the father of a given node. Note that the function returns the depth/level of the given leaf node.
Note that we assume that the father pointer in the root node is NULL.
int LeafDepth(nodeptr *lptr)
{
nodeptr *p;
int level=0;
p = lptr;
while(p->father != NULL){
level ++;
p = p ->father;
}
return level;
}
------