数据结构代写|CSCI 2100C Data Structures Quiz 1

这是一个中国香港的数据结构限时测试代写

1. Michael has written the following header files stack.h and queue.h for the ADTs of stack
of integers and queue of integers. He has correctly implemented the ADTs in stack.c and
queue.c.

/* File: stack.h */
/* Author: Michael */

typedef struct stackCDT *stackADT;
typedef int stackElementT;

stackADT EmptyStack(void);
void Push(stackADT, stackElementT);
stackElementT Pop(stackADT);
int StackIsEmpty(stackADT);

/* File: queue.h */
/* Author: Michael */

typedef struct queueCDT *queueADT;
typedef int queueElementT;

queueADT EmptyQueue(void);
void Enqueue(queueADT, queueElementT);
queueElementT Dequeue(queueADT);
int QueueIsEmpty(queueADT);

a) (20 marks) What will be printed if the following program is run?

#include <stdio.h>
#include <stdlib.h>
#include “stack.h”
#include “queue.h”

main() {
stackADT S1 = EmptyStack();
queueADT Q1 = EmptyQueue();
Enqueue(Q1, 7); Enqueue(Q1, 3);
Push(S1, Dequeue(Q1)); Push(S1, 6); Push(S1, 4);
Enqueue(Q1, 1 + Pop(S1));
while (!StackIsEmpty(S1)) printf(“%d “, Pop(S1)); printf(“\n”);
while (!QueueIsEmpty(Q1)) printf(“%d “, Dequeue(Q1)); printf(“\n”);
}

Tom is going to use the stack ADT and queue ADT that Michael defines to write a function
twoStacks. The function takes two stackADT arguments and returns a stackADT value:

stackADT twoStacks(stackADT A, B) { … … }

The function returns a new stack that is constructed with all elements of stacks A and B.

In the stack returned, all elements of stack A are put at the lower part, and all elements
of stack B are put at the upper part, while the order of the elements are unchanged.
Meanwhile, it is important that when the function returns, stacks A and B are not altered.

The following diagram shows some examples of the function call.

Stack A Stack B twoStacks(A, B)