对应的算法如下：
voiddelsame（SqList&L）j]中所有元素都不相同
{j++;
[j]=[i];
}
}
=j+1;0]，置e=[0]，用i从1开始遍历L的所有元素：
当[i]≠e时，将它放在[k]中，k增1，置e=[i]，最后将L的length置为k。
对应的算法如下：
voiddelsame1（SqList&L）单项选择题
（1）栈中元素的进出原则是（）。
A.先进先出B.后进先出C.栈空则进D.栈满则出
答：
B
（2）设一个栈的进栈序列是A、B、C、D（即元素A～D依次通过该栈），则借助该栈所得到的输出序列不可能是（）。
B,C,D,C,B,A,C,D,B,A,B,C
答：
D
（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。
答：
C
（4）已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n）则第j（1≤j≤n）个出栈元素是（）。
+1D.不确定
答：
D
（5）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（）。
答：
A
（6）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈满的条件是。
答：
D
（7）队列中元素的进出原则是（）。
A.先进先出B.后进先出C.栈空则进D.栈满则出
答：
A
（8）元素A、B、C、D顺序连续进入队列qu后，队头元素是（①），队尾元素是（②）。
答：
①A②D。
（9）一个队列的入列序列为1234，则队列可能的输出序列是（）。
答：
B
（10）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队满条件是（）。
A.+1）%MaxSize==+1）%MaxSize
B.+1）%MaxSize==+1
C.+1）%MaxSize==
答：
C
（11）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队空条件是（）。
A.+1）%MaxSize==+1）%MaxSize
B.+1）%MaxSize==+1
C.+1）%MaxSize==
答：
D
（12）设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r（队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（）。
C.（r-f）％N+1D.（r-f+N）％N
答：
D
（13）设有4个数据元素a、b、c和d，对其分别进行栈操作或队操作。
在进栈或进队操作时，按a、b、c、d次序每次进入一个元素。
假设栈或队的初始状态都是空。
现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（①），第二次出栈得到的元素是（②）；类似地，考虑对这4个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（③），第二次出队得到的元素是（④）。
经操作后，最后在栈中或队中的元素还有（⑤）个。
①～④：
⑤：
答：
①B②D③A④B⑤B
（14）设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。
答：
C
2.填空题
（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（①）。
不允许插入和删除运算的一端称为（②）。
答：
①栈顶②栈底
（2）一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为（）。
答：
1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。
（3）有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有（）。
答：
CDBAE、CDEBA、CDBEA。
（4）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（）。
答：
data[top]=x;top++;
（5）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（）。
答：
top--;x=data[top];
（6）（）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
答：
队列
（7）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（）。
答：
rear=（rear+1）%（m+1）;A[rear]=x;
（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操作是（）。
答：
front=（front+1）%（m+1）;x=A[rear];
3.简答题
（1）简要说明线性表、栈与队的异同点。
答：
相同点：
都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：
①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
②用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。
（2）顺序队的“假溢出”是怎样产生的？
如何知道循环队列是空还是满？
答：
一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决循环队列是空还是满的办法如下：
①设置一个布尔变量以区别队满还是队空；
②浪费一个元素的空间，用于区别队满还是队空。
③使用一个计数器记录队列中元素个数（即队列长度）。
通常采用法②，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置，这样判断循环队列队空标志是：
front=rear，队满标志是：
（rear+1）%MaxSize=front。
4.算法设计题
（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。
这里只能使用栈st的基本运算来完成，不能直接用[0]来得到栈底元素。
解：
假定采用顺序栈结构。
先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。
对应算法如下：
intGetBottom（SqStackst,ElemType&x）
{ElemTypee;
SqStacktmpst;
单项选择题
（1）串是一种特殊的线性表，其特殊性体现在（）。
A.可以顺序存储B.数据元素是一个字符
C.可以链式存储D.数据元素可以是多个字符
答：
B
（2）以下（）是"abcd321ABCD"串的子串。
A.abcdC."abcABC"D."21AB"
答：
D
（3）两个串相等必有串长度相等且（）。
A.串的各位置字符任意B.串中各对应位置字符均相等
C.两个串含有相同的字符D.两个所含字符任意
答：
B
2.填空题
（1）空串是指（①），空白串是指（②）。
答：
①不包含任何字符（长度为0）的串②由一个或多个空格（仅由空格符）组成的串
（2）对于带头结点的链串s，串为空的条件是（）。
答：
s->next==NULL。
（3）对于一个含有n个字符的链串s，查找第i个元素的算法的时间复杂度为（）。
答：
O（n）
3.简答题
（1）设s为一个长度为n的串，其中的字符各不相同，则s中的互异的非平凡子串（非空且不同于s本身）的个数是多少？
答：
由串s的特性可知，1个字符的子串有n个，2个字符的子串有n-1个，3个字符的子串有n-2个，…，n-2个字符的子串有3个，n-1个字符的子串有2个。
所以，非平凡子串的个数=n+（n-1）+（n-2）+…+2=
。
（2）若s1和s2为串，给出使s1算法设计题
（1）设计一个算法RepChar（s,x,y），将顺序串s中所有字符x替换成字符y。
要求空间复杂度为O
（1）。
解：
因要求算法空间复杂度为O
（1），所以只能对串s直接替换。
从头开始遍历串s，一旦找到字符x便将其替换成y。
对应算法如下：
voidRepStr（SqString&s,charx,chary）
{inti;
for（i=0;i<;i++）
if[i]==x）
[i]=y;
}
（2）设计一个算法，判断链串s中所有元素是否为递增排列的。
解：
用p和q指向链串s的两个连续结点，p先指向开始结点，当q->data≥p->data时，p和q同步后移一个结点；否则返回0。
当所有元素是递增排列时返回1。
对应算法如下：
intincrease（LinkString*s）
{LinkString*p=s->next,*q;
if（p!
=NULL）
{while（p->next!
=NULL）
{q=p->next;单项选择题
（1）假设有60行70列的二维数组a[1..60,1..70]（数组下标从1开始）以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。
D.以上都不对
答：
A
（2）对特殊矩阵采用压缩存储的目的主要是为了（）。
A.表达变得简单B.对矩阵元素的存取变得简单
C.去掉矩阵中的多余元素D.减少不必要的存储空间
答：
D
（3）一个n×n的对称矩阵，如果采用压缩存储以行或列为主序放入内存，则压缩存储的容量是（）。
A.n2B.n2/2C.n（n+1）/2D.（n+1）2/2
答：
C
（4）设矩阵a是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组b[1..n（n-1）/2]中（数组下标均从1开始），对下三角部分中任一元素ai,j（i≤j）在一维数组b中下标k的值是（）。
（i
升级会员 