p=p->next; }
q->next=0; }
(A) 计算单链表L的长度
(B) 查找单链表L中倒数第k个结点 (C) 删除单链表L中最后面的k个结点 (D) 将单链表L中第k个结点q的指针置0
只遍历一次的高效算法 （排除法） B
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) (B) O(n) (C) O(m) (D) O(min(n，m)) A
首先取一个指针p指向la的第一个节点（不包括头节点，头节点是空），然后让la头指针指向lb的第二个节点，接着用lb的第一个节点填充lb的头节点，最后将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出栈） 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);
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 ? %c\\n\ else {
F(n-1, x, z, y);
printf(\ %c ? %c\\n\ F(n-1, y, x, z); } }
自己去计算，类似汉诺塔 1 A->C 2 A->B 1 C->B 3 A->C 1 B->A 2 B->C 1 A->C
2-17 已知一维数组B[0..20]用于存储一个下三角矩阵A元素。设A中第一个元素的下标为1，1，则数组元素B[10]对应A中下标为( )的元素。
(A) 2，5 (B) 4，3 (C) 5，1 (D) 6，1 C
因此B中第10个元素，也就是B[9]对应A[4][4]
[B[10]对应A中是A[5][1]
2-18 已知An?n为稀疏矩阵。试从时间和空间角度比较，采用二维数组和三元组顺序表两种存储结构计算∑aij的优缺点。
稀疏矩阵为n行n列.
1) 采用二维数组存储，其空间复杂度为Ｏ(n×n)；因为要将所有的矩阵元素累加起来，所
以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(n×n)。
2) 采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，
将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << n×n时，采用三元组顺序表存储可获得较好的时、空性能。
2-19 链地址法是Hash表的一种处理冲突的方法，它是将所有哈希地址相同的数据元素都存放在同一个链表中。关于链地址法的叙述，不正确的是( )。
(A) 平均查找长度较短 pptP165上面有表述
(B) 相关查找算法易于实现 查找的时候只需找到哈希地址的那条链，再顺着那条链
遍历下去就可以实现。
(C) 链表的个数不能少于数据元素的个数 可以少于，很明显 (D) 更适合于构造表前无法确定表长的情况 链表的特点之一‘
C
2-20 设哈希(Hash)函数H(k)=(3k)，用线性探测再散列法处理冲突，di=i。已知为关键字序列22，41，53，46，30，13，01，67构造哈希表如下： 哈希地址 0 1 2 3 4 5 6 7 8 9 10 关键字 22 41 30 01 53 46 13 67
则在等概率情况下查找成功时的平均查找长度是( )。
(A) 2 (B) 24/11 (C) 3 (D) 3.5 有公式 ASL=1/2(1+1/(1-a)) = 1/2(1+1/(1+11/3))=7/3 其中a = 8/11（实际填入的数量/线性表的大小） 2-21 有100个不同的关键字拟存放在哈希表L中。处理冲突的方法为线性探测再散列法，其平均查找长度为
。试计算L的长度(一个素数)，要求在等概
率情况下，查找成功时的平均查找长度不超过3。
素数表：101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167。
设线性表L长度ln,有:
α=100/ln<=0.8 求出 ln>=125,即由题意选择127这个素数
习题3 树
3-1 若深度为5的完全二叉树第5层有3个叶子结点，则该二叉树一共有( )个结点。
(A) 8 (B) 13 (C) 15 (D) 18 D
利用公式 前四层有2^5-1 = 15个节点，总共为15+3=18个。
3-2 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )。
(A) 5 (B) 6 (C) 7 (D) 8
一共有1*4+2*2+3+4=15个度，4+2+1+1=8个节点
叶子为15-8+1=8
解析：节点数=度数+1
此题也可用画图法（图略）
3-3 已知二叉树T中有50个叶子结点，试计算T的总结点数的最小值。
由于是二叉树，那么可知欲使节点数最小，则该二叉树需满足至多存在一个结点的入度为1（即——使每两个结点都有一个父节点）。50/2=25, （25-1）/2=12 12/2=6 6/2=3 (3+1)/2=2 2/2=1 红色部分+1为之前25个结点归根时剩下的1个。 那么总共有50+25+12+6+3+2+1=99个结点
节点数/2+1 =叶子数
3-4 已知一棵度为k的树中，有n1个度为1的结点，n2个度为2的结点，?，nk个度为k的结点。试计算该树的叶子结点数。
解析：节点数=度数+1