20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是____top-1< maxsize 。

21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句___ x=sq[top]; top=top-1___。

22．栈的特性是___先进后出___。

23．对栈进行退栈时的操作是先移动___栈顶指针_，后 取出元素 。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是_ top==max+1。

25．设链栈的栈顶指针为top（有头结点），则栈非空的条件是__top->next!=NULL__。 26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为_(n+r-f）%n__。

27．在一个循环队列中，队首指针指向 队首元素。 28．队列中允许进行删除的一端称为___队头_。

29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第__n_个元素。

30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_lq.Front==lq.Rear_。

31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动___队头指针___。 32．队列中允许进行插入的一端称为_队尾__。 三、判断题

1．栈和队列都是限制存取点的线性结构。（ √） 2．不同的人栈和出栈组合可能得到相同输出序列。（ × ） 3．消除递归一定要用栈。（ × ） 4．循环队列是顺序存储结构。（ √ ） 5．循环队列不会产生溢出。（ × ） 6．循环队列满的时候rear= =front。（ × ）

7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（√） 四、综合题

1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。 A、B、C、D A、B、D、C A、C、B、D A、C、D、B A、D、C、B B、A、C、D B、A、D、C B、C、A、D B、C、D、A B、D、C、A C、B、A、D C、B、D、A C、D、B、A D、C、B、A

2．输入n个10以内的数，每输入k（0＜=k＜=9），就把它插人到第k号队列中。最后

13

把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。

3．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下：

(l) 初始化队列 initqueue (Q)：建立一个新的空队列 Q。 (2) 人队列enqueue (Q，x)：将元素 x插人到队列 Q中。 (3) 出队列delqueue (Q)：从队列Q中退出一个元素。 (4) 取队首元素getL (Q)：返回当前队首元素。 (5) 判断队列是否为空：emptyqueue (Q)。 (6) 显示队列中元素：dispqueue (Q)。 4．“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃”的时候表示结束。请用栈和队列编写一个算法判断一个字符串是否回文。

5．假设表达式中有三种括号：圆括号“（）”、方括号“[ ]”和花括号“{ }”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。

6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。

7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。

8．写出汉诺塔问题的递归和非递归算法。

汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、?、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子：

(1) 每次只能移动柱子最上面的一个圆盘。 (2) 任何圆盘都不能放在比它小的圆盘之上。 (3) 圆盘只能在X、Y和Z三根柱子之上放置。

9．假设CQ[0…10]是一个环形队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 (1) d,e,b,g,h入队 (2)d,e出队 (3)i,j,k,l,m入队 (4)b出队 (5) n,o,p入队

14

习题四

一、选择项

l．空串与空格串（B）。

A．相同 B．不相同 C．可能相同 D．无法确定

2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ C ）。 A．连接 B．求子串 C．模式匹配 D．判子串

3．串与普通的线性表相比较，它的特殊性体现在（C）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（ B ）。 (n *（n+1）/2+1) A．36 B．37 C．8 D．9 二、境空题

1．串是由零个或多个字符组成的__有限序列_。通常记作：s＝“c1，c2，?，cn”(n=>0)，其中，S称为__串名_；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是_串值_．即串S的内容。

2．串中字符的个数称为串的__长度__。

3．不含有任何字符的串称为__空串_，它的长度为___零__。

4．由一个或多个空格构成的串称为__空格串__，它的长度为__空格的个数__。 5．串中任意多个连续字符组成的子序列称为该串的__子串__；包含_子串__的串称为主串。

6．字符在序列中的序号称为该字符在串中的__位置_。 7．两个字符串相等是指两个字符串的 值相等 ，也就是说这两个字符串不仅_长度相等_，而且对应位置上的字符也 相等 。

8．两个串的比较实际上是__ ASCII码_的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现__ ASCII码__大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为__较大者__。

9．串的__顺序存储__就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种___紧缩式存储结构__。

11．串的__非紧缩式存储结构__是以存储单元为存储单位，一个存储单元中只存放__一个字符_。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放___一个字符__。

12．串在非紧缩方式下，串长度的存储是隐式的，__串所占用的存储单元的个数_即串的长度。

13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放__一个字符_的分配方式，这种方式就是一种_单字节存储方式_。这种方式一般不需要存放__串长_的存储单元，而需要以程序中各变量值所 不包含 的字符为结束符。 14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：_ 数据 _域和___指针_域。其中___数据__域用于存放数据，__指针_域用于存放下一个结点的指针。

15．子串定位StrIndex (s，t)，也称为_模式匹配__，是返回串t在s主串中的位置。 三、判断回

1．子串是主串中字符构成的有限序列。（ × ）

2．KMP算法的最大特点是指示主串的指针不需要回溯。（ √ ）

15

3．串中的元素只能是字符。（ √ ）

4．串中的元素只可能是字母。（ × ） 5．串是一种特殊的线性表。（ √ ） 6．串中可以包含有空白字符。（ √ ） 7．串的长度不能为零。（ × ） 8．两个串相等必有串长度相同。（ √ ） 9．两个串相等则各位置上字符必须对应相等。（ √ ） 四、综合题

l．编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： ＃define MAXSIZE 81 struct string{

int len；

char ch［MAXSIZE］； ｝stringtype；

2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。

3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。

4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。

16