.
2-10 设链表L不带头结点，试分析算法的功能。 A(Linklist &L) {
if (L && L->next) {
Q=L; L=L->next; P=L;
while (P->next) P=P->next; P->next=Q; Q->next=NULL;
}
} //A算法结束
将链表的第一个结点接到最后一个结点后面
2-11 设两个循环链表的长度分别为n和m，则将这两个循环链表连接成一个循环链表，最好的时间复杂度为( )。
(A) O(1) m)) A
首先取一个指针p指向la的第一个节点（不包括头节点，头节点是空），然后让la头指针指向lb的第二个节点，接着用lb的第一个节点填充lb的头节点，最
Word 资料
(B) O(n) (C) O(m) (D) O(min(n，
.
后将la头节点next指向p 如下图：
还是不明白请自己看ppt第二章P65
2-12 设有6个数据元素A，B，C，D，E，F依次进栈。如果6个数据元素的出栈顺序为B，C，D，F，E，A，则该栈的最小容量为( )。
(A) 2
(B) 3
(C) 4
(D) 5
B 操作 栈元素 A，B入栈 A,B B出栈 A C入栈 A,C C出栈 A D入栈 A,D D出栈 A E,F入栈 A,E,F F出栈 A,E E出栈 A A出栈 因此栈的最小容量只需3
出栈顺序
B B,C
B,C,D
B,C,D,F B,C,D,F,E B,C,D,F,E,A
2-13 设进栈序列为123，试给出所有可能的出栈序列。 所有可能的出栈序列为：
1,2,3 （1入栈，1出栈，2入栈，2出栈，3入栈，3出栈）
Word 资料
.
1,3,2 （1入栈，1出栈，2,3,入栈，3出栈，2出栈） 2,1,3 （1,2入栈，2出栈，1出栈，3入栈，3出栈） 2,3,1 （1,2入栈，2出栈，3入栈，3出栈，1出栈） 3,2,1 （1,2,3入栈，3出栈，2出栈，1出栈）
注意：唯一只有3,1,2不可能出现，因为3要先出栈，前面1,2,3要按顺序一起入栈，因此不可能出现1在2的前面，后面的题目也是一样。 原则就是只要后入栈的先出栈，那么这个元素前面入栈的元素一定按照入栈顺序的反序排列
2-14 如果进栈序列为123456，能否得到出栈序列435612和135426? 435612 不能得到 6的后面不可能出现1,2的出栈顺序 135426 能够得到
2-15 简述算法的功能(设数据元素类型为int)： void proc(LinkQueue *Q) {
LinkStack S; InitStack(S);
while(!EmptyQueue(Q) ) {
DeleteQueue(Q, d); Push(S,d); }
while(!EmptyStack(S) ) {
Pop(S, d);
Word 资料
.
InsertQueue(Q, d); } }
将链队列中的顺序倒过来
如原来ABCDEF，执行完这个算法之后是FEDCBA 2-16 按照格式要求给出调用F(3,'A','B','C')的运行结果： void F(int n, char x, char y, char z) {
if (n==1) printf(\ %c else {
F(n-1, x, z, y); printf(\ %c F(n-1, y, x, z); } }
自己去计算，类似汉诺塔 1 A->C 2 A->B 1 C->B 3 A->C 1 B->A
%c\\n\
%c\\n\
Word 资料
.
2 B->C 1 A->C
2-17 已知一维数组B[0..20]用于存储一个下三角矩阵A元素。设A中第一个元素的下标为1，1，则数组元素B[10]对应A中下标为( )的元素。
(A) 2，5 C
(B) 4，3
(C) 5，1
(D) 6，1
因此B中第10个元素，也就是B[9]对应A[4][4]
[B[10]对应A中是A[5][1]
2-18 已知Ann为稀疏矩阵。试从时间和空间角度比较，采用二维数组和三元
组顺序表两种存储结构计算∑aij的优缺点。
稀疏矩阵为n行n列.
1) 采用二维数组存储，其空间复杂度为Ｏ(n×n)；因为要将所有的矩阵元素累加起来，所
以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(n×n)。
2) 采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，
将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << n×n时，采用三元组顺序表存储可获得较好的时、空性能。
2-19 链地址法是Hash表的一种处理冲突的方法，它是将所有哈希地址相同的数据元素都存放在同一个链表中。关于链地址法的叙述，不正确的是( )。
(A) 平均查找长度较短 pptP165上面有表述
(B) 相关查找算法易于实现 查找的时候只需找到哈希地址的那条链，再顺着那条链
遍历下去就可以实现。
(C) 链表的个数不能少于数据元素的个数 可以少于，很明显 (D) 更适合于构造表前无法确定表长的情况 链表的特点之一‘
Word 资料
厦门大学数据结构与算法(陈海山)期末习题答案解析
