Introduction to Data Structures

Exam II Review

1.) In the following program, the parameters are missing on the function calls in the main(). Rewrite the function calls, in the main(), using the proper parameters (you may choose any integers you wish). You may rewrite the corrected function calls next to the current function calls.

#include<stdlib.h>

#include<iostream.h>

const int STACK_SIZE = 50;

struct stack{

int count;

int data[STACK_SIZE];

};

void stack_init(struct stack &the_stack)

{

the_stack.count = 0;

}

void stack_push(struct stack &the_stack, const int item);

{

the_stack.data[the_stack.count] = item;

++the_stack.count;

}

int stack_pop(struct stack &the_stack)

{

--the_stack.count;

return(the_stack.data[the_stack.count]);

}

main()

{

struct stack stack_it;

stack_init( );

stack_push( );

stack_push( );

stack_push( );

cout << "Top of stack ->" << stack_pop( ) << '\n';

cout << "Next on stack ->" << stack_pop( ) << '\n';

cout << "Bottom of stack ->" << stack_pop( ) << '\n';

return(0); }

2.) Given the following postfix expression, use the evaluation algorithm to evaluate the expression. Note that the algorithm uses a stack and you must show the contents of the stack (and the top of the stack) at each step.

5_4_7_+_*_5_+

3.) Use the algorithm that converts an infix expression to a suffix expression to convert the following infix expression to suffix:

(A + B ) / E * C + Z

Again, you must show the stack and the top at each step.

4.) Define what is meant by a C++ class. Describe the differences, if any, between a C++ class and a regular struct. Think of the Stack programs to discuss the benefits of using a class over struct. Make sure you discuss public and private in your answer.

5.) a.) Read the following segment of code carefully. What is printed:

struct linknode {

int someletter;

struct linknode *nextnode;

}a, b, c,d, *ptr1;

a.someletter = ‘A’;

b. someletter = ‘B’;

c. someletter = ‘C’;

d. someletter = ‘D’;

a.nextnode = &c;

c.nextnode = &d;

d.nextnode = &b;

b.nextnode = NULL;

ptr1 = a.nextnode;

while (ptr1 != NULL) {

cout << ptr1 -> someletter << endl;

ptr1 = ptr1 -> nextnode;

}

b.) Draw the picture of the linked list of part a.).

c.) Illustrate (draw) how we would add a node, using the add_nth_node function, before the last node (n = 4). To do this show the arrows after each step (recall there are two main steps in this process).

6.) Given:

typedef struct car {

char make[12];

char color[12];

int year;

} NICECARS;

NICECARS car1, car2, car3, *car_ptr;

strcpy(car1.make, “BMW”);

strcpy(car2.make, “Mercedes”);

strcpy(car3.make, “Alpha Romeo”);

a.) Change the typedef structure to a self-referential structure to be used to implement a linked list of cars.

b.) Write the C code to link the nodes (cars) in a linked list. That is, the BMW is first then the Mercedes then the Alpha Romeo. The Alpha Romeo should end the list.