第1题. 一颗完全二叉树共有21个结点，现顺序存放在一个向量中，向量的下标正好为结点的序号，请问有序号为12的双亲结点存在吗？为什么？

第2题. 何谓队列的"假溢"现象？如何解决？

第3题. 简述以下算法的功能。

Status A(LinkedList L){
if(L&&L->next){
Q=L;L=L->next;P=L;
while(P->next) P=P->next;
P->next=Q;Q->next=NULL;
}
return OK;
}

第4题. 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程求得问题的解。

第5题. 线性表可用顺序表或链表存储。试问：若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这是，应采用哪种存储表示？为什么？

第6题. 假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。

第7题. 试证明：若借助栈由输入序列1，2，…，n,得到输出序列P1,P2,…,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情况：存在i

第8题. 空串在串的处理中有何作用？

第9题. 两个字符串相等的充要条件是什么？

第10题. 已知一棵二叉树的中序遍历序列和先序遍历序列为，试问能不能唯一确定一棵二叉树。若给定先序遍历序列和后序遍历序列，能不能唯一确定呢？

第11题. 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？

第12题. 二叉树与树之间有何区别？

第13题. 简述以下算法的功能（栈和队列的元素类型均为int)

void algo3(Queue &Q){
Stack S; int d;
InitStack(S);
while(!QueueEmpty(Q)){
DeQueue(Q,d);Push(S,d);
}
while(!StackEmpty(S)){
Pop(S,d); EnQueue(Q,d);
}
}

第14题. 编写一个函数用不多于3n/2的平均比较次数，在一个向量A中找出最大和最小值的元素。

第15题. 有两个具有相同结点个数的单链表A和B，A={a1,a2,…,an},B={b1,b2,…,bn},编写一个函数将其合并成一个链表C，C={a1,b1,a2,b2,…,an,bn}

第16题. 试将下列递归过程改写为非递归过程。

void test(int &sum){
int x;
scanf(x);
if(x==0) sum=0;
else {test(sum);sum+=x;}
printf(sum);
}

第17题. 采用顺序结构存储串，编写一个函数substring(s1,s2),用于判定s2是否是s1的子串。

第18题. 线性表有两种存储结构：一是顺序表，二是链表，简述各自的优缺点。

第19题. 假定有n个关键字，具有相同的散列函数值，如果用线性探测法把这n个关键字放到散列表中，要做多少次探测？

第20题. 设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用哪种方法最好？为什么？（快速排序，堆排序，基数排序）

答案

第1题. 在共有21个结点的完全二叉树中不存在序号为12的双亲结点。因为若存在序号为12的双亲结点，该完全二叉树中至少应有序号为12×2＝24的结点是其左孩子结点与题设共有21结点矛盾。

第2题. 队列的假溢现象是指用数组实现的顺序队列中，队尾指针已到达数组的下标上界产生上溢而队头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间首尾相连。

第3题. 如果L的长度不小于2，则将首元结点删去并插入到表尾

第4题. 出局人的顺序为5，1，7，4，3，6，9，2，8。

第5题. 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这是采用顺序存储表示较好。

第6题. 共有14种可能的出栈序列，即为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA

第7题. 若有jPk,则必然把Pk留在栈中，直到Pj进栈之后。显然，由上面两条可知，条件i

第8题. 空串在处理过程中可用于作为任意字符串的子串。

第9题. 两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。

第10题. 由中序遍历序列和先序遍历序列能唯一确定一棵二叉树。由先序遍历和后序遍历序列不能唯一确定一棵二叉树。

第11题. 显然，能达到最大深度的是单支树，其深度为n；深度最小的是完全k叉树。

第12题. 1.二叉树的一个结点至多有2个子树，树则不然；2.二叉树的一个结点的子树有左，右之分，而树则没有此要求。

第13题. 算法的功能：利用栈作辅助，将队列中的数据元素进行逆置。

第14题. void maxmin(A,n)
vector A;

int n;
{
int max,min,i;
max=A[1];min=A[1];
for(i=2;i<=n;i++)
if(A[i]>max) max=A[i];
else if(A[i]
printf("max=%d,min=%d\n",max,min);
void maxmin(A,n)
vector A;
int n;
{
int max,min,i;
max=A[1];min=A[1];
for(i=2;i<=n;i++)
void maxmin(A,n)
vector A;
int n;
{
int max,min,i;
max=A[1];min=A[1];
for(i=2;i<=n;i++)
if(A[i]>max) max=A[i];
else if(A[i]
printf("max=%d,min=%d\n",max,min);
}

第15题. node *sum(a,b)
node *a,*b;
{
node *r,*s,*p,*q,*c;
c=(node *)malloc(sizeof(node));
r=c;p=a;q=b;
while(p!=NULL)
{
s=(node *)malloc(sizeof(node));
s->data=p->data;
r->next=s;
p=p->next;
r=s;
new(s);
s->data=q->data;
r->next=s;
q=q->next;
r=s;
}
r->next=NULL;
c=c->next;
return(c);
}

第16题. void test(int &sum)
{
Stack S;
int x;
scanf(x);
InitStack(S);
while(x) {
Push(S,x);
scanf(x);
}
sum=0;
printf(sum);
while(Pop(S,x)) {
sum+=x;
printf(sum);
}

}

第17题. int substring(s1,s2)
orderstring *s1,*s2;
{
int i,j,k,yes=0;
i=0;
while(ilen && !yes)
{
j=0;
if(s1->vec[k]==s2->vec[j])
{
k=i+1;
j++;
while(s1->vec[k]==s2->vec[j])
{
k++;
j++;
}
if(j==s2->len) yes=1;
else i++;
}
else i++;
}
return(yes);
}

第18题. 线性表的两种存储结构各有其优缺点。顺序表中数据元素的物理位置相邻与逻辑相邻关系一致，无需为表示数据元素之间的关系增加额外存储空间，可以随机存取表中任一元素；缺点是插入和删除元素需要移动大量元素，效率较低，且要为线性表预先分配空间，过小会产生表满溢出，过大会造成空间浪费。链表则不需要预先分配存储空间，插入和删除运算效率高；缺点是存取表中元素需从链头开始，效率较低，且需为表示数据元素间的关系增加指针域空间。

第19题. 具有n个相同散列函数值的关键字用线性探测法放到散列表中，第一个需要一次探测，第二个需两次探测，。。。，第n个需n次探测，共需的探测次数为1+2+3+。。。+n=n(n+1)/2

第20题. 用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。