[答案]
void delete(sqlist A)
{int i,j;
i=0;
while(i<=A.last-1)
if(A.data[i]!=A.data[i+1])
i++;
else
{for(j=(i+2);j<=A.last;j++)
A.data[j-1]=A.data[j];
A.last--;
}
}
三.栈、队列和数组
1.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是( )。
[分析]s1,s2进栈后，此时栈中有2个元素，接着s2出栈，栈中尚有一个元素；s3,s4进栈后，此时栈中有3个元素，接着s4,s3出栈，栈中尚有一个元素；s5,s6进栈后，此时栈中有3个元素，接着s6,s5出栈，栈中尚有一个元素；s1出栈后，此时栈为空栈。由此可知，栈的容量至少应该是3。
[答案]B)
2.链栈与顺序栈相比，有一个比较明显得优点是( )。
A)通常不会出现栈满的情况
B)通常不会出现栈空的情况
C)插入操作更加方便
D)删除操作更加方便
[分析]不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。
[答案]A)
3.在具有n个单元的循环队列中，队满共有_______个元素。
[分析]在循环队列中，为了能正确区分队满、队空两个判断条件，当前头指针front所指单元总是空的。因此最多(队满时)能存放n-1个元素。
[答案]n-1
4.栈的逻辑特点是_______，队列的逻辑特点是_______。两者的共同点是只允许在它们的_______处插入和删除数据元素。
[分析]由于只能在栈顶处执行插入、删除操作，使得数据元素的进栈顺序恰好与出栈顺序相反，所以栈的逻辑特点是先进后出(或后进先出)。而对队列来讲，插入、删除操作必须在队列的两端进行，数据元素的进队顺序与出队顺序是一致的。所以队列的逻辑特点是先进先出(或后进后出)。两者的共同点是所有操作只能在端点处进行。
[答案]先进后出(或后进先出)，先进先出(或后进后出)，端点。
5.二维数组M的的成员是6个字符(每个字符占一个存储单元)组成的串，行下标I的范围从0到8，列下标从1到10，则存放M至少需要_______个字节；M的第8列和第5行共占________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。
[分析]按题意二维数组M共有9行(行号0～8)，每行有10列(列号1～10)，合计有90个元素，每个元素占6个字节，所以存放M至少需要96×6＝540个字节。
M的第8列上若有9个元素，第5行上共有10个元素，合计有19个元素，但是其中有两个元素是重复的(M[5][8])，故实际有18个元素，共需占用18×6＝108个字节。
元素M[8][5]在数组中位于第9行的第5列，当按行优先方式存储时，在其前面已经存储了8×10＋4＝84个元素，因此M[8][5]时顺序存储的第85个元素。而当按列优先方式存储时，第85个元素应该是位于第10列的第3行上(前9列共有81个元素，第10列有4个元素)，即元素M[3][10]。
[答案]540,108,M[3][10]。
6.借助栈(可用栈的基本运算)来实现单链表单的逆置运算。
[分析]由于进栈顺序与出栈顺序正好相反，因此，借助栈来实现单链表的逆置运算很方便，也很容易理解。方法是先依次让单链表上的元素进栈，然后再依次出栈。
[答案]
void invert (pointer head)
{LstackTp s;
Inistack(s);
P=head;
while(p<>NULL)
{push(s,p->data);
p=p->next;
}
p=head;
while(not EmptyStack(s))
{pop(s,p->data;
p=p->next;
}
}
四.树
1.深度为6的二叉树最多有( )个结点。
A)64 B)63 C)32 D)31
[分析]由二叉树的性质2知，最多结点个数26-1=64-1=63。
[答案]B)
2.任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。
A)肯定发生变化 B)有时发生变化
C)肯定不发生变化 D)无法确定
[分析]由于在三种遍历中总是先遍历左子数，后遍历右子数，所以二叉树的叶子结点在三种遍历序列中的相对位置不好发生变化。
[答案]C)。
3.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
A)k+1 B)2k C)2k-1 D)2k+1
[分析]因为不存在度为1的结点，所以二叉树上除根结点外，每增加一层，至少要增加2个结点，如图5所示。
因此当h=1时，结点总数为1(2*1-1=1)，它是根结点；当h=2时，结点总数为3(2*2-1=3)；当h=2时，结点总数为5(2*3-1=5);…当b=k时，结点总数为2*k-1。
[答案]C)
4.具有n个结点的完全二叉树，若按层次从上到下，从左到右对其编号(根结点为1号)，则编号最大的分支结点序号是________，编号最小的分支结点序号是_________，编号最大的叶子结点序号是_________，编号最小的叶子结点序号是__________。
[分析]由二叉树的性质5知，最后一个结点的编号是n，那么它的双亲结点编号是[n/2]，这个双亲结点应该是二叉树中最后一个分支结点。也就是说，在二叉树中，编号1～[n/2]属于分支结点，编号[n/2]+1-n属于叶子结点。
[答案][n/2]，1，n，[n/2]+1。
5.已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。
[分析]根据二叉树的前根、中根遍历特点可知，在二叉树的前根遍历序列中，第一个结点肯定是根结点；而其中根遍历序列中，根结点将所有结点分为两部分，左边一部分对应于二叉树的左子树，右边一部分对应 于二叉树的右子树。依此类推，在左子树的前根遍历序列中，第一个结点一定是左子数的根结点；而其中根遍历序列中，根结点又将左子树的所有结点分为两部分，左边一部分对应于左子树的左子树，右边一部分对应于左子树的右子树。同理，在右子树的前根遍历序列中，第一个结点也一定是右子树的根结点；而其中根遍历序列中，根结点又将右子树的所以结点分为两部分，左边一部分对应于右子树的左子树，右边一部分
对应于右子树的右子树。如果按照上述思想递归下去，就可以完整地得到一颗所求的二叉树。
[答案]应用上面的思想,本题的解题过程如下:
1)由前根序列知A是二叉树的根结点；由中根序列知GDHBE是A的左子树中的结点，CIJF是A的右子树中的结点。
2)由前根序列知B是A的左子树的根结点；由中根序列知GDH是B的左子树中的结点，E是B的右子树中的结点。
3)由前根序列知D是B的左子树的根结点；由中根序列知G是B的左子树中的结点，H是B的右子树中的结点。
4)由前根序列知C是A的右子树的根结点；由中根序列知IJF是C的右子树中的结点(C的左子树为空)。
5)由前根序列知F是C的右子树的根结点；由中根序列知IJ是F的左子树中的结点(F的右子树为空)。
6)由前根序列知I是F的左子树的根结点；由中根序列知J是I的右子树中的结点(F的左子树为空)。
图6为上述解题过程的示意图，完整的二叉树如图7所示。
(fig6)(fig7)
五.图
1.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A)1 B)n/2 C)n-1 D)n
[分析]连通图是指任意两个不相同的的顶点之间都存在路径的无向图，而简单路径是指不带有回路的路径，因此连通图上不带有回路的路径，其长度不可能超过n-1。
| 
