Name:Date: 15 April 2005
12
3
4
T
Number:
EEE 212 -Algorithms & Data Structures
First MidtermExam
Instructor: Dr. Hasan Demirel
Read the Following Instructions Carefully:
- The duration of the exam is strictly 100 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.IMF keeps the information of 180 countries in the world by using the following record structure:
- country name
- population
- economy
The economy of each country is another record with the following structure:
- budget
- income
- expenditure (spending)
Write a program with the following details:
(a) (%5) Create the data types ECONOMY to represent the economy of a country and COUNTRY to represent each country,
(b)(%10) The program should call a function, ReadCountry, to enter the information of all the countries in the world.
(c)(%15) The program should also call a function, RichestCountry, to provide and display the name of the country with highest Net National Income per Person (NNIP), where NNIP is defined to be the difference between the income and expenditure divided by the population.
#include<stdio.h>
#definesize180
typedef struct{
floatbudget, income, expenditure;
}ECONOMY;
typedef struct{
charname[20];
longpop;
ECONOMY e;
}COUNTRY;
void ReadCountry(COUNTRY [], int);
void RichestCountry(COUNTRY [], int);
void main()
{
COUNTRY C[size];
ReadCountry(C, size);
RichestCountry(C, size);
}
void ReadCountry(COUNTRY A[], int size)
{
int i;
for(i=0;i<size;i++){
printf(“\nEnter the record of country %d\n”,i+1);
scanf(“%s”,A[i].name);
scanf(“%ld”,&A[i].pop);
scanf(“%f”,&A[i].e.budget);
scanf(“%f”,&A[i].e.income);
scanf(“%f”,&A[i].e.expenditure);
}
}
void RichestCountry(COUNTRY A[], int size)
{
int i, pos;
float NNIP;
NNIP=(A[0].e.income - A[0].e.expenditure)/A[0].pop;
pos=0;
for(i=1;i<size;i++){
if((A[i].e.income - A[i].e.expenditure)/A[i].pop > NNIP){
NNIP=(A[i].e.income - A[i].e.expenditure)/A[i].pop;
pos=i;
}
}
printf(“The richest country is %s\n”,A[pos].name);
}
2.(%25) Assume that a new data structure called Priority Stack is to be developed. The Priority Stack is to have the same push function as in the ordinary stack. However in the case of popping the Priority Stack removes the item with the maximum value from the stack.
Write the definition of the function PriorityPop to pop the element with the highest value from the Priority Stack. Consider a Priority Stack with floating point numbers.
Assume that we use the following stack structure:
typedef struct{
int top;
int items[STACKSIZE];
}STACK;
float PriorityPop(STACK *sptr)
{
float max;
int maxpos,t;
t=sptr->top;
max=items[sptr-top];
maxpos=sptr->top;
if(sptr->top =-1)){
printf("Stack is empty\n");
exit(1);/*exit from the function*/
}
else {
while(sptr->top !=-1){
if(items[sptr->top]>max){
max=items[sptr->top];
maxpos=sptr->top;
}
sptr->top--;
}
}
for(i=maxpos; i < t; i++)
sptr->items[i] = sptr->items[i+1];
sptr->top=t-1;
return max;
}
3.Given a infix expression, we can convert the infix to prefix expression by using the following steps:
- input infix expression: i.e. a*b+(c-d)
- reverse the expression: i.e. )d-c(+b*a
- correct the parenthesis characters: i.e. (d-c)+b*a
- apply infix to postfix conversion: i.e. dc-ba*+
- reverse the expression: i.e. +*ab-cd
Assume that InfixtoPostfix function with the following prototype is already defined and can be usedfor conversion from Infix to Postfix.
void InfixtoPostfix(char *, char*);
(a)(%25) Write a function, InfixtoPrefix to convert the given Infix expression to Prefix and display it on the screen.
void InfixtoPrefix(char *infx, char*prefx)
{
int i, count;
char A[20],B[20];
count=strlen(infx); /* strlen() is a library function in string.h that */
/* returns the size of the given string */
for(i=0;i<count;i++)/*reverse the string*/
A[i]=infx[count-(1+i)];
A[i]=’\0’;
for(i=0;i<count;i++){/*correct the paranthesis*/
if(A[i]==’(‘)
A[i]=’)’;
if(A[i]==’)‘)
A[i]=’(’;
}
InfixtoPostfix(A,B);/*assume input A is converted and copied to B*/
for(i=0;i<count;i++)/*reverse the string*/
prefx[i]=B[count-(1+i)];
prefx[i]=’\0’;
printf(“The Infix Expression %s is converted to Prefix Expression %s\n),infx,prefx);
}
(b)(%5) Convert the following infix expression to prefix expression.
(a+b)/d+e*(f-g*h+k) = reverse and correct: (k+h*g-f)*e+d/(b+a)
Infix-to-postfix:khg*f-+e*dba+/+
Reverse:+/+abd*e+-f*ghk
4.(%15) Write a function, QueueStatus that returns 0 if a queue is empty, returns -1 if the queue is full and returns the number of elements in the queue otherwise. Consider a queue with circular array implementation.
Assume that we use the following queue structure:
struct queue{
int front, rear;
int items[MAXQUEUE];
}QUEUE;
intQueueStatus (QUEUE *qptr)
{
int f,r,count=0;
f=qptr->front;
r=qptr->rear;
if(qptr->front == qptr->rear)/*empty case*
return 0;
else if((qptr->rear++)%MAXQUEUE == qptr->front) /* full case*/
return -1;
else{
while(qptr->front !=qptr->rear){
qptr->front =(qptr->front++)%MAXQUEUE;/*Circular inc*/
count++;
}
qptr->front=f;
qptr->rear=r;
return count;
}
}