习题及答案文档

习题二1简述以下术语：线性表，顺序表，链表。线性表：最经常使用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。顺序表：是指用一组持续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。链表：逻辑结构相邻的数据元素物理结构不必然相邻。采纳指针的形式连接起来。2何时选用顺序表，何时选用链表作为线性表的存储结构适合?各自的要紧优缺点是什么?不需要常常大量的修改表或需要随机存取的情形下能够选用顺序表；相反需要常常大量的修改表，但不是频繁的随机存取的情形下可选用链式表。3在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?答：平均需要移动n/2个结点。表的长度，和要插入的位置。4链表所表示的元素是不是有序?如有序，那么有序性表现于何处?链表所表示的元素是不是必然要在物理上是相邻的?有序表的有序性又如何明白得?答：有序。有序性体此刻通过指针数据元素有序的相连。物理上不必然要相邻。5设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。StatusListInsert(SqList&L,inti,ElemTypee){ if((i>+1)||i<1) returnERROR; if>= { newbase=(ElemType*)realloc(+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(-1); =newbase; +=LISTINCREMENT; } ElemType*q,*p; q=&[i-1]; for(p=&[];p>=q;p--) *(p+1)=*p; *q=e; ++; returnOK;}9设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时刻复杂度。voidListInsert(SqListA,SqListB,SqListC){ ElemType*p,*q,*s; P=&A; q=&B; s=&C; while!=NULL||!=NULL) { if { if!=NULL) =; =; p++; } else { if!=NULL) =; =; q++; } } while!=NULL) { =; =; } while!=NULL) { =; =; }习题三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)

{主串和子串的区别：主串是相关于子串而言的，子串是主串中持续的一段，是主串的一个子集。目标串和模式串的区别：目标串是在模式匹配中的主串，是相关于模式串运算的母串，而模式串是子串，是在主串中运算的子串。⑵假设x和y是两个采纳顺序结构存储的串，写一算法比较这两个字符串是不是相等。解：intstreql(Hstringx,Hstringy)if(x[0]!=y[0])return(0);elsei=1;while(x[i]==y[i]&&i<x[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个字符在电文中显现的概率别离为{,,,,,,,}。①请画出对应的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-33所示。①求出每一个事件的最先发生时刻和最晚发生时刻。②该工程完工至少需要多少时刻?③求出所有关键途径和关键活动。习题九⑴关于一个有n个元素的线性表，假设采纳顺序查找方式时的平均查找长度是什么？假设结点是有序的，那么采纳折半查找法是的平均查找长度是什么?⑵设查找表采纳单链表存储，请别离写出对该表进行顺序查找的静态查找和动态查找的算法。⑶设二叉排序树中的关键字互不相同：那么①最小元素无左小孩，最大元素无右小孩，此命题是不是正确？②最大和最小元素必然是叶子结点吗？③一个新结点老是插入在叶子结点上吗？⑷试比较哈希表构造时几种冲突处置方式的优势和缺点。⑸将关键字序列(10,2,26,4,18,24,21,15,8,23,5,12,14)依次插入到初态为空的二叉排序树中，请画出所取得的树T；然后画出删除10以后的二叉排序树T1；假设再将10插入到T1中取得的二叉排序树T2是不是与T1相同?请给出T2的先序、中序和后序序列。⑹设有关键字序列为：(Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar)，请手工构造一棵二叉排序树。该树是平稳二叉排序树?假设不是，请为其构造一棵平稳二叉排序树。⑺设关键字序列是(19,14,23,01,68,84,27,55,11,34,79)，散列表长度是11，散列函数是H(key)=keyMOD11，①采纳开放地址法的线性探测方式解决冲突，请构造该关键字序列的哈希表。②采纳开放地址法的二次探测方式解决冲突，请构造该关键字序列的哈希表。⑻试比较线性索引和树形索引的优势和缺点。⑼设关键字序列是(19,24,23,17,38,04,27,51,31,34,69)，散列表长度是11，散列函数是H(key)=keyMOD11，①采纳开放地址法的线性探测方式解决冲突，请构造该关键字序列的哈希表。②求出在等概率情形下，该方式的查找成功和不成功的平均查找长度ASL。⑽以下图是一棵3阶B_树，请画出插入关键字B,L,P,Q后的树形。习题十⑴回答以下各题：①从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方式是什么？②在待排序的元素大体有序的前提下，效率最高的排序方式是什么?③从未排序序列中依次掏出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置方式是什么？④设有1000个元素，希望采纳最快的速度挑选出其中前10个最大的元素，最好的方式是什么?⑵假设对关键字序列为(54,37,93,25,17,68,58