（12）假定栈用顺序的方式存储，栈类型 stack定义如下：TYPE stack=RECORDA：ARRAY［l..m0] OF datatype;t：O..m0;END；下面是栈的一种基本运算的实现：PROCEDURE xxxx(VAR s:satack)；BEGINIF s.t＝0THEN print（‘underflow’）ELSE s.t：＝s.t-1；END;请问这是栈的哪一种基本运算？A) 栈的推入B)栈的弹出C）读栈顶元素D)将栈置为空栈

使用VC6打开考生文件夹下的工程test34_3。此工程包含一个test34_3.cpp，其中定义了表示栈的类stack。源程序中stack类的定义并不完整，请按要求完成下列操作，将程序补充完整。

(1)定义类stack的私有数据成员sp和size,它们分别为整型的指针和变量，其中sP指向存放栈的数据元素的数组，size为栈中存放最后一个元素的下标值。请在注释“//**1**”之后添加适当的语句。

(2)完成类stack的构造函数，该函数首先从动态存储空间分配含有100个元素的int型数组，并把该数组的首元素地址赋给指针sp，然后将该数组的所有元素赋值为0，并将size赋值为-1(size等于-1表示栈为空)。请在注释“//**2**”之后添加适当的语句。

(3)完成类stack的成员函数push的定义。该函数将传入的整型参数x压入栈中，即在size小于数组的最大下标情况下， size自加1，再给x赋值。请在注释“//**3**”之后添加适当的语句。

(4)完成类stack的成员函数pop的定义，该函数返回栈顶元素的值，即在size不等于-1的情况下，返回数组中下标为size的元素的值，并将size减1。请在注释“//**4**”之后添加适当的语句。

程序输出结果如下：

the top elem：1

the pop elem：1

the stack is empty

注意：除在指定位置添加语句之外，请不要改动程序中的其他内容。

源程序文件test34_3.cpp清单如下：

include＜iostream.h＞

class stack

{

//** 1 **

public:

stack ( );

bool empty(){return size==-1;}

bool full() {return size==99;}

void push(int x);

void pop();

void top();

};

stack::stack()

{

//** 2 **

for(int i=0; i＜100; i++)

*(sp+i)=0;

size=-1;

}

void stack::push(int x)

{

//** 3 **

cout＜＜"the stack is full"＜＜end1;

else

{

size++;

*(sp+size) = x;

}

}

void stack::pop()

{

//** 4 **

cout＜＜"the stack is empty"＜＜end1;

else

{

cout＜＜"the pop elem:"＜＜*(sp+size)＜＜end1;

size--;

}

}

void stack::top()

{

if iempty() )

cout＜＜"the stack is empty"＜＜end1;

else

{

cout＜＜"the top elem:"＜＜*(sp+size)＜＜end1;

}

}

void main ( )

{

stack s;

s.push(1);

s.top();

s.pop();

s.top()；

}

（ 15 ）请将下列栈类 Stack 补充完整

class Stack{

private:

int pList[100]; // int 数组 , 用于存放栈的元素

int top; // 栈顶元素 ( 数组下标 )

public:

Stack():top(0){}

void Push(const int &item); // 新元素 item 压入栈

int Pop(void); // 将栈顶元素弹出栈

};

void Stack::Push(const int &item){

if(top == 99) // 如果栈满 , 程序终止

exit(1);

top++; // 栈顶指针增 1

___________;

}

int Stack::Pop(){

if(top<0) // 如果栈空 , 程序终止

exit(1);

return pList[top--];

}

栈(Stack)是限定仅在(18)进入插入或删除操作的线性表。对栈来说，表尾端称为(18)；表头端称为(18)。

A．表头 栈顶(top)，栈底(bottom)

B．表头，栈底(bottom)栈顶(top)

C．表尾，栈顶(top)栈底(bottom)

D．表尾，栈底(bottom)栈顶(top)

下面是一个栈类的模板，其中push函数将元素i压入栈顶，pop函数弹出栈顶元素。栈初始为空，top值为0，栈顶元素在stack[top-1]中，在下面横线处填上适当的语句，完成栈类模板的定义。

template＜class t＞

class Tstack

{

enum{size=1000};

T stack[size]

int top;

public:

Tsack():top(0){}

void push(const T&i){

if(top＜size)

stack[top++]=i;

}

T pop()

{

if(top==O)exit(1)；//栈空时终止运行

retum【 】;

}

};

请将下列栈类Stack的横线处补充完整。

class Stack{

private:

int pList[100]; ∥int数组，用于存放栈的元素

int top; ∥栈顶元素(数组下标)

public:

Stack():top(0){}

void Push(const int &item); ∥新元素item

阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明】

栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stock Top)，而另一端称为栈底(Stock Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。

当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示)。

以下C代码采用链式存储结构实现一个整数栈操作。

【C代码】

typedef struct List {

int data； //栈数据

struct List* next； //上次入栈的数据地址

}List；

typedef struct Stack{

List* pTop； //当前栈顶指针

}Stack；

Stack* NewStack() {return (Stack*) calloc(1/sizeof(Stack))；}

int IsEmpty(Stack* S){//判断栈S是否为空栈

if((1))return 1;

return 0;

}

int Top(Stack* s){//获取栈顶数据。若栈为空，则返回机器可表示的最小整数

if(IsEmpty(S))return INT_ MIN；

return (2)；

}

void Push(Stack* S，int theData) {//将数据theData压栈

List* newNode；

newNode=(List*)calloc(1/sizeof (List))；

newNode-＞data=theData；

newNode-＞next=S-＞pTop；

S-＞pTop=(3)；

}

void Pop(Stack* S) {//弹栈

List* lastTop；

if(IsEmpty(S) ) return；

lastTop=S-＞pTop；

S-＞pTop=(4)；

free(lastTop)；

}

define MD(a) a＜＜2

int main(){

int i;

Stack* myStack；

myStack= NewStack()；

Push(myStack，MD(1))；

Push(myStack，MD(2))；

Pop(myStack)；

Push(myStack，MD(3)+1)；

while( !IsEmpty(myStack) ){

printf("%d"，Top(myStack))；

Pop(myStack)；

}

return 0；

}

以上程序运行时的输出结果为:(5)

试题七（共 15 分）

阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。

下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类

STACK,关于栈基本操作的函数原型说明如下：

void InitStack(STACK *s)：初始化栈。

void Push(STACK *s,int e): 将一个整数压栈，栈中元素数目增 1。

void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减 1。

int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

int IsEmpty(STACK s)：若是空栈则返回 1，否则返回 0。

【C 程序】

include<stdio.h>

/*此处为栈类型及其基本操作的定义，省略*/

int main( ){

STACK station;

int state[1000];

int n; /*车厢数*/

int begin, i, j, maxNo; /*maxNo 为 A端正待入栈的车厢编号*/

printf("请输入车厢数： ");

scanf("%d",&n);

printf("请输入需要判断的车厢编号序列（以空格分隔） ： ");

if (n < 1) return -1;

for (i = 0; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */

scanf("%d",&state[i]);

（1） ; /*初始化栈*/

maxNo = 1;

for(i = 0; i < n; ){/*检查输出序列中的每个车厢号 state[i]是否能从栈中获取*/

if ( （2） ){/*当栈不为空时*/

if (state[i] == Top(station)){ /*栈顶车厢号等于被检查车厢号*/

printf("%d ",Top(station));

Pop(&station); i++;

}

else

if ( （3） ){

printf("error\n");

return 1;

}

else {

begin = （4） ;

for(j = begin+1; j<=state[i]; j++) {

Push(&station, j);

}

}

}

else { /*当栈为空时*/

begin = maxNo;

for(j = begin; j<=state[i]; j++){

Push(&station, j);

}

maxNo = （5） ;

}

}

printf("OK");

return 0;

}

阅读以下说明C++代码，将应填入(n)处的字句写在对应栏内。

[说明]

以下程序的功能是实现堆栈的一些基本操作。堆栈类stack共有三个成员函数：empty判断堆栈是否为空；push进行人栈操作；pop进行出栈操作。

[C++程序]

include "stdafx. h"

include ＜iostream, h＞

eonst int maxsize = 6;

class stack {

float data[ maxsize];

int top;

public:

stuck(void);

～ stack(void);

bool empty(void);

void push(float a);

float pop(void);

};

stack: :stack(void)

{ top =0;

cout ＜ ＜ "stack initialized." ＜ ＜ endl;

}

stack:: ～stack(void) {

cout ＜ ＜" stack destoryed." ＜ ＜ endl;

bool stack:: empty (void) {

return (1);

void stack: :push(float a)

if(top= =maxsize) {

cout ＜ ＜ "Stack is full!" ＜ ＜ endl;

return;

data[top] =a;

(2);

}

float stack:: pop (void)

{ if((3)){

cout＜ ＜ "Stack is undcrflow !" ＜ ＜ endl;

return 0;

(4);

return (5);

}

void main( )

{ stack s;

coat ＜ ＜ "now push the data:";

for(inti=l;i< =maxsize;i+ +) {

cout＜ ＜i＜ ＜" ";

s. push(i);

}

coat ＜ ＜ endl;

cout＜ ＜ "now pop the data:";

for(i = 1 ;i ＜ = maxsize ;i + + )

cout＜ ＜s. pop()＜ ＜" ";

}

以下程序实现栈的入栈和出栈的操作。其中有两个类：一个是节点类node,它包含点值和指向上一个节点的指针 prev；另一个类是栈类 stack, 它包含栈的头指针 top。

生成的链式栈如下图所示。

〈IMG nClick=over(this) title=放大 src="tp/jsj/2jc++j28.1.gif"〉

下面是实现程序，请填空完成此程序。

include 〈iostream〉

using namespace std;

class stack;

class node

{

int data;

node *prev;

public:

node(int d, node *n)

{

data=d;

prev=n;

}

friend class stack;

};

class stack

{

node *top; //栈头

public:

stack()

{

top=0;

}

void push(int i)

{

node *n=【 】;

top=n;

}

int pop()

{

node *t=top;

if (top)

{

top=top-〉prev;

int c= t-〉data;

delete t;

return c;

}

return 0;

}

int main ()

{

stack s;

s.push(6);

s.push(3);

s.push (1);

return 0;

}

阅读以下说明和C++程序，将应填入(n)处的字句写在对应栏内。

【说明】

以下程序的功能是设计一个栈类stack＜T＞，并建立一个整数栈。

【程序】

include ＜ iostream. h ＞

include ＜ stdlib. h ＞

const int Max =20; //栈大小

template ＜ class T ＞

class stack{ //栈元素数组

T s[Max]; //栈顶下标

int top;

public:

stack( )

{

top =-1; //栈顶初始化为-1

}

void push( const T &item); //item入栈

T pop( ); //出栈

int stackempty( ) const; //判断栈是否为

};

template ＜ class T ＞

void stack ＜T ＞::push(const T &item)

{

if(top==(1))

{

cout ＜＜"栈满溢出" ＜＜endl;

exit(1);

}

top ++

s[top] = item;

}

template ＜ class T ＞

T stack＜T＞ ::pop()

{

T temp;

if(top==(2))

{

cout ＜＜"栈为空，不能出栈操作" ＜ ＜ endl;

exit(1);

}

temp =s[top];

top --;

return temp;

}

template ＜ class T ＞

int stack ＜ T ＞:: stackempty( ) const

{ return top == -1;

{

void main( )

{

stack ＜int＞ st;

int a[] ={1,2,3,4,5};

cout ＜＜"整数栈" ＜＜endl;

cout ＜＜"入栈序列:" ＜＜endl;

for(int i=0;i＜4;i ++)

{

cout ＜＜a[i] ＜＜" ";

(3);

}

cout ＜＜ endl ＜＜"出栈序列";

while((4))

tout＜＜(5)＜＜" ";

cout＜ ＜ endl;

}

假定栈用顺序的方式存储，栈类型stack定义如下：

TYPE stack=RECORD

A: ARRAY[1..M0OF datatype;

t:0..M0;

END;

下面是栈的一种基本运算的实现：

PROCEDURE xxxx(VAR s:stack)

BEGIN

IF s.t=0

THEN print('underflow')

ELSE s.t:=s.t-1;

END;

请问这是栈的哪种基本运算?( )。

A) 栈的推入

B) 栈的弹出

C) 读栈顶元素

D) 将栈置为空栈

A．

B．

C．

D．

使用VC6打开考生文件夹下的工程MyProj8。此工程包含一个源程序文件MyMain8.cpp，该程序实现栈的入栈和出栈的操作。其中有两个类：一个是节点类node，它包含节点值和指向上一个节点的指针prey；另一个类是栈类stack，它包含栈的头指针top。但类的定义并不完整。

请按要求完成下列操作，将类Sample的定义补充完成：

①定义私有节点值data，它是血型的数据，以及定义一个指向上一个节点的指针prev。请在注释“//* *1* *”之后添加适当的语句。

②完成构造函数node(int d,node*n)的定义，使得私有成员data和prev分别初始化为d和n。请在注释“//* *2* *”之后添加适当的语句。

③完成类stack的成员函数push(int i)的类体内的定义。函数push()实现入栈这个操作，即把形参i压入栈中，那么此时应该创建一个新的节点，并让这个节点的prev指针指向栈顶。请在注释“//* *3 * *”之后添加适当的语句。

注意：除在指定位置添加语句之外，请不要改动程序中的其他内容。

源程序文件MyMain8.cpp清单如下：

//MyMain 8.cpp

include ＜iostream＞

using namespace std;

class stack;

class node

{

private:

//* * 1 * *

public:

node(int d, node *n)

{

//* * 2 * *

}

friend class stack;

};

class stack

{

node *top; //栈头

public:

stack()

{

top=0;

}

void push(int i)

{

//* * 3 * *

}

int pop()

{

node*t=top；

if(top)

{

top=top-＞prev；

int c=t-＞data；

delete t；

return c；

}

return 0；

}

}；

int main()

{

stack s；

s.push(6)；

s.push(3)；

s.push(1)；

return 0；

}

The line of computing jobs waiting to be run might be a （ ） . These job requests are serviced in order of their arrival.

A. array B. queue C. record D. stack