《计算机软件技术基础》课后题答案 - 图文(7)

a3，a2，a1

4．和顺序栈相比，链栈有一个比较明显的优势是( )。

*A．通常不会出现栈满的情况 B．通常不会出现栈空的情况 C．插入操作更容易实现 D．删除操作更容易实现

5．若一个栈的输入序列是1，2，3，4，?，n，输出序列的第一个元素是n，则第i个输出元素是( )。

A．不确定 B．n-i *C．n-i+1 D．n-i-1 6．以下说法正确的是( )。

*A．因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 B．因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 C．对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢” D．对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”

7．顺序队列的入队操作应为( sq.rear初值为-1 )。

*A．sq.rear=sq.rear+1；sq.data[sq.rear]=x; B．sq.data[sq.rear]=x；sq.rear=sq.rear+1； C．sq.rear=(sq.rear+1)％maxsize；sq.data[sq.rear+1]=x;

D

．

sq.data[sq.rear]=x

；

sq.rear=x;

sq.rear=(sq.rear+1)％maxslze；

8．循环队列的入队操作应为(sq.rear初值为-1 )。

A．sq．rear=sq．rear+1；sq．data[sq．rear]=x B．sq．data[sq．rear]=x；sq．rear=sq．rear+l； *C．sq．rear=(sq．rear+1)％maxsize；

31

sq．data[sq．rear]=x； D．sq．data[sq．rear]=x；sq．rear=(sq．rear+1)％maxsize；

9．顺序队列的出队操作为(sq. front初值为-1 )。

A．sq．front=(sq．front+1)％maxsize； *B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+1; 10．循环队列的出队操作为(sq. front初值为-1 )。

*A．sq．front=(sq．front+1)％maxsize； B．sq．front=sq．front+1； C．sq．rear=(sq．rear+1)％maxsize； D．sq．rear=sq．rear+l； 11．循环队列的队满条件为( )。

A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； *C．(sq．rear+1)％maxsize==sq．front； D．sq．rear==sq．front； 12．循环队列的队空条件为( )。

A．(sq．rear+1)％maxsize==(sq．front+1)％maxsize； B．(sq．rear+1)％maxsize==sq．front+1； C．(sq．rear+1)％maxsize==sq．front； *D．sq．rear==sq．front；

13．如果以链表作为栈的存储结构，则出栈操作时( )。

A．必须判别栈是否满 B．判别栈元素的类型 *C．必须判别栈是否空 D．对栈不做任何判别

14，向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )。

A．Top->next=s； B．s->next=Top->next；Top->next=s； *C．s->next=Top；Top=s； D．s->next=Top；Top=Top->next；

15．从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中，其操作步骤为( )。

32

*A．x=Top->data；Top=Top->next； B．Top=Top->next；x=Top->data； C．x=Top；Top=Top->next； D．x=Top->data；

16．在一个链队中，苕f、r分别为队头、队尾指针，则插入s所指结点的操作为( )。

A．f->next=s；f=s； *B．r->next=s；r=s； C．s->next=r；r=s； D．s->next=f；f=s；

17．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。 A．e，d，c，b，a B．d，e，c，b，a *C．d，c，e，a，b D．a，b，c，d，e

18．一个队列的入队序列是1，2，3，4，则队列可能的输出序列是( )。 A．4，3，2，1 *B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 19．设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。

A．线性表的顺序存储结构 *B．栈 C．队列 D．线性表的链式存储结构 二、判断题

√1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。 ╳2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。

╳3．若一个栈的输入序列为1，2，3，?，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1，2，?，n)。 √4．在链队中，即使不设置尾指针也能进行入队操作。

√5．在对链队(带头指针)做出队操作时，不会改变front指针的值。 ╳6．循环队列中元素个数为rear-front。

╳7．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2．

33

√8．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。 ╳9．若以链表作为栈的存储结构，则入栈需要判断栈是否满． √10．若以链表作为栈的存储结构，则出栈需要判断栈是否空。 三、填空题

1．向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是__ s->next=Top；Top =s；__。

2．从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ x=Top->data；Top=Top->next；__。

3．在具有n个单元的循环队列中，队满时共有___n-1_个元素。

4．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为__ b，c，e，d，a ___。 5．设有数组A[m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是_rear=（rear +1）％（m+1）； A[rear]=x;__。 6．在一个链队中，如果f、r分别为队头、队尾指针，则插入s所指结点的操作是_r->next=s; r=s;___。

7．栈的逻辑特点是__后进先出____，队列的逻辑特点是_先进先出__，二者的共同特点是_操作受限__。

8．___栈___可以作为实现递归函数调用的一种数据结构。 9．在队列中，新插入的结点只能添加到__队尾__。

10．链队在一定范围内不会出现__队满___的情况。当lq．front==lq．rear时，队中无元素，此时___队空__。

11．设一个链栈的栈顶指针为ls，栈中结点的格式为data:next，栈空的条件是_ ls = NULL__；如果栈不为空，则出栈操作为p=ls; ___ ls = ls ->next __；free(p)。

34

12．对带有头结点的链队lq，判定队列中只有一个数据元素的条件是__lq->front->next= lq->rear___。

13．设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push后，栈顶指针所指元素是__4__。

14．设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__加1___，从栈中弹出一个元素时，变量t的值___减1___。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c__。 四、应用题

2．设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符入栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。

答：XSXXXSSSXXSXXSXXSSSS

3．设有一个输入序列a，b，c，d，元素经过一个栈到 …… 此处隐藏：2238字，全部文档内容请下载后查看。喜欢就下载吧 ……