内容发布更新时间 : 2025/6/20 8:29:30星期一 下面是文章的全部内容请认真阅读。
8 顺序栈
选择题
（1） 在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为
栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A．不变 B．top=0 C．top-1 D．top=top+1
（2） 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满
时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。 A．S1的栈底位置为0，S2的栈底位置为n-1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为0，S2的栈底位置为n D．S1的栈底位置为0，S2的栈底位置为1
（3） 为了增加内存空间的利用率和减少溢出的可能性，两个栈共享一片连续的内存
空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当（ ）时才产生上溢。
A．两个栈的栈顶同时到达栈空间的中心点 B．其中一个栈的栈顶到达栈空间的中心点 C．两个栈的栈顶在栈空间的某一位置相遇
D．两个栈均不空，且一个栈的栈顶到达另一个栈的栈底
（4） 两个栈共享一个数组空间的好处是（ ）。 A．减少存取时间，降低发生上溢的可能性 B．节省存储空间，降低发生上溢的可能性 C．减少存取时间，降低发生下溢的可能性 D．节省存储空间，降低发生下溢的可能性
算法设计题
（5） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出
栈的操作序列可表示为仅有I和O组成的序列，称可以操作的序列为合法序列，否则称为非合法序列。
①下面所示的序列中哪些是合法的？
②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
（6） 下面的算法将一个整数e压入到堆栈S，请在空格处填上适当的语句实现该操
作。
Typedef struct { int *base; int top; int stacksize; }SqStack;
21
int Push(SqStack S,int e) { if ( ① ) { S.base=(int *)realloc(S.base,(S.stacksize+1)*sizeof(int));
if ( ② ) { printf (“Not Enough Memory!\\n”); retuan 0; }
S.top= ③ ; S.stacksize= ④ ; }
⑤ ; retuan 1; } 22
9 链栈
选择题
（1） 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行
（ ）。 A．h->next=s; B．s->next=h; C．s->next=h; h->next=s; D．s->next=h->next; h->next=s;
（2） 从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行
（ ）。
A．x=top; top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．x=top->data; top=top->next;
23
10 队列的基本概念
选择题