vu cs301 data structures

Welcome to Virtually helps.
www.vuhelp.com

For public part of the Throttle declaration below, mark each function member header as

follows:

• Mark C for any constructor;

• mark X for any function that is forbidden from changing the throttles data fields.

class Throttle

{

public:

Throttle( );

Throttle(int size);

void shut_off( );

void shift(int amount);

double flow( ) const;

bool is_on( ) const;

...

Answer/Solution

class Throttle

{

public:

Throttle( ); C

Throttle(int size); C

void shut_off( );

void shift(int amount);

double flow( ) const; X

bool is_on( ) const;X

...

Question No: 14 Marks: 5

I am going to execute this code with THREE pushes and ONE pop:

Stack s;

s.push(1);

s.push(2);

s.push(3);

cout <<>

Suppose that the stack s is represented by a fixed-sized array. Draw the state of the private

member variables “data” and “top” of “s” after the above code:

Answer/Solution

0 1 2 3 4 5 6 7 8 9

1 2 Top 1

Question No: 15 Marks: 10

Complete the body of this function. Use a Queue of characters to store the input line as

it is being read.

int counter( )

// Precondition:

// There is a line of input waiting to be read from cin.

// Postcondition:

// A line of input has been read from cin, up to but not

// including the newline character. The return value of

// the function is the number of times that the LAST

// character of the line appeared somewhere in this line.

// EXAMPLE

// Input: ABBXDXXZX The value returned by counter would

// be 4 for this input since there are 4 X’s in

// the input line.

{

int answer = 0;

Queue q;

Answer/Solution

int counter()

{

char a[100];

int i=0;

int answer=0;

Queue q;

cin.getline(a,98,'\n');

for(i=0;i

{

q.enqueue(a[i]);

}

i--;

while(!q.isEmpty())

{

if(a[i]==q.dequeue())

{

answer++;

}

}

return answer;

}

Question No: 16 Marks: 5

I am going to execute this code with THREE inserts and ONE remove:

Queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout <<>

Suppose that s is represented by a singly linked linked list. Draw the linked list and the state of the

private member variables of s after the above code:

front_ptr

rear_ptr

Answer/Solution

Question No: 17 Marks: 10

Consider CList and Node classes defined as follows:

class Node

{

public:

Node *next;

Node *prev;

int data;

};

class CList

{

public:

void insertHead(int);

void insertTail(int);

void removeHead();

void removeTail();

bool isEmpty();

bool find(int);

private:

Node *head;

Node *tail;

};

A. write the body of the member function insertHead which inserts a new element at the head

of the list.

void Clist::insertHead( int x )

{

B. write the body of the member function removeTail which removes the element at the tail of

the list.

void Clist::removeTail( int x )

{

Front_prt

2 3

rear_prt

Answer/Solution

(a) Solution for Question 17 option (a)

void CList::insertHead(int x)

{

Node *newNode=new Node();

newNode->data=x;

newNode->next=NULL;

newNode->prev=NULL;

if(isEmpty())

head=tail=newNode;

else

{

newNode->next=head;

newNode->prev=NULL;

head->prev=newNode;

head=newNode;

}

}

(b) Solution for Question 17 option (b)

void CList::removeTail(int &x)

{

if(isEmpty())

return;

else

{

Node *p=tail;

if(head==tail)

head=tail=NULL;

else

{

tail=tail->prev;

tail->next=NULL;

}

x=p->data;

delete p;

return;

}

}

Question No: 18 Marks: 10

Trace the running of the infix to postfix conversion algorithm on the infix expression

(A - B) + C/D

Answer/Solution

Symbol Postfix Stack

( (

A A (

- A (-

B AB (-

) AB-

AB-

(

+ AB- +

C AB-C +

/ AB-C +/

Question No: 19 Marks: 13

Here is a small binary tree:

A. What are all the leaves? (2pts)

C. What are the ancestors of the node 10? (2pts)

D. What are the descendants of the node 30? (2pts)

E. Is the tree a binary search tree (BST) (true/false)? (2pts)

F. Print the tree when visited in post-order manner? (5pts)

Answer/Solution

A) Leaves of the tree = 1,3,7,40

B) Ancestors of the node 10 = 11,14

C) Descendants of the node 30 = 40

D) Is the tree a binary search tree (BST) (true/false) False

E) Post Order Traversal = 1,3,2,7,10,40,30,11,14

Contact vuhelps@gmail.com
Regards
Vuhelps