2014考研计算机数据结构冲刺课程讲义

[[题1]以下算法的时间复杂度是（）voidfn){inti,j,fori=1i<nfor(intj=n;j>=i+1;j--)x++；} B. C.O(nlog2n)D.分析：基本运算是语句x++，设其执行时间为Tn解答：D==n(n-1)/2=[[题2]以下算法的时间复杂度是（）voidfn){inti=0;}A. B. C.O(nlog2n)D.)分析：基本运算是语句i++，设其执行时间为则有T(n)×T(n)×T(n)即解答：D=)[[题3]以下算法的时间复杂度是（）voidf(intwhile(d>0){if(d%2==1) =*f=f*f;d=d/2;}} B. C. D.则有d=n/2T(n>0≥1，2T(n)≤n1、线2、线性表有顺序和链式两 结构（1），插入操作平均移动n/2个结点，删除操作平均移动 #defineLISTSIZEtypedef ElemType//#defineLIST_INIT_SIZE#defineLISTINCREMENTtypedefstruct{ElemType*elem;////}（（2）间 typedefstruct data;//数据域structLNode*next;//指针域} [[题1]设线性表有n个元素，以下操作中，（）在顺序表上D．输出与给定值x相等的元 性表中的序[[题2]采用顺结构的线性表的插入算法中，当n已满时，可申请再增加分配m个空间。若申请失败，则明系统没有（）可分配的 A．m个B．m个连续的 分析：此题主要考查线性表的顺序结构的特点。线性表的顺序是指在内存中用地址连续的一块空间解答移动上，在第ixai到an都要向后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素。时间复杂度为Ｏ(n)。 ；分析：此题主要考查线性表的顺序结构（这里为数组）的应用。算法的基。这样，可使算法的时间复杂度为O(n)voidvoidAdjust（int{inti=1,j=n,temp;while(A[i]%2!=0)i++;∥A[i]为奇数时，i增1while(A[j]%2==0)j++;∥A[j]为偶数时，j减1if(i<j){temp=A[i];A[i]=A[j];A[j]=temp;}∥A[i]为偶数、A[j]为奇数时，交}}该算法的时间复杂度为O(n)；算法的空间复杂度为O(1)1、建立单链表（1）头插法2、链表中查找第i3法5点不是新结点而是利用原表结点，因此这类算法中建立链表的法 结点的单链voidCrea n){LNode*s;inti; s->next=L- L-}}voidCrea istR(LinkList&L,ElemTypea[],intn){LNode*s，*r;inti;));r=L；∥rfor(i=0;i<n;i++) ∥将s插入到rr=s;r->next=NULL;∥终端结点next域置为}题1in。分析：此题主要考查线性表的链式结构的应用，此题空链表，然后将待排序链表的结点依次插入这个空链表的有序链表。voidvoidInsertsort（LinkList{LNodep=L->next;L->next=NULL;//空链表，将原链表结点逐个插入到有序表中 r=L;q=L-while(q!=NULL&&q->data<=p-}}题2在一个单链表中的ps执行如下操作（填空）：s->next=① t=p-p->data=② s->data= 分析：采用的方法是在ps将p所指结点和s解答：①p->next②s- voidvoidIntersection(LinkListha,LinkListhb,LinkList∥将ha和hb中共同的元 到单链表hcLNodeInsertsort(ha∥参考题1将ha指向的单链表由小到大排序Insertsort(hb∥参考题1将hb指向的单链表由小到大排序hc=(LinkList)malloc(sizeof(LNode));∥申请头结点hc-whliewhlie(pa&& pa=pa- pb=pb->nxtelse{∥pa和pb)); }}[[题1]在一个双向链表中，在*p结点之后插入结点*q的操作是（）q- p- p->next->prior=q;q->next=p-q->next=p->next;p->next->prior=q;p->next=q;q-p->next=q;q->prior=p;q->next=p->next;p->next-p->next->prior=q;q->next=p->next;q->prior=p;p-1、栈是运算受限（限制在表的一端进行插入和）的线性表，允许插入、删除的这一端称为栈顶，操作序列——“进栈、出栈、进栈、出栈……”——可以使数据通过栈后仍然保持次序不变。，对于顺序结构的栈还需注意（1）进题1]设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是,3，…，n，若p=1，则i（1≤n1）的值是。A.n- B.n- D.有多种p=1进栈序列是p1，p2，3，…，1，由输出序列可知，1，p2，p3，…，pn进栈，然后依次出栈，即pn-题2设np1p2p3…，pn序列是123，…，np=1p11≤≤n1）的值是（）。A.可能是 B.一定是 C.不可能是 D.不可能是分析：当p3=1时，进栈序列是p1，p2，p3，…，pn，由输出序列可知，p1，p2，p3都进栈，出栈p3，此后紧跟着出栈的一个元素是2，而p1不可能紧跟着p3出栈，因为栈中前面有p2，因此p1不可能是2。解答：C使队列的向量空间得到充分的利用。判断循环队列的“空”和[[题1]若用一个大小为6的数组来实现循环队列，且当前rear加入两个元素后，rear和front的值分别为（）。A．1和 B.2和 C.4和 D.5和分析：ar值为0，进队两个元素后，er循环递增2，则ear值为2；ot值为3，出队一个元素后，ont循环递增1，则on值为4。解答：B1LOC(aij)=LOC(a00)+(i×n+j)×d ，每个数组元素占据d个地址单元,LOC(aij)=LOC(a00)+(j×n+i22、特殊矩阵（假设以行序为主序（1）对称矩阵：将对称矩阵A压 到SA[n(n+1)/2]，j的下标、与在Akk下：当0≤，≤n10k＜n+1时，（上）三角中的元后，接着对角线上（下）方的A压缩到SA[n(n+1)/2+1]中，aij的下标i、j与在SA[k]中（（3）对角矩阵：一个有m（1≤m＜n）条非0元素的n阶对角阵，在这种矩阵中，所有的非0中心的带状区域中，其非0u将对角矩阵A压到一维数组SA[0..u-1]中，aij的下标i、与在SA[k]中的对应元素的下标k的关系是当0≤i，j≤n-1时 [[题1]设矩阵A[1..n][1..n]下三角部分按行序存放在一维数组B[1..n(n-1)/2]置k的值为（）。—A.i(i-1)/2+j- B.i(i- C.i(i+1)/2+j- D.分析：对称矩阵A的下标从1开始，对于任一元素aij（由于，故它在下三角形中），其前有1行，第1行有1个元素，第2行有2个元素，…，第1行有1个元素，共计12个元素，在第行中，该元素前有1个元素，所以，元素j前共有i1)/2+1个元素，k=(1/2+1+1=1)/2+j。解答：B[[题2]设二维数组A[6][10]，每个数组元素占用4单元若按行优先顺序存放的数组元素a[3][5] 地址为，则a00 地址是（） LOC(aij)=LOC(a00)+(i×n+j)×d可知，LOC(a[3][5])=LOC(a[0][0])+(3×10+5)×4=1000，计算可解答：B九、树、九、树、二叉树 结2。即使树中结点只有一棵，也要区分它是左还是右。满二叉树：在一棵二叉树中，如果所有分支结点都存在左和右，并且所33、二叉树 结（1）顺 结完全二叉树和满二叉树采用顺比较合适，树中结的序号可以唯一地反映出结点之间的逻辑关系，这样 下标值确定结点在二叉树中的位置，以及结点之间的系灵活、操作方便，对于一般情况的二叉树，甚至比顺序结构还节省空间。因此，二叉链表是最常用的二叉树方式。typedef emTypestructBiTNode*lchild;*rchild;//BiTree 解答：C[[题2]设二叉树只有度为0和2的结点，其结点个数为15二叉树的最大深度为 ）分析：对于结点的度只有0和2的二叉树，为使其深度h除根结点层外，树中其余层有两个结点，即结点总数=2h-。由于结点个数为15，因此二叉树的深度h为8解答：C性质性质4：具有n个结点的完全二叉树的深度k。二二叉树性质的性质2k1k1结点总数多1个。性质3推广：已知一棵度为m的树中有0个叶子结点数，1个度为1的结点，N2个度为2的结点，，N个度为m的结点，则有：N=+2+Nm1N。性质性质4①有n>0个叶结点的完全二叉树的高度(结点层次数)当n≠2k,即n不是2的 或者n=2k但是一棵满二叉树，其高度为。当n=2k但是非满二叉树，其高度 ②有n个结点的完全k叉树的高度为性质性质5k1①编号为p=1结点无父结点，否则为p结点的父结点是 （k≥2）；②编号为p的结点的第k1个孩子的编号为pk，所以，如果编号为p结点有孩子，则编号其第i个孩子的编号为p×kk-；③编号为p的结点有右兄弟的条件是(p-1)%k0时，其右兄弟性质1：树中的结点数等于所有结点的度数+1性质2：度为m树中第i层上至多有mi-1个结点（i≥1）性质3：高度为h的度为m树至多有(mh-1)/(m-1)个结点。性质4：具有n个结点的度为m树的最小高度为logm(n(m-。[[题1]若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有 D.不存在第7。题2]若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的点点，该树一共有（）个叶结点。 分析：由二叉树性质3的推广，度为7的树应该有＋3n445＋56＋67（1的结点的个数无关）。因此，如0n01＋7+2×+35+44+×3×278。（表示度为的结点解答：D十一、十一、二叉树的遍历及应用1先序遍历：递归算法、非递归中序遍历：递归算法、非递归后序遍历：递归算法、非递归层次遍2、遍历二叉树2、遍历二叉树制和左、右之间的交换，其思想是质、结构特点和遍历算法的基础上，可[[题1]任何一棵非空二叉树中的叶子结点在先序遍历、中序遍历与后序遍历中的相对位置（）。A．都会发生改 B．不会发生改变C．有可能会发生改 D．部分会发生改分析：无论是先序遍历（DR）还是中序遍历（DR），或是后序遍历（D），对于叶子结点而言，被的先后次序都是先左后右，因此，叶子结点在先序遍历、解答：B[[题2]对于二叉树的两个结点X和Y，应该选择（）两个序A．先序和后 B．先序和中C．中序和后 D．A、B、C都分析：虽然先序和后序无法得出二叉树的结构，但是可以判断祖先。其他两个序列可以直接得出二叉树的结构，就可以判断祖先。解答：D理由二：一棵树可以转换成一棵没有右的二叉树，反之亦然。所以，对于理由二：一棵树可以转换成一棵没有右的二叉树，反之亦然。所以，对于n个结点（（2）如（1）所述，不一定能得到一棵树。但是如果所给出的序列合法，就能够得到一棵树，而且得到的树是唯列为p1,p2,…pn，那么只有当pn=1时，而且在p1,p2,…pn-1中亦然。所以，对于n除去根结点（即1）以外的n1）在这里23np,,…1就是相应二叉树的中序遍历序列—— 的理由二：对于合法的序列：先根序理由二：对于合法的序列：先根序为,,,n，后根列p,,…n,1，先可以确定树根为其形成的森林的先根序列为,,n，后根序列p,,p1，这些森林被分成（m≥0）个不交的集T2,m，且这些集合的每一个又都是树，在先根序列中照,,m的结点顺序出现，在后根序列中也按,,m的结点序出现（但是对应的每个i中，结点出的顺序不同）。因此可以找到每棵 的结点集合，进行递归处理，最终只能得到一棵确定的树。[[题4]结，利用结点的右孩子指针rchildvoidvoidlink(BiTreebt,BiTNode*head,BiTNodeif(bt!=NULL){if(bt->lchild==NULL&&bt->rchild==NULL)//叶子结点if(head==NULL){ if(bt->lchild!=NULL)link(bt->lchild,head,tail);if(bt->rchild!=NULL)link(bt-}} f(b,path,pathlen)：将b->data放入path，pathlen++；//其他情况f(b-inti；ifif(b->lchild==NULL&&b-printf(%c到根结点路径：%c,b>data);for(i=pathlen-1;i>=0;i--) (“%c”,path[i]);printf(“\n”);} Allpath(b->lchild,path,pathlen);//递归扫描左Allpath(b->rchild,path,pathlen);//递归扫描右 }}}十二、十二、线索二叉树 ，也不使用栈（其中后序线索二叉树中查找后继仍需要栈）22当标志位取1[[题索二叉树中，下面说法不正确的是（）点.[[题2]域的个数是（）），先序序列的最后结点的右线索为空（无后继），共解答：D 1,T2,…,Tn) 其中，T1=(root，t11,t12,…,t1m)；二叉树B=(LBT,Node(root),RBT)；若F=Φ，则B=Φ；ROOTT1对应得到由(t11t12t1mLBT(T2T3TnRBT若B=Φ,F=Φ；否则，由Node(root)ROOTT122、树的遍历可有2（1）先根(次序)依次先根遍历各 （2）后根(次序)，然 根结点33、森林的遍历①森林中第一棵树的根结点；②森林中第一棵树 森林③森林中其他树构成的森林。森林的遍历可有2①先序遍历②中序遍历[[题]用孩子兄弟链表表示一棵树，若要找到结点p的第5个孩子，则只要先找到*p的第1个孩子，然后（）。D.从兄弟域指针连续扫描4个结点即可分析：树的孩子兄弟链表表示法和所对应的二叉树的二叉链表表示法完全一样，以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。因此可利用二叉树的算法来实现对树的操作。应当注意的是，和树对应的二叉树，其左、右解答：DB中，X是其双亲的右孩子，下列结论正确的是（）。右孩子对应原树结点的右边兄弟。所以X一定有左边兄弟。解答：D十十四、二叉排序树与平衡二叉树 左、 ASL值，显然，由值相同的n个关键字，构造所得的不同形。33、（1）②若二叉排序树非空，则新结点的根结点比较，若小根结点，则插入左 ；否则插入右 。（2）*p（*），以下三种情况：①被删除的结点*p②被删除的结点*p③被删除的结点*p；◦的二叉排序树：它的左和右都是平衡二叉树，且左和 高度之差的绝对值不超过1LL型平衡旋转，A；RR型平衡旋转；A； [[题1]二叉树为二叉排序树的（）条件是其任一结点的值均大A．充分不必 B．必要不充C．充分必 D．既不充分也不必分析：本题主要考查二叉排序树的定义。由二叉排序树的定义可知，在二叉排序树中，任意非终端结点的关键字的值大于其左上所有结点的关键字的值（当然也大于其左孩子的值）；小于右上所有结点的关键字的值（当然也小于其右孩子的值）。所以，该题的选项中至少应该包含必要条件，A、D[[题2]输入序列为（20,35,…），构造平衡二叉树，当在树中插入值30时发生不平衡，则应进行的平衡旋转是（）。 D.分析：平衡二叉树的旋转有4将以35为根的树向右旋转，然后将以20为根的树向左旋转[[题3]在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值是（）。 B. 解答：D树和编122在集合F叉树加入到集合F重复（2）（3）两步，当F便是所要建立的树。33树的总（1）用n个权值（对应n个叶子结点）构树，共需n-1次合并， 树中非叶子结点的总数为n-1，总结个数为2n-1树中没有度为1的结点因为非子结点都是通过两个结点合并而来。但是，没有为的二叉树并不一是 树。 44中字符的使用频率或次数，构造树。此树中从根到每个叶子结点都有一条唯一的路径，对路径上各分支约定，左分支标识为“0”码，右标识为“1”码，则从根结点到叶子结点的路径上分支的“0”、“”码组成的字符串即为该叶子结点的55、 树编码的总编码是能使电文代码总长最编码方式。结论由 树是带权路径长度最树的特征可得。 ，而叶子结点不可能从根结点到其他叶子结点的路径上所以一个字符编码的前缀（3）深度为h。编码不可能是另一个字树，其叶子结点的最大编码长度为h-[[题1]若度为m 树，其叶子结点个数为n，则非叶子点的个数为（）分析：在构造度为m树过程中，每次把m并为一个父结点（第一次合并可能少于m个子结点），合并减少m1个结点，n个叶子结点少到最后只剩一个共需 次合并，每次合并增加一个非叶子结解答：C十六、十六、图的基本概念12、无3、有4、无向完全图：在一个含有n个顶点的无向完全，有n(n-1)/25、有向完全图：在一个含有n个顶点的有向完全，有n(n-1)66789101111、子图：对于图G=（V，E），G’=（V’，E’），若存在是V的子集，E’是E的子集，则称图G’是G的一个子12、连通图、连通13、强连通图、强14、生15、生成[[题1]以下关于图的叙述中，正确的是（）[[题2]一个有28条边的非连通无向图至少有（）个顶 分析：88×8/2=2非连通无向图则有至少9解答：C十七、十七、图的结角矩阵的元素即可，又由于主对角线为0，则至少需要n(n-1)/2空间。对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度Dv)（或入度Dv)）。用邻接矩阵方法图，很容易确定图中任意两个顶点之间是否有边相测，所花费的时间代价很大。这是用邻接矩阵图的局限性。稠密图适合用邻接矩阵的若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。稀疏图用邻接表表示比邻接矩阵节省空间，当和边相关的信息较多时更是如此。在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需搜索第i个或第j个链表，因此，这种方法不及邻接矩阵方便。34^^例例abcde441a121^4^2b3c32344d5e52^3^5^[[题 n个顶点的无向图的邻接表中边表结点总数最多有（） D.n(n-分析：nnn1表中，每条边对应两个边表结点。解答：D十十八、图的遍历1、图的遍历通常有深度优先搜索和广度优先搜索两种方式一个非递归过程。（1）①递归算法②非递归 时间复杂度为O(n2)。当以邻接表作结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。深度优先搜索遍（（2）广度优先搜索：广度优搜索遍图的时间复杂度深度优先搜索遍历的相同，两者不处仅仅在于对顶点 的顺序不同。所有顶点，则该图一定是（）。 到图中的所有顶点，但若无向图是非连通图，则只顶点不可能到。解答：B[[题2]假设图G，设计一个算法，输出图G从顶点u到v的长度为k。由于在搜索过程中，每个顶点只，所以这条路径必定是一条简单路径。因此，在搜索过程中，需要把当前的搜索线路记录下来。为了记录当前的搜索路径，可设立一个数组pth保存走过的路径，用d记录走过的路径长度。若当前扫描到的结点u等于v且路径长度为kath。voidvoidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintm,i; ode*p; 路径长度加 ifu=v&&d=k)fori=0;i<=d;i++)printfpath[i输出一条路径p=G->adjlist[u].firstarc;//p指向顶点u的第一条弧的弧头结点while if(visited[m]==0) ，则用递归p->nextarc;} } 十九、图的最小生成树问题十九、图的最小生成树问题1法算2 姆（Prim）算法的基本思3 （Kruskal）算法的基本思4、Prim算法的时间复杂度为O(n2)[[题1]设有无向图G=（V，E）和G’=（V’，E’），如果G’是G的生成树，则下面不正确的说法是（）。A.G是G的连通分 B.G是G的无环子C.G’是G的子 G’是G的极小连通子图且B、而选项A为概念错误。解答：A二十、二十、图的拓扑排序问题1、拓扑有序序列是AOV网G中的顶点所构成的有序序列1,…,i,…,n），AOVAOV33、对AOV网进行拓扑排序的方法和。当有向图中无环时，也可用深度优先遍历的方法进行拓扑排序，按DF扑有序序列。[[题1]出一个有向图是否有回路（）A．深度优先遍历BC．求最短路 D．求关键路（2）设图是n个顶点的无向图，若的边数e≥n一定有回路存在。理由是：设整个图G的度之和为N，则N≥2n，又因为图中边数，因此图G至少有n条边因为多于n-1条边的图中必然存在回路，所以图G中一定有回路解答：A[[题2]已知带权图G＝（V，E），其中V＝{v1，v2，v3，v4，v5，v6＝{<v1，v2>，<v1，v4>，<v2，v6>，<v3，v1>，<，<v5，v2>，<v5，v6>},G的拓扑序列是（）。 D．v1，v4，v3，v5，v2，v6二二十一、图的关键路径问题22求AOV网中所 的最早发生时间求AOV网中所 的最迟发生时间求AOV网中所有活动的最早发生时间求AOV网中所有活动的最迟发生时间（5）求AOV网中所有活动 余量 ； （6）找出所有 )为0的活动构成的关键路径, ve(源点ve(k)=Max{ve(j)+dut(<j,vl(汇点ve(汇点vl(j)=Min{vl(k)–dut(<j,e[i]=l[i]的活动就是关键活动，关键活动所在的路径就是关键路径[[题1]下面关于关键路径的问题中说法正确的是（）IA．仅Ⅰ和IIB．仅Ⅰ和IIIC．仅ⅠD．仅III解答：D[[题2]下面关于工程计划的AOE网的叙述中，不正确的是（）二十二、二十二、图的最短路径问题法的时间复杂度也是O(n3)[[题1]下列说法不正确的是（）I求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权值可以为负值IV求单源路径的Dijkstra算法不适合用于有回路A.I、II、III、 B.I、 C.I、III、 D.II、分析：每次以一个顶点为源点，重复利用Dijkstra算法n次求得每一对不同顶点间的最短路径，其算法时间为O(n3)，因此II正确；而最短路径算法要求弧的权值必须为正数，所以I、III错误；Dijkstra算法可用于有回路的有向网，例如知识点聚焦22的例题1中就是有回路的有向网。解答：C。二十三、二十三、顺序查找、折半查找、分块查找顺序查找算法的时间复杂度为O(n)。它的缺点是当n，平均查找长度较大，效率低；优点是表的结构是顺22。对表中每个数据元素的查找过程，二叉树来描述，称这个描述折半查找过程的二叉树为判定表的中间结点是二树的根，左子表相当于左 ，右相当于右。折查找的过程是从根结点到待查找结过程，不论查找成或失败，查找长度均不超过树的高因此，如果有序表长度为n，那么在查找成功时给定值行比较的关键字个多为。折半查找的时间效率折半查找的时间效率为Oo2n。可见折半查找的效率比顺序查找高，但折半查找只适用于有，且限于顺序 构（对线性链表无法有效地进行折找）。因此，折半找不适用于对查找表频繁插入和删适合表中元素变化少而查找频繁的情况。3比较的特征。同时，考生要特别注找在顺序结构链式结构上的区别。44、分块查找分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）块的长度均匀，最后一块可以不满。每块中元素任意排构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）214078查找长度为LB，以及在相应块内进行顺序查找的平均查找长度为LW假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假将将题15（若最后一个结点的数据元素不满50），法查找值为nn0typedefstructnode{intA[m]；structnode*next;//指向下一结点的指针typedefstruct{intj; LNode*s;

n){rcd*R;while&&!found){forif(p->A[jn)found=1;//查找成功if(p==NULL)returnelse R.j=i;return}}[[题2]顺的某线性表共有123个元素，按分块查找的要等分为3块。若对索引表采用顺序查找方法来确定子块，在确定的子块中也采用顺序查找方法，则在，分块查找成功的平均查找长概率况 B. C. D.SL=(2s+n/2题中，n=1，s=23/=41，23。解答二十四、二十四、B‐树与B+1、一棵m阶的B-树，或者为空树，或为满足下列特性的m⑴树中每个结点至多有m ⑶除根结点之外的所有非终端结点至少有m/2棵Kii=12…n)，An所指中所有结点的关键码均大于Kn，m/22、B-2、B-树的基本（1）B-树的查找类似二叉排序树的查找，不同的是-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码，查找失败。即在-树上的查找过程是一个顺指针查找结点在含有n个关键码的B点的路径上涉及的结点数不超过（2）（2）B-树的生成是从空树开始，逐个插入关键字而得。但由于B-树结点中的关键字个数必须大于等于m/21，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层不超过m1，则插入完成，否则要产生结点的（3）在B-”33、一棵m阶的B+树和m阶的B-树的差异在于：有n 的结点中含有n个关键码自小而大地顺序；其根结点中最大（或最小）关。[[题1]下面关于m阶B-树说法正确的是（） IV当插入一个数据引起B-A．I、II、 B．II、C．II、III、 [[题2]下面关于B-树和B+树的叙述中，不正确的是（）A．B-树和B+树都是平衡的多分支B．B树和B+树都可用于文件的索引结构分析：因为+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小到大地顺序，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是-树不具有这种结构特性，所以只支持从根解答：D二十五、二十五、在一般情况下，很容易产生 ”现象，即：key1，而f(key1)=f(key2)H(key)=keyMODp 33Hi=H +diMOD1≤i<m ②二次探测法 Hi=(H(key)±di)MOD其中：di为增量序列12，-12，22，-22，……，q2，-q2且q≤m/2。特点是：发生时，在表的左右进行跳跃式探测，比较灵活。（2）链地址法：将所有散列地址相同的记录都在同一链表中。在这[[题1]下列有关散列查找的叙述正确的是（） D.若散列表的装填因子α<<1，则可避 得到，散 法 数据，所以选项A正确；散 关键字不一定总是存放在一片连续 单元中，选项C错误；装填解答：A。[题2][题2]散列表的平均查找长度）与处 方法有关而与表的长度无与处 方法无关而与表的长度有与处 方法有关且与表的长度有与处 方法无关且与表的长度无、与处理 方法有关、与表的装子有关，但与表的关。解答：A[[题3]采用散列函数H(k)=3×kMOD13并用线性探测开放地 构造散列表（画示意图装填因等概率情况下查找成功的平均查找长等概率情况下查找失败的平均查找长度[[题 已知一组关键字为，51，25），链地址法解决。设装填因子=.7，散列函数的形式为Hke =keyMODp，回答下列问题：构造散列函画出散列计算出等概率情况下查找成功的平均查计算出等概率情况下查找不成功的平均查找长，查找成功表示找到了关键字集合中的某记录的比较次数，查找不成功表示在散列表中未找到指定关键字的记录的比较次数。首先，首先，回忆一下串匹配(查找)的定义INDEX(S,T,初始条件：ST存在，T1≤pos≤StrLength(S)操作结果：ST次出现的位置;否则函数值为0。intintIndex(StringS,StringT,intpos)回第一个这样的子串在S中的位置，否则返回0if(pos>0)n=StrLength(S);m=StrLength(T);i=while(i<=n-m+1)SubString(sub,S,i,if pare(sub,T)!=0)++ielse}//}//return //}//一、简单算法二、首尾匹配算法J.H.Morris)算法intintIndex(SStringS,SStringT,intpos)返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0其中，T非空，1≤pos≤StrLenthSi=pos;j=while(i<=S[0]&&j<=T[0])if(S[i]T[j])++i;++j}elseii-j+2;j1;}if(j>T[0])returni-elsereturn}//二、二、首尾匹配intintIndex_FL(SStringS,SStringT,intpos)sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=while(i<=sLength–tLength+1)if(S[i]patStartChar++i;//elseif(S[i+tLength-1]!=patEndChar)else}return}KMP算法的时间复杂度可以达到S[iT[j时，若已 T[1..k-1]==T[j-k+1..j-则 定义：定义：模式串的next[题1]串[题1]串‘ababaaababaa’的n