数据结构期末试题

数据结构课后练习题一、填空题（第二章）1、顺序表中逻辑上相邻元素的物理位置相邻，单链表中逻辑上相邻的元素物理位置可以相邻，也可以不相邻。2、在一个长度为n的顺序表中删除第i个元素，平均要移动n-i个元素，如果在第i个元素之前插入一个元素，平均要移动n-i+1个元素。3、在一个单链表中，若p所指的结点不是最后结点，在p之后插入s结点，则执行s-next=p-next;p-next=s。4、在一个长度为n的顺序表的表尾插入一个新元素的时间负责度为O。5、非空的单循环链表head的尾结点（由指针P所指）满足p-next=head。（第三章）1.栈和队列都是线性结构，对于栈来说，它的插入和删除操作智能在栈顶进行，而队列的插入操作是在队尾进行，删除元素的操作是在队首进行。2.设有一顺序栈s，元素s1,s2,s3,s4,s5,s6吃入栈，如果六个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是3。3.在具有n个单元的循环队列中，队满时共有n-1个元素。4.从栈顶指针为Top的链栈中删除一个结点，并将结点值保存在X中，进行的操作是x=Top-data;Top=Top-next。5.中缀表达式（A+B）*D+E/(F+A*D)对应的后缀表达式为AB+D*EFAD*+/+6.在操作序列push（1）；push（2）;pop (2);push（3）；push（4）；push（5）；push（6）；push（7）；pop (7)之后栈顶元素和栈底元素分别是6和1。7.在操作序列Qinsert（1）；Qinsert（2）；Qdelete（1）；Qdelete（2）；Qinsert（3）；Qinsert（4）；Qinsert（5）；Qinsert（6）；Qinsert（7）；Qdelete（3）；Qdelete（4）；Qinsert（8）；Qinsert（9）；之后队头元素和队尾元素分别是5和9。（第四章）1.串是由0个或多个字符组成的序列。2.不包含任何字符串称为空串；由一个或多个空格组成的串称为空格串。3.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。（第五章）1.广义表的深度是等于括号嵌套的最大层数。2.在广义表的存储结构中，每个结点均包含3个域。3.一个广义表的深度等于括号嵌套的最大层数。4.对矩阵压缩是为了节省存储空间。5.当广义表中的每个元素都是原子时，广义表便成了线性表。6.广义表的表尾是指除第一个元素之外，其余元素组成的表。7.广义表的深度定义为广义表中括弧的重数。8.设广义表L=（），（），则hesd（L）是 （） ；tail（L）是（）；L的长度是2；深度是2。9.广义表（a，（a,b）,d,e,(i,j),k)）的长度是5，深度是3。（第六章）1.对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1。2.一颗=棵深度为5的满二叉树中的结点树为31个。3.假定一棵树的广义表表示为A（B(C,D(E,F,G),H(I,J)），则树种所含的结点数为10个，树的深度为四个，树的度为3.4.假定一棵树的广义表表示为A（B(C,D(E,F,G),H(I,J)）,则度为3，2，1，0的结点树分别为2、1、1和6个。5.假定一棵树的广义表表示为A（B(C,D(E,F,G),H(I,J)），则结点H的双亲结点为B，孩子结点为I和J。6.在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10 外，还可以最多对4个字符编码。7.对于一棵二叉树，若一个结点的编码为i，则它的左孩子结点的编号为2i，右孩子结点的编号为2i+1，双亲结点编号为i/2。8.在一棵二叉树中，第5层上的结点数最多为16。9.假定一棵二叉树的结点树为18，则它的最小深度为5，最大深度为18。10. 假定一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为a2i，右孩子元素为a2i+1，双亲元素（i-1）为ai/2。11. 假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a0元素中，让编号为2的结点存入a1元素中，其余类推，则编号为i结点的左孩子结点对应的存储位置为2i-1。12.对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为2n个，其中n-1个用于指向孩子结点，n+1个指向空闲着。13.一棵二叉树广义表表示为a(b(d(h),c(e,f(g,i(k),该树的结点数为10个，深度为5。14.假定一棵二叉树广义表表示为a（b(c),d(e,f)）,则对它进行的先序遍历结果为a b c d e f,中序遍历结果为c b a e d f，后续序遍历结果为c b e f d a。（第七章）1. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度。2. 图的逆邻接表存储结构之适用于有向图。3.图的深度优先遍历序列不是唯一的。4.图的BFS生成树的树高比DFS生成树的树高矮或相当。5.拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。6.若要求一个稀疏图G的最小生成树，最好用Kruskal算法来求解。（第八章）1.关键字是数据元素（或记录）中某个属性,用它的标识(或识别)一个查找表中的数据元素（或记录）。并且，在一个查找表中，能够唯一标识一个数据元素（或记录）的关键字称为主关键字。2.查找又称为（检索），它是根据给定的某个值，在查找表中确定是否有元素或记录的关键字等于给定值的操作。若操作之后确定表中存在这样的记录，则称为查找是成功的，否则称为不成功（或失败）。3.平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较的关键字个数的平均值（或期望值）。4.采用顺序查找法查找长度为n大的线性表时，假设查找成功与查找不成功的概率对等，对每个记录的查找概率也相等，则平均查找长度为3（n+1）/4。5.折半查找又称为二分查找，其查找思路是：每次将给定值与查找表中所要查找区域中间位置的关键字进行比较，而不是查找表中的第一条或最后一条。6.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希表查找法。7.哈希表的查找小绿主要取决于哈希表建表时选择的哈希函数和装填因子。8.构造哈希函数的方法有直接定址法、数字分析法、平方取中法、折叠法和除留余数法。9.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行（K/1）K/2次探测。10.二叉排序树又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的一棵二叉树；（1）若左子树不空，则左子树上所有结点的值小于根结点的值。（2）若右子树不空，则左子树上所有结点的值大于根结点的值。（3）左、右子树又分别是一棵二叉排序树。11.平衡二叉树是有Abelson-Velskil和Landis提出的一种附加一定限制条件的二叉树。又称为AVL树。平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树；它的左子树和右子树都是一棵平衡二叉树，且左子树和右子树的深度之差绝对值不大于1。12.在向哈希表中存储关键字的时候，有时会出现一个待插入关键字的记录已经被占用的情况，这种对不同关键字得到同一地址的现象称为冲突（或碰撞），相应的把这些具有相同哈希函数值得关键字称为同义词。13.构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生，一旦冲突发生了，就必须讯企鹅合适的方法来解决冲突。常用开放地址法和链地址法两种方法来解决冲突。14.对长度n=50的有序表进行折半查找，则对应的判定树高度为6，判定树前5层的结点树是31，最后一层的结点树为9。二、单选题（第二章）1、线性表L=（a1,a2,ai,an），下列说法正确的是（D）A、每个元素都有一个直接前驱和直接后继B、线性表中至少有一个元素C、表中诸元素的排列顺序必须是从小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。2、对于顺序表，以下说法错误的是（A）A、顺序表是一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中3、对顺序表上的插入、删除、算法的时间复杂度分析来说，通常以（B）对标准操作。A、条件判断B、结点移动C、算术表达式D、赋值语句4、对于顺序表的优、缺点，以下说法错误的是（C）A、无须为表示结点间的逻辑关系而增加额外的存储空间B、可以方便的随机存储表中任一结点C、插入和删除操作较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）5、在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动的点的平均次数为（B）A、nB、n/2C、(n-1)/2D、(n+1)/26、在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（C）A、nB、n/2C、(n-1)/2D、(n+1)/27、带头结点的单链表head为空的条件是（B）A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL8、非空循环单链表head的尾结点*p满足（C）A、p-next=NULLB、p=NULLC、p-next=headD、p=head9、在循环双链表的*p结点之后插入*s满足（D）A、p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B、p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C、s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D、s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;10、在线性表的下列存储结构中，读取元素花费时间最少的是（D）A、单链表B、双链表C、循环列表D、顺序表（第三章）1.有一栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为（B）。A. 4 B 5 C 6 D 72.和顺序栈相比，链栈有一个比较明显的优势是（A）。A 通常不会出现栈满的情况 B通常不会出现栈空的情况C 插入操作更容易实现 D 删除操作更容易实现3.若一个栈的输入序列是1、2、3、4、n，输出序列第一个元素是n，则第i个输出元素是(C)。A 不确定 B n-i C n-i+1 D n-i-1 4.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是（C）A e、d、c、b、a B d、e、c、b、a C d、c、e、a、b D a、b、c、d、e5.一个队列的入队列是1、2、3、4，则队列的可能输出序列是（B）A. 4、3、2、1B. 1、2、3、4 C.1、4、3、2 D .3、2、4、16.顺序列队的出队操作为（B）A sq.front=(sq.front+1)%maxsize B sq.front=sq.front+1Csq.rear=(sq.rear+1)maxsize D sq.rear=sq.rear+17.循环队列q的出队操作为（A）A q,front=(q.front+1)%maxsizeB q.front=q.front+1C q.rear=(q.rear+1)%maxisize Dq.rear=q.rear+18.循环队列用数组A0，m-1存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中的元素个数是（A）。A.(rear-front+m)%m B read-front+1C.read-front-1 D.read-front9.在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算是（C）。A,r=f-next B.r=r-next C.f=f-next D f=r-next（第四章）1.串是（D）A. 一些符号构成的序列 B.一些字母构成的序列C.一个以上的字符构成的序列 D.任意有限个字符构成的序列2.S1=“abcd”，S2=“cd”，则S2在S1中的位置是（C）。A.1 B.2 C.3 D.43.下列为空串的是（C）。A.” B.” “ C.” D.”“4.朴素模式匹配算法在最好的情况下的运行时间是（以一次内循环为单位）（C）。A.M B.N C.MN D.M+N（第五章）1.已知广义表LS=（a,b,c），（d,e,f）,运用head和tail函数取出LS中元素e的运算是（C）A.head(tail(LS) B.tail(head(LS)C.head(tail(head(tail(LS) D.head(tail(tail(head(LS)2.将一个A1100,1100的三对角矩阵，按行优先存入一维数组B1298中，A中元素a66，65（即该元素下标i=66,j=65）在B数组中的位置K为（B）A.198 B.195 C.197 D.1963.若广义表A满足Head（A）=Tail（A），则A为（B）。A.() B.() C.(),() D.(),(),()4.广义表A=（a,b,(c,d),(e,(f,g)）,则下面式子Head（Tail(Head(Tail(Tail(A)）的值为（D）。A.(g) B.（d） C.c D.d5.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,，8,列下标j=1,2，10.若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（B）的起始地址相同。设每个字符占一个字节。A. A8，5 B.A3，10 C,A5，8 D.A0，96.在以下的叙述中，正确的是（B）A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元数为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出7.二维数组SA中，每个元素的长度为3个字节，行下标i从07，列下标j从09，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素SA47的起始地址为（B）。A.SA+141 B.SA+180 C.SA+222 D.SA+2258.下面结论正确的是（B）。A.一个广义表的表头肯定不是一个广义表。B.一个广义表的表尾肯定是一个广义表。C.广义表L=(),(A,B)的表头为空表D.广义表中原子个数即为广义表的长度9.下面说法不正确的是（A）A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构 D,广义表可以是一个多层次的结构（第六章）1.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）。A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶子结点 D.是任意一棵二叉树2.一棵完全二叉树上有1001个结点，其中椰子结点个数是（D）。A.250 B.500 C.254 D.以上答案都不对3.任何一棵二叉树的叶结点在前（先）序、中序、后序遍历序列中的相对次序（A）。A不发生变化 B.发生变化 C.不能确定4.设A,B为一棵二叉树上的两个结点，在中序遍历时，A在B前面的条件是（B）。.A在B的右方 B. A在B的左方 C.A是B的祖先 D.A是B的子孙5.在一棵具有n个结点的完全二叉树中，数值结点最大编号为（D）A. (n+1)/2 B.(n-1)/2 C. n/2 D. n/26.在N个结点的线索二叉树中，线索的数目为（C）。A.N-1 B.N C.N+1 D.2N7.设深度为K的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为（C）A.K+1 B.2K C. 2K1 D, 2K+18.下列有关二叉树的说法，正确的是（B）。A.二叉树的度为2 B.一棵二叉树度可以小于2C.二叉树中至少有一个结点的度为2 D.二叉树中任意个结点的度都为29.在一棵深度为H的完全二叉树中，所含结点的个数不小于（D）。A.2H B.2H-1 C.2H -1 D.2H+110.在一棵具有N个结点的二叉树第I层上，最多具有（C）个结点。A. 2I B. 2H-1 C. .2H -1 D.2N11.在下列情况下，可称为二叉树的是（A）。A.每个结点至多有两棵子树的树 B.哈夫曼树C. 每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树12.树最适合用来表示（C）。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据13.某二叉树的前序序列和后序序列正好相反，则二叉树一定是（A）的二叉树。A.空或只有一个结点 B.任一结点无左子树C.高度等于其结点数 D.任一结点无右子树14.按照二叉树的定义，具有3个结点的二叉树有（C）种。.A.3 B.4 C.5 D.615.对一个满二叉树，m个树叶，n个结点，深度为h，则（D）。A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-116.在一非空二叉树的中序遍历序列中，根结点的右边（A）。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点17.任何一棵二叉树的结点在先序、中序、后序遍历中的相对次序（A）。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对18.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（D）A.acbed B.decab C.deabc D.cedba19.由带权为8、2、5、7的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（D）A.23 B.37 C.46 D.4320.对二叉排序树进行（B）遍历，可以得到该二叉树所有结点构成的排序序列。A.前序 B.中序 C.后序 D.按层次（第七章）1.在一个有向图中，所有顶点的入度和等于所有顶点的出度之和的（B）倍。A 1/2 B.1 C.2 D.42.用邻接表表示图进行广度优先遍历时，通常采用（B）来实现算法。A.栈 B.队列 C.树 D.图3.具有n个顶点的无向完全图，边的总数为（D）。A,n B.n+1 C.2n-1 D.n（n-1）/24.有n个顶点的连通G的最小生成树有（C）条边。A.n-1 B.n C.n+1 D.不确定5.一个有向无环图的拓扑序列个数是（B）。A.1个 B.1个或多个 C.0个 D.多个6.在AOE网中，入度为0的顶点称为（B）A.起点 B.源点 C.终点 D.汇点7.Prim算法的时间复杂度是（B）A.O（n） B.O（n2） C.O（e） D.O(eloge)8.在无向图的邻接矩阵A中，若Aij=1，则Aji的值为（C）A.i+j B.i-j C.1 D.0（第八章）1.静态查找表与动态查找表的根本区别在于（B）A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样2.顺序查找适用于存储结构为（C）的线性表。A.哈希表 B.压缩存储 C.顺序存储或链接存储 D.索引存储3.对线性表进行折半查找最方便的存储结构是（B）。A.顺序表B.有序的顺序表C.链表D,有序的链表4.对一个排好序的线性表，用折半查找法检索表中的元素，被检索的表应当采用（A）。A.顺序存储B.链接存储C.散列法存储D.存储表示不受限制5.若在线性表中采用折半查找法查找元素，该线性表应该（C）。A.元素按值有序 B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构 D.元素按值有序，且采用链式存储结构6.在顺序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半查找法查找关键码值11，所需的关键码比较次数为（C）。A.2 B.3 C.4 D.57.用折半查找法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较（C）次。A.5 B.2 C.4 D.18.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）。A.n B.n/2 C.（n+1）/2 D.(n-1)/2 9.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内每个元素等概率情况下查找成功时所需的平均比较次数是（B）A.35/12 B.37/12 C.39/12 D.41/1210.设有100个元素，用折半查找法进行查找时，最小比较次数是（D）。A.1 B.2 C.4 D.711.利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素35要进行（A）次元素间的比较。A.4 B.5 C.6 D.712.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（B）量级相当。A顺序查找B折半查找C分块查找D以上都不正确13.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（C）查找方法。A顺序B折半C散列D以上都不正确14.一棵平衡二叉树，其每个非终端节点的平衡因子均为0，则该树共有（D）个结点。A.2k-1-1B.2k-1C2k-1+1D.2k-115.设哈希表上m=14，哈希表函数H(key)=key%11。表中已有4个结点：addr(15)=4；addr(38)=5；;addr(61)=6；addr(84)=7；其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是（D）A.9B.8C.5D.316.在哈希查找中，平均查找长度主要与（C）有关。A.哈希表长度B哈希元素的个数C装填因子D处理冲突方法17.在采用线性探测法处理冲突的散列表上，假定装填因子的值为0.5，则查找任一元素的平均查找长度约为（B）A 1B 1.5C2D3.518.在采用链接法处理冲突的散列表上，假定装填因子的值为4，则查找任一元素的平均查找长度约为（A）A 3B 3.5C2D 419.若对一组关键字（23,44,36,48,52,73,64,58）建立散列表，采用H（K）=K%7计算散列地址，则同义词元素的个数最多为（B）个A 2B 3C 4D 520.若对一组关键字（23,44,36,48,52,73,64,58）建立散列表，采用H(K)=K%13计算散列地址，并采用链接法处理冲突，则元素64的初始散列地址（C）A.2 B.8 C.12 D.13三、简答题（第二章）（1）简述合适选用顺序表或链表作为线性表的存储结构为宜。答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑。基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首、尾两端，则采用尾指针表示循环单链表为宜。（2）为什么在循环单链表中设置尾指针比设置头指针更好？答：尾指针是指向终端节点的指针，用它来表示循环单链表可以使得查找链表的开始节点和终端节点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始节点和终端节点的位置分别是rear-next-next和rear，查找时间都是O（1）。（第三章）1.链栈中为何不设置头结点？ 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更加复杂。所以只要有链表的头指针就可以了。2.循环队列的优点是什么？如何判别它的空和满？答：循环列队的优点是：它可以克服顺序列队的“假上溢”现象，能够使存储队列的向量空间得到充分利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一个是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。（第四章）1.试回答空串与空格串有何区别？答：空串是不含任何字符的串，长度为0，空格串是有空格字符组成的串，串的长度为空格的个数。（第六章）1.试找出分别满足下面条件的所有二叉树（1）前序序列和中序序列相同。答：空二叉树或没有左子树的二叉树（右单支树）（2）中序序列和后序序列相同。答：空二叉树或没有右子树的二叉树（左单支树）（3）前序序列和后序序列相同。答：空二叉树或只有根的二叉树。（4）前序、中序、后序序列相同。答：空树或只有根结点的二叉树2.从概念上讲，树、森林和二叉树是3种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。答：目的：树和森林采用二叉树的存储结构，可以利用二叉树已有算法解决树和森林的有关问题。 主要区别：树中结点的最大度数没有限制，而二叉树结点的最大度数为2.。树的结点无左右之分，而二叉树的结点有左右之分。四、算法题（第二章）（1）写一算法在单链表上实现线性表的ListLength(L)运算。答：求单链表长只能用遍历的方法，从头数到尾，总能数出来。算法如下：int ListLength(LinkList L)int len=0;ListNode *p;p=L;/设该表有头结点while(p-next) p=p-bext; len+; return len;（2）试设计一个算法，在无头结点的动态单链表上实现线性表操作Insert（L,I,b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。答：算法分析：生成新结点存放元素b，由指针new所指。将new插入在单链表的第i个元素的位置上：若i=1，new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。算法如下：void Insert(LinkList *L,int I,int b)LinkList new;new=(LinkList *)mallic(sizeof(LNode);new-data=b;if(i=1) /*插入在链表头部*/ New-next=*L; *L=new; else /*插入在第i个元素的位置*/ p=*L; while(-i1) p=p-next; new-next=p-next; p-next=new; /*Insert*/（第六章）1.设计一个算法统计二叉树中叶子结点个数（先序遍历）。答： void CountLeaf(BiTree T, int& count)if(T)if(!T-lchild)&(!T-rchild)count+;CountLeaf(T-lchild,count);/统计左子树中叶子结点个数CountLeaf(T-rchild,count);/统计右子树中叶子结点个数2.设计一个算法求二叉树的深度（后序遍历）答： int Depth(BiTree T)if(!T)defthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);return depthval;