Question

帮忙作一下数据结构的题

填空题：
循环单链表与非循环单链表的主要不同是_____。
S(n) 表示_________。
在采用顺序存储结构的线性表中逻辑上相邻的元素物理位置______紧邻。
单链表中逻辑上相邻的物理位置_______紧邻。
在一颗二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有_____个。
简答题
1、已知一棵二叉树的前序遍历序列和中序遍历序列分别是ABCDEFGHIJ和BCDAFEHJIG试给出该二叉树的后序遍历序列。
2、以关键码序列{503，087，512，061，908，170，897，275，653，426}为例，手工执行以下排序算法，写出每一趟排序结束是的关键码序列。
1）直接插入排序；
2）希尔排序（增量d[1]=5)；
3）快速排序；
4）堆排序；
5）归并排序；
6）基数排序；
3、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少？

对下面的递归算法写出调用test(3)的调用过程和调用结果。
status test(int w)
{ if (w>0) {
printf(w);
test(w-1);
test(w-1);
}
}//test
也可以把结果发到我的邮箱里virtuallife_bian@163.com 给我说以下我分给你

Answer 1

循环单链表的尾结点指针
表示点定位结构的规模
随机
非随机
m
n0=1 + ∑ ((i-1)*ni)（这个是公式）
i=2
简单题
1.解：

后序序列为：DCBFJIHGEA
2.解：
#define Max 10
int num[Max]={503, 87, 512, 61, 908,
170, 897, 275, 653, 426};

void shellsort(int *num)
{
int change;
int temp;
int i, j, k;
int length=Max/2;
while (length > 0)
{
change=0;
for (i=0; i<=length; i++)
{
for (j=i+length; j<Max; j+=length)
{
temp=num[j];
while (num[j-length] > num[j] && j-length >= 0)
{
num[j]=num[j-length];
j-=length;
change=1;
}
num[j]=temp;
}
}
if (change)
{
for (k=0; k<Max; k++)
{
printf("%5d",num[k]);
}
printf("\n");
}
length=length/2;
}
}

main()
{

shellsort(num);
}

3.解：
最少应为3
动作 状态 栈中元素
S1入栈 S1
S2入栈 S1,S2
S2出栈,S3入栈 S2 S1,S3
S3出栈,S4入栈 S2,S3 S1,S4
S4出栈,S5入栈 S2,S3,S4 S1,S5
S6入栈 S2,S3,S4 S1,S5,S6 //最少需要3个容量
S6出栈 S2,S3,S4,S6 S1,S5
S5出栈 S2,S3,S4,S6,S5 S1
S1出栈 S2,S3,S4,S6,S5

最后一题没时间做了，要下班了，呵呵