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;//语句的频度是______________________。
}
（2）k=0;
for（i=1;i<=n;i++）{
for（j=i;j<=n;j++）
@k++;//语句的频度是______________________。
}
【7，3，2】线性表（a1，a2，…，an）有两种存储结构：
顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：
___存储密度较大；____存储利用率较高；____可以随机存取；_____不可以随机存取；____插入和删除操作比较方便。
【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。
【9，3，2】带头结点的单链表Head为空的条件是__________。
【10，3，2】在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行s->next=_____;和p->next=________的操作。
【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作：
q=p->next;
p->data=p->next->data;
p->next=_;
free（q）;
【12，3，2】带头结点的单循环链表Head的判空条件是_____；不带头结点的单循环链表的判空条件是_____。
【13，3，2】已知L是带表头结点的非空单链表,且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接前驱结点的语句序列是________________________________。
b.删除结点P的语句序列是________________________________。
c.删除尾元结点的语句序列是________________________________。
（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，则全部不可能的输出序列有。
【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是 。
【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。
voidconversion10_16（）
{InitStack（&s）;
scanf（“%d”,&N）;
while（N）{
_____________________;
N=N/16;
}
while（!
StackEmpty（s））{
_____________________;
if（e<=9）printf（“%d”,e）;
elseprintf（“%c”,e-10+’A’）;
}
}/*conversion*/
【17，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是和。
【18，3，4】堆栈和队列都是线性表,堆栈是____________________________________的线性表,而队列是____________________________________的线性表。
【19，3，4】若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是和。
【20，4，2】已知一棵树边的集合是{,,,,,,,,}。
那么根结点是，结点b的双亲是，结点a的子孙有，树的深度是，树的度是，结点g在树的第层。
【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是 。
【22，4，3】满三叉树的第i层的结点个数为，深度为h时该树中共有结点。
【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。
则该完全二叉树总共结点有________个；有_______层；第91号结点的双亲结点是_______号；第63号结点的左孩子结点是_________号。
【24，4，3】下列表示的图中，共有_______个是树；有_______个是二叉树；有_______个是完全二叉树。
【25，4，4】n个结点的二叉排序树的最大深度是，最小深度为。
【26，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先序遍历序列的第一个字母是，最后一个字母是。
【27，4，3】下列二叉树的中序遍历序列是___________;后序遍历序列是______________________________________。
【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所在地址的下标分别是、______和。
插入上述6个元素的平均比较次数是。
【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于，22、设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][i]等于。
【30，6，3】若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是。
【31，6，2】设一个图
G={V,{A}},V={a,b,c,d,e,f},A={,,,,,,}。
那么顶点e的入度是；出度是；通过顶点f的简单回路有条；就连通性而言，该图是图；它的强连通分量有个；其生成树可能的最大深度是 。
【32，7，1】排序过程一般需经过两个基本操作，它们是和。
【33，7，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较次。
【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;
}
【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。
令
，计算
的值。
利用clock（）函数得到两种算法在同一机器上的运行时间。
【3，1，3】试分析最大子列和算法1.3的空间复杂度。
【4，1，3】试给出判断
是否为质数的
的算法。
【5，2，2】请编写程序，输入整数n和a，输出S=a+aa+aaa+…＋aa…a（n个a）的结果。
【6，2，3】请编写递归函数，输出123..n的全排列（n小于10）,并观察n逐步增大时程序的运行时间。
【7，3，2】给定一个顺序存储的线性表L=（
,
），请设计一个算法删除所有值大于min而且小于max的元素。
【8，3，2】给定一个顺序存储的线性表L=（
,
），请设计一个算法查找该线性表中最长递增子序列。
例如，（1,9,2,5,7,3,4,6,8,0）中最长的递增子序列为（3,4,6,8）。
【9，3，3】如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop,push）顺序可得到不同的堆栈输出序列。
请问共有多少种不同的输出序列？
为什么？
【10，3，2】请编写程序将中缀表达式转换为后缀表达式。
【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）写出该树的前序、中序和后序遍历的序列。
【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？
请写出其中的任意4个。
【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答：
（1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）；
（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；
【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}，求该哈夫曼树的带权路径长度。
【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。
【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：
H（key）=key%17，采用平方探测方法解决冲突。
试在0到18的散列地址空间中对该关键字序列构造散列表。
【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。
处理冲突采用线性探测法，散列函数为：
H（key）=（key×3）modTableSize，要求装入因子为0.7。
【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：
V0 01011000
V1 10101000
V2 01000100
V3 10000010
V4 11000010
V5 00100000
V6 00011001
V7 00000001
（1）画出该图的图形；
（2）给出从V0出发的深度优先遍历序和广度优先遍历序。
【19，6，3】已知有向图如右图所示，请给出该图的
（1）每个顶点的入度和出度；
（2）邻接矩阵；
（3）邻接表；
（4）逆邻接表；
（5）各个强连通分量。
【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
【21，6，3】给出如下图所示的具有7个结点的网G。
请：
（1）画出该网的邻接矩阵；
（2）采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法的执行过程及最小生成树的生成示意图）。
【22，7，4】给定数组{48,25,6,90,17,84,62,48,27,96,49,72,17}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【23，7，4】给定数组{48,25,6,90,17,84,62,48,27,96,49,72,17}，请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【24，7，4】给定数组{48,25,6,90,17,84,62,48,27,96,49,72,17}，请用3种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
升级会员 