习-题及答案

习题二1简述下列术语：线性表，顺序表，链表。线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。2何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。3在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?答：平均需要移动n/2个结点。表的长度，和要插入的位置。4链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。5设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。StatusListInsert(SqList&L,inti,ElemTypee){if((iL.length+1)||i1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc((L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(-1);L.elem=newbase;L.listsize+=LISTINCREMENT;}ElemType*q,*p;q=&L.elem[i-1];for(p=&L.elem[L.length-1];p=q;p--)*(p+1)=*p;*q=e;L.length++;returnOK;}9设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。voidListInsert(SqListA,SqListB,SqListC){ElemType*p,*q,*s;P=&A;q=&B;s=&C;while(p.next!=NULL||q.next!=NULL){if(p.next.data=q.next.data){if(s.next!=NULL)p.next=s.next;s.next=p.next;p++;}else{if(s.next!=NULL)q.next=s.next;s.next=q.next;q++;}}while(p.next!=NULL){p.next=s.next;s.next=p.next;}while(q.next!=NULL){q.next=s.next;s.next=q.next;}习题三1设有一个栈，元素进栈的次序为a,b,c。问经过栈操作后可以得到哪些输出序列？Abc,acb,bac,bca,cba.2循环队列的优点是什么?如何判断它的空和满?优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分利用。判断循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元素的总数，不仅可判别空或满，还可以得到队列中元素的个数。3设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？队列为空：front=rear。队满：rear=MAX-1或front=rear(队首指针front，一个队尾指针rear)4设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？循环队列为空：front=rear。循环队列满：(rear+1)%MAX=front。(队首指针front，一个队尾指针rear)5利用栈的基本操作，写一个返回栈S中结点个数的算法intStackSize(SeqStackS)，并说明S为何不作为指针参数的算法?intStackSize(SeqStackS){//计算栈中结点个数　intn=0;　　if(!EmptyStack(&S))　　　{　　　　Pop(&S);　　　　n++;　　　}　　returnn;}上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。7设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。a,b,c,d入队a,b,c出队i,j,k,l,m入队d,i出队n,o,p,q,r入队图解：8假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p,q,r入队图解：习题四2解释下列每对术语的区别：空串和空白串；主串和子串；目标串和模式串。解：空串和空白串的区别：空串不含任何字符，它的长度为0，而空白串含有一个空格，它的长度为1.主串和子串的区别：主串是相对于子串而言的，子串是主串中连续的一段，是主串的一个子集。目标串和模式串的区别：目标串是在模式匹配中的主串，是相对于模式串运算的母串，而模式串是子串，是在主串中运算的子串。⑵若x和y是两个采用顺序结构存储的串，写一算法比较这两个字符串是否相等。解：intstreql(Hstringx,Hstringy)if(x[0]!=y[0])return(0);elsei=1;while(x[i]==y[i]&&ix[0])i++;if(i==x[0])return(1)elsereturn(0)习题五⑴什么是广义表？请简述广义表与线性表的区别？广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于扩充的线性结构（只不过元素并不具有同一类型：可以是原子，也可以是广义表）。当广义表中的元素都是原子时，广义表就蜕变为线性表。广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表⑵一个广义表是(a,(a,b),d,e,(a,(i,j),k))，请画出该广义表的链式存储结构。图解：⑶设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算：①数组a的最后一个元素a[5][7]起始地址；②按行序优先时，元素a[4][6]起始地址；③按行序优先时，元素a[4][6]起始地址。LOC(a[5][7])=LOC(a[0][0])+47*4=1188LOC(a[4][6])=LOC(a[0][0])+(48+6)4=1152LOC(a[4][6])=LOC(a[0][0])+（6*6+4）4=1160⑸设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表和十字链表存储结构。图解：图中未标记空指针，作业中请注意标记习题六⑴假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用树型表示法表示该树，并回答下列问题：①哪个是根结点?哪些是叶子结点?哪个是g的双亲?哪些是g的祖先?哪些是g的孩子?那些是e的子孙?哪些是e的兄弟?哪些是f的兄弟?②b和n的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?⑵一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：①各层的结点数是多少?②编号为i的结点的双亲结点(若存在)的编号是多少?③编号为i的结点的第j个孩子结点(若存在)的编号是多少?④编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?⑶设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。⑷已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。⑸设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA，请画出这棵二叉树，然后给出该树的先序序列。⑹已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。⑺以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。⑻设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。⑼设有一棵树，如图6-28所示。①请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。②请给出该树的先序遍历序列和后序遍历序列。③请将这棵树转换成二叉树。⑽设给定权值集合w={3,5,7,8,11,12}，请构造关于w的一棵huffman树，并求其加权路径长度WPL。⑾假设用于通信的电文是由字符集{a,b,c,d,e,f,g,h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。②求出每个字符的huffman编码习题七⑴分析并回答下列问题：①图中顶点的度之和与边数之和的关系?②有向图中顶点的入度之和与出度之和的关系?③具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图?若采用邻接矩阵表示，则该矩阵的大小是多少?④具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的?为什么?⑵设一有向图G=(V,E)，其中V={a,b,c,d,e}，E={a,b,a,d,b,a,c,b,c,d,d,e,e,a,e,b,e,c}①请画出该有向图，并求各顶点的入度和出度。②分别画出有向图的正邻接链表和逆邻接链表。⑶对图7-27所示的带权无向图。①写出相应的邻接矩阵表示。②写出相应的边表表示。③求出各顶点的度。⑷已知有向图的逆邻接链表如图7-28所示。①画出该有向图。②写出相应的邻接矩阵表示。③写出从顶点a开始的深度优先和广度优先遍历序列。④画出从顶点a开始的深度优先和广度优先生成树。⑸一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一?⑹对于图7-27所示的带权无向图。①按照Prime算法给出从顶点2开始构造最小生成树的过程。②按照Kruskal算法给出最小生成树的过程。⑺已知带权有向图如图7-29所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。⑻已知带权有向图如图7-30所示，请利用Floyd算法求出每对顶点之间的最短路径及路径长度。⑼一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该AOV网的一个拓扑序列，给出相应的步骤。⑽拓扑排序的结果不是唯一的，请给出如图7-32所示的有向图的所有可能的拓扑序列。⑾请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。⑿设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。⒀假设一个工程的进度计划用AOE网表示，如图7-