if（i+j==n-1）
a[i][j]=0;
}
【6，1，3】设n为正整数，试确定下列各程序段中前置以记号的语句的频度:
（1）i=1;k=0;
while（i<=n-1）{
i++;
k+=10*i;//语句的频度是n-1。
}
（2）k=0;
for（i=1;i<=n;i++）{
for（j=i;j<=n;j++）
k++;//语句的频度是n（n+1）/2。
}
【7，3，2】线性表（a1，a2，…，an）有两种存储结构：
顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：
顺序存储密度较大；顺序存储利用率较高；顺序可以随机存取；链式不可以随机存取；链式插入和删除操作比较方便。
【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i个元素。
【9，3，2】带头结点的单链表Head为空的条件是Head->next=NULL。
【10，3，2】在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行s->next=_p->next;和p->next=s的操作。
【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作：
q=p->next;
p->data=p->next->data;
p->next=p->next->next;
free（q）;
【12，3，2】带头结点的单循环链表Head的判空条件是Head->next==Head；不带头结点的单循环链表的判空条件是Head==NULL。
【13，3，2】已知L是带表头结点的非空单链表,且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接前驱结点的语句序列是1012811414。
b.删除结点P的语句序列是10127314。
c.删除尾元结点的语句序列是911314。
（1）P=P->next;
（2）P->next=P;
（3）P->next=P->next->next;
（4）P=P->next->next;
（5）while（P!
=NULL）P=P->next;
（6）while（Q->next!
=NULL）{P=Q;Q=Q->next};
（7）while（P->next!
=Q）P=P->next;
（8）while（P->next->next!
=Q）P=P->next;
（9）while（P->next->next!
=NULL）P=P->next;
（10）Q=P;
（11）Q=P->next;
（12）P=L;
（13）L=L->next;
（14）free（Q）;
【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有CAB。
【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是 head->next==NULL。
【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。
voidconversion10_16（）
{InitStack（&s）;
scanf（“%d”,&N）;
while（N）{
Push（s,N%16）;
N=N/16;
}
while（!
StackEmpty（s））{
Pop（s,e）;
if（e<=9）printf（“%d”,e）;
elseprintf（“%c”,e-10+’A’）;
}
}/*conversion*/
【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。
【18，3，4】堆栈和队列都是线性表,堆栈是后进先出的线性表,而队列是先进先出的线性表。
【19，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。
【20，4，2】已知一棵树边的集合是{,,,,,,,,}。
那么根结点是e，结点b的双亲是d，结点a的子有bcdj，树的深度是4，树的度是3，结点g在树的第3层。
【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是 采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题 。
【22，4，3】满三叉树的第i层的结点个数为3i-1，深度为h时该树中共有3h-1结点。
【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。
则该完全二叉树总共结点有111个；有7层；第91号结点的双亲结点是45号；第63号结点的左孩子结点是32号。
【24，4，3】下列表示的图中，共有5个是树；有3个是二叉树；有2个是完全二叉树。
【25，4，4】n个结点的二叉排序树的最大深度是n，最小深度为[log2n]+1。
【26，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先序遍历序列的第一个字母是I，最后一个字母是G。
【27，4，3】下列二叉树的中序遍历序列是DBNGOAEC;后序遍历序列是DNIGBECA。
【28，5，4】设HASH表的大小为n（n=10）,HASH函数为h（x）=x%7,如果二次探测再散列方法Hi=（H（key）+di）mod10（di=12,22,32,…,）解决冲突，在HASH表中依次插入关键字{1,14,55,20,84,27}以后，关键字1、20和27所在地址的下标分别是1、7和5。
插入上述6个元素的平均比较次数是2。
【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于1，22、设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于0。
【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是矩阵第i行全部置为零。
【31，6，2】设一个图
G={V,{A}},V={a,b,c,d,e,f},A={,,,,,,}。
那么顶点e的入度是2；出度是1；通过顶点f的简单回路有2条；就连通性而言，该图是强连通图；它的强连通分量有1个；其生成树可能的最大深度是 5 。
【32，7，1】排序过程一般需经过两个基本操作，它们是比较和移动。
【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较3次。
【34，7，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有希尔排序、快速排序、堆排序。
二、综合题（选自教材《数据结构》各章习题，采用word文件格式上传）
【1，1，3】试分析下面一段代码的时间复杂度：
if（A>B）{
for（i=0;ifor（j=N*N;j>i;j--）
A+=B;
}
else{
for（i=0;ifor（j=N*2;j>i;j--）
A+=B;
}
答：
ifA>B为真，则for语句的外循环N次，循环为N（N-1）次，因此时间复杂度为O（N*N（N-1）），也就是N的三次方。
ifA>B为假，则for语句的外循环2N次，循环为N次，因此时间复杂度为O（2N*N），也就是N的平方。
整段取最大的，时间复杂度就是N立方。
【2，1，3】测试例1.3中九韶算法与直接法的效率差别。
令
，计算
的值。
利用clock（）函数得到两种算法在同一机器上的运行时间。
答：
直接法：
0.1μs
九韶算法：
0.04μs
【3，1，3】试分析最大子列和算法1.3的空间复杂度。
答：
算法1.3的基本思路是将原问题拆分成若干小型问题，分别解决后再将结果合而治之，用递归方法实现。
算法1.3的负责度分析略有难度：
若记整体时间复杂度为T（N），则函数DivideAndConquer过递归实现“分”的复杂度为2T（N/2），因为我们解决了2个长度减半的字问题。
求跨分界线的最大子列和时，有两个简单的for循环，所用步骤一共不超过N，所以可以在O（N）时间完成。
其他步骤都只需常熟O
（1）时间。
综上分析则有递推式：
T
（1）=O
（1）；
T（N）=2T（N/2）+O（N）
=2[2T（（N/2）/2+O（N/2）]+O（N）=22T（N/22）+2O（N）
=…=2KT（N/2k）+kO（N）
当不断对分直到N/2k=1,即2k=N时，就得到T（N）=NT
（1）+logN*O（N）=O（NlogN）。
此算法比算法1.2又快了一些，当N=104时，效果会非常明显。
但是这仍然不是最快的算法。
【4，1，3】试给出判断
是否为质数的
的算法。
答:
intsushu（intN）{
inti;
intflag=1;
if（N==1）returnfalse;//1既不是合数也不是质数
if（N==2）returntrue
for（i=2;i<=sqrt（N）;i++）
{if（N%i==0）
{flag=0；break;}
}
returnflag;
}
【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a（n个a）的结果。
答：
#include"stdio.h"
intmain（）
{
inta,b,n,i,s=0;
scanf（"%d%d",&a,&n）;
b=a;
for（i=1;i<=n;i++）
{
s+=a;
a=a*10+b;
}
printf（"%d\n",s）;
}
【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。
答：
#include
#defineN8
intn=0;
voidswap（int*a,int*b）
{
intm;
m=*a;
*a=*b;
*b=m;
}
voidperm（intlist[],intk,intm）
{
inti;
if（k>m）
{
for（i=0;i<=m;i++）
printf（"%d",list[i]）;
printf（"\n"）;
n++;
}
else
{
for（i=k;i<=m;i++）
{
swap（&list[k],&list[i]）;
perm（list,k+1,m）;
swap（&list[k],&list[i]）;
}
}
}
intmain（）
{
intlist[N];
intnum,i=0;
printf（"Pleaseinputanum:
"）;
scanf（"%d",&num）;
while（num!
=0）
{
list[i]=num%10;
num=num/10;
i++;
}
perm（list,0,i-1）;
printf（"total:
%d\n",n）;
return0;
}
【7，3，2】给定一个顺序存储的线性表L=（
,
），请设计一个算法删除所有值大于min而且小于max的元素。
答：
#include
#include
#include
typedefintElemType;
typedefstructLNode
{
ElemTypedata;/*数据子域*/
structLNode*next;/*指针子域*/
}
LNode;/*结点结构类型*/
LNode*L;/*函数声明*/
LNode*creat_L（）;
voiddelete_L（LNode*L,inti）;//返回值格式变为空
/*建立线性链表*/
LNode*creat_L（）
{
LNode*h,*p,*s;ElemTypex;
h=（LNode*）malloc（sizeof（LNode））;/*分配头结点*/
h->next=NULL;
p=h;
printf（"输入一串数字（以-1结束）:
\ndata="）;
scanf（"%d",&x）;/*输入第一个数据元素*/
while（x!
=-1）/*输入-1，结束循环*/
{
s=（LNode*）malloc（sizeof（LNode））;/*分配新结点*/
s->data=x;s->next=NULL
p->next=s;p=s;
printf（"data="）;
scanf（"%d",&x）;/*输入下一个数据*/
}
return（h）;
}/*creat_L*/
/*输出单链表中的数据元素*/
voidout_L（LNode*L）
{
LNode*p;
p=L->next;
printf（"\n数据是:
"）;
while（p!
=NULL）
{
printf（"%5d",p->data）;
p=p->next;
}
}/*out_link*/
/*删除大于x小于y的值*/
voiddelete_L（LNode*L,inta,intb）
{
LNode*p,*q;
p=L;
q=p;
p=p->next;
if（p==NULL）printf（"ERROR:
链表为空"）;
while（p!
=NULL）
{
if（（p->data>a）&&（p->data{
q->next=p->next;
free（p）;
p=q->next;
}
else
{
q=p;
p=p->next;
}
}
}/*delete_L*/
voidmain（）
{
inta,b
L=creat_L（）;out_L（L）;
printf（"\n\n请输入你要删除的元素的围min和max:
\n"）;
scanf（"%d%d",&a,&b）;
delete_L（L,a,b）;out_L（L）;
printf（"\n"）;
}/*main*/
【8，3，2】给定一个顺序存储的线性表L=（
,
），请设计一个算法查找该线性表中最长递增子序列。
例如，（1,9,2,5,7,3,4,6,8,0）中最长的递增子序列为（3,4,6,8）。
答：
#include
#include
usingnamespacestd;
#defineMAXN1003
intA[MAXN];
intdp[MAXN];
//动态规划思想O（n^2）
intmain（）
{
intn,i,j,k;
cin>>n;
for（i=1;i<=n;i++）
cin>>A[i];
dp[1]=1;
//有n个阶段
for（i=2;i<=n;i++）
{
dp[i]=1;
//每个阶段只有1个状态
//每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度
for（j=i-1;j>=0;j--）
{
if（A[i]>A[j]）
dp[i]=max（dp[i],dp[j]+1）;
}
}
intmaximum=dp[1];
for（i=2;i<=n;i++）
maximum=max（maximum,dp[i]）;
cout<}
【9，3，3】如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop,push）顺序可得到不同的堆栈输出序列。
请问共有多少种不同的输出序列？
为什么？
答：
共有34种不同的输出序列
1234512354124351254313245132541432515432
2134521435215432314523154234152345123541
2431524351245312543132145321543241532451
3254134215342513452135421432154325143521
4532154321
【10，3，2】请编写程序将中缀表达式转换为后缀表达式。
答:
#include
#include
#include
usingnamespacestd;
intprior（charop）
{
if（op=='+'||op=='-'）
return1;
if（op=='*'||op=='/'）
return2;
return0;
}
stringmiddletolast（stringmiddle）
{
stackop;
stringans;
for（inti=0;i{
charc=middle[i];
if（c>='0'&&c<='9'）
{
ans.append（1,c）;
}
else
{
if（c=='（'）
op.push（'（'）;
else
{
if（c=='）'）
{
while（op.top（）!
='（'）
{
ans.append（1,op.top（））;
op.pop（）;
}
op.pop（）;
}
else
{
if（op.empty（））
{
op.push（c）;
}
else
{
if（prior（c）>prior（op.top（）））
op.push（c）;
else
{
while（!
op.empty（）&&prior（c）<=prior（op.top（）））
{
ans.append（1,op.top（））;
op.pop（）;
}
op.push（c）;
}
}
}
}
}
}
while（!
op.empty（））
{
ans.append（1,op.top（））;
op.pop（）;
}
returnans;
}
intmain（）
{
stringmdata,res;
cin>>mdata;
res=middletolast（mdata）;
for（inti=0;i{
if（i==0）
cout<else
cout<<''<}
cout<return0;
}
【11，4，3】设二叉树的存储结构如下：
1
2
3
4
5
6
7
8
9
10
Lchild
0
0
2
3
7
5
8
0
10
1
data
J
H
F
D
B
A
C
E
G
I
Rchild
0
0
0
9
4
0
0
0
0
0
其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。
（1）画出二叉树的逻辑结构。
答：
（2）写出该树的前序、中序和后序遍历的序列。
答：
前序序列：
ABCEDFHGI
中序序列：
ECBHFDJIGA
后序序列：
ECHFJIGDBA
【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？
请写出其中的任意4个。
答：
可以生成如上二叉排序树的关键字的初始排列有30种
任写4个序列如下：
（5，7，6，4，2，1，3）
（5，7，6，4，2，3，1）
（5，4，2，3，7，6，1）
（5，4，2，1，7，6，3）
【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答：
（1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）；
答：
11
713
41622
5
（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；
11
516
471322
【14，4，6】假设一个文本使用的字符集为{a,b,c,d,e,f,g},字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。
（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；
答：
（2）若这些字符在文本中出现的频率分别为：
{3,35,13,15,20,5,9}
升级会员 