return OK; }/*listDelete*/
答案：(1)p->next!=NULL (2)p->next=q->next 4、写出算法的功能。
int func(LinkList L){ LinkList p=L; int n=0; while(p!=NULL) { p=p->next; n++; } return(n); }
答案：求单链表head的长度
第三章 栈和队列
一、选择题
1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。
A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a
2、判断一个循环队列Q（最多n个元素）为满的条件是（ ）。
A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 3、设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
A. 顺序表 B. 链表 C. 队列 D. 栈 5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ ）。
A. 1243 B. 2134 C. 1432 D. 4312 E. 3214
6、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
A. 1和5 B. 2和4 C. 4和2 D. 5和1 7、队列的插入操作是在（ ）。
A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后 9、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ ）。
A. *S->top=e;S->top++; B. S->top++;*S->top=e; C. *S->top=e D. S->top=e; 10、表达式a*(b+c)-d的后缀表达式是（ ）。
A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、将递归算法转换成对应的非递归算法时，通常需要使用（ ）来保存中间结果。
A. 队列 B. 栈 C. 链表 D. 树 12、栈的插入和删除操作在（ ）。 A. 栈底 B. 栈顶 C. 任意位置 D. 指定位置 13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（ ）的编组。 A. 3，4，5，1，2 B. 2，4，1，3，5
C. 3，5，4，2，1 D. 1，3，5，2，4 14、判定一个顺序栈S（栈空间大小为n）为空的条件是（ ）。
A. S->top==0 B. S->top!=0 C. S->top==n D. S->top!=n
15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
6
A. front=front->next B. s->next=rear;rear=s C. rear->next=s;rear=s; D. s->next=front;front=s; 16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。 A. 1，2，3，4 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，2
17、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。
A. a B. b C. c D. d
18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（ ）。
A. top不变 B. top=0 C. top=top+1 D. top=top-1 19、判断一个循环队列Q（空间大小为M）为空的条件是（ ）。
A. Q->front==Q->rear B. Q->rear-Q->front-1==M C. Q->front+1=Q->rear D. Q->rear+1=Q->front 21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（ ）。
A. N B. N+1 C. N-1 D. N-2 22、队列的删除操作是在（ ）。
A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后 23、若让元素1，2，3依次进栈，则出栈次序不可能是（ ）。
A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2
24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ ）。 A. (rear-front+m)%m B. rear-front+1
C. rear-front-1 D. rear-front
25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。
A. 堆栈 B. 队列 C. 数组 D. 线性表 26、栈和队列都是（ ）。
A. 链式存储的线性结构 B. 链式存储的非线性结构 C. 限制插入删除位置的线性结构 D. 限制存取点的非线性结构
27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（ ）。
A. front=front->next B. rear= rear->next C. rear->next=front D. front->next=rear 28、队和栈的主要区别是（ ）。
A. 逻辑结构不同 B. 存储结构不同 C. 所包含的运算个数不同 D. 限定插入和删除的位置不同
二、填空题
1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。 答案：3
2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为： 。 答案：(rear-front+M)%M
3、在具有n个元素的循环队列中，队满时具有 个元素。 答案：n-1
4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为 。 答案：61
5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的
7
当前的长度为_______。 答案：15
三、判断题
1、栈和队列都是受限的线性结构。?
3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。?
四、程序分析填空题
1、已知栈的基本操作函数： int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack *S,ElemType e);//入栈 int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数，请将函数补充完整。
void conversion(){ InitStack(S); scanf(“%d”,&N); while(N){ （1） ; N=N/8;
}
while( （2） ){ Pop(S,&e); printf(“%d”,e); }
}//conversion 答案：（1）Push(S,N%8) （2）!StackEmpty(S)
2、写出算法的功能。
int function(SqQueue *Q,ElemType *e){ if(Q->front==Q->rear) return ERROR; *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return OK; }
答案：出队。删除顺序队列Q的队头元素，并将被删元素保存至形参e
第四章 串
一、选择题
1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ C ）。
A. 连接 B. 求子串 C. 模式匹配 2、串与普通的线性表相比较，它的特殊性体现在（ C ）。
A. 顺序的存储结构 B. 链式存储结构 C. 数据元素是一个字符 D. 数据元素任意 3、空串和空格串（ B ）。
D. 判断子串
8
A. 相同 B. 不相同 C. 可能相同 D. 无法确定
4、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B ）。
A. ?ijing? B. ?jing&? C. ?ingNa? D. ?ing&N?
第五章 数组和广义表
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3 2、广义表((a),a)的表尾是（ B ）。
A. a B. (a) C. () D. ((a)) 3、稀疏矩阵的常见压缩存储方法有（ C ）两种。
A. 二维数组和三维数组 B. 三元组和散列表 C. 三元组和十字链表 D. 散列表和十字链表 4、一个非空广义表中的数据元素（ D ）。
A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子 6、广义表G=(a, (b,c,d,(e,f)),g)的长度是（ A ）。 A. 3 B. 4 C. 7 D. 8
7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。
A. 正确 B. 错误 C. 无法确定 D. 以上均不对 8、广义表(a,b,c)的表尾是（ B ）。
A. b,c B. (b,c) C. c D. (c) 9、常对数组进行两种基本操作是（ C ）。
A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。
A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销
11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11 为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B ）。
A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 13、广义表A=((a),a)的表头是（ B ）。
A. a B. (a) C. b D. ((a)) 14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。
?0?8060??0?8060?????7000070003????A. ? B. ??50400? 00000???????50400??00000?????
9
?0?8060??0?8060?????0000370000????C. ? D. ??50403? 70000???????50400??00000?????16、以下有关广义表的表述中，正确的是（ A ）。
A. 由0个或多个原子或子表构成的有限序列 B. 至少有一个元素是子表 C. 不能递归定义 D. 不能为空表
17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（ ）。
A. d B. e C. (e) D. （e,f）
二、判断题
（错 ）1、广义表中原子个数即为广义表的长度。
（错）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。
（错）3、广义表的长度是指广义表中括号嵌套的层数。 （√）4、广义表的深度是指广义表中括号嵌套的层数。
（√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。
三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。 3、稀疏矩阵的压缩存储方式有： 三元组 和 十字链表 。
四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
?0?1??0??0i1123340?000?? 210??0?20?j231233v31121-231答案：
10